LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 3

Reply
 
Thread Tools Display Modes
  #1  
Old 04-21-2012, 03:58 AM
ladybird2012 ladybird2012 is offline
Member
 
Join Date: Apr 2012
Posts: 32
Default 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.
Reply With Quote
  #2  
Old 04-21-2012, 10:54 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Clarification on VC bound

Quote:
Originally Posted by ladybird2012 View Post
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 (2N 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
Reply With Quote
  #3  
Old 04-22-2012, 03:22 AM
silvrous silvrous is offline
Member
 
Join Date: Apr 2012
Posts: 24
Default Re: Clarification on VC bound

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

Quote:
Originally Posted by silvrous View Post
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
Reply With Quote
  #5  
Old 04-26-2012, 04:15 PM
pventurelli@gotoibr.com pventurelli@gotoibr.com is offline
Member
 
Join Date: Apr 2012
Posts: 12
Default 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.
Reply With Quote
  #6  
Old 04-26-2012, 07:33 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Clarification on VC bound

Quote:
Originally Posted by pventurelli@gotoibr.com View Post
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
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 03:18 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.