Overfitting, Underfitting, and Model Complexity

Definition Fit a learning procedure to a training set of $n$ examples $(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)$ to get a predictor $\hat{f}$, and let $L(y, \hat{y}) \ge 0$ be the loss charged when the target is $y$ and the prediction is $\hat{y}$. The training error is the average loss of $\hat{f}$ on the same examples,

where $\hat{y}_i = \hat{f}(\mathbf{x}_i)$. With squared loss it is the training mean squared error (MSE), the average of $e_i^2$ for the errors $e_i = \hat{y}_i - y_i$, each a prediction minus the actual value. Every target in this average helped shape the predictor that is scored on it, so training error measures how closely the procedure reproduces answers it has already seen. It tends to understate the error on new cases, and the more freely a procedure can adapt to individual examples, the more it tends to understate it. When a nearest-neighbor model is scored on its own training inputs, each training example takes part in the neighbor search for its own prediction, at distance zero.

Definition A validation set is a collection of $m$ examples $(\mathbf{x}'_1, y'_1), \dots, (\mathbf{x}'_m, y'_m)$ that take no part in fitting, including any preprocessing learned from data, and that are used to compare candidate procedures, for example different values of a hyperparameter. The validation error of a fitted predictor $\hat{f}$ is its average loss on these examples,

where $\hat{y}'_j = \hat{f}(\mathbf{x}'_j)$. If the validation examples are independent draws from the population the model will be applied to, and independent of the training data, then for one fixed predictor the validation error is an unbiased estimate of the expected loss on a new case from that population. It is still random, it changes with the particular validation cases, and it can be far from that expected loss when $m$ is small. When validation error picks the best of several candidates, the winner’s value tends to understate its error on new cases, so the final assessment uses a test set that played no part in any choice. Generalization, good performance on new cases from the intended deployment setting, is what validation error is meant to estimate, and it does so only as far as the validation cases resemble that setting.

Definition Model complexity, or flexibility, describes how wide a range of prediction functions a learning procedure can produce, and so how closely it can follow the particular training sample it is given. No single measure fits every kind of model. Within one family it is usually set by a hyperparameter, a setting chosen before fitting instead of learned by the fitting step, such as the degree of a polynomial or the number of neighbors $k$. In $k$-nearest neighbor regression with equal weights, $k$ is an integer with $1 \le k \le n$, and each prediction is the average of $k$ training targets. The neighbors of a query depend only on the inputs and the tie rule, so changing one training target by $\Delta$ moves every prediction by either $0$ or $\Delta / k$. The choice $k = 1$ gives the most flexible and most sample-sensitive rule, and $k = n$ predicts the training mean for every query. Complexity therefore decreases as $k$ grows, the opposite direction from polynomial degree. Like any hyperparameter, the neighbor count is chosen with validation evidence and never tuned on the test set.

Definition A fitting or model-selection procedure overfits when it adapts to details of its particular training sample that do not carry over to the cases it will predict, such as noise in individual targets, so that its predictions on relevant new cases are worse than those of an available less flexible alternative. The usual evidence combines low training error, clearly higher validation error, and a less flexible candidate with lower validation error. A gap between training and validation error does not prove overfitting by itself. Some gap is common even for a well-chosen model, because training error reuses the targets that shaped the predictor. A small validation set makes any comparison noisy, a gap measured on a validation set from a different population may reflect that mismatch rather than overfitting, and leakage or a faulty split can distort either number. So check the roles and comparability of the data before treating a gap as a complexity problem.

Definition A model or training procedure underfits when it is too restricted, or trained too incompletely, to capture structure in the data that is real and useful for prediction. The typical sign is that training error and validation error are both high, and that an available alternative that is more flexible, better trained or given more informative features lowers the validation error. Common causes are too little flexibility, such as a large $k$ or a straight line for a curved relationship, features that leave out information the target depends on, and an optimization stopped before it converged. High error alone does not prove underfitting, since noise in the targets limits how small the error on new cases can be for any predictor. The evidence is a justified change that lowers validation error, not only training error.

Definition A memorizing predictor stores the training examples and answers any query whose input exactly matches a stored training input with a stored target for that input. Every other input needs a fallback rule, such as the training mean or the target of the nearest stored input. If the training inputs are all distinct, a memorizer has training error $0$ under any loss with $L(y, y) = 0$. If one input appears with different targets, no rule that depends only on the input can reproduce them all, so under squared loss the training error stays above $0$. A one-nearest-neighbor regressor is a memorizer whose fallback is the target of the nearest stored input. For a memorizer, zero training error shows only that the answers were stored, and its performance on new inputs depends entirely on the fallback.