#1




Question 2
Hi all,
Is it correct to assume that each one of the thousand coins is its own "bin" in the multiple bin scenario of the Hoeffding inequality as explained in lecture 2, and therefore, is a separate hypothesis from the other bins? Prof. Yaser mentioned in another post (see here) that: Quote:

#2




Re: Question 2
I am hung up on this question too.
As I interpret it, a "bin" in this question corresponds to a particular way for defining a random experiment. In any case, we flip 1000 coins 10 times each and: 1) the random experiment for coin 1 consists of taking the 10 flips for that coin and averaging the number of heads, reporting that average as the sample frequency. 2) For the random coin, the random experiment consists in taking a random coin (11000) and averaging out the number of heads in the 10 flips for that coin. 3) for the "minimum number of heads coin", we flip 1000 coins 10 times each as before, but take the minimum frequency of heads obtained among the 1000 coins as the reported sample frequency. Each of these 3 situations constitutes a random experiment because it can be replicated any number of times. Each of the three scenarios has an expected frequency. The first two have an expected frequency (mu) of 0.5, the third has a different expected frequency but it can be calculated analytically (the probability distribution for the possible sample frequencies 0, 0.1, ..., 0.9, 1 can be determined for the "minimum heads" coin). The sample frequencies converge to the respective expected frequencies for the three scenarios, according to the law of large numbers. (No surprise)... So back to this: Quote:

#3




Re: Question 2
Quote:
The bin corresponds to the input space , with each marble corresponding to an input point . The colors in a bin correspond to how a hypothesis agrees with the target; the color of a marble being red if for that 'marble' . Fixed hypothesis means the colors inside the bin are fixed prior to drawing the sample. What makes a hypothesis 'not fixed' is that we have a bunch of bins and we select a bin according to the sample it produced (e.g., an all green sample). The reason we call the hypothesis not fixed in this case is because which bin we pick (hence which colors are inside, hence which hypothesis we are talking about) depends on the samples that have already been produced.
__________________
Where everyone thinks alike, no one thinks very much 
#4




Re: Question 2
Quote:

#5




Re: Question 2
Quote:
http://book.caltech.edu/bookforum/sh...0360#post10360 The main point is that once you consider the sample, the probability becomes conditional on how this sample came out, and that could violate the bound, whereas the probability before a sample was drawn always obeys the bound.
__________________
Where everyone thinks alike, no one thinks very much 
#6




Re: Question 2
Quote:
The possible difference I can see is that in Cmin case, sample kept changing, while in pocket case sample does not change, only color of marbles insidebin and outside bin changes, as the hypothesis changes. Is that the key point? 
#7




Re: Question 2
Quote:
Quote:
__________________
Where everyone thinks alike, no one thinks very much 
Thread Tools  
Display Modes  

