LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Appendix and Notation (http://book.caltech.edu/bookforum/forumdisplay.php?f=142)
-   -   Discussion of the VC proof (http://book.caltech.edu/bookforum/showthread.php?t=4524)

yaser 11-03-2014 11:18 PM

Re: Discussion of the VC proof
 
Quote:

Originally Posted by jokovc (Post 11806)
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.

jokovc 11-04-2014 08:24 PM

Re: Discussion of the VC proof
 
Quote:

Originally Posted by yaser (Post 11810)
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.

ilson 10-01-2015 07:32 PM

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!

magdon 10-13-2015 12:04 PM

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 (Post 12078)
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!


CharlesL 09-26-2016 09:56 PM

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?

htlin 10-05-2016 02:23 PM

Re: Discussion of the VC proof
 
Quote:

Originally Posted by CharlesL (Post 12439)
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.

tayfun29 10-08-2016 03:44 PM

Re: Discussion of the VC proof
 
Quote:

Originally Posted by htlin (Post 12450)
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...

gamelover623 10-25-2016 07:39 AM

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

CountVonCount 10-26-2016 03:23 AM

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é

magdon 10-26-2016 01:38 PM

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 (Post 12469)
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é



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