View Single Post
Old 08-29-2012, 09:30 AM
magdon's Avatar
magdon magdon is offline
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 597
Default Re: Possible correction to Problem 2.14 (b)

The problem, though an over-estimate seems correct.

Hint: If you have \ell points, then {\cal H}_1 can implement at most \ell^{d_{VC}}+1\le\ell^{d_{VC}+1} dichotomies on those points. Now try to upper bound the number of dichotomies that all K hypothesis sets can implement on these \ell points and proceed from there.

Originally Posted by vsthakur View Post
The problem says,

(b) Suppose that l satisfies 2^l  > K l^{d_{vc}+1}. Show that d_{vc}(H) \le l.

I suppose it should say,

(b) Suppose that l satisfies 2^l  > l^{K(d_{vc}+1)}. Show that d_{vc}(H) \le l.

If this is indeed the case, then can you please clarify part (c) as well.

Thank you,

Have faith in probability
Reply With Quote