Empirical Risk Minimization: From Intuition to a Proof of Generalization for Finite Hypothesis Classes
Let’s take a quick dive into the statistical learning framework behind machine learning to understand where the need for ERM naturally arises.
Statistical Learning Theory — Framework For Machine Learning
Before we get started, let’s take a look at the analogy we'll use throughout the article. As a lover of oranges, trying to get a bunch of sweet oranges at the market. Based on your previous experience, you attribute the sweetness of the oranges to their color and softness — the red, very soft ones tend to be the sweetest. To verify our prediction rule, we get a lot of oranges, ranging in color and softness, and then taste each of them to determine whether they are sweet or not. Therefore, we’ve just learned how to predict sweet oranges. The same learning algorithm applies to machines trying to learn how to predict sweet oranges, and can be referred to as Supervised Learning. Our first step is to describe a formal model aimed at capturing such learning tasks — The Statistical Learning Framework.
- The learner’s Input: In statistics, learners have access to the following
- Domain set: An arbitrary set of objects we need to label, usually denoted as X. Regarding our analogy above, our X can be a finite set of oranges. Domain sets are usually represented by a vector of features or properties — color and softness of the oranges, in our case of learning.
- Label set (Y): Label set Y represents the set of possible outputs that can be assigned to an element in domain X. Y can be continuous in case of regression learning problems or be a discrete set of K unordered classes. Subsequently, the label set Y for our scenario comprises the labels sweet and bitter. Therefore, we let Y be {0, 1}, where 0 represents bitter oranges and 1 represents sweet ones.
- Sample Set (Training data): Sample set, usually referred to as a training data, is a collection of n examples drawn independently and identically distributed (i.i.d.) according to an unknown probability distribution, P over X x Y, such that
But in theoretical analysis, we study the behavior of learning algorithms as
In the case of the asymptotic approach.
2. The learner’s Output: The main goal of the learner is to output a prediction function, h, such that h: X — > Y. This function is called a predictor, a classifier, or a hypothesis. In other words, a function that takes in an input and predicts a corresponding label. In our oranges example, our predictor takes a set of oranges as input and classifies them as sweet or bitter
Measure of Success
In supervised learning, we assume that there exists an unknown target function, f:x -> y, that assigns the correct label to every input x ∈ X. Consequently, the performance of a predictor h is measured with respect to the unknown correct labeling function, f, and unknown probability distribution P, from which the data are generated at random. To determine how good a predictor h is, its performance is evaluated by the expected loss between h(x) and the true label given by f(x), where the expectation is taken with respect to the data-generating distribution P. This quantity is called the true error, generalization error, or population risk. These three terms — true error, generalization error, and population risk — are used interchangeably.
The true error is defined as
Given two predictors, h(x) and g(x), how do we decide which is better?
To answer this, we introduce a loss function
which measures the discrepancy between a prediction h(x) and the true label y. Using the loss function, the quality of a predictor is evaluated by its expected loss under the data-generating distribution P. Therefore, the loss function measures the error of a single prediction and true error ( generalization error or population risk), as its name suggests, measures the average loss of a predictor over the data-generating distribution P.
Examples of Loss Functions
- 0–1 loss: In case of classification problems (y is a discrete set of k unordered classes), 0 if the prediction is equal to the true label and 1 if otherwise
2. Squared loss: Squared loss is used in cases where the label set Y is a set of real numbers (y ∈ R). Such as regression problems, where y is continuous.
Using a loss function, we define the population risk (true risk) of a predictor h as
In other words, the expected value (mean) of the loss under the distribution P. With these definitions, we are able to formalize the problem of supervised learning. Precisely, seeking a predictor h from a set of predictors H, that minimizes the population risk such that L(h) is ideally close to 0. For some small ϵ>0, we may require a predictor such that L(h)≤ ϵ
Now, the question is: how do we compute our population risk, since our probability distribution P is unknown and our correct labeling function f is also unknown? The learner does not know P, because it represents the unseen data distribution, nor f(x), the true labeling function. Hence, the need for Empirical Risk Minimization arises.
Empirical Risk Minimization
We now have the setup needed to introduce ERM. As mentioned earlier, the goal of supervised learning is to minimize the generalization risk (population risk). In practice, however, the learner only has access to the training data — a finite sample drawn from the data-generating distribution P. Think of it this way: the learner only has a few oranges compared to all the oranges in the world. Naturally, we can’t minimize the population risk when we don’t have access to the full distribution of oranges. This is exactly where Empirical Risk Minimization (ERM) comes in. Since we can’t minimize the risk on the unknown distribution P, we instead minimize the risk on the training data (sample set) S. This risk is known as the empirical risk (or empirical error), and we minimize it using a learning paradigm called Empirical Risk Minimization (ERM).
Get Abdulqoyyum Aileru’s stories in your inbox
Join Medium for free to get updates from this writer.
Mathematically, the empirical risk is simply the average loss on the training data. If our training set is
Then the empirical risk of a predictor h is given by:
Therefore, ERM is simply choosing the predictor h that minimizes this empirical risk
Although the ERM principle appears intuitive, it can fail dramatically when applied without care. To see why, let us return to our example of predicting whether an orange is sweet. Suppose that after applying ERM, we obtain a predictor g such that Ls(g)=0. At first glance, this suggests that we have found a perfect predictor. However, when this predictor is evaluated on an unseen dataset K drawn from the same distribution P, it often performs poorly. In many cases, the resulting risk is large, with Lk(g)>ϵ. In other words, a predictor that perfectly classifies all the oranges in the training set can fail miserably when faced with a new, unseen set of oranges. This is referred to as overfitting, where a model fits the training data too closely but fails to generalize.
Empirical Risk Minimization with Inductive Bias
Since ERM can lead to overfitting, rather than abandoning the paradigm, we seek ways to mitigate this issue. Specifically, we look for conditions under which ERM is guaranteed not to overfit — that is, conditions under which the ERM predictor performs well on the training data and is also likely to perform well on unseen data drawn from the same distribution. A common way to achieve this is by restricting the search space of the predictor. Formally, a learner chooses its set of predictors before seeing the data. This set of predictors, denoted by H, is known as the hypothesis class. In the context of our orange taste prediction problem, the learner considers different hypotheses for predicting whether an orange is sweet or bitter before assessing the oranges; hence, this is based on prior knowledge. Each hypothesis represents a possible rule for making this prediction, and the collection of all such rules forms the hypothesis class. By restricting the hypothesis class — thereby limiting its complexity — we reduce the search space for a good predictor h∈H. This restriction plays a crucial role in preventing overfitting and improving generalization to unseen data.
Finite Hypothesis Classes
A simple form of restriction is to impose an upper bound on the size of H, requiring it to contain only finitely many hypotheses. Under this assumption, we will show that ERM_H does not overfit, provided that the training sample is sufficiently large. To make this precise, we need two further assumptions.
The realizability assumption: There exists some h* ∈ H such that L_(P,f)(h*) = 0. That is, there exists a predictor in our hypothesis class that achieves zero true error — it predicts the correct label on every input. A direct consequence is that L_S(h*) = 0 as well, since h* makes no errors anywhere. This is a strong assumption that will be relaxed later, as it is rarely satisfied in real-world cases.
The i.i.d. assumption: As introduced earlier, our training set S is drawn independently and identically distributed from P, written S ~ P^n, where n is the size of S. This ensures that the empirical risk is a meaningful estimate of the true risk.
PROOF: We call a training sample misleading if it causes ERM_H to fail — that is, if L_(P,f)(h_S) > ϵ. For sufficiently large n, the probability of drawing a misleading sample is at most δ.
Therefore, given a confidence parameter δ, an accuracy parameter ϵ, and a sample size n satisfying the bound above, the predictor returned by ERM_H has true risk at most ϵ with probability at least 1 − δ. This proves that a finite hypothesis class does not overfit, given enough data. Notably, the required sample size grows only logarithmically in the number of predictors in the hypothesis class. So, even a very large (but finite) H can be learned with a modest number of examples.
This is where I’ll leave things for now. Writing this out helped me understand ERM far better than just reading it ever did, and I hope it did the same for you. There’s much more to come — both the theory that underpins machine learning and the applied side where it all gets put to work. Until the next one.
