 LFD Book Forum Q2.2/Hoeffding clarifications

#1
 chris Junior Member Join Date: Sep 2012 Posts: 5 Q2.2/Hoeffding clarifications

A few questions regarding question 2.2:

- Is the question asking which statistics (v_1, v_r and v_min) fit the assumptions underlying application of the Hoeffding inequality for estimating the bias of an individual coin (i.e. mu = out of sample probability of a head)?

- Is it fair to say that Hoeffding can be applied to any of these statistics as long as mu reflects the out of sample distribution of that statistic?

- What is the appropriate value of N when applying Hoeffding to the average of 100,000 repetitions of the average number of heads realised by 10 coin flips? Is it 100,000 or 1,000,000? Seems to me that the overall process is equivalent to averaging the number of heads over 1,000,000 coin flips?

#2 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477 Re: Q2.2/Hoeffding clarifications

Quote:
 Originally Posted by chris - Is the question asking which statistics (v_1, v_r and v_min) fit the assumptions underlying application of the Hoeffding inequality for estimating the bias of an individual coin (i.e. mu = out of sample probability of a head)?
Correct

Quote:
 - Is it fair to say that Hoeffding can be applied to any of these statistics as long as mu reflects the out of sample distribution of that statistic?
Hoeffding involves both in-sample and out-of-sample frequencies, so just (out of sample) may not suffice.

Quote:
 - What is the appropriate value of N when applying Hoeffding to the average of 100,000 repetitions of the average number of heads realised by 10 coin flips? Is it 100,000 or 1,000,000? Seems to me that the overall process is equivalent to averaging the number of heads over 1,000,000 coin flips?
If the basic event here involves 10 coin tosses (say the event being that the number of heads out of 10 tosses is 10), and that experiment is repeated 100,000 times, then of the Hoeffding inequality is 100,000.
__________________
Where everyone thinks alike, no one thinks very much
#3
 chris Junior Member Join Date: Sep 2012 Posts: 5 Re: Q2.2/Hoeffding clarifications

Regarding my second question, I was trying to determine whether Hoeffding can be applied to v_min using mu = the expected minimum fraction of heads from 10 flips of 1000 coins (<< 0.5 for unbiased coins) rather than mu = the expected fraction of heads from 10 flips of a single coin (0.5 for an unbiased coin). I interpreted the question as assuming the latter but my understanding of Hoeffding is that it could be applied to v_min assuming the former. Does that make sense?

And to clarify my final question, I was thinking about the case of v_1 where the expected value of the statistic in question is not affected by the number of coins or number of flips of each coin per experiment. Specifically, I would like to understand the difference between 2 approaches to estimating the probability of flipping a head from a Hoeffding perspective (1) averaging the fraction of heads realised by 10 coin flips over 100,000 experiments, and (2) the fraction of heads realised by 1,000,000 repetitions of a single flip. They are the same in terms of the calculation of the average statistic over 1,000,000 total flips but (2) gives a tighter Hoeffding bound. Presumably to calculate a simple statistic such as the probability of a head for a specific coin (vs a more complex statistic such as the min fraction of heads from 10 flips of 1000 coins), one would always frame the experiment as (2) to take advantage of the lower Hoeffding probability of error bound?
#4 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477 Re: Q2.2/Hoeffding clarifications

Quote:
 Originally Posted by chris Regarding my second question, I was trying to determine whether Hoeffding can be applied to v_min using mu = the expected minimum fraction of heads from 10 flips of 1000 coins (<< 0.5 for unbiased coins) rather than mu = the expected fraction of heads from 10 flips of a single coin (0.5 for an unbiased coin).
Hoeffding cannot be directly applied, but more general forms that use expected values and variances of general random variables (rather than just the probability of an event and the frequency of occurence of that event) can be applied.

Quote:
 Specifically, I would like to understand the difference between 2 approaches to estimating the probability of flipping a head from a Hoeffding perspective (1) averaging the fraction of heads realised by 10 coin flips over 100,000 experiments, and (2) the fraction of heads realised by 1,000,000 repetitions of a single flip.
Hoeffding can be directly applied to (1), the event being "ten heads out of 10 flips," whereas (2) involves the expected value of a random variable as discussed above.
__________________
Where everyone thinks alike, no one thinks very much
#5
 chris Junior Member Join Date: Sep 2012 Posts: 5 Re: Q2.2/Hoeffding clarifications

Quote:
 Originally Posted by yaser Hoeffding cannot be directly applied, but more general forms that use expected values and variances of general random variables (rather than just the probability of an event and the frequency of occurence of that event) can be applied.
I think I'm starting to converge on an understanding. So the basic form of Hoeffding introduced in lecture only addresses estimating the probability of an event. I checked the Wikipedia entry for the Hoeffding inequality (http://en.wikipedia.org/wiki/Hoeffding%27s_inequality) and it states a more general form that covers the expected value of bounded random variables. Is this one of the more general forms that you mentioned? Looks like the Hoeffding equation in the lecture could be derived from this form by setting the lower and upper bounds to 0 and 1. Am I on the right track here?

Quote:
 Originally Posted by yaser Hoeffding can be directly applied to (1), the event being "ten heads out of 10 flips," whereas (2) involves the expected value of a random variable as discussed above.
Could the basic form of Hoeffding be used for (2) where the event is described as flipping a head on a single coin toss?
#6 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477 Re: Q2.2/Hoeffding clarifications

Quote:
 Originally Posted by chris it states a more general form that covers the expected value of bounded random variables. Is this one of the more general forms that you mentioned?
Correct. You can also look up Chebyshev inequality and Chernoff bounds.

Quote:
 Could the basic form of Hoeffding be used for (2) where the event is described as flipping a head on a single coin toss?
Yes, although this case may not be of particular interest.
__________________
Where everyone thinks alike, no one thinks very much
#7
 chris Junior Member Join Date: Sep 2012 Posts: 5 Re: Q2.2/Hoeffding clarifications

Thanks for your help in resolving my queries Yaser, it is very much appreciated. Fantastic course by the way and looking forward to reading the book when it arrives in my post box.

 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 12:07 AM. 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.