LFD Book Forum - View Single Post

MindExodus · #8 04-28-2013, 09:56 PM

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$

Quote:

Originally Posted by OlivierB

@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

and

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

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