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.

  1. 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?
  2. 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?
  3. 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}$?

  4. 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$?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.