View Single Post
Old 04-29-2013, 01:24 AM
jforbes jforbes is offline
Join Date: Apr 2013
Posts: 12
Default Re: Q10 higher bound

Originally Posted by MindExodus View Post
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
Bad news: the problem requires that each hypothesis set has a finite positive VC dimension, so this particular example does not guarantee that the maximum is greater than the sum of the VC dimension for the case we're being asked about.

I'm still on the fence for this question - my first attempts at constructing an example similar to this where each hypothesis set had a VC dimension of 1 failed to shatter 3 points, but I'm not 100% sure yet that I can't get it to work.
Reply With Quote