Empirical risk minimization

Short description: Principle in statistical learning theory

Machine learning and
data mining

Problems

* Classification
* Clustering
* Regression
* Anomaly detection
* 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
* t-SNE

Structured prediction

* Graphical models
* Bayes net
* Conditional random field
* Hidden Markov

Anomaly detection

* k-NN
* Local outlier factor

Artificial neural networks

* Autoencoder
* Deep learning
* DeepDream
* Multilayer perceptron
* RNN
* LSTM
* GRU
* Restricted Boltzmann machine
* GAN
* SOM
* Convolutional neural network
* U-Net

Reinforcement learning

* Q-learning
* SARSA
* Temporal difference (TD)

Theory

* Bias–variance dilemma
* Computational learning theory
* Empirical risk minimization
* Occam learning
* PAC learning
* Statistical learning
* VC theory

Machine-learning venues

* NeurIPS
* ICML
* ML
* JMLR
* ArXiv:cs.LG

Glossary of artificial intelligence

* Glossary of artificial intelligence

Related articles

* List of datasets for machine-learning research
* Outline of machine learning

* v
* t
* e

Empirical risk minimization is a principle in statistical learning theory which defines a family of learning algorithms based on evaluating performance over a known and fixed dataset. The core idea is based on an application of the law of large numbers; more specifically, we cannot know exactly how well a predictive algorithm will work in practice (i.e. the true "risk") because we don't know the true distribution of the data, but we can instead estimate and optimize the performance of the algorithm on a known set of training data. The performance over the known set of training data is referred to as the empirical risk.

## Contents

* 1 Background
* 2 Empirical risk minimization
* 3 Properties
* 3.1 Imposibility results
* 3.2 Computational complexity
* 4 Tilted empirical risk minimization
* 5 See also
* 6 References
* 7 Further reading

## Background

Consider the following situation, which is a general setting of many supervised learning problems. We have two spaces of objects X and Y and would like to learn a function  h:X->Y (often called hypothesis) which outputs an object y∈Y, given x∈X. To do so, we have at our disposal a training set of n examples  (x1,y1),…,(xn,yn) where xi∈X is an input and yi∈Y is the corresponding response that we wish to get from h(xi).

To put it more formally, we assume that there is a joint probability distribution P(x,y) over X and Y, and that the training set consists of n instances  (x1,y1),…,(xn,yn) drawn i.i.d. from 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 y is not a deterministic function of x, but rather a random variable with conditional distribution P(y|x) for a fixed x.

We also assume that we are given a non-negative real-valued loss function L(y^,y) which measures how different the prediction y^ of a hypothesis is from the true outcome y. For classification tasks these loss functions can be scoring rules. The risk associated with hypothesis h(x) is then defined as the expectation of the loss function:

R(h)=𝐄[L(h(x),y)]=∫L(h(x),y)dP(x,y).

