关于VC尺寸的问题

Question

如果我有输入空间（1,2，... 999）。我有一个概念类C，有10个概念：C0，C1，C2 ... C9。

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

这个概念类C的VC Dimension是什么？

Answer 1

我不想在这里发表的整体解决方案，但这里的东西...

寻找VC维涉及到输入空间，可通过C.

是shattered找到点集我可以很容易地找到一组可以被C破坏的三个点（14,24,3）。

很难找到一组可以被C破坏的四个点，但是（157,256,367,4）起作用。

找到可以被C破坏的五个点非常非常困难，这强烈地表明C（给定输入空间）的VC维度为4.但是，棘手的部分是证明不可能找到任意一组可以破碎的五点。

---

实际上，问题可能存在一些含糊之处。这取决于概念类能够“正确分类”一组点的意义。即C1是否正确地分类（1，2）其中1被赋予一个负面的类别标签，2被赋予正面的一个（因为它正确地分割它），或者只有C2可以做到这一点？我认为它可以，因为这个问题稍微有趣一些。

Answer 2

这个答案是否正确？

破碎意味着对于您选择的一组数据点，例如。 （14,24,3），对于它的每一个可能的标签，都存在与该标签一致的概念。给出，这里

但考虑例子（14,24,3）是所有可能的真/假labellings的列表这三个点，哪些类是与他们一致：

0 0 0 C_5， C_6，C_7，C_8，C_9，C_0仅此

0 0 1 C_3都一致（因为第三数量是三个，只有类C_3包含它）

0 1 0 C_2和C_4（因为“ 24“包含2和4）

0 1 1 C_2，C_4和C_3

1 0 0 C_1及C_4

1 0 1没有一致的类别（因为 “14” 和 “3” 不共享任何位数）

1 1 0 C_4（因为 “14” 和“24”都包含4）

111没有一致的类

因此类集合不打破这个数据集。 （或者我误解了定义中的某些东西？）