如果我有 (1,2,....999) 的输入空间。我有一个概念类 C，有 10 个概念：C0、C1、C2...C9。
给定一个输入，如果该输入包含数字 i，则该输入是 ci 的一个元素。例如，数字 123 是 c1 和 c2 和 c3 的元素。
这个概念类 C的VC Dimension是多少？
问问题
1049 次
2 回答
2
我不想在这里发布整个解决方案，但这里有一些东西......
找到 VC 维度涉及在输入空间中找到可以被C粉碎的点集。
我可以很容易地找到一组可以被 C 破碎的三个点，(14, 24, 3)。
很难找到一组可以被 C 粉碎的四个点，但是 (157, 256, 367, 4) 有效。
很难找到可以被 C 粉碎的五个点，这强烈表明 C 的 VC 维度（给定输入空间）是 4。然而，棘手的部分是证明不可能找到任何五个的集合可以粉碎的点。
实际上，这个问题可能有一些模棱两可的地方。这取决于概念类在什么意义上可以“正确分类”一组点。即 C1 是否正确分类 (1, 2)，其中 1 被赋予负类标签，2 被赋予正类标签（因为它正确划分它），还是只能 C2 这样做？我假设它可以，因为这样问题会稍微有趣一些。
于 2009-10-21T14:47:56.713 回答
0
这个答案真的正确吗？
粉碎意味着对于您选择的一组数据点，例如。(14,24,3)，对于它的每一个可能的标签，在集合中都存在一个与该标签一致的概念。
但是考虑给定的示例（14,24,3），这里列出了这三个点的所有可能的真/假标签，以及哪些类与它们一致：
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）
1 1 1 没有一致的类
所以类集不会破坏这个数据集。（或者我是否误解了定义中的某些内容？）
于 2012-08-17T17:30:45.400 回答