LFD Book Forum - View Single Post

magdon · #10 08-29-2012, 09:30 AM

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.

Quote:

Originally Posted by vsthakur

The problem says,

(b) Suppose that

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

I suppose it should say,

(b) Suppose that

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,

Vishwajeet.