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)
-   -   Shattering by dichotomies (http://book.caltech.edu/bookforum/showthread.php?t=376)

timhndrxn 04-18-2012 05:46 PM

Shattering by dichotomies
 
OK, Definition 2.2 talks about shattering dichotomies based on H. So H shatters dichotomies. So all was OK until Definition 2.4, which talks about shattering dichotomies by other dichotomies. :clueless:

magdon 04-19-2012 01:46 PM

Re: Shattering by dichotomies
 
Def 2.2 defines m(n) using H(x_1,x_2,\ldots,x_N) which is the restriction of H to a data set, i.e the number of different hypotheses that H can implement on this particular data set. A hypothesis when restricted to a finite data set results in a dichotomy, a collection of \pm 1 on the data points; A dichotomy is similar to a hypothesis. H does not shatter a dichotomy. It shatters a data set. So H shatters a data set if when restricted to that data set, H can implement all the 2^N dichotomies.


Def 2.4 is introducing a more subtle concept. Fix a break point k and consider the worst possible hypothesis set with the condition that it must have a break point k. Worst means having the largest m(N). The growth function of this worst hypothesis set is called B(N,k). The k indicates that the hypothesis set must have a break point there; otherwise B(N) is very much like m(N) except it is not for a particular hypothesis set, but rather for the worst possible hypothesis set with the break-point property.

We can analyze B(N,k) (even though it looks harder to analyze since we don't know what this worst hypothesis set is). However, for a particular hypothesis with break point k, we cannot really analyze m(N) without more information on they hypothesis set. But since B(N,k) is for the worst possible hypothesis set, the particular hypothesis set cannot be worse than this and so must have a smaller growth function. That is we indirectly bound m(N) by

m(N)\le B(N,k)

for any hypothesis set that has a break point at k.

Quote:

Originally Posted by timhndrxn (Post 1435)
OK, Definition 2.2 talks about shattering dichotomies based on H. So H shatters dichotomies. So all was OK until Definition 2.4, which talks about shattering dichotomies by other dichotomies. :clueless:


jcatanz 04-19-2012 02:51 PM

Re: Shattering by dichotomies
 
Thanks for this helpful explanation!

timhndrxn 04-19-2012 04:45 PM

Re: Shattering by dichotomies
 
Magdon, the explanation helps. Thank you. --Tim


All times are GMT -7. The time now is 06:28 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.