LFD Book Forum  

Go Back   LFD Book Forum > Book Feedback - Learning From Data > Appendix and Notation

Reply
 
Thread Tools Display Modes
  #11  
Old 11-04-2014, 12:18 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,474
Default Re: Discussion of the VC proof

Quote:
Originally Posted by jokovc View Post
Hi Prof. Yaser. I have a problem with the proof of Lemma A.2., page 190. I don't understand what this part means
Here is what it means. Let's say that you have P(A|B)\le \alpha for every B. Then, regardless of what the probability distribution of B, it will be true that P(A)\le \alpha since we can multiply both sides of P(A|B)\le \alpha by P(B) and integrate B out.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #12  
Old 11-04-2014, 09:24 PM
jokovc jokovc is offline
Junior Member
 
Join Date: Nov 2014
Posts: 2
Default Re: Discussion of the VC proof

Quote:
Originally Posted by yaser View Post
Here is what it means. Let's say that you have P(A|B)\le \alpha for every B. Then, regardless of what the probability distribution of B, it will be true that P(A)\le \alpha since we can multiply both sides of P(A|B)\le \alpha by P(B) and integrate B out.
I think this is so much clearer than when it is put in sentences. Thank you.
Reply With Quote
  #13  
Old 10-01-2015, 08:32 PM
ilson ilson is offline
Member
 
Join Date: Sep 2015
Posts: 10
Default Re: Discussion of the VC proof

I was going through the proof in Appendix A and I just want to make sure that something written towards the bottom of pg. 189 is a typo.

Namely,

Quote:
Inequality (A.3) folows because the events "|E'_{in}(h^*)-E_{out}(h^*)|\leq \frac{\epsilon}{2}" and "|E_{in}(h^*)-E_{out}(h^*)|>\epsilon" (which is given) imply "|E_{in}(h)-E'_{in}(h)|>\frac{\epsilon}{2}".
should read

Quote:
Inequality (A.3) folows because the events "|E'_{in}(h^*)-E_{out}(h^*)|\leq \frac{\epsilon}{2}" and "|E_{in}(h^*)-E_{out}(h^*)|>\epsilon" (which is given) imply "|E_{in}(h^*)-E'_{in}(h^*)|>\frac{\epsilon}{2}".
I'm 99.999999999999% sure this is indeed a typo since the latter case easily follows from reverse triangle inequality and it suffices to show the inequality in (A.3) and I cannot see how one can arrive at the implication in the former case nor how the former case implies the inequality (A.3), but it would ease my mind if I can get a verification that it is a typo. Thank you in advance!
Reply With Quote
  #14  
Old 10-13-2015, 01:04 PM
magdon's Avatar
magdon magdon is offline
RPI
 
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 592
Default Re: Discussion of the VC proof

Yes, this is a typo. Thank you for pointing it out. You have it correct.

If A and C imply B, then

P[B|C]  \ge P[A|C]

Quote:
Originally Posted by ilson View Post
I was going through the proof in Appendix A and I just want to make sure that something written towards the bottom of pg. 189 is a typo.

Namely,



should read



I'm 99.999999999999% sure this is indeed a typo since the latter case easily follows from reverse triangle inequality and it suffices to show the inequality in (A.3) and I cannot see how one can arrive at the implication in the former case nor how the former case implies the inequality (A.3), but it would ease my mind if I can get a verification that it is a typo. Thank you in advance!
__________________
Have faith in probability
Reply With Quote
  #15  
Old 09-26-2016, 10:56 PM
CharlesL CharlesL is offline
Junior Member
 
Join Date: Sep 2016
Location: Vancouver
Posts: 1
Default Re: Discussion of the VC proof

Recently I have started reading the proof of the VC inequality in the appendix. On the bottom of page 190(Lemma A.3) , why does

