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-11-2013, 11:32 PM
i_need_some_help i_need_some_help is offline
Junior Member
 
Join Date: Sep 2013
Posts: 4
Default Stuck on Problem 1.7

On part (a), I tried a few different things. Most recently, 1 - binomcdf(1 to 10 | N, mu) ^ (number of coins), but this doesn't seem to be correct.

In the case where mu is 0.05 and we try with one coin, the probability should be 1 - 0.05**10. I can't figure out how to generalize that to multiple coins.

WON'T YOU HELP??
Reply With Quote
  #2  
Old 09-12-2013, 06:11 AM
magdon's Avatar
magdon magdon is offline
RPI
 
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 592
Default Re: Stuck on Problem 1.7

First you need to compute the probability that any one specific coin has nu=0. Call this probability P. Now the number of coins that have nu=0 is itself a binomial distribution with probability P.

You can use the above observation, or you can use a trick: the probability that at least one coin has nu=0 is related in a simple way to the probability that all coins have \nu\not=0


Quote:
Originally Posted by i_need_some_help View Post
On part (a), I tried a few different things. Most recently, 1 - binomcdf(1 to 10 | N, mu) ^ (number of coins), but this doesn't seem to be correct.

In the case where mu is 0.05 and we try with one coin, the probability should be 1 - 0.05**10. I can't figure out how to generalize that to multiple coins.

WON'T YOU HELP??
__________________
Have faith in probability
Reply With Quote
  #3  
Old 09-10-2014, 01:44 PM
foenix foenix is offline
Junior Member
 
Join Date: Sep 2014
Posts: 1
Default Re: Stuck on Problem 1.7

Greetings,

This is in reference to part (b) of Problem 1.7
I am having some difficulty understanding what is meant by using the max over two coins.

My understanding is that the two coins both have binomial distributions for nu with 6 trials and a mu of .5. As such, wouldn't the probability of a given nu be the same for both coins? What am I missing here?

Appreciate the help.
Reply With Quote
  #4  
Old 09-11-2014, 05:12 AM
magdon's Avatar
magdon magdon is offline
RPI
 
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 592
Default Re: Stuck on Problem 1.7

Your understanding is correct that each \nu has the same binomial distribution. What you are missing is that each coin is tossed independently. An example might help.

Toss the two coins 6 times and suppose the first has 3 heads and the second gas 2 heads.

\nu_1=0.5,\nu_2=\frac{1}{3}.

Define the deviations:

d_1=|\nu_1-\mu_1|=0,\ d_2=|\nu_2-\mu_2|=\frac{1}{6}.

Define the worst deviation:

d=\max_i |\nu_i-\mu_i|=\max(d_1,d_2)=\frac{1}{6}.

In this particular instance the deviation is 0.16666. You are asked to compute the probability distribution for d. In particular,

P[d>\epsilon]


Quote:
Originally Posted by foenix View Post
Greetings,

This is in reference to part (b) of Problem 1.7
I am having some difficulty understanding what is meant by using the max over two coins.

My understanding is that the two coins both have binomial distributions for nu with 6 trials and a mu of .5. As such, wouldn't the probability of a given nu be the same for both coins? What am I missing here?

Appreciate the help.
__________________
Have faith in probability
Reply With Quote
  #5  
Old 03-10-2016, 05:22 AM
MaciekLeks MaciekLeks is offline
Member
 
Join Date: Jan 2016
Location: Katowice, Upper Silesia, Poland
Posts: 17
Default Re: Stuck on Problem 1.7

Hello Professor Malik Magdon-Ismail,

I did Exercise 1.10/c and Problem 1.7. I've done it but I still do not know how to interpret the results correctly.

Questions:
1. How the worst deviation method you mentioned is related to the hint in the book (the sum rule)?
2. If I use Hoeffding Inequality with your method, should I multiply RHS of Hoeffding Inequality by a number of coins (in this case M=2)? IMHO, I should not.
3. Why cmin in (Exercise 1.10) does not hold the hoeffding bound while max deriation in Problem 1.7 holds the bound (see the plot and the linked post)?
4. While increasing the sample size to N=10 the Hoeffding bound is not longer held for Problem 1.7. Why?

The plots:

N=6, RHS=2.0*exp(-2.0*(ε^2.0)*N)


N=10, RHS=2.0*exp(-2.0*(ε^2.0)*N)


P.S. Please see my unanswered question for Exercise 1.10 (c) here: http://book.caltech.edu/bookforum/showthread.php?t=4616
Reply With Quote
  #6  
Old 06-05-2016, 06:47 AM
henry2015 henry2015 is offline
Member
 
Join Date: Aug 2015
Posts: 31
Default Re: Stuck on Problem 1.7

1. I think here is how P[max(..)>\epsilon] relates to the Rule of Addition:

Let's say A=|v0-u0|>\epsilon, B=|v1-u1|>\epsilon
P[max(..)>\epsilon]
<= P[A or B]
= P[A] + P[B] - P[A and B]

Since P[A] and P[B] are both bound by Hoeffding Inequality (HI), hence,
P[A] + P[B] - P[A and B]
<= 2 * (HI's bound) - P[A and B]
<= 2 * (HI's bound) because P[A and B] >= 0

In this case, we can see that M is 2 (as expected because we are using 2 coins).

2. See above.

3. I believe that if you rerun your script several times, you will see that the vanilla HI doesn't apply but M*HI's bound does. The reason your plot showed that HI applied because you were just lucky, and HI is talking about the upper bound, which indicates "always true" if the condition meets; that's why Exercise 1.10 asks the reader to run 100000 trials and then pick the min to make sure the reader won't be "lucky" to have vmin bound by the vanilla HI but M * HI's bound.

4. See #3.

I am not an expert so I could be wrong.

If any prof can confirm, it would be benefit for everyone reading here

Thanks!



Quote:
Originally Posted by MaciekLeks View Post
Hello Professor Malik Magdon-Ismail,

I did Exercise 1.10/c and Problem 1.7. I've done it but I still do not know how to interpret the results correctly.

Questions:
1. How the worst deviation method you mentioned is related to the hint in the book (the sum rule)?
2. If I use Hoeffding Inequality with your method, should I multiply RHS of Hoeffding Inequality by a number of coins (in this case M=2)? IMHO, I should not.
3. Why cmin in (Exercise 1.10) does not hold the hoeffding bound while max deriation in Problem 1.7 holds the bound (see the plot and the linked post)?
4. While increasing the sample size to N=10 the Hoeffding bound is not longer held for Problem 1.7. Why?

The plots:

N=6, RHS=2.0*exp(-2.0*(ε^2.0)*N)


N=10, RHS=2.0*exp(-2.0*(ε^2.0)*N)


P.S. Please see my unanswered question for Exercise 1.10 (c) here: http://book.caltech.edu/bookforum/showthread.php?t=4616

Last edited by henry2015; 06-05-2016 at 09:29 PM. Reason: clarity
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 02:23 AM.


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.