Discussion of the VC proof - Page 2

yaser · #11 11-04-2014, 12:18 AM

Quote:

Originally Posted by jokovc

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

. Then, regardless of what the probability distribution of

, it will be true that $P(A)\le \alpha$ since we can multiply both sides of $P(A|B)\le \alpha$ by

and integrate

out.

jokovc · #12 11-04-2014, 09:24 PM

Quote:

Originally Posted by yaser

Here is what it means. Let's say that you have $P(A|B)\le \alpha$ for every

. Then, regardless of what the probability distribution of

, it will be true that $P(A)\le \alpha$ since we can multiply both sides of $P(A|B)\le \alpha$ by

and integrate

out.

I think this is so much clearer than when it is put in sentences. Thank you.

ilson · #13 10-01-2015, 08:32 PM

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 · #14 10-13-2015, 01:04 PM

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

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 · #15 09-26-2016, 10:56 PM

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 · #16 10-05-2016, 03:23 PM

Quote:

Originally Posted by CharlesL

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 · #17 10-08-2016, 04:44 PM

Quote:

Originally Posted by htlin

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 · #18 10-25-2016, 08:39 AM

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 · #19 10-26-2016, 04:23 AM

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 · #20 10-26-2016, 02:38 PM

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

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é

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode