Generalization error

Definition

In a learning problem, the goal is to develop a function ${\displaystyle f_n(\overrightarrow{x})}$ that predicts output values ${\displaystyle y}$ for each input datum ${\displaystyle \overrightarrow{x}}$. The subscript ${\displaystyle n}$ indicates that the function ${\displaystyle f_n}$ is developed based on a data set of ${\displaystyle n}$ data points. The generalization error or expected loss or risk ${\displaystyle I[f]}$ of a particular function ${\displaystyle f}$ over all possible values of ${\displaystyle \overrightarrow{x}}$ and ${\displaystyle y}$ is the expected value of the loss function ${\displaystyle V(f)}$:

${\displaystyle I[f]={\int }_{X\times Y}V(f(\overrightarrow{x}),y)\rho (\overrightarrow{x},y)d\overrightarrow{x}dy,}$

where ${\displaystyle \rho (\overrightarrow{x},y)}$ is the unknown joint probability distribution for ${\displaystyle \overrightarrow{x}}$ and ${\displaystyle y}$.

Without knowing the joint probability distribution ${\displaystyle \rho }$, it is impossible to compute ${\displaystyle I[f]}$. Instead, we can compute the error on sample data, which is called empirical error (or empirical risk). Given ${\displaystyle n}$ data points, the empirical error of a candidate function ${\displaystyle f}$ is:

${\displaystyle I_n[f]=\frac{1}{n}\sum _{i=1}^{n}V(f({\overrightarrow{x}}_i),y_i)}$

An algorithm is said to generalize if:

${\displaystyle \underset{n\to \mathrm{\infty }}{lim}I[f]-I_n[f]=0}$

Of particular importance is the generalization error ${\displaystyle I[f_n]}$ of the data-dependent function ${\displaystyle f_n}$ that is found by a learning algorithm based on the sample. Again, for an unknown probability distribution, ${\displaystyle I[f_n]}$ cannot be computed. Instead, the aim of many problems in statistical learning theory is to bound or characterize the difference of the generalization error and the empirical error in probability:

${\displaystyle P_G=P(I[f_n]-I_n[f_n]\le ϵ)\ge 1-{\delta }_n}$

That is, the goal is to characterize the probability ${\displaystyle 1-{\delta }_n}$ that the generalization error is less than the empirical error plus some error bound ${\displaystyle ϵ}$ (generally dependent on ${\displaystyle \delta }$ and ${\displaystyle n}$). 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 ${\displaystyle n\to \mathrm{\infty }}$. The second condition, expected-to-leave-one-out error stability (also known as hypothesis stability if operating in the ${\displaystyle 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.

These conditions can be formalized as:

Leave-one-out cross-validation Stability

An algorithm ${\displaystyle L}$ has ${\displaystyle CVloo}$ stability if for each ${\displaystyle n}$, there exists a ${\displaystyle {\beta }_{CV}^{(n)}}$ and ${\displaystyle {\delta }_{CV}^{(n)}}$ such that:

${\displaystyle \mathrm{\forall }i\in \{1,...,n\},{\mathbb{P}}_S\{|V(f_{S^i},z_i)-V(f_S,z_i)|\le {\beta }_{CV}^{(n)}\}\ge 1-{\delta }_{CV}^{(n)}}$

and ${\displaystyle {\beta }_{CV}^{(n)}}$ and ${\displaystyle {\delta }_{CV}^{(n)}}$ go to zero as ${\displaystyle n}$ goes to infinity.

Expected-leave-one-out error Stability

An algorithm ${\displaystyle L}$ has ${\displaystyle Elo{o}_{err}}$ stability if for each ${\displaystyle n}$ there exists a ${\displaystyle {\beta }_{EL}^m}$ and a ${\displaystyle {\delta }_{EL}^m}$ such that:

${\displaystyle \mathrm{\forall }i\in \{1,...,n\},{\mathbb{P}}_S\left\{\left|I[f_S]-\frac{1}{n}\sum _{i=1}^{N}V\left(f_{S^i},z_i\right)\right|\le {\beta }_{EL}^{(n)}\right\}\ge 1-{\delta }_{EL}^{(n)}}$

with ${\displaystyle {\beta }_{EL}^{(n)}}$ and ${\displaystyle {\delta }_{EL}^{(n)}}$ going to zero for ${\displaystyle n\to \mathrm{\infty }}$.

For leave-one-out stability in the ${\displaystyle L_1}$ norm, this is the same as hypothesis stability:

${\displaystyle {\mathbb{E}}_{S,z}[|V(f_S,z)-V(f_{S^i},z)|]\le {\beta }_H^{(n)}}$

with ${\displaystyle {\beta }_H^{(n)}}$ going to zero as ${\displaystyle n}$ goes to infinity.

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.