关于VC维度,为什么你可以用圆圈打碎3点而不是4点?

数据挖掘 机器学习 分类 vc理论
2021-10-12 07:44:58

在使用 VC-dimensions 估计二元分类器的能力时,您可以在 R 2中找到 3 个可以被粉碎的点,例如: 在此处输入图像描述

但是你不能用一个圆圈粉碎任何4 个点。

这在这些讲义中有所说明。谁能给我一个直观的解释?

1个回答

给定4积分A,B,C,D. 如果它们不在凸包的边界上,则不可能从边界粉碎内部点。

所以假设它们位于船体的边界上。所以它们形成一个凸四边形。意义A+B+C+D=360 然后我们可以假设 wlog A+C180, 在哪里 AC 是相反的点。

现在声称你不能有一个包含 A,C, 但不是 B,D.

假设你有这样一个圆圈,它包含 A,C 但不是 B,D. 然后我们可以在必要时使圆更小,这样A,C 位于边界上,但 B,D 仍然没有包含在圈子中。

但是现在由于这些点位于圆外 B+D<180. 但这是一个矛盾,因此这样的圈子是不存在的。

最后一部分与以下事实有关:对于圆形四边形,相反的天使总和为 180 再加上圆外点的角度小于圆上的角度。

https://en.wikipedia.org/wiki/Cyclic_quadrilateral