Thread: Q10 higher bound View Single Post
#15
04-29-2013, 07:19 PM
 jforbes Member Join Date: Apr 2013 Posts: 12
Re: Q10 higher bound

Quote:
 Originally Posted by MindExodus thus: , and can shatter all 3 point
MindExodus - very nice; I'm thoroughly convinced.

Quote:
 Originally Posted by nkatz Here is another example for the upper bound: * H1 takes any 1 point and sets it to + or -, with the other points--if any--getting 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
nkatz, your example has me slightly puzzled. The only way H1 can fail to shatter 2 points is if there are exactly two points:
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.