 LFD Book Forum Q1 and Q2
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read Thread Tools Display Modes
#1
 fgpancorbo Senior Member Join Date: Jul 2012 Posts: 104 Q1 and Q2

I am a bit confused about these two questions. Without getting the actual answers, any insight would be appreciated.

First, with regards to Q1; I have run the experiment many times, and I don't get any of the suggested answers. This is my code,

v_1 = 0;
v_rand = 0;
v_min = 0;
vmins = zeros(100000,1);
for i=1:100000
experiment = zeros (10,1000);
vs = zeros (1,1000);
experiment = randi([0 1],10,1000); % Do the experiment
vs = sum(experiment)/10; % compute frequencies
v_1 = v_1 + vs(1);
v_rand = v_rand + vs(randi(1000));
vmins(i) = min(vs); % find v_min
v_min = v_min + vmins(i);
end

v_1 = v_1/100000
v_rand = v_rand/100000
v_min = v_min/100000

With that code I get a v_min which is neither of the suggested. I don't see what I am doing wrong.

Regarding Q2; there is another thread on the matter http://book.caltech.edu/bookforum/showthread.php?t=880 but I am still unclear. I kind of believe what is the right answer, but I am confused about the wording of the question.

Hoeffdings inequality requires a particular setup to be useful from a quantitative point of view: N (number of experiments, in Q1 that's 10) and epsilon (the tolerance, which we haven't been given). Without a required epsilon, we cannot reach any conclusions from a quantitative point of view. My feeling is that Q2 is a question independent of any N (thus, forget about 10) or epsilon (thus not required). Something along the lines:

"suppose we have 1000 thousand identical coins and we wanted to estimate the bias of any the coins. We choose c_1, c_rand and c_min as explained in Q1. For which coin (or coins) could we use Hoeffdings inequality to get a fair estimate of the number of samples required to have an estimate of the bias for a given tolerance? For example, plugging in N = 10000, epsilon = 0.01, 2*exp(-2*(0.01)^2*100000) = 4.1223e-009, which is pretty good. Which coin(s) will give us the coin bias with a probability 1 - 4.1223e-009?"

If Q2 is about what goes in between "", then I know the answer. If not, I am confused.
#2
 tzs29970 Invited Guest Join Date: Apr 2012 Posts: 52 Re: Q1 and Q2

Quote:
 Originally Posted by fgpancorbo With that code I get a v_min which is neither of the suggested. I don't see what I am doing wrong.
The reason you can't see what you are doing wrong is simple: you aren't doing anything wrong! Q1 asks which of the 5 given answers is closest to v_min. When the professor says "closest" in this course, it doesn't mean one answer is going to turn out to be the expected value of the experiment and you should expect to get an answer close to that, just deviating a little due to chance. Nope. The homework choices often are several standard deviations from the expected experimental result.

For instance, if the expected value of some experiment was 40 with a standard deviation of 5, the homework might give you choices of 1, 10, and 100. None of those are numbers you would ever actually see in your experiment. The right answer in that case would be 10, because abs(10-40) = 30, and that is less than abs(100-40).

I ran your code in Octave, and the result it gave was within 0.0004 of what my Python code gave. I've already submitted mine, and I got it right, so you are fine as long as you correctly pick which is closest to your result.

Last edited by tzs29970; 07-23-2012 at 01:14 AM. Reason: I accidentally a word
#3
 fgpancorbo Senior Member Join Date: Jul 2012 Posts: 104 Re: Q1 and Q2

Quote:
 Originally Posted by tzs29970 I ran your code in Octave, and the result it gave was within 0.0004 of what my Python code gave. I've already submitted mine, and I got it right, so you are fine as long as you correctly pick which is closest to your result.
Thanks . I'll run it tonight and will let you know.

Cheers,

Fernando.
#4
 fgpancorbo Senior Member Join Date: Jul 2012 Posts: 104 Re: Q1 and Q2

Quote:
 Originally Posted by fgpancorbo Thanks . I'll run it tonight and will let you know. Cheers, Fernando.
I've run it and the method works. I got this one right . Now, I want to point out that my understanding of question 2 seems to be correct as well.
#5
 Marc Zucker Member Join Date: Jan 2013 Posts: 24 Re: Q1 and Q2

I have a quick question regarding the 2nd question on the 2nd homework. When the question asks for which coin or coins satisfy Hoeffding's Inequality, is it asking which coin(s) satisfy the conditions for us to apply Hoeffding's Inequality, or is it asking practically which actually satisfy the Inequlaity. If it is the latter of the two, how are we to choose epsilon for this question?

Thanks.
#6 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478 Re: Q1 and Q2

Quote:
 Originally Posted by Marc Zucker I have a quick question regarding the 2nd question on the 2nd homework. When the question asks for which coin or coins satisfy Hoeffding's Inequality, is it asking which coin(s) satisfy the conditions for us to apply Hoeffding's Inequality, or is it asking practically which actually satisfy the Inequlaity. If it is the latter of the two, how are we to choose epsilon for this question?
Hi Marc,

It is the former.
__________________
Where everyone thinks alike, no one thinks very much
#7
 nroger Member Join Date: Jan 2013 Posts: 10 Re: Q1 and Q2

But does question 2 ask:
(a) whether the nu's from question 1 can be plugged in to Hoeffding's Inequality (involving an average over 100000 experiments), or
(b) whether the nu's from just 10 flips can be plugged in ?
Thanks....Neil
#8 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478 Re: Q1 and Q2

Quote:
 Originally Posted by nroger But does question 2 ask: (a) whether the nu's from question 1 can be plugged in to Hoeffding's Inequality (involving an average over 100000 experiments), or (b) whether the nu's from just 10 flips can be plugged in ? Thanks....Neil
For Problem 2, it's (b).
__________________
Where everyone thinks alike, no one thinks very much
#9
 melipone Senior Member Join Date: Jan 2013 Posts: 72 Re: Q1 and Q2

How to choose epsilon?
I understand that any epsilon will do for the Hoeffding inequality but I think I want an epsilon that will give me a probability that P(v - mu) > epsilon is greater than 0, correct?
What is a good range of epsilon to try?
#10 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478 Re: Q1 and Q2

Quote:
 Originally Posted by melipone How to choose epsilon? I understand that any epsilon will do for the Hoeffding inequality but I think I want an epsilon that will give me a probability that P(v - mu) > epsilon is greater than 0, correct? What is a good range of epsilon to try?
For Problem 2, satisfying Hoeffding's Inequality means that the inequality is valid for all 's. Whether applying the Inequality with a particular leads to a useful bound is a separate question.
__________________
Where everyone thinks alike, no one thinks very much 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 09:32 PM.

 Contact Us - LFD Book - Top

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.