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 11-20-2012, 09:11 AM
eakarahan eakarahan is offline
Junior Member
 
Join Date: Nov 2012
Posts: 3
Default Proof of Hoeffding's inequality is required

Ref: Page 22, Chp 1, last paragraph.

What are the assumptions that are needed to prove Hoeffding's inequality that no longer hold if we are allowed to change h after we generate the data set? Please give a proof of Hoeffding inequality in this context, explicitly showing these assumptions.
Reply With Quote
  #2  
Old 11-20-2012, 02:46 PM
htlin's Avatar
htlin htlin is offline
NTU
 
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 601
Default Re: Proof of Hoeffding's inequality is required

Quote:
Originally Posted by eakarahan View Post
Ref: Page 22, Chp 1, last paragraph.

What are the assumptions that are needed to prove Hoeffding's inequality that no longer hold if we are allowed to change h after we generate the data set? Please give a proof of Hoeffding inequality in this context, explicitly showing these assumptions.
You can refer to homework e/2 of my current class

http://www.csie.ntu.edu.tw/~htlin/co...oc/hw0_5_e.pdf

for guided steps of the proof. The proof needs the distribution that generates the random variable (in the problem z_i or in the learning context [ y_n \neq h(\mathbf{x}_n) ]) to be "fixed" before starting the proof, and of course z_i needs to come independently from the distribution. If a different h is used, P(z) is different, and if many different h are considered altogether, we need to be cautious about the independence assumption. Hope this helps.
__________________
When one teaches, two learn.
Reply With Quote
  #3  
Old 11-21-2012, 04:49 AM
eakarahan eakarahan is offline
Junior Member
 
Join Date: Nov 2012
Posts: 3
Default Re: Proof of Hoeffding's inequality is required

It seems a proof requires very strong probability background. But now I know at least that [ y_n \neq h(\mathbf{x}_n) ] to be "fixed" before starting the proof. I will defer the proof until I will reach the required math level, and will refresh my probability knowledge reserving an eye on the guidelines you send. Before I write this reply, I've reviewed some probability books that I've possess. I Could find the Markov's inequality, and Chernoff bound in some of them. I could not find Hoeffding's bound in any of them. Thus, I especially interested if you have a probability book (tailored for ML) you can recommend. The main difficulty in ML is the level of required math and I think it is never enough.
Reply With Quote
  #4  
Old 01-01-2013, 11:38 AM
donthireddy donthireddy is offline
Junior Member
 
Join Date: Jul 2012
Location: USA
Posts: 1
Default Re: Proof of Hoeffding's inequality is required

Thanks to eakarahan for asking, and to Prof. Lin for designing a great exercise.

I think I have managed to complete the proof. Most of the steps pushed my math skills to the limit. Took 2-3 hours spread over a couple of days.
The first one made me think harder about what a probability distribution is.
A fair bit of algebraic manipulation in the other steps, some optimization in step 4. I needed to think of using the Taylor expansion for one of the steps. Overall, it was excellent exercise for the brain.
Reply With Quote
Reply

Tags
hoeffding's inequality, proof

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 04:02 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.