VC联盟维度？
假设我有两个概念类：C1 和 C2。 假设C1的VC维为d，C2的VC维为d。
C1 和 C2 并集的 VC 维数的最大值是多少？
Suppose I have two concept classes: C1 and C2.
Suppose that the VC Dimension of C1 is d and the VC Dimension of C2 is d.
What is the biggest value of the VC dimension of the union of C1 and C2?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
请参阅 Eisenstat 和 Angluin 的论文“The VC Dimension of k-fold union”，他们在其中表明 VC 维度随着 Theta(klogk) 渐近增加。
StompChicken 的答案不可能是正确的，因为它意味着 k 重并集的 VC 维数是 O(k)。我相信他对 d_1+d_2 的下限的论证是正确的。
See Eisenstat and Angluin's paper, "The VC Dimension of k-fold union", where they show that the VC dimension increases asymptotically as Theta(klogk).
The StompChicken answer can not be correct, because it implies the VC dimension of k-fold union is O(k). I believe he argues correctly for a lower bound of d_1+d_2.
下面我假设您并不是要指定 C1 和 C2 具有相同的 VC 尺寸 d，而是指定不同的 VC 尺寸 d1 和 d2。我还将假设（不失一般性）d1 >= d2。
这取决于“C1 和 C2 的并集”的含义。由C1和C2并集形成的概念类的VC维具有VC维d1。这非常简单，因为要粉碎 d1 或更少的点，只需使用 C1 中的东西即可。然而，根据定义，C1 或 C2 都不会破坏 d1 + 1 点。
编辑 - 下段中的论点是错误的，请参阅HRJ对所谓“k-fold union”真实故事的回答。
不同意 HRJ 的观点，我认为这甚至不是工会的正确下限。例如，让
X = {x1,x2,x3,x4}和C = {{x1,x3},{x2,x4}}那么 C 可以粉碎任何大小为 1 的子集，但不是，例如{x1,x2}，因此C的 VC 维度为 1。但是，C 的 2 重并集是C^ 2={{x1,x3},{x2,x4},{x1,x2,x3,x4}}仍然是 VC 维度 1。进一步的并集最终会得到同样的结果。所以，我认为 k 重并集的下界是 d。话又说回来，我可能是错的。In the following I am going to assume you didn't mean to specify that the C1 and C2 have the same VC dimension d, but rather different VC dimensions d1 and d2. I'm also going to assume (without loss of generality) that d1 >= d2.
It depends what you mean by 'the union of C1 and C2'. The VC dimension of the concept class formed by the union of C1 and C2 has VC dimension d1. This is pretty straightforward, since to shatter d1 or fewer points, just use something from C1. However, neither C1 or C2 will shatter d1 + 1 points, pretty much by definition.
EDIT - The argument in the following paragraph is wrong, see HRJ's answer for the real story of what is apparently called the 'k-fold union'.
To disagree with HRJ I don't think it's even a correct lower bound of the union. For example, let
X = {x1,x2,x3,x4}andC = {{x1,x3},{x2,x4}}then C can shatter any subset of size 1 but not, for example{x1,x2}soChas VC dimension 1. But, the 2-fold union of C isC^2={{x1,x3},{x2,x4},{x1,x2,x3,x4}}which is still of VC dimension 1. Further unions are just going to end up with the same thing. So, I think the lower bound of the k-fold union isd. Then again, I could be wrong.如果 VC(H_1)=d_1 且 VC(H_2)=d_2 且 d=max(d_1,d_2)，则并集 VC 上的一般界限为 2d+1。请参阅附图，因为我找不到插入乳胶的方法。
If VC(H_1)=d_1 and VC(H_2)=d_2 and d=max(d_1,d_2) the general bound on the VC of the union is 2d+1. See attached img since i could not find a way to insert latex.
如果 VCdim(A) = d_A 且 VCdim(B) = d_B，则 A 和 B 的并集（我们称之为并集 C）的 VCdim 至多为 d_A + d_B + 1。 这是我的证明：
If VCdim(A) = d_A and VCdim(B) = d_B, VCdim of union of A and B (We call the union C) is at most d_A + d_B + 1. Here is my proof: