LFD Book Forum  

Go Back   LFD Book Forum > Book Feedback - Learning From Data > Chapter 2 - Training versus Testing

Reply
 
Thread Tools Display Modes
  #1  
Old 04-18-2012, 05:46 PM
timhndrxn timhndrxn is offline
Junior Member
 
Join Date: Apr 2012
Posts: 9
Default 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.
Reply With Quote
  #2  
Old 04-19-2012, 01:46 PM
magdon's Avatar
magdon magdon is offline
RPI
 
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 595
Default 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 View Post
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.
__________________
Have faith in probability
Reply With Quote
  #3  
Old 04-19-2012, 02:51 PM
jcatanz jcatanz is offline
Member
 
Join Date: Apr 2012
Posts: 41
Default Re: Shattering by dichotomies

Thanks for this helpful explanation!
Reply With Quote
  #4  
Old 04-19-2012, 04:45 PM
timhndrxn timhndrxn is offline
Junior Member
 
Join Date: Apr 2012
Posts: 9
Post Re: Shattering by dichotomies

Magdon, the explanation helps. Thank you. --Tim
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -7. The time now is 10:51 AM.


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.