LFD Book Forum - View Single Post

vsthakur · #15 09-01-2012, 10:46 AM

Quote:

Originally Posted by magdon

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

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}$ ).