LFD Book Forum Clarification on VC bound
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
04-21-2012, 03:58 AM
 ladybird2012 Member Join Date: Apr 2012 Posts: 32
Clarification on VC bound

Hi,
I would like to request a little clarification on the VC bound from Lecture 6. For the slide entitled "What to do about Eout?", I understand that the Ein and Ein' both track Eout, although more loosely than Ein on just one sample. But I don't understand why having the Ein on two samples (Ein and Ein') allows us to characterize them in terms of dichotomies. What is so special about 2 samples (why not 1 or 3?)? Is this something that becomes clear in the proof (which I haven't looked at yet) or is this something that can be understood conceptually?

Sorry I wasn't able to ask this question in the Q&A but it is not practical for me to follow the lectures live.

Thanks a lot.
#2
04-21-2012, 10:54 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Clarification on VC bound

Quote:
 Originally Posted by ladybird2012 Hi, I would like to request a little clarification on the VC bound from Lecture 6. For the slide entitled "What to do about Eout?", I understand that the Ein and Ein' both track Eout, although more loosely than Ein on just one sample. But I don't understand why having the Ein on two samples (Ein and Ein') allows us to characterize them in terms of dichotomies. What is so special about 2 samples (why not 1 or 3?)? Is this something that becomes clear in the proof (which I haven't looked at yet) or is this something that can be understood conceptually? Sorry I wasn't able to ask this question in the Q&A but it is not practical for me to follow the lectures live. Thanks a lot.
The two samples are a technical trick that allows us to consider the dichotomies on a finite sample of data points ( of them), while still capturing the fact that with multiple hypotheses, the Hoeffding-type bounds become looser and looser. This gives us a concrete way of accounting for the overlaps in terms of a combinatorial quantity rather than full probabilistic analysis of dependence between events.

Having said that, what I did in the lecture was only a sketch of the proof to underline the main ideas in the formal proof. To pin it down completely, there is really no alternative to going through the formal proof which appears in the Appendix. It is not that hard, but certainly not trivial.
__________________
Where everyone thinks alike, no one thinks very much
#3
04-22-2012, 03:22 AM
 silvrous Member Join Date: Apr 2012 Posts: 24
Re: Clarification on VC bound

So the proof is only available in the coursebook?
#4
04-22-2012, 12:03 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Clarification on VC bound

Quote:
 Originally Posted by silvrous So the proof is only available in the coursebook?
There are different versions of the VC inequality and its proof in the literature. The version in the book follows the logic and notation I used in the lecture.
__________________
Where everyone thinks alike, no one thinks very much
#5
04-26-2012, 04:15 PM
 pventurelli@gotoibr.com Member Join Date: Apr 2012 Posts: 12
Re: Clarification on VC bound

I have a question regarding a statement made in the textbook. On page 51 in the second paragraph, it is said that the m_H grows logarithmically with N and so is crushed by the factor 1/N. First, igiven that (from page 50) m_H is bounded from above by N^d_vc + 1, how is it true that m_H grows logarithmically with N? Second, is the crushed part of the statement saying that a function that is of the form f1=log(N) is dominated by a function f2=1/x in the sense that f1/f2 tends to zero as N tends to infinity?

Thanks for your help in clarifying this point.
#6
04-26-2012, 07:33 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Clarification on VC bound

Quote:
 Originally Posted by pventurelli@gotoibr.com I have a question regarding a statement made in the textbook. On page 51 in the second paragraph, it is said that the m_H grows logarithmically with N and so is crushed by the factor 1/N. First, igiven that (from page 50) m_H is bounded from above by N^d_vc + 1, how is it true that m_H grows logarithmically with N? Second, is the crushed part of the statement saying that a function that is of the form f1=log(N) is dominated by a function f2=1/x in the sense that f1/f2 tends to zero as N tends to infinity? Thanks for your help in clarifying this point.
The growth function grows polynomially, but the generalization bound has a logarithm in it, and the logarithm of a polynomial grows at a logarithmic rate itself, and hence gets crushed by the linear denominator. It is essentially the same as a polynomial getting crushed by a negative exponential, with the only difference being that we went into a logarithmic scale for both.
__________________
Where everyone thinks alike, no one thinks very much

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 03:18 PM.

 Contact Us - LFD Book - Top

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.