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 Then, . In which case and the bound in Theorem A.1 is trivial.
Hello,

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

or for

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

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

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 is simply the average of all P[A|S], since 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 or for 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