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)
-   -   Chapter 1 - Exercise 1.9 (http://book.caltech.edu/bookforum/showthread.php?t=4412)

goldsj3 09-11-2013 10:31 AM
Chapter 1 - Exercise 1.9
 
Based on the marbles example, I understand that u is the probability of choosing a red marble from the bin of marbles and v is the fraction of red marbles in the sample of chosen marbles. And I think that the LHS of the Hoeffding Inequality represents the probability of v deviating from u being greater than the error bar epsilon. Now, I am not sure how I should choose an epsilon to evaluate this probability and where I should begin. Can someone point me in the right direction?

magdon 09-11-2013 12:31 PM
Re: Chapter 1 - Exercise 1.9
 
If \mu=0.9 and \nu\le0.1, it implies that |\nu-\mu|>0.8^- (any number slightly less than 0.8). By the implication bound,

P[\nu\le0.1] \le P[|\nu-\mu|>0.8^-]

By looking at the RHS, one can identify \epsilon for applying the Hoeffding bound.

eshmrt 09-15-2015 02:51 PM
Re: Chapter 1 - Exercise 1.9
 
Since we're only looking at epsilon applied in one direction, meaning that we're only interested in nu being mu - 0.8 and not mu + 0.8, should we drop the leading 2 from the bound calculation? I'm not sure if I'm interpreting this bound correctly or simply overthinking things.

magdon 09-21-2015 04:27 PM
Re: Chapter 1 - Exercise 1.9
 
You are right. If al you want is the "one sided deviation", you could drop the factor of 2. However keeping the factor of 2 is a worse but still valid bound.


Quote:
Originally Posted by eshmrt (Post 12036)
Since we're only looking at epsilon applied in one direction, meaning that we're only interested in nu being mu - 0.8 and not mu + 0.8, should we drop the leading 2 from the bound calculation? I'm not sure if I'm interpreting this bound correctly or simply overthinking things.

henry2015 11-05-2017 07:17 AM
Re: Chapter 1 - Exercise 1.9
 
Quote:
Originally Posted by magdon (Post 11480)
If \mu=0.9 and \nu\le0.1, it implies that |\nu-\mu|>0.8^- (any number slightly less than 0.8). By the implication bound,

P[\nu\le0.1] \le P[|\nu-\mu|>0.8^-]

By looking at the RHS, one can identify \epsilon for applying the Hoeffding bound.
Hi, I am a bit confused.

I thought when it says \nu\le0.1, it means 0\le\nu\le0.1 because smallest probably is 0; hence, 0.8\le|\nu-\mu|\le0.9....I am sure I miss something.

Any pointer?

Thanks!

mike7 09-11-2018 03:03 PM
Re: Chapter 1 - Exercise 1.9
 
Quote:
Originally Posted by magdon (Post 11480)
If \mu=0.9 and \nu\le0.1, it implies that |\nu-\mu|>0.8^- (any number slightly less than 0.8). By the implication bound,

P[\nu\le0.1] \le P[|\nu-\mu|>0.8^-]

By looking at the RHS, one can identify \epsilon for applying the Hoeffding bound.
If I am understanding the implications of this correctly, \epsilon = 0.8 is too large within the Hoeffding bound, correct? One would need to select some \epsilon < 0.8, perhaps arbitrarily?


All times are GMT -7. The time now is 12:53 PM.

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