VC联盟维度？

Question

假设我有两个概念类：C1 和 C2。假设C1的VC维为d，C2的VC维为d。

C1 和 C2 并集的 VC 维数的最大值是多少？

Answer 1

下面我假设您并不是要指定 C1 和 C2 具有相同的 VC 尺寸 d，而是指定不同的 VC 尺寸 d1 和 d2。我还将假设（不失一般性）d1 >= d2。

这取决于“C1 和 C2 的并集”的含义。由C1和C2并集形成的概念类的VC维具有VC维d1。这非常简单，因为要粉碎 d1 或更少的点，只需使用 C1 中的东西即可。然而，根据定义，C1 或 C2 都不会破坏 d1 + 1 点。

编辑- 下一段中的论点是错误的，请参阅 HRJ 对所谓“k 折叠联盟”的真实故事的回答。

因为这很无聊，也许您指的是概念类，在该概念类中您可以根据 C1 的一个元素和 C2 的一个元素的并集形成一个假设。这里的 VC 维数是 d1 + d2。要看到这一点，请将任何 d1+d2 点划分为两个子集，并分别用 C1 和 C2 中的元素粉碎它们。这样做的结果是，对于 2D 中的线性分隔符，VC 维度将是 3+3=6，您可以从以下事实看出这一点：有一个相当明显的六边形标记，不能被两条线打碎。

不同意 HRJ 的观点，我认为这甚至不是工会的正确下限。例如，letX = {x1,x2,x3,x4}和C = {{x1,x3},{x2,x4}}then C 可以粉碎大小为 1 的任何子集，但不能，例如VC 维度 1 也是{x1,x2}如此。C但是，C 的 2 重并集C^2={{x1,x3},{x2,x4},{x1,x2,x3,x4}}仍然是 VC 维度 1。进一步的并集即将结束做同样的事情。所以，我认为 k 重并集的下界是d。话又说回来，我可能是错的。