Problem 2.10
I understand that for the case m(N) = 2^N, we can show that this is true. But how do we prove it when m(N) < 2^N? It seems like every single theorem is giving me an upper bound. Any hints would be super appreciated.

Re: Problem 2.10
Hint: Any dichotomy 2N points can be viewed as a dichotomy on the first N points plus a dichotomy on the second N points.
Quote:

Re: Problem 2.10
I am still not quite clear about this problem. To prove this problem is true for all N values, I think we should discuss different relationship between break point k, N and 2N. I can prove that when N < 2N < k or k is infinite, the inequality holds. Also when N < k < 2N, the in equality also holds. When k < N < 2N, do you mean mH(2N) = 2mH(N)? However I did not figure it out.:clueless:

Re: Problem 2.10
@Magdon  Can you explain us in detail.
That would help! Thanks for your time! 
All times are GMT 7. The time now is 11:47 PM. 
Powered by vBulletin® Version 3.8.3
Copyright ©2000  2021, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. AbuMostafa, Malik MagdonIsmail, and HsuanTien Lin, and participants in the Learning From Data MOOC by Yaser S. AbuMostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.