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-04-2014 12:18 AM

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 for every . Then, regardless of what the probability distribution of , it will be true that since we can multiply both sides of by and integrate out.

 jokovc 11-04-2014 09: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 for every . Then, regardless of what the probability distribution of , it will be true that since we can multiply both sides of by and integrate out.
I think this is so much clearer than when it is put in sentences. Thank you.

 ilson 10-01-2015 08: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 "" and "" (which is given) imply "".

Quote:
 Inequality (A.3) folows because the events "" and "" (which is given) imply "".
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 01: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

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 10: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 03: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 04: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 08: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?

 CountVonCount 10-26-2016 04: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 02:38 PM

Re: Discussion of the VC proof

Suppose

Then, .

In which case 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 04:13 AM.