View Single Post
Old 04-30-2013, 06:31 PM
jforbes jforbes is offline
Join Date: Apr 2013
Posts: 12
Default Re: Q10 higher bound

Originally Posted by Elroch View Post
There are no rules constraining the specific hypotheses in a hypothesis set. It can be any subset of the power set of the underlying set of points.
OK, so if we assume that H is such that it "takes any 1 point and sets it to + or -, with the other points--if any--getting the opposite sign" as proposed by nkatz, then:
for N=1, H={+,-} and shatters this 1 point
for N=2, H={+-,-+} and does not shatter these two points.
for N=3, H={++-, +-+, -++, --+, -+-, +--} and does shatter two points.

What is the VC dimension of this hypothesis set? From the N=2 case, I might conclude that it's 1 (it fails to shatter two points), but from the N=3 case I might conclude it's 2 (it shatters 2 of the points within this set of points). Where am I going wrong?
Reply With Quote