Hoeffding's Inequality I am studying the feasibility of learning  from the book Learning from Data. The author uses a bin analogy to discuss the feasibility of learning in a probabilistic sense. I have certain questions to ask. 

First, I will try to summarize what the author is trying to do: 
Consider a bin containing red and green marbles, possibly infinitely many. The proportion of the red and green marbles is such that if we pick a marble at random, the probability that it will be red is $\mu$. We assume that $\mu$ is unknown to us. We pick a random sample of $N$ independent marbles (with replacement). Let $X_i$ be the indicator for the $i$th marble in the sample to be red. That is, $X_i=1$ if $i$th marble in the sample is red, $X_i=0$ otherwise. Define $\nu:=\frac{1}{n}\sum_{i=1}^N X_i$. By Hoeffding's inequality, $$\mathbb{P}(|\nu-\mu|>\varepsilon)\le 2\mathrm{e}^{-2\varepsilon ^2N}$$
In a learning problem, there is an unknown target function $f:\mathcal{X}\to\mathcal{Y}$ to be learned. The learning algorithm picks a hypothesis $g:\mathcal{X}\to\mathcal{Y}$ from a hypothesis set $\mathcal{H}$. We can connect the bin problem to the learning problem as follows. 
Take a single hypotheis $h\in\mathcal{H}$ and compare it to $f$  on each point $\mathbf{x}\in\mathcal{X}$. If $h(\mathbf{x})=f(\mathbf{x})$, color the point $\mathbf{x}$ green, else color it red. The color each point gets is unknown to us, since $f$ is unknown. However, if we pick $\mathbf{x}$ at random according to some probability distribution $P$ over $\mathcal{X}$, we know that $\mathbf{x}$ wil be red with some probability $\mu$. Regardless of the value of $\mu$, the space $\mathcal{X}$ bow behaves like a bin. The training examples play the role of a sample from a bin. If the inputs $\mathbf{x_1},\ldots,\mathbf{x_N}$ in the data set $\mathcal{D}$ are picked independently according to $P$, we will get a random sample of red and green points. Each point will be red with probability $\mu$. The color of points $\mathbf{x_1},\ldots,\mathbf{x_N}$ will be known to us since we know $f$ on the data set $\mathcal{D}$. We define $E_{in}(h)$ to be the fraction of $\mathcal{D}$ where $f$ and $h$ disagree, also called in-sample error, and similarly out-of-sample error $E_{out}$. Thus $$E_{in}(h)=\dfrac{1}{N}\sum_{i=1}^N[[h(\mathbf{x_i})\neq f(\mathbf{x_i})]], E_{out}=\mathbb{P}(h(\mathbf{x})\neq f(\mathbf{x})) $$
Using the Hoeffding's inequality, we have $$\mathbb{P}(|E_{in}(h)-E_{out}(h)|>\varepsilon)\le 2\mathrm{e}^{-2\varepsilon^2 N}\qquad\qquad(1)$$
Let us consider a finite hypothesis set $\mathcal{H}=\{h_1,\ldots,h_M\}$ instead of just one hypothesis $h$. We can construct a bin equivalent in this case by having $M$ bins. Each bin still represents the input space $\mathcal{X}$ with the red marbles in the $i$th bin corresponding to the points $\mathbf{x}\in\mathcal{X}$ where $h_i(\mathbf{x})\neq f(\mathbf{x})$. The probability of red marbles in the $i$th bin is $E_{out}(h_i)$ and the fraction of red marbles in the $i$th sample is $E_{in}(h_i)$ for $i=1,2,\ldots,M$. Hoeffding's inequality applies to each bin separately.
The Hoeffding's inequality $(1)$ assumes that the hypothesis $h$ is fixed before you generate the data set, and the probability is with respect to random data sets $\mathcal{D}$. The learning algorithm picks a final hypothesis $g$ based on $\mathcal{D}$. That is, after generating the data set. Thus we cannot plug in $g$ for $h$ in the Hoeffding's inequality. A way to get around this is to try to bound $\mathbb{P}(|E_{in}(h)-E_{out}(h)|>\varepsilon)$ in a way that does not depend on which $g$ the learning algorithm picks. 
$$\left(|E_{in}(g)-E_{out}(g)|>\varepsilon\right)\subseteq\bigcup_{i=1}^M (|E_{in}(h_i)-E_{out}(h_i)|>\varepsilon)$$
and hence, 
$$\mathbb{P}\left(|E_{in}(g)-E_{out}(g)|>\varepsilon\right)\le\sum_{i=1}^M\mathbb{P}\left(|E_{in}(h_i)-E_{out}(h_i)|>\varepsilon\right)$$.
Applying Hoeffding's inequality to $M$ terms one at a time, we get $$\mathbb{P}\left(|E_{in}(g)-E_{out}(g)|>\varepsilon\right)\le 2M\mathrm{e}^{-2\varepsilon ^2N} $$

