View Single Post
Old 04-29-2013, 08:19 PM
jforbes jforbes is offline
Join Date: Apr 2013
Posts: 12
Default Re: Q10 higher bound

Originally Posted by MindExodus View Post
d_{H1} = 1 , d_{H2} = 1
and \{H_1 \cup H_2\} can shatter all 3 point

d_{H_1 \cup H_2} = 3
MindExodus - very nice; I'm thoroughly convinced.

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 d_{VC}(H_1) > 1, but I'd be unsurprised if I were missing something.
Reply With Quote