computer-science - 关于VC维度的问题

Question

如果我的输入空间为(1,2,....999)。我有一个概念类 C，有 10 个概念:C0、C1、C2...C9。

给定一个输入，如果该输入包含数字 i，则该输入是 ci 的元素。例如，数字123是c1、c2和c3的元素。

VC Dimension是什么？这个概念属于 C 类吗？

Answer 1

我不想在这里发布整个解决方案，但这里有一些......

查找 VC 维度涉及查找输入空间中的点集，这些点可以是 shattered作者:C.

我可以轻松找到一组可以被 C 粉碎的三个点，(14, 24, 3)。

找到可以被 C 粉碎的四个点的集合比较困难，但 (157, 256, 367, 4) 可以。

找到五个可以被 C 粉碎的点是非常非常困难的，这强烈表明 C 的 VC 维度(给定输入空间)是 4。然而，棘手的部分是证明不可能找到 < em>任何一组可被粉碎的五个点。

<小时/>

实际上，这个问题可能存在一些歧义。这取决于概念类在什么意义上可以“正确分类”一组点。即，C1 是否正确分类 (1, 2)，其中 1 被赋予负类标签，2 被赋予正类标签(因为它正确划分了它)，还是只有 C2 才能做到这一点？我认为可以，因为这样问题会更有趣一些。