#11




Re: Q10 higher bound
sry about didn't notice that requirement
but the key to this problem is the same: let me just put another example: just think of H1 and H2 on H1: H2: thus: , and can shatter all 3 point Quote:

#12




Re: Q10 higher bound
Here is another example for the upper bound:
* H1 takes any 1 point and sets it to + or , with the other pointsif anygetting the opposite sign * H2 sets all to + or all to  H1 can only shatter 1 point, and H2 can only shatter 1 point Their union however can shatter 3 points 
#13




Re: Q10 higher bound
And this method can be generalizes!!
for with VC dimension H1: hypothesis over mapping these point to cases that at most points to +1 and other points to 1 H2: hypothesis over mapping these point to cases that at most points to 1 and other points to +1 so there is at least +1 and other points to 1 easy to prove that since so can shatter all point By proper extension with same idea, it can reach higher bound in k points cases 
#14




Re: Q10 higher bound

#15




Re: Q10 higher bound
MindExodus  very nice; I'm thoroughly convinced.
Quote:
H1 contains + and +, but not  or ++ Whereas if you give it three points, it contains +, +, +, ++, ++, and ++. Just looking at the first two points, now H1 contains all 4 combinations. How can this be if its VC dimension is only 1? I think it must be the case that , but I'd be unsurprised if I were missing something. 
#16




Re: Q10 higher bound
A useful little construction is this.
If you have two underlying disjoint sets of points and , and hypothesis sets and (where is the set of subsets of ), then you can can form a new hypothesis set with one hypothesis for each pair of hypotheses in and (in the obvious way). There is a simple relationship between the VCdimensions of these three hypothesis sets, which can be used in examples. 
#17




Re: Q10 higher bound
Quote:

#18




Re: Q10 higher bound
Good work on this problem by several of you guys!

#19




Re: Q10 higher bound
Quote:
I'm still curious about what went wrong if H1 does in fact include +, +, ... Is this sort of hypothesis set disallowed for some reason? 
#20




Re: Q10 higher bound
Great work everyone  this question had me scratching my head until I found this post. The one thing I don't understand is the above statment. Am I missing something? It seems like it should be an inequality.

Thread Tools  
Display Modes  

