Thread: Q10 higher bound View Single Post
#6
 OlivierB Member Join Date: Apr 2013 Location: Paris Posts: 16 Re: Q10 higher bound

Let me try and rephrase, not adding much.

For a hypothesis set H with VD dimension d, we have The second equality is the result of 2 inequalities in opposite direction. In class, we saw '≤' and '≥' is the subject of problem 2.4 in the book.

Let 2 hypothesis sets and with VC dimensions respectively and .

We can construct two disjoint and putting the intersection of both with one of them only.  The VC dimension of is The VC dimension of is Let H be the union of these hypothesis sets: Let Now in order to try and determine the VC dimension of H, let us compute a higher bound of : which we can simplify:  For to be true i.e. for H to shatter N, all inequalities must be equalities.
In other words, we must have:
1/ The growth functions of and must be exactly and 2/ Removing the intersection of and from does not decrease the VC dimension of . If the intersection is empty then this condition holds.

If these 2 requirements are not contradictory (which seems plausible but I cannot prove - neither can I visualize with an example), then the VC dimension of is at least .

Now unless there is a mistake in the reasoning, the question is: Can these requirements be met ? Ideally via an example, because beyond the abstract equations, I would really like to 'visualize' a case where these inequalities are 'saturated'.