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)

CountVonCount 10-26-2016 02:28 PM

Re: Discussion of the VC proof
 
I have also another question on the same page (190):
At the end of the page there is the formula:

https://latex.codecogs.com/gif.latex...pace;S&space;]

I don't understand why the RHS is greater or equal to the LHS. The only legitimation I see for this is, that the distribution of P[S] is uniform, but this has not been stated in the text.
Or do I oversee here anything and this is also valid for all kinds of distribution?

CountVonCount 10-26-2016 02:32 PM

Re: Discussion of the VC proof
 
Quote:

Originally Posted by magdon (Post 12472)
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.

Hello,

thanks for the answer. I understand this argument, however this holds also for

e^{-\frac12\epsilon^2N}\ge\frac18

or for

e^{-\frac12\epsilon^2N}\ge\frac{1}{16}

Thus the value 1/4 is somehow magic for me.

Edit: I think you choose 1/4 because it is so easy to see, that the RHS of Theorem A.1 gets 1. Nevertheless with a different value you would get a different outcome of the final formula.

CountVonCount 10-28-2016 12:52 AM

Re: Discussion of the VC proof
 
Quote:

Originally Posted by CountVonCount (Post 12473)
...
I don't understand why the RHS is greater or equal to the LHS. The only legitimation I see for this is, that the distribution of P[S] is uniform, but this has not been stated in the text.
Or do I oversee here anything and this is also valid for all kinds of distribution?

I got it by myself.
When we have a uniform distribution of P[S] the outcome of the product-sum

\sum_S P[S] \times P[A|S]

is simply the average of all P[A|S], since

\sum_S P[S] = 1

And an average is of course less than or equal to the maximum of P[A|S].
If P[S] is not distributed uniformly we still have an average, but a weighted average. But also here the result is always less than or equal to the maximum. Because you cannot find weighting factors that are in sum 1 but will lead to a higher result as the maximum P[A|S].

magdon 11-09-2016 05:21 AM

Re: Discussion of the VC proof
 
Correct.

Quote:

Originally Posted by CountVonCount (Post 12475)
I got it by myself.
When we have a uniform distribution of P[S] the outcome of the product-sum

\sum_S P[S] \times P[A|S]

is simply the average of all P[A|S], since

\sum_S P[S] = 1

And an average is of course less than or equal to the maximum of P[A|S].
If P[S] is not distributed uniformly we still have an average, but a weighted average. But also here the result is always less than or equal to the maximum. Because you cannot find weighting factors that are in sum 1 but will lead to a higher result as the maximum P[A|S].


magdon 11-09-2016 05:23 AM

Re: Discussion of the VC proof
 
You are correct. We could have made other assumptions.

But there is a special reason why we DO want 1. Because we are bounding the probability, and so there is nothing to prove if we claim that a probability is less equal to 1. So, whenever the RHS (i.e. the bound) evaluates to 1 or bigger, there is nothing to prove. So we only need to consider the case when the bound evaluates to less than 1.


Quote:

Originally Posted by CountVonCount (Post 12474)
Hello,

thanks for the answer. I understand this argument, however this holds also for

e^{-\frac12\epsilon^2N}\ge\frac18

or for

e^{-\frac12\epsilon^2N}\ge\frac{1}{16}

Thus the value 1/4 is somehow magic for me.

Edit: I think you choose 1/4 because it is so easy to see, that the RHS of Theorem A.1 gets 1. Nevertheless with a different value you would get a different outcome of the final formula.


CountVonCount 11-11-2016 02:52 AM

Re: Discussion of the VC proof
 
Thank you very much for your answers. This helps me a lot to understand the intention of the single steps of this prove.

sarafox 08-28-2017 09:13 AM

Re: Discussion of the VC proof
 
i had same question but thanks to your website my question just solved. thanks

samyar1 04-23-2018 08:00 AM

Re: Discussion of the VC proof
 
thank you for your answer. i like it.

delinglish 07-04-2018 04:52 AM

Re: Discussion of the VC proof
 
at the beginning everything was complicated, so at first, I gave it a thought, but I could take in nothing. by the way that was pretty easy. thank you so much.


All times are GMT -7. The time now is 07:36 AM.

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.