View Single Post
Old 04-28-2013, 09:56 PM
MindExodus MindExodus is offline
Junior Member
Join Date: Apr 2013
Posts: 3
Default Re: Q10 higher bound

Your requirement 2 can be simply rendered from Q9 that the VC dimension of intersection of hypothesis could not exceed any one of them(hope I got Q9 right)

As for requirement 1, I come up with the case that
H1 := mapping all points to +1
H2 := mapping all points to -1
thus d_1 = 0 , d_2 = 0 , d_{1+2} = 1 = d_1 + d_2 + 1

Originally Posted by OlivierB View Post
@marek, Thanks for your contribution.
Let me try and rephrase, not adding much.


For m_{H}(N)=2^N 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 H_{1} and H_{2} must be exactly B(N, d_1+1) and B(N, d_2+1)
2/ Removing the intersection of H_{1} and H_{2} from H_{2} does not decrease the VC dimension of H_{2}. 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 H is at least d_1+d_2+1.

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'.
Reply With Quote