我读过一个圆可以在 2D 空间中粉碎 3 个点，这实际上是圆的 VC 维度。
假设我们有三个点 (5,2) (5,4) 和 (5,6)。如何绘制一个包含（5,2）和（5,6）而没有（5,4）的圆圈？那是不可能的！
如果它不能破碎，那么VC Dimension怎么会是3个圆圈。或者我在 VC Dimension 的定义中假设是错误的；一个假设必须粉碎所有可能的空间子集的所有可能场景？
问问题
14941 次
2 回答
13
VC 维度是可以破碎的最大点数。{(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，找到任何具有属性 P 的 m 个点的集合就足够了。如果你找到一个或一千组不具有性质 P 的 m 个点，那么这并不能证明关于 n 的任何事情。（除非您已经枚举了所有可能的大小为 m 的点集。）
VC 维度是可以粉碎的最大点数。如果分类器的 VC 维数为 100，仍然可以找到 3 个分类器无法粉碎的点。我们可以将 VCB 维度定义为最大数 n，这样所有大小为 n 或更小的集合都可以被粉碎。Asymptote的原始示例表明，笛卡尔平面上的圆形分类器的VCB维度（假设圆内为1，圆外为0）小于或等于2，因为这三个点不能被破碎；但是，Asymptote 的示例并未显示 VC 维度小于 3，因为还有其他大小为 3 的点集可以被粉碎。
于 2012-09-18T12:57:58.273 回答
2
关键是可以绘制圆，使得属于一个类的所有点都在里面，而其余的点在外面。哪个类是哪个并不重要，因为交换标签只需要反转分类器。
在您的情况下，将 (5,2) 和 (5,6) 与 (5,4) 分开很简单，只需将后者包含在圆圈中即可。对于分类器，“内部”和“外部”无关紧要。重要的是它们可以归为 0 错误。
编辑
严格来说，VC维度是为参数化分类器定义的，并且有多个分类器，其边界将被描述为“圆”。例如，f(x)=(x-x0)*(x-x0)不能在一条线上打散一组三个点，但是f(x)=a*(x-x0)*(x-x0)可以，并且两个分类器都有圆形边界。第二个的 VC 维度实际上是 3，而第一个的 VC 维度是 2。
于 2012-09-18T18:35:21.080 回答