LFD Book Forum  

Go Back   LFD Book Forum > Book Feedback - Learning From Data > Chapter 1 - The Learning Problem

Reply
 
Thread Tools Display Modes
  #1  
Old 09-29-2015, 01:14 AM
kongweihan kongweihan is offline
Junior Member
 
Join Date: Sep 2015
Posts: 1
Default Problem 1.9

I'm working through this problem and stuck on (b).

Since P[u_n \geq \alpha] \leq e^{-s\alpha}U(s), we get
\prod_{n=1}^N P[u_n \geq \alpha] \leq (e^{-s\alpha}U(s))^N

We also know\prod_{n=1}^N P[u_n \geq \alpha] \leq P[\sum_{n=1}^N u_n \geq N\alpha] = P[u \geq \alpha]

Both terms in the desired inequality is bigger than the common term, so I don't know how these two inequalities can lead to the desired conclusion, what did I miss?

Also, in (c), why do we want to minimize with respect to s and use that in (d)?
Reply With Quote
  #2  
Old 03-21-2016, 07:29 AM
MaciekLeks MaciekLeks is offline
Member
 
Join Date: Jan 2016
Location: Katowice, Upper Silesia, Poland
Posts: 17
Default Re: Problem 1.9

Quote:
Originally Posted by kongweihan View Post
I'm working through this problem and stuck on (b).

Since P[u_n \geq \alpha] \leq e^{-s\alpha}U(s), we get
\prod_{n=1}^N P[u_n \geq \alpha] \leq (e^{-s\alpha}U(s))^N

We also know\prod_{n=1}^N P[u_n \geq \alpha] \leq P[\sum_{n=1}^N u_n \geq N\alpha] = P[u \geq \alpha]

Both terms in the desired inequality is bigger than the common term, so I don't know how these two inequalities can lead to the desired conclusion, what did I miss?

Also, in (c), why do we want to minimize with respect to s and use that in (d)?

How do you know that \prod_{n=1}^N P[u_n \geq \alpha] \leq (e^{-s\alpha}U(s))^N? I think that is a problem in your proof that you assumed that the joint probability works with Problem 1.9(b) inequality.

To proof (b) I went this way:

1. I used Markov Inequality \mathbb{P}[u\geq\alpha]\leq\frac{\mathbb{E}_{u}[u]}{\alpha}

2. Problem 1.9(a) gave me this: \mathbb{P}[t\geq\alpha]=\mathbb{P}[e^{sNt}\geq e^{sN\alpha}]\leq\frac{\mathbb{E}[e^{sNt}]}{e^{sN\alpha}}, hence \mathbb{P}[u\geq\alpha]\leq\frac{\mathbb{E}_{u}[e^{sNu}]}{e^{sN\alpha}}

Using this the rest of the proof is quite nice to carry out.
Reply With Quote
  #3  
Old 05-12-2016, 02:18 AM
waleed waleed is offline
Junior Member
 
Join Date: May 2016
Posts: 4
Default Re: Problem 1.9

Quote:
Originally Posted by MaciekLeks View Post
How do you know that \prod_{n=1}^N P[u_n \geq \alpha] \leq (e^{-s\alpha}U(s))^N? I think that is a problem in your proof that you assumed that the joint probability works with Problem 1.9(b) inequality.

To proof (b) I went this way:

1. I used Markov Inequality \mathbb{P}[u\geq\alpha]\leq\frac{\mathbb{E}_{u}[u]}{\alpha}

2. Problem 1.9(a) gave me this: \mathbb{P}[t\geq\alpha]=\mathbb{P}[e^{sNt}\geq e^{sN\alpha}]\leq\frac{\mathbb{E}[e^{sNt}]}{e^{sN\alpha}}, hence \mathbb{P}[u\geq\alpha]\leq\frac{\mathbb{E}_{u}[e^{sNu}]}{e^{sN\alpha}}

Using this the rest of the proof is quite nice to carry out.
I don't think the condition right
Reply With Quote
  #4  
Old 09-17-2016, 10:43 AM
svend svend is offline
Junior Member
 
