View Single Post
Old 09-01-2012, 10:46 AM
vsthakur vsthakur is offline
Join Date: Jun 2012
Posts: 14
Default Re: Possible correction to Problem 2.14 (b)

Originally Posted by magdon View Post
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.
Got it, thanks. The inequality should be strict i think (d_{vc}(H) < l, when \; 2^l > Kl^{d_{vc}+1}).
Reply With Quote