View Single Post
Old 04-28-2013, 12:12 PM
marek marek is offline
Join Date: Apr 2013
Posts: 31
Default Re: Q10 higher bound

Originally Posted by alasdairj View Post
In 2d, a positive "2d ray" in the x direction can shatter 1 point, and a positive "2d ray" in the y direction can shatter 1 point, whereas their union can shatter 2 points...

So at least I can feel comfortable that the union of hypothesis sets *can* achieve a VC dimension which is the sum of the VC dimensions of its parts, but can it exceed it??
I am struggling with this question as well. Based on this discussion, I can intuit what the right answer should be, but I am struggling with the justification.

I figure if I can simply come up with an H1 and H2 such that d(H1 U H2) = d(H1) + d(H2) + 1, I would be done. I can come up 1 short of that (much like your example, even consider 1d positive and negative rays). But I cannot think of an example that would hit the higher bound.

That being said, I decided to just play around with the growth function. We know that m_H(N) \leq \sum_{i=0}^{d} {N \choose i}. If all the terms in that expansion are present, we get 2^N and hence can shatter. The binomial expansion is symmetric, so if I had two growth functions that were "disjoint" one could get the terms from the bottom and the other could get terms from the top and these could together give the full expansion.

More formally:\sum_{i=0}^{d_1} {N \choose i} + \sum_{i=0}^{d_2} {N \choose i} = \sum_{i=0}^{d_1} {N \choose i} + \sum_{i=N-d_2}^{N} {N \choose i}. This gives the full expansion if the second sum starts off one term after the first sum ends, specifically N-d_2 \leq d_1 + 1 \Leftrightarrow N \leq d_1 + d_2 + 1.

This simple analysis gives me my desired d_1 + d_2 + 1. But clearly something is missing. How can growth functions be "disjoint"? Any example I come up with, there is a significant overlap in dichotomies. I feel like I'm definitely on the right track here, but I also feel like something is clearly missing. Maybe B(N,k) is a better starting point than the growth function?

Hopefully someone can pick up the ball and carry it over the finish line...
Reply With Quote