Stability (learning theory)
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Stability, also known as algorithmic stability, is a notion in computational learning theory of how a machine learning algorithm output is changed with small perturbations to its inputs. A stable learning algorithm is one for which the prediction does not change much when the training data is modified slightly. For instance, consider a machine learning algorithm that is being trained to recognize handwritten letters of the alphabet, using 1000 examples of handwritten letters and their labels ("A" to "Z") as a training set.
One way to modify this training set is to leave out an example, so that only 999 examples of handwritten letters and their labels are available. A stable learning algorithm would produce a similar classifier with both the 1000-element and 999-element training sets. Stability can be studied for many types of learning problems, from language learning to inverse problems in physics and engineering, as it is a property of the learning process rather than the type of information being learned.
The study of stability gained importance in computational learning theory in the 2000s when it was shown to have a connection with generalization. It was shown that for large classes of learning algorithms, notably empirical risk minimization algorithms, certain types of stability ensure good generalization.
Stability, also known as algorithmic stability, is a notion in computational learning theory of how a machine learning algorithm output is changed with small perturbations to its inputs. A stable learning algorithm is one for which the prediction does not change much when the training data is modified slightly. For instance, consider a machine learning algorithm that is being trained to recognize handwritten letters of the alphabet, using 1000 examples of handwritten letters and their labels ("A" to "Z") as a training set.
One way to modify this training set is to leave out an example, so that only 999 examples of handwritten letters and their labels are available. A stable learning algorithm would produce a similar classifier with both the 1000-element and 999-element training sets. Stability can be studied for many types of learning problems, from language learning to inverse problems in physics and engineering, as it is a property of the learning process rather than the type of information being learned.
The study of stability gained importance in computational learning theory in the 2000s when it was shown to have a connection with generalization. It was shown that for large classes of learning algorithms, notably empirical risk minimization algorithms, certain types of stability ensure good generalization. S = \{z_1 = (x_1,\ y_1)\ ,..,\ z_m = (x_m,\ y_m)\} and is of size m in Z = X \times Y drawn i.i.d. from an unknown distribution D.
Thus, the learning map L is defined as a mapping from Z_m into H , mapping a training set S onto a function f_S from X to Y . Here, we consider only deterministic algorithms where L is symmetric with respect to S , i.e. it does not depend on the order of the elements in the training set. Furthermore, we assume that all functions are measurable and all sets are countable. The loss V of a hypothesis f with respect to an example z = (x,y) is then defined as V(f,z) = V(f(x),y) . The empirical error of f is I_S[f] = \frac{1}{n}\sum V(f,z_i) .
The true error of f is I[f] = \mathbb{E}_z V(f,z) Given a training set S of size m, we will build, for all i = 1....,m, modified training sets as follows: By removing the i-th element S^{|i} = \{z_1 ,...,\ z_{i-1},\ z_{i+1},...,\ z_m\} By replacing the i-th element S^i = \{z_1 ,...,\ z_{i-1},\ z_i',\ z_{i+1},...,\ z_m\}
Hypothesis Stability
An algorithm L has hypothesis stability β with respect to the loss function V if the following holds: \forall i\in \{1,...,m\}, \mathbb{E}_{S,z} [|V(f_S,z)-V(f_{S^{|i}},z)|]\leq\beta.
Point-wise Hypothesis Stability
An algorithm L has point-wise hypothesis stability β with respect to the loss function V if the following holds: \forall i\in\ \{1,...,m\}, \mathbb{E}_{S} [|V(f_S,z_i)-V(f_{S^{|i}},z_i)|]\leq\beta.
Error Stability
An algorithm L has error stability β with respect to the loss function V if the following holds: \forall S\in Z^m, \forall i\in\{1,...,m\}, |\mathbb{E}_z[V(f_S,z)]-\mathbb{E}_z[V(f_{S^{|i}},z)]|\leq\beta
Uniform Stability
An algorithm L has uniform stability β with respect to the loss function V if the following holds: \forall S\in Z^m, \forall i\in\{1,...,m\}, \sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta A probabilistic version of uniform stability β is: \forall S\in Z^m, \forall i\in\{1,...,m\}, \mathbb{P}_S\{\sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta\}\geq1-\delta An algorithm is said to be stable, when the value of \beta decreases as O(\frac{1}{m}) .
Leave-one-out cross-validation (CVloo) Stability
An algorithm L has CVloo stability β with respect to the loss function V if the following holds: \forall i\in\{1,...,m\}, \mathbb{P}_S\{ |V(f_S,z_i) - V(f_{S^{|i}},z_i)|\leq\beta_{CV}\}\geq1 - \delta_{CV} The definition of (CVloo) Stability is equivalent to Pointwise-hypothesis stability seen earlier.
Expected-leave-one-out error ( Eloo_{err} ) Stability
An algorithm L has Eloo_{err} stability if for each n there exists a \beta_{EL}^m and a \delta_{EL}^m such that: \forall i\in\{1,...,m\}, \mathbb{P}_S\{|I[f_S]-\frac{1}{m}\sum_{i=1}^m V(f_{S^{|i}},z_i)|\leq\beta_{EL}^m\}\geq1-\delta_{EL}^m , with \beta_{EL}^m and \delta_{EL}^m going to zero for m,\rightarrow\infty
Algorithms that are stable
This is a list of algorithms that have been shown to be stable, and the article where the associated generalization bounds are provided. Linear regression k-NN classifier with a {0-1} loss function. Support Vector Machine (SVM) classification with a bounded kernel and where the regularizer is a norm in a Reproducing Kernel Hilbert Space. A large regularization constant C leads to good stability. Soft margin SVM classification. Regularized Least Squares regression. The minimum relative entropy algorithm for classification. A version of bagging regularizers with the number k of regressors increasing with n . Multi-class SVM classification. All learning algorithms with Tikhonov regularization satisfies Uniform Stability criteria and are, thus, generalizable.
Further reading
S.Kutin and P.Niyogi.Almost-everywhere algorithmic stability and generalization error. In Proc. of UAI 18, 2002 S. Rakhlin, S. Mukherjee, and T. Poggio. Stability results in learning theory. Analysis and Applications, 3(4):397–419, 2005 V.N. Vapnik. The Nature of Statistical Learning Theory. Springer, 1995 Vapnik, V., Statistical Learning Theory. Wiley, New York, 1998 Poggio, T., Rifkin, R., Mukherjee, S. and Niyogi, P., "Learning Theory: general conditions for predictivity", Nature, Vol.
428, 419–422, 2004 Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, Stability of Randomized Learning Algorithms, Journal of Machine Learning Research 6, 55–79, 2010 Elisseeff, A. Pontil, M., Leave-one-out Error and Stability of Learning Algorithms with Applications, NATO SCIENCE SERIES SUB SERIES III COMPUTER AND SYSTEMS SCIENCES, 2003, VOL 190, pages 111–130 Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010
Text derived from https://en.wikipedia.org/w/index.php?oldid=1362040236 under CC BY-SA 4.0; modifications have been made.