sigma_S P[S] x P[sup_h E_in - E_in' > ... |S ] <= sup_S P[sup_h E_in - E_in' >...|S ]?
(Sorry for the terrible notations, I don't know how I can input math symbols)

what does it mean by taking the supremum on S?
Reply With Quote
  #16  
Old 10-05-2016, 03:23 PM
htlin's Avatar
htlin htlin is offline
NTU
 
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 562
Default Re: Discussion of the VC proof

Quote:
Originally Posted by CharlesL View Post
Recently I have started reading the proof of the VC inequality in the appendix. On the bottom of page 190(Lemma A.3) , why does

sigma_S P[S] x P[sup_h E_in - E_in' > ... |S ] <= sup_S P[sup_h E_in - E_in' >...|S ]?
(Sorry for the terrible notations, I don't know how I can input math symbols)

what does it mean by taking the supremum on S?
All complicated math aside, supremum on S carries the physical meaning of taking the "maximum" value over all possible S.

So this inequality simply says an expected value (of P[sup_...]) is less than or equal to the maximum value.

Hope this helps.
__________________
When one teaches, two learn.
Reply With Quote
  #17  
Old 10-08-2016, 04:44 PM
tayfun29 tayfun29 is offline
Junior Member
 
Join Date: Oct 2016
Posts: 1
Default Re: Discussion of the VC proof

Quote:
Originally Posted by htlin View Post
All complicated math aside, supremum on S carries the physical meaning of taking the "maximum" value over all possible S.

So this inequality simply says an expected value (of P[sup_...]) is less than or equal to the maximum value.

Hope this helps.
Thank...
__________________
kuranı kerimde geçen dualar
Reply With Quote
  #18  
Old 10-25-2016, 08:39 AM
gamelover623 gamelover623 is offline
Junior Member
 
Join Date: Sep 2016
Posts: 1
Default Re: Discussion of the VC proof

I am a machine learning practitioner currently applying machine learning to algorithmic trading, yet highly interested in the theoretical grounds of the field.

I have read your book "Learning from data" from cover to cover. I haven't solved the problems though. I however did go through the proof of the VC bound in the appendix. I succeeded to understand most of it except (A.4) in the bottom of page 189. I can understand that you have applied Hoeffding Inequality to h*, but your explanation on how this applies to h* conditioned to the sup_H event, is hard to grasp for me.

Can you please give more explanation on how using Hoeffding (A.4) holds ? Or give a reference that helps clarifying this result?





Openload Movies
Free Download Movies HD Online
__________________
Free Download Movies HD Online
Reply With Quote
  #19  
Old 10-26-2016, 04:23 AM
CountVonCount CountVonCount is offline
Member
 
Join Date: Oct 2016
Posts: 17
Default Re: Discussion of the VC proof

Hi,

I have a question about the sentence on page 190:
Quote:
Note that we can assume e^(-0.5*N*eps^2) < 1/4, because otherwise the bound in Theorem A.1 is trivially true.
While I understand the argument here, I don't understand, why it is especially the value 1/4?
When set the above term to 1/4 I will receive -2*ln(1/4) as value for N*eps^2.
Now I can set N*eps^2 to that value in Theorem A.1 and I will get on the RHS (assuming the growth function is just 1) 4*0,707... so it is much more than 1.

A value of 1 in the RHS would be sufficient to say the bound in Theorem A.1 is trivially true. And this would assume, that the above term is less than 1/256.
With this in mind 1 - 2*e^(-0.5*N*eps^2) is greater than 0,99... and thus instead of a 2 in the lemmas outcome, I would receive a value around 1, which is a much better outcome.

So why is the value 1/4 chosen for the assumption?

Best regards,
André
Reply With Quote
  #20  
Old 10-26-2016, 02:38 PM
magdon's Avatar
magdon magdon is offline
RPI
 
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 592
Default Re: Discussion of the VC proof

Suppose e^{-\frac12\epsilon^2N}\ge\frac14

Then, e^{-\frac18\epsilon^2N}\ge e^{-\frac12\epsilon^2N}\ge\frac14.

In which case 4 m(2N) e^{-\frac18\epsilon^2N}\ge 4m(2N)/4\ge 1 and the bound in Theorem A.1 is trivial.


Quote:
Originally Posted by CountVonCount View Post
Hi,

I have a question about the sentence on page 190:


While I understand the argument here, I don't understand, why it is especially the value 1/4?
When set the above term to 1/4 I will receive -2*ln(1/4) as value for N*eps^2.
Now I can set N*eps^2 to that value in Theorem A.1 and I will get on the RHS (assuming the growth function is just 1) 4*0,707... so it is much more than 1.

A value of 1 in the RHS would be sufficient to say the bound in Theorem A.1 is trivially true. And this would assume, that the above term is less than 1/256.
With this in mind 1 - 2*e^(-0.5*N*eps^2) is greater than 0,99... and thus instead of a 2 in the lemmas outcome, I would receive a value around 1, which is a much better outcome.

So why is the value 1/4 chosen for the assumption?

Best regards,
André
__________________
Have faith in probability
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:15 PM.


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