VC Dimension of union?

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?

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.

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'.

Since that's quite boring, maybe you meant the the concept class where you are allowed to form a hypothesis from the union of one element of C1 and one element of C2. The VC dimension here is d1 + d2. To see this, partition any d1+d2 points into two subsets and shatter them with elements in C1 and C2 respectively. A consequence of this is that, for linear separators in 2D, the VC dimension is going to be 3+3=6 and you can see this from the fact that there is a fairly obvious labelling of a hexagon that cannot be shattered by two lines.

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} and C = {{x1,x3},{x2,x4}} then C can shatter any subset of size 1 but not, for example {x1,x2} so C has VC dimension 1. But, the 2-fold union of C is C^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 is d. Then again, I could be wrong.

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.

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: