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)
-   -   Exercise 2.1 (http://book.caltech.edu/bookforum/showthread.php?t=4618)

ilson 09-21-2015 10:33 AM

Exercise 2.1
 
Hi,

For the convex set case, it seems to me that since N points on a circle can always be shattered, there's always at least one data set of size k that can be shattered by \mathcal{H}. Thus, the break point does not exist for this \mathcal{H}. So then you can't really verify that m_{\mathcal{H}}(k)< 2^k for this case - or can you say that it's trivially true since break point k doesn't even exist? Is this the correct interpretation of this exercise?

magdon 09-21-2015 04:50 PM

Re: Exercise 2.1
 
Yes, when there is no break point, the theorem says that m_H(N)=2^N for all N. So the theorem is trivially verified.
Quote:

Originally Posted by ilson (Post 12050)
Hi,

For the convex set case, it seems to me that since N points on a circle can always be shattered, there's always at least one data set of size k that can be shattered by \mathcal{H}. Thus, the break point does not exist for this \mathcal{H}. So then you can't really verify that m_{\mathcal{H}}(k)< 2^k for this case - or can you say that it's trivially true since break point k doesn't even exist? Is this the correct interpretation of this exercise?


svend 09-19-2016 01:03 AM

Re: Exercise 2.1
 
I don't understand why the breaking point inequality holds for the positive rays or positive intervals .

For instance, it seems to me that no set of 3 real points can be shattered by a positive ray, since at least always the [cross, circle, cross] dichotomy cannot be achieved, no matter how large N is, so k=3 would be a breaking point and m_H(N) < 2^3, which is obviously not true for N>7 since the real growth function is m_H(N) = N + 1.

I understand that to be a breaking point, we need that no set of size k can be shattered, am I failing to imagine such set or did I misunderstand some of the definition?

dubwub 09-21-2016 07:11 PM

Re: Exercise 2.1
 
For N > 7 you need your growth function to be less than 2^N, not 2^3.


All times are GMT -7. The time now is 10:38 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, 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.