I'm referring to Section 3.5, ex. 2 in Understanding machine learning.

To my understanding, given $\varepsilon, \delta$, I need to find minimum sample size $n$ s.t. $$P[e_P(ERM(S_n) > \varepsilon] < \delta$$ Where $S_n$ is a sample of size $n$. and $ERM$ is an algorithm that given the sample return an hypothesis with minimum empirical error.

I tried to count the number of hypotheses that are "bad", in a way that their true error is more then $\varepsilon$, and to show that the the probability that the $ERM$ algorithm will choose one of those is less than $\delta$, but that wasn't successful.

I also tried doing the opposite - count all possible hypotheses that the $ERM$ algorithm can output and show that the probability that any of them has true error which is larger then $\varepsilon$ is less then $\delta$. That wasn't successful either.

Is there a way proving it without using VC-dimension-arguments?


For completeness, the complete question is:

Let $X$ be a discrete domain, and let $\mathcal{H}_{Singleton} = \{h_z : z \in X\} \cup \{h_−\}$, where for each $z \in X$, $h_z$ is the function defined by $h_z(x) = 1$ iff $x = z$ and $0$ otherwise.
$h_−$ is simply the all-negative hypothesis, namely, for all $x \in X, h_−(x) = 0$.

The realizability assumption here implies that the true hypothesis $f$ labels negatively all examples in the domain, perhaps except one.

  1. Describe an algorithm that implements the ERM rule for learning $\mathcal{H}_{Singleton}$ in the realizable setup.
  2. Show that $\mathcal{H}_{Singleton}$ is PAC learnable. Provide an upper bound on the sample complexity.

I will first describe a learning algorithm for $\mathcal{H}_{Singleton}$, and then show that this learning algorithm outputs a hypothesis that satisfies the requirements of PAC learning.

Assume an arbitrary distribution $D$ over $X$.
Given the training set $S$ consisting of $m$ samples independently sampled from $D$ and labelled by the true hypothesis $f$, ie, $S = \{(x_1, f(x_1)) \ldots (x_m, f(x_m))\}$, our learning algorithm is:
1. Suppose $y_i = 1$ for some $(x_i, y_i) \in S$. Note that this can happen for exactly one $i$, if it does, because of the realizability condition. Then, output $h_{x_i}$.
2. Otherwise, all $y_i = 0$. Then, output $h_-$.

Note that in both cases, if the output hypothesis is $h_S$, the loss over the training set for this hypothesis, $L_S(h_S)$, is $0$ always. Thus, this is an ERM rule, because $0$ is the lowest possible loss.

This concludes part 1. We will now analyse the error of this learning algorithm.
For $S = \{(x_1, f(x_1)) \ldots (x_m, f(x_m))\}$, define $S_x = \{ x_1, x_2, \ldots x_m \},$ the list of unlabelled samples obtained from $X$ through sampling from $D$ exactly $m$ times. Note that $S_x$ completely determines $S$.

We wish to bound the probability of a bad sample (parametrised by the accuracy $\epsilon$) by the confidence parameter $\delta$. More precisely, given some $\epsilon, \delta$ in $(0, 1)$, we want to show that there is an $m$, such that when our learning algorithm is trained on $m$ samples, we have, $$ P(\{S_x|L_{(D, f)}(h_S) > \epsilon\}) < \delta $$ Note that $m$ will be a function of $\epsilon$ and $\delta$. $P$ above is the probability measure given by the distribution $D^m$ over $X^m.$
The true error $L_{(D, f)}$ is defined as, $$ L_{(D, f)}(h) = P(\{h(x) \neq f(x)\}) $$ Now, suppose the true hypothesis (or, the actual labelling function) $f$ is $h_-$. Then, our learning algorithm outputs $h_-$ as well. The true error of the error hypothesis will be $0$, and hence, will be greater than any $\epsilon > 0$ with probability $0$, which is less than $\delta$. In this case, our learning algorithm outputs a suitable hypothesis.

Otherwise, the true hypothesis $f$ is $h_{x_0}$ for some $x_0$ in $X$. Here, we have two cases:
1. $x_0 \in S_x$ : Our learning algorithm will output $h_{x_0}$ here, and hence, will have zero true error as $f = h_{x_0}$.
2. $x_0 \not\in S_x$ : This is the only case where we can have a non-zero true error, because our algorithm will output $h_-$. Thus, $$ P(\{S_x|L_{(D, f)}(h_S) > \epsilon\}) \leq P(\{x_0 \not\in S_x\}) $$ Note that, as the samples in $S$ are identically and independently sampled from $D$, the probability that $x_0 \not \in S_x$ is the same as the probability that we never sample $x_0$ in $m$ independent trials from the distribution $D$, which is $(1 - P(\{x_0\}))^m$. Note that, $f$ and $h_-$ differ only at one point, $x_0$. Thus, $$ \epsilon < L_{(D, f)}(h_-) = P(\{h_-(x) \neq f(x)\}) = P(\{x_0\}) $$ It follows that, $$ P(\{x_0 \not\in S_x\}) = (1 - P(\{x_0\}))^m < (1 - \epsilon)^m .$$ Thus, if we have, $(1 - \epsilon)^m \leq \delta$, we are done. This is equivalent to, $$ m \geq \left\lceil{\frac{\ln(\frac{1}{\delta})}{\ln(1 - \epsilon)}}\right\rceil $$ and, the righthand-side is an upper bound on the sample complexity of the hypothesis class $\mathcal{H}_{Singleton}$ by definition of the sample complexity.
This shows that the output hypothesis satisfies the PAC learning requirements, given a sufficiently large but finite $m$. Thus, $\mathcal{H}_{Singleton}$ is PAC-learnable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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