LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 1 - The Learning Problem (http://book.caltech.edu/bookforum/forumdisplay.php?f=108)
-   -   Problem 1.9 (http://book.caltech.edu/bookforum/showthread.php?t=4625)

RicLouRiv 06-23-2017 04:42 PM

Re: Problem 1.9
 
Quick question on Part D...

I agree that s = ln(a / (1-a)) is the value of s that minimizes e^(-sa)U(s), where I'm using "a" to represent "alpha."

I think that, if you plug this value of s in, you get 2^(-b), where I'm using "b" to represent "beta."

So, 2^(-b) < e^(-sa)U(s), by definition of minimization.

Then, raising to the power of N, we get:

2^(-bN) < (e^(-sa)U(s))^N, but this inequality is the wrong way.

Any tips?

RicLouRiv 06-24-2017 09:36 AM

Re: Problem 1.9
 
Ah, maybe it's because the inequality holds for any s, it must hold for the min.

htlin 06-29-2017 10:00 PM

Re: Problem 1.9
 
Quote:

Originally Posted by RicLouRiv (Post 12685)
Ah, maybe it's because the inequality holds for any s, it must hold for the min.

You got it. :-)

mygame182 10-22-2017 04:19 AM

Re: Problem 1.9
 
Quote:

Originally Posted by RicLouRiv (Post 12685)
Ah, maybe it's because the inequality holds for any s, it must hold for the min.

Excuse me, I can understand your last reply, but confuse in this one.
More tips please.

When 2^(-b) is the minimize of e^(-sa)U(s), i find that 1-a = 1/2 + e (e means epsilon), so P[u>=a] = P[u>= 1/2 - e] , but not P[u>=1/2+e].

mygame182 10-23-2017 08:23 AM

Re: Problem 1.9
 
When 2^(-b) equal to the minimize of e^(-sa)U(s), i try to assume that 1-a=1/2-e, so that a = 1/2 + e, P[u>=a]=P[u>=1/2+e]

According to (b), P[u>=1/2+e] = P[u>=a] <= (e^(-sa)U(s))^N for any s , even if the minimize of e^(-sa)U(s) when s = ln(a / (1-a)).

Hence P[u>=1/2+e] <= 2^(-bN)

don slowik 11-14-2017 03:14 PM

Re: Problem 1.9
 
That's correct. But it doesn't get us anywhere.

don slowik 11-14-2017 03:18 PM

Re: Problem 1.9
 
Ahhhm, That was a reply to kongweihan's OP.
It is correct as shown by the first line: Since...
But ends up barking up the wrong tree.
There is a nice description on wikipedia of Chernoff bound.
It is similar to maciekleks path.

Ulyssesyang 11-09-2018 07:02 PM

Re: Problem 1.9
 
Quote:

Originally Posted by svend (Post 12434)
Here's my take on Problem 1.9, part(b), which is following the same lines as the description of MaciekLeks above.

We have:

\begin{split}
P(u \geq \alpha ) & = P(\frac{1}{N}{}\sum_n x_n \geq \alpha)  \\
 & = P(\sum_n x_n \geq N \alpha) \\
 & = P(e^{s \sum_n x_n} \geq e^{s N \alpha})
\end{split}

Since e^{s t} is monotonically increasing in t.

Also, e^{s t} is non negative for all t, implying Markov inequality holds:

\begin{split}
P(e^{s \sum_n x_n} \geq e^{s N \alpha}) & \leq \frac{E(e^{s \sum_n x_n})}{e^{s N \alpha}} \\
& = \frac{E(\prod_n e^{s x_n})}{e^{s N \alpha}} \\
& = \frac{\prod_n E(e^{s x_n})}{e^{s N \alpha}}
\end{split}

The last line being true since [math]x_n[\math] are independent.

From there it directly follows that

P(u \geq \alpha ) \leq U(s)^N e^{-s N \alpha}

I just think you should note that there are two expectations, one is based on e^su_n, while other is based on u_n. Of course, you can refer the law of unconscious statisticians to prove that both are same.


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