machine-learning - 圆的 VC 维数，一个特例

Question

我读到，一个圆可以粉碎 2D 空间中的 3 个点，这实际上是圆的 VC 维数。

假设我们有三个点 (5,2) (5,4) 和 (5,6)。如何画一个包含 (5,2) 和 (5,6) 且不包含 (5,4) 的圆？这不可能!
如果它不能 splinter ，那么为什么圆的 VC 维数是 3。或者我在 VC Dimension 的定义中假设是错误的；一个假设必须打破所有可能的空间子集的所有可能场景？

Answer 1

VC维度是可以 splinter 的最大点数。 {(5,2), (5,4), (5,6)} 不能被圆打碎，但 {(5,2), (5,4), (6,6)} 可以被圆打碎，所以 VC 维数至少为 3。证明它恰好是 3 更困难。

这里有一个与 Qnan 的回答相关的技术点。如果圆分类器总是将圆内的点分类为1，将圆外的点分类为0，则{(5,2),(5,4),(5,6)}不能被粉碎。另一方面，如果圆分类器也可以将圆内的点分类为0，那么{(5,2),(5,4),(5,6)}就可以被打碎，如Qnan所解释的。

Qnan，关于你的评论，如果有人说 n 是具有属性 P 的点的最大数量，那么要证明 n >= m，就足以找到 m 的任意集合具有属性 P 的点。如果您找到一组或一千组不具有属性 P 的 m 个点，那么这并不能证明有关 n 的任何信息。 (除非您已经枚举了所有可能的大小为 m 的点集。)

VC维度是可以 splinter 的最大点数。如果分类器的VC维为100，仍然有可能找到3个不能被分类器打碎的点。我们可以将 VCB 维数定义为最大的数字 n，这样所有大小为 n 或更小的集合都可以被粉碎。 Asymptote 的原始示例表明，笛卡尔平面上的圆形分类器的 VCB 维数(假设圆内为 1，圆外为 0)小于或等于 2，因为这三个点无法 splinter ；然而，Asymptote 的例子并没有表明 VC 维数小于 3，因为还有其他大小为 3 的点集可以被粉碎。