Generalization error

In supervised learning applications in machine learning and statistical learning theory, generalization error (also known as the out-of-sample error[1]) is a measure of how accurately an algorithm is able to predict outcome values for previously unseen data. Because learning algorithms are evaluated on finite samples, the evaluation of a learning algorithm may be sensitive to sampling error. As a result, measurements of prediction error on the current data may not provide much information about predictive ability on new data. Generalization error can be minimized by avoiding overfitting in the learning algorithm. The performance of a machine learning algorithm is measured by plots of the generalization error values through the learning process and are called learning curve.

Definition

In a learning problem, the goal is to develop a function f(x) that predicts output values y based on some input data x. The expected error, I[f_n] of a particular function f_n over all possible values of x and y is:

 I[f_n] = \int_{X \times Y} V(f_n(x),y) \rho(x,y) dx dy,

where V denotes a loss function and \rho(x,y) is the unknown joint probability distribution for x and y.

Without knowing the joint probability distribution, it is impossible to compute I[f]. Instead, we can compute the empirical error on sample data. Given N data points, the empirical error is:

 I_S[f_n] = \frac{1}{n} \sum_{i=1}^n V(f_n(x_i),y_i)

The generalization error is the difference between the expected and empirical error. This is the difference between error on the training set and error on the underlying joint probability distribution. It is defined as:

 G = I[f_n] - I_S[f_n]

An algorithm is said to generalize if:

 \lim_{n \rightarrow \infty} I[f_n] - I_S[f_n] = 0

Since I[f_n] cannot be computed for an unknown probability distribution, the generalization error cannot be computed either. Instead, the aim of many problems in statistical learning theory is to bound or characterize the generalization error in probability:


P_G = P(I(f_n) - I_S[f_n]) \leq \epsilon) \geq 1 - \delta_n

That is, the goal is to characterize the probability 1 - \delta_n that the generalization error is less than some error bound \epsilon (known as the learning rate and generally dependent on \delta and n.

Relation to stability

For many types of algorithms, it has been shown that an algorithm has generalization bounds if it meets certain stability criteria. Specifically, if an algorithm is symmetric (the order of inputs does not affect the result), has bounded loss and meets two stability conditions, it will generalize. The first stability condition, leave-one-out cross-validation stability, says that to be stable, the prediction error for each data point when leave-one-out cross validation is used must converge to zero as N\rightarrow \infty. The second condition, expected-to-leave-one-out error stability (also known as hypothesis stability if operating in the L_1 norm) is met if the prediction on a left-out datapoint does not change when a single data point is removed from the training dataset.[2]

These conditions can be formalized as:

Leave-one-out cross-validation Stability

An algorithm L has CVloo stability if for each n, there exists a \beta_{CV}^{(n)} and \delta_{CV}^{(n)} such that:

\forall i\in\{1,...,n\}, \mathbb{P}_S\{|V(f_{S^i},z_i)-V(f_S,z_i)|\leq\beta_{CV}^{(n)}\}\geq1-\delta_{CV}^{(n)}

and \beta_{CV}^{(n)} and \delta_{CV}^{(n)} go to zero as N goes to infinity.[3]

Expected-leave-one-out error 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,...,n\}, \mathbb{P}_S\{|I[f_S]-\frac{1}{n}\sum_{i=1}^N V(f_{S^{i}},z_i)|\leq\beta_{EL}^{(n)}\}\geq1-\delta_{EL}^{(n)}

with \beta_{EL}^m and \delta_{EL}^m going to zero for n\rightarrow\inf.

For leave-one-out stability in the L_1 norm, this is the same as hypothesis stability:

 \mathbb{E}_{S,z}[|V(f_S,z) - V(f_{S^i},z)|] \leq \beta_H^{(n)}

with \beta_H^{(n)} going to zero as N goes to infinity.[4]

Algorithms with proven stability

A number of algorithms have been proven to be stable and as a result have bounds on their generalization error. A list of these algorithms and the papers that proved stability is available here.

Relation to overfitting

See also: Overfitting
This figure illustrates the relationship between overfitting and the generalization error I[f_n] - I_S[f_n]. Data points were generated from the relationship y = x with white noise added to the y values. In the left column, a set of training points is shown in blue. Two functions were fit to the training data, a first and seventh order polynomial. In the right column, the functions are tested on data sampled from the underlying joint probability distribution of x and y. In the top row, the functions are fit on a sample dataset of 10 datapoints. In the bottom row, the functions are fit on a sample dataset of 100 datapoints. As we can see, for small sample sizes and complex functions, the error on the training set is small but error on the underlying distribution of data is large and we have overfit the data. As a result, generalization error is large. As the number of sample points increases, the prediction error on training and test data converges and generalization error goes to 0.

The concepts of generalization error and overfitting are closely related. Overfitting occurs when the learned function f_S becomes sensitive to the noise in the sample. As a result, the function will perform well on the training set but not perform well on other data from the joint probability distribution of x and y. Thus, the more overfitting occurs, the larger the generalization error.

The amount of overfitting can be tested using cross-validation methods, which splits the sample into simulated training samples and testing samples. The model is then trained on a training sample and evaluated on the testing sample. The testing sample is previously unseen by the algorithm and so represents a random sample from the joint probability distribution of x and y. This test sample allows us to approximate the expected error and as a result approximate a particular form of the generalization error.

Many algorithms exists to prevent overfitting. The minimization algorithm can penalize more complex functions (known as Tikhonov regularization, or the hypothesis space can be constrained, either explicitly in the form of the functions or by adding constraints to the minimization function (Ivanov regularization).

The approach to finding a function that does not overfit is at odds with the goal of finding a function that is sufficiently complex to capture the particular characteristics of the data. This is known as the bias–variance tradeoff. Keeping a function simple to avoid overfitting may introduce a bias in the resulting predictions, while allowing it to be more complex leads to overfitting and a higher variance in the predictions. It is impossible to minimize both simultaneously.

References

  1. Y S. Abu-Mostafa, M.Magdon-Ismail, and H.-T. Lin (2012) Learning from Data, AMLBook Press. ISBN 978-1600490064
  2. S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006.
  3. S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006.
  4. S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006.

Additional literature

This article is issued from Wikipedia - version of the Monday, February 01, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.