I have the following questions.


*

*Why does Hoeffding's inequality requires that $h$ is fixed before generating the data set $\mathcal{D}$? Is it because $X_i$s, the indicator of $i$th point in $\mathcal{D}$ being red, are no longer independent after generating the data set, which is an assumption required for Hoeffding's inequality? For instance, after generating $\mathcal{D}$, knowing $X_i$ for some $1\le i\le N$ would give information for other $X_j$. Is this correct?

*In the last step,for each term in the summation $\sum_{i=1}^M\mathbb{P}\left(|E_{in}(h_i)-E_{out}(h_i)|>\varepsilon\right)$, author states that Hoeffding's inequality applies to each bin separately and $\mathbb{P}\left(|E_{in}(h_i)-E_{out}(h_i)|>\varepsilon\right)\le 2\mathrm{e}^{-2\varepsilon ^2N}$ for all $1\le i\le M$. How is this possible? According to the previous question, the hypothesis $h$ must be fixed before generating the data set, but in this case we have a single data set $\mathcal{D}$ and we are later considering the hypothesis $h_1,h_2,\ldots,h_M$. How is the application of Hoeffding's inequality to each term in summation justified since the data set  is generated before hand i.e., before choosing a hypothesis? 

*If we could apply Hoeffding's to each term in the summation separately, why don't we say that $g$ is one of the hypothesis $h_1,h_2,\ldots,h_M$ and hence $\mathbb{P}\left(|E_{in}(g)-E_{out}(g)|>\varepsilon\right)\le 2\mathrm{e}^{-2\varepsilon ^2N}$?

*Is the probability distribution $P$ on $\mathcal{X}$ independent of the hypothesis $h$, i.e., is $P$ chosen without bothering about the color of points in $\mathcal{X}$, which in turn is dictated by $h$?
 A: I hope this answer can help:


*

*Why does Hoeffding's inequality requires that h is fixed before generating the data set... Is this correct ?

*How is the application of Hoeffding's inequality to each term in summation justified?
I would suggest you think of it like this.  You have M models, all trained on the same training data.  You also have a validation data set, with N samples, and now you want to select the best model by using accuracy on the validation set.  Hoeffding's inequality bounds the probability that the accuracy is indicative of real world performance.


*

*If we could apply Hoeffding's to each term in the summation separately, why don't we say that g is one of the hypothesis h1, h2, ⋯, hm and hence ℙ(|Ein(g)−Eout(g)| > ε) ≤ 2e−2ε2N?


Because you don't know which one it is, it could be any of them, hence "or", hence sum.  If you see the inequality as a very crude and naive upper bound, it will help.  Look at it almost tautologically.


*

*Is the probability distribution P on X independent of the hypothesis h?


P is the probability of the statement that |E_in(h) - E_out(h)| > ε.  If my hypothesis is that a coin is 60% vs 40% heads vs tails, then what is the probability that the estimate from 100 coin flips is more that 2% inaccurate.  It is over the same validation data set.  E_in and E_out are binomial distributions.  
