Empirical risk minimization
|Machine learning and|
Consider the following situation, which is a general setting of many supervised learning problems. We have two spaces of objects and and would like to learn a function (often called hypothesis) which outputs an object , given . To do so, we have at our disposal a training set of m examples where is an input and is the corresponding response that we wish to get from .
To put it more formally, we assume that there is a joint probability distribution over and , and that the training set consists of instances drawn i.i.d. from . Note that the assumption of a joint probability distribution allows us to model uncertainty in predictions (e.g. from noise in data) because is not a deterministic function of , but rather a random variable with conditional distribution for a fixed .
We also assume that we are given a non-negative real-valued loss function which measures how different the prediction of a hypothesis is from the true outcome The risk associated with hypothesis is then defined as the expectation of the loss function:
The ultimate goal of a learning algorithm is to find a hypothesis among a fixed class of functions for which the risk is minimal:
Empirical risk minimization
In general, the risk cannot be computed because the distribution is unknown to the learning algorithm (this situation is referred to as agnostic learning). However, we can compute an approximation, called empirical risk, by averaging the loss function on the training set:
The empirical risk minimization principle states that the learning algorithm should choose a hypothesis which minimizes the empirical risk:
Thus the learning algorithm defined by the ERM principle consists in solving the above optimization problem.
This section needs expansion. You can help by adding to it. (February 2010)
Empirical risk minimization for a classification problem with a 0-1 loss function is known to be an NP-hard problem even for such a relatively simple class of functions as linear classifiers. Though, it can be solved efficiently when the minimal empirical risk is zero, i.e. data is linearly separable.
In practice, machine learning algorithms cope with that either by employing a convex approximation to the 0-1 loss function (like hinge loss for SVM), which is easier to optimize, or by imposing assumptions on the distribution (and thus stop being agnostic learning algorithms to which the above result applies).
- V. Vapnik (1992). [http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf Principles of Risk Minimization for Learning Theory.]
- V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). Agnostic Learning of Monomials by Halfspaces is Hard. (See the paper and references therein)