Empirical risk minimization

Part of a series on
Machine learning and data mining
Problems Classification Clustering Regression Anomaly detection Data Cleaning AutoML Association rules Reinforcement learning Structured prediction Feature engineering Feature learning Online learning Semi-supervised learning Unsupervised learning Learning to rank Grammar induction
Supervised learning (classification • regression) Decision trees Ensembles Bagging Boosting Random forest k-NN Linear regression Naive Bayes Artificial neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH CURE Hierarchical k-means Expectation–maximization (EM) DBSCAN OPTICS Mean shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA PGD t-SNE
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection k-NN Local outlier factor
Artificial neural network Autoencoder Cognitive computing Deep learning DeepDream Multilayer perceptron RNN LSTM GRU ESN Restricted Boltzmann machine GAN SOM Convolutional neural network U-Net Transformer Vision Spiking neural network Memtransistor Electrochemical RAM (ECRAM)
Reinforcement learning Q-learning SARSA Temporal difference (TD)
Theory Kernel machines Bias–variance tradeoff Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine-learning venues NeurIPS ICML ML JMLR ArXiv:cs.LG
Related articles Glossary of artificial intelligence List of datasets for machine-learning research Outline of machine learning
v t

Empirical risk minimization (ERM) is a principle in statistical learning theory which defines a family of learning algorithms and is used to give theoretical bounds on their performance. The core idea is that we cannot know exactly how well an algorithm will work in practice (the true "risk") because we don't know the true distribution of data that the algorithm will work on, but we can instead measure its performance on a known set of training data (the "empirical" risk).

Background[]

Consider the following situation, which is a general setting of many supervised learning problems. We have two spaces of objects ${\displaystyle X}$ and ${\displaystyle Y}$ and would like to learn a function ${\displaystyle \ h:X\to Y}$ (often called hypothesis) which outputs an object ${\displaystyle y\in Y}$, given ${\displaystyle x\in X}$. To do so, we have at our disposal a training set of ${\displaystyle n}$ examples ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ where ${\displaystyle x_{i}\in X}$ is an input and ${\displaystyle y_{i}\in Y}$ is the corresponding response that we wish to get from ${\displaystyle \ h(x_{i})}$.

To put it more formally, we assume that there is a joint probability distribution ${\displaystyle P(x,y)}$ over ${\displaystyle X}$ and ${\displaystyle Y}$, and that the training set consists of ${\displaystyle n}$ instances ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ drawn i.i.d. from ${\displaystyle P(x,y)}$. Note that the assumption of a joint probability distribution allows us to model uncertainty in predictions (e.g. from noise in data) because ${\displaystyle y}$ is not a deterministic function of ${\displaystyle x}$, but rather a random variable with conditional distribution ${\displaystyle P(y|x)}$ for a fixed ${\displaystyle x}$.

We also assume that we are given a non-negative real-valued loss function ${\displaystyle L({\hat {y}},y)}$ which measures how different the prediction ${\displaystyle {\hat {y}}}$ of a hypothesis is from the true outcome ${\displaystyle y.}$ The risk associated with hypothesis ${\displaystyle h(x)}$ is then defined as the expectation of the loss function:

${\displaystyle R(h)=\mathbf {E} [L(h(x),y)]=\int L(h(x),y)\,dP(x,y).}$

A loss function commonly used in theory is the 0-1 loss function: ${\displaystyle L({\hat {y}},y)={\begin{cases}1&{\mbox{ if }}\quad {\hat {y}}\neq y\\0&{\mbox{ if }}\quad {\hat {y}}=y\end{cases}}}$.

The ultimate goal of a learning algorithm is to find a hypothesis ${\displaystyle h^{*}}$ among a fixed class of functions ${\displaystyle {\mathcal {H}}}$ for which the risk ${\displaystyle R(h)}$ is minimal:

${\displaystyle h^{*}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,{R(h)}.}$

For classification problems, the Bayes classifier is defined to be the classifier minimizing the risk defined with the 0-1 loss function.

Empirical risk minimization[]

In general, the risk ${\displaystyle R(h)}$ cannot be computed because the distribution ${\displaystyle P(x,y)}$ is unknown to the learning algorithm (this situation is referred to as ). However, we can compute an approximation, called empirical risk, by averaging the loss function on the training set:

${\displaystyle \!R_{\text{emp}}(h)={\frac {1}{n}}\sum _{i=1}^{n}L(h(x_{i}),y_{i}).}$

The empirical risk minimization principle^[1] states that the learning algorithm should choose a hypothesis ${\displaystyle {\hat {h}}}$ which minimizes the empirical risk:

${\displaystyle {\hat {h}}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,R_{\text{emp}}(h).}$

Thus the learning algorithm defined by the ERM principle consists in solving the above optimization problem.

Properties[]

This section needs expansion. You can help by . (February 2010)

Computational complexity[]

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.^[2] 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 ${\displaystyle P(x,y)}$ (and thus stop being agnostic learning algorithms to which the above result applies).

See also[]

• Maximum likelihood estimation
• M-estimator

References[]

Further reading[]

• Vapnik, V. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. ISBN 978-0-387-98780-4.