LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 2 - Training versus Testing (http://book.caltech.edu/bookforum/forumdisplay.php?f=109)
-   -   Problem 2.10 (http://book.caltech.edu/bookforum/showthread.php?t=4696)

wolszhang 09-28-2016 07:29 PM

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.

magdon 09-29-2016 11:01 AM

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:

Originally Posted by wolszhang (Post 12441)
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.


EliLee 12-01-2017 04:31 PM

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:

pdsubraa 12-08-2017 10:11 PM

Re: Problem 2.10
 
@Magdon - Can you explain us in detail.

That would help!

Thanks for your time!

magdon 03-04-2018 04:48 AM

Re: Problem 2.10
 
For example, if you have 10 ways to dichotomize 4 points x_1,\ldots,x_4 and 8 ways to dichotomize another 4 points x_5,\ldots,x_8, for each of the 10 ways for the first 4 points there are at most 8 ways to dichotomize the second 4 points (why?). Therefore, there are at most 10\times 8 ways to dichotomize all 8 points.



Quote:

Originally Posted by pdsubraa (Post 12876)
@Magdon - Can you explain us in detail.

That would help!

Thanks for your time!



All times are GMT -7. The time now is 11:19 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.