A loss function commonly used in theory is the 0-1 loss function: L(y^,y)={1 if y^≠y0 if y^=y.

The ultimate goal of a learning algorithm is to find a hypothesis h* among a fixed class of functions ℋ for which the risk R(h) is minimal:

h*=argminh∈ℋ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 R(h) cannot be computed because the distribution P(x,y) is unknown to the learning algorithm (this situation is referred to as agnostic learning[citation needed]). However, given a sample of iid training data points, we can compute an estimate, called the empirical risk, by computing the average of the loss function over the training set; more formally, computing the expectation with respect to the empirical measure:

Remp(h)=1n∑i=1nL(h(xi),yi).

The empirical risk minimization principle[1] states that the learning algorithm should choose a hypothesis h^ which minimizes the empirical risk over the hypothesis class ℋ:

h^=argminh∈ℋRemp(h).

Thus, the learning algorithm defined by the empirical risk minimization principle consists in solving the above optimization problem.

## Properties

Guarantees for the performance of empirical risk minimization depend strongly on the function class selected as well as the distributional assumptions made.[2] In general, distribution-free methods are too coarse, and do not lead to practical bounds. However, they are still useful in deriving asymptotic properties of learning algorithms, such as consistency. In particular, distribution-free bounds on the performance of empirical risk minimization given a fixed function class can be derived using bounds on the VC complexity of the function class.

For simplicity, considering the case of binary classification tasks, it is possible to bound the probability of the selected classifier, ϕn being much worse than the best possible classifier ϕ*. Consider the risk L defined over the hypothesis class 𝒞 with growth function 𝒮(𝒞,n) given a dataset of size n. Then, for every ϵ>0:[3]

ℙ(L(ϕn)−L(ϕ*))≤𝟖S(𝒞,n)exp⁡{−nϵ2/32}

Similar results hold for regression tasks.[2] These results are often based on uniform laws of large numbers, which control the deviation of the empirical risk from the true risk, uniformly over the hypothesis class.[3]

### Imposibility results

It is also possible to show lower bounds on algorithm performance if no distributional assumptions are made.[4] This is sometimes referred to as the No free lunch theorem. Even though a specific learning algorithm may provide the asymptotically optimal performance for any distribution, the finite sample performance is always poor for at least one data distribution. This means that no classifier can provide on the error for a given sample size for all distributions.[3]

Specifically, Let ϵ>0 and consider a sample size n and classification rule ϕn, there exists a distribution of (X,Y) with risk L*=0 (meaning that perfect prediction is possible) such that:[3] 𝔼Ln≥1/2−ϵ.

It's further possible to show that the convergence rate of a learning algorithm is poor for some distributions. Specifically, given a sequence of decreasing positive numbers ai converging to zero, it is possible to find a distribution such that:

𝔼Ln≥ai

for all n. This result shows that universally good classification rules do not exist, in the sense that the rule must be low quality for at least one distribution.[3]

### 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 a relatively simple class of functions such as linear classifiers.[5] Nevertheless, it can be solved efficiently when the minimal empirical risk is zero, i.e., data is linearly separable.[citation needed]

In practice, machine learning algorithms cope with this issue 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 P(x,y) (and thus stop being agnostic learning algorithms to which the above result applies).

In the case of convexification, Zhang's lemma majors the excess risk of the original problem using the excess risk of the convexified problem.[6] Minimizing the later using convex optimization also allow to control the former.

## Tilted empirical risk minimization

Tilted empirical risk minimization is a machine learning technique used to modify standard loss functions like Squared Error by introducing a tilt parameter. This parameter dynamically adjusts the weight of data points during training, allowing the algorithm to focus on specific regions or characteristics of the data distribution. Tilted empirical risk minimization is particularly useful in scenarios with imbalanced data or when there is a need to emphasize errors in certain parts of the prediction space.

## See also

* Maximum likelihood estimation
* M-estimator

## References

1. ↑ V. Vapnik (1992). Principles of Risk Minimization for Learning Theory.
2. ↑ 2.0 2.1 Györfi, László; Kohler, Michael; Krzyzak, Adam; Walk, Harro (2010-12-01) (in en). A Distribution-Free Theory of Nonparametric Regression (Softcover reprint of the original 1st ed.). New York: Springer. ISBN 978-1-4419-2998-3. https://www.amazon.com/Distribution-Free-Nonparametric-Regression-Springer-Statistics/dp/1441929983.
3. ↑ 3.0 3.1 3.2 3.3 3.4 Devroye, L., Gyorfi, L. & Lugosi, G. A Probabilistic Theory of Pattern Recognition. Discrete Appl Math 73, 192–194 (1997)
4. ↑ Devroye, Luc; Györfi, László; Lugosi, Gábor (1996). "A Probabilistic Theory of Pattern Recognition" (in en). Stochastic Modelling and Applied Probability. doi:10.1007/978-1-4612-0711-5. ISSN 0172-4568. https://link.springer.com/book/10.1007/978-1-4612-0711-5.
5. ↑ V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). Agnostic Learning of Monomials by Halfspaces is Hard. (See the paper and references therein)
6. ↑ "Mathematics of Machine Learning Lecture 9 Notes | Mathematics of Machine Learning | Mathematics" (in en). https://ocw.mit.edu/courses/18-657-mathematics-of-machine-learning-fall-2015/resources/mit18_657f15_l9/.

## Further reading

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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Empirical risk minimization. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Empirical_risk_minimization&oldid=176231"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template