ERM Learning

ERM stands for Empirical Risk Minimization

Empirical Risk Minimization

A learning algorithm receives as input a training set $S$, sampled from an unknown distribution $\mathcal{D}$ and labeled by some target function $f$, and should output a predictor $h_S:\mathcal{X}\to \mathcal{Y}$ (where the subscript indicates the fact that the output predictor depends on $S$).

The goal of the algorithm is to find $h_S$ that minimizes the error with respect to the unknown $\mathcal{D}$ and $f$. Since the learner does not know what $\mathcal{D}$ and $f$ are, the true error is not directly available to the learner. Instead, we could calculate the training error over the training sample:

$$L_S(h):=\frac{\left|\{i\in [m]:h(x_i)\ne y_i\}\right|}{m}$$

where $[m]=\left\{1,\dots ,m\right\}$

The term empirical error and empirical risk are often used interchangeably for this error. And this learning paradigm coming up with a predictor $h$ that minimizes $L_S(h)$ is called Empirical Risk Minimization or ERM for short.

Empirical Risk Minimization with Inductive Bias

However, learning to fit the training sample may lead to overfitting. A common solution to avoid this issue is to apply the ERM learning rule over a restricted search space. Formally, the learner should choose in advance (before seeing the data) a set of predictors. This set is called a hypothesis class and is denoted by $\mathcal{H}$. Each $h\in \mathcal{H}$ is a function mapping from $\mathcal{X}$ to $\mathcal{Y}$. For a given class $\mathcal{H}$, and a training sample $S$, the ${\text{ERM}}_{\mathcal{H}}$ learner uses the ERM rule to choose a predictor $h\in \mathcal{H}$ with the lowest possible error. Formally,

$${\mathrm{ERM}}_{\mathcal{H}}(S)\in \underset{h\in \mathcal{H}}{\mathrm{argmin}}{L}_S(h)$$

where $\mathrm{argmin}$ stands for the set of hypotheses in $\mathcal{H}$ that achieve the minimum value of $L_S(h)$ over $\mathcal{H}$ (namely the argument that achieve the minimum value). By restricting the learner to choosing a predictor from $\mathcal{H}$, we bias it toward a particular set of predictors. Such restrictions are often call an inductive bias. Sine the choice of such a restriction is determined before the learner sees the training data, it should ideally be based on some prior knowledge about the problem to be learned.

Finite Hypothesis Classes

The simplest type of restriction on a class is imposing an upper bound on its size (that is, the number of predictors $h$ in $\mathcal{H}$). In this section, we show that if $\mathcal{H}$ is a finite class then ${\mathrm{ERM}}_{\mathcal{H}}$ will not overfit on a sufficiently large training sample.

Let us now analyze the performance of the ${\mathrm{ERM}}_{\mathcal{H}}$ learning rule assuming that $\mathcal{H}$ is a finite class.

For a training sample, $S$, labeled according to some $f:\mathcal{X}\to \mathcal{Y}$, let $h_S$ denote a result of applying ${\mathrm{ERM}}_{\mathcal{H}}$ to S, namely,

$$h_S\in \underset{h\in \mathcal{H}}{\mathrm{argmin}}{L}_S(h)$$

And we make this Realizability Assumption

Realizability Assumption

There exists $h^{\ast }\in \mathcal{H}\text{ s.t. }{L}_{(D,f)}(h^{\ast })=0$, where $L_{(D,f)}(h^{\ast })$ is the true risk of $h^{\ast }$ This assumption implies that with probability $1$ over random samples, S, where the instances of $S$ are sampled according to $\mathcal{D}$ and labeled by $f$, we have $L_S(h^{\ast })=0$ Clearly, any guarantee on the error with respect to the underlying distribution, $\mathcal{D}$, for an algorithm that has access only to s sample $S$ should depend on the relationship between $\mathcal{D}$ and $S$. The common assumption in statistical machine learning is that the training sample $S$ is generated by sampling points from the distribution $\mathcal{D}$ independently of each other. Formally, we make The i.i.d. Assumption

i.i.d. Assumption

The examples in the training set are independently and identically distributed (i.i.d.) according to the distribution $\mathcal{D}$. That is, every $x_i$ in $S$ is freshly sampled according to the distribution $\mathcal{D}$ and then labeled according to the labeling function, $f$. We denote this assumption by $S\sim {\mathcal{D}}^m$ where $m$ is the size of $S$, and ${\mathcal{D}}^m$ denotes the probability over $m$-tuples induced by applying $\mathcal{D}$ to pick each element of the tuple independently of the other members of the tuple.

Since $L_{(\mathcal{D},f)}(h_S)$ depends on the training set, $S$, and that training set is picked by a random process, there is randomness in the choice of the predictor $h_S$ and, consequently, in the risk $L_{(\mathcal{D},f)}(h_S)$. Formally, we say that it is a random variable. Since we cannot guarantee perfect label prediction, we introduce another parameter for the quality of prediction, the accuracy parameter, commonly denoted by $ϵ$. We interpret the event $L_{(\mathcal{D},f)}(h_S)>ϵ$ as a failure of the learner, while if $L_{(\mathcal{D},f)}(h_S)\le ϵ$ we view the output of the algorithm as an approximately correct predictor. Therefore we are interested in upper bounding the probability to sample $m$-tuple of instances that will lead to failure of the learner. Formally, let $S{|}_x=(x_1,\cdots ,x_m)$ be the instances of the training set. We would like to upper bound

$${\mathcal{D}}^m(\{S{|}_x:L_{(\mathcal{D},f)}(h_S)>ϵ\})$$

Let ${\mathcal{H}}_B$ be the set of "bad" hypotheses, that is,

$${\mathcal{H}}_B=\{h\in \mathcal{H}:L_{(\mathcal{D},f)}(h)>ϵ\}$$

In addition, let

$$M=\{S{|}_x:\exists h\in {\mathcal{H}}_B,L_S(h)=0\}$$

be the set of misleading samples: Namely, for every $S{|}_x\in M$, there is a "bad" hypothesis, $h\in {\mathcal{H}}_B$, that looks like a "good" hypothesis on $S{|}_x$. Now, recall that we would like to bound the probability of the event $L_{(\mathcal{D},f)}(h_S)>ϵ$. But, since the realizability assumption implies that $L_S(h_S)=0$, it follows that the event $L_{(\mathcal{D},f)}(h_S)>ϵ$ can only happen if for some $h\in {\mathcal{H}}_B$ we have $L_S(h)=0$. In other words, this event will only happen if our sample is in the set of misleading samples, $M$. Formally, we have shown that

$$\{S{|}_x:L_{\mathcal{D},f}(h_S)>ϵ\}\subseteq M$$

Note that we can rewrite $M$ as

$$M=\bigcup _{h\in {\mathcal{H}}_B}\{S{|}_x:L_S(h)=0\}$$

Hence,