Join Date: Sep 2016
Posts: 2
Default Re: Problem 1.9

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}
Reply With Quote
  #5  
Old 03-03-2017, 07:53 AM
k_sze k_sze is offline
Junior Member
 
Join Date: Dec 2016
Posts: 5
Question Re: Problem 1.9

Quote:
Originally Posted by kongweihan View Post
Also, in (c), why do we want to minimize with respect to s and use that in (d)?
I also have trouble understanding (c).

Actually I don't even know how to tackle it. I think I'll need a lot of hand-holding through this one because my math got really rusty since I left school (I'm 34).
Reply With Quote
  #6  
Old 03-03-2017, 08:25 AM
k_sze k_sze is offline
Junior Member
 
Join Date: Dec 2016
Posts: 5
Default Re: Problem 1.9

Quote:
Originally Posted by k_sze View Post
I also have trouble understanding (c).

Actually I don't even know how to tackle it. I think I'll need a lot of hand-holding through this one because my math got really rusty since I left school (I'm 34).
Will I need to summon notions such as "moment generating function" for part (c) of this problem?
Reply With Quote
  #7  
Old 03-06-2017, 03:38 AM
Sebasti Sebasti is offline
Junior Member
 
Join Date: Mar 2017
Posts: 2
Default Re: Problem 1.9

Quote:
Originally Posted by k_sze View Post
Actually I don't even know how to tackle it. I think I'll need a lot of hand-holding through this one because my math got really rusty since I left school
So I'm not the only one. Gee, thanks
Reply With Quote
  #8  
Old 03-15-2017, 06:11 AM
k_sze k_sze is offline
Junior Member
 
Join Date: Dec 2016
Posts: 5
Default Re: Problem 1.9

Quote:
Originally Posted by k_sze View Post
Will I need to summon notions such as "moment generating function" for part (c) of this problem?
So I did end up using moment generating function. And I think the answer to (c) is s = \ln{\frac{\alpha}{1-\alpha}}, using calculus.

But now I'm stuck at (d).

Directly substituting \alpha = \mathbb{E}(u) + \epsilon is probably wrong? Because e^{s}U(s) can be simplified to the point where no logarithm appears (unless I made a really big mistake).
Reply With Quote
  #9  
Old 03-16-2017, 09:36 AM
k_sze k_sze is offline
Junior Member
 
Join Date: Dec 2016
Posts: 5
Default Re: Problem 1.9

Quote:
Originally Posted by k_sze View Post
So I did end up using moment generating function. And I think the answer to (c) is s = \ln{\frac{\alpha}{1-\alpha}}, using calculus.

But now I'm stuck at (d).

Directly substituting \alpha = \mathbb{E}(u) + \epsilon is probably wrong? Because e^{s}U(s) can be simplified to the point where no logarithm appears (unless I made a really big mistake).
*sigh*

I did end up getting \beta by substituting \mathbb{E}(u) + \epsilon for \alpha, but only after simplifying e^{-s\alpha}U(s) all the way down, until there is no more e or \ln, otherwise I get two powers of 2 with no obvious way to combine them.

So now the remaining hurdle is to prove that \beta > 0.

Yay
Reply With Quote
  #10  
Old 04-01-2017, 07:19 AM
k_sze k_sze is offline
Junior Member
 
Join Date: Dec 2016
Posts: 5
Default Re: Problem 1.9

Quote:
Originally Posted by k_sze View Post
*sigh*

I did end up getting \beta by substituting \mathbb{E}(u) + \epsilon for \alpha, but only after simplifying e^{-s\alpha}U(s) all the way down, until there is no more e or \ln, otherwise I get two powers of 2 with no obvious way to combine them.

So now the remaining hurdle is to prove that \beta > 0.

Yay
I finally worked out the proof for \beta > 0. Apparently using Jensen's inequality is supposed to be the simple way, but I simply don't get Jensen's inequality, so I used some brute force calculus (first and second derivatives, find the minimum, etc.)
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -7. The time now is 10:23 PM.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2017, 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.