View Single Post
Old 09-23-2012, 10:42 AM
magdon's Avatar
magdon magdon is offline
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 597
Default Re: Problem 2.3 c

You will note from the definition of the hypothesis set: \cal H contains functions which are +1 for

a\le\sqrt{x_1^2+\cdots+x_d^2}\le b

You only get to vary a,b, and so the two spheres are restricted to be centered on the origin.

And yes, the m_{\cal H}(N) for this hypothesis set is very related to the growth function for positive intervals.

Originally Posted by doris View Post
the last comment confused me a little bit.
For a given set of N points, we should change the center of the sphere to get as many dichotomies as we can, thus measuring the effective number of hypotheses (spheres) in this hypothesis set.

Does it make sense to move project the spheres from 3D to 1D and look at the problem as intervals of +1 for a<=x<=b and -a>=x>=b?
Have faith in probability
Reply With Quote