Generalization

Problem

Training minimizes a loss on a finite set of examples. But nobody wants the answer to "how well do you know these ten examples?" They want to know how the model will do tomorrow, on inputs it has not met. A model can score perfectly on its training set by memorizing it and still be useless, so the training score alone says almost nothing about what you care about.

Every practical choice in machine learning is, underneath, a bet about this gap: how big a model, how much data, when to stop training, how to measure success honestly. If you cannot tell memorizing from learning, you cannot tell a good model from a lucky one.

Intuition

A student who memorizes last year's exam gets a perfect score on last year's exam and learns nothing about the subject. A student who understands the material may miss a couple of old questions but does well on a new paper. The old exam is the training set; the new paper is the world. We measure understanding by setting some questions aside and never practising on them.

Two things make a new paper harder than the old one. If the student has too much freedom to bend an answer around every quirk of the practice questions, they fit noise. And if the new paper covers a different syllabus than the practice set, even a student who understood everything may fail. These are the two halves of this page: capacity and distribution shift.

Generalization means doing well across P, not just on the dots you trained on. A shifted P' is a different world.

Mechanics

True risk and empirical risk

Suppose examples (x, y) are drawn from some unknown distribution P, and a loss ℓ scores a prediction f(x) against y (see loss functions). The quantity we want to be small is the true risk, the expected loss over P:

R(f) = E_(x,y)∼P [ ℓ(f(x), y) ]

We can't compute it, because we don't know P. What we can compute is the empirical risk, the average loss over the n training examples:

R̂(f) = (1 / n) Σ_i ℓ(f(x_i), y_i)

Training is empirical risk minimization: pick the f in some family that makes R̂ small. The generalization gap is R(f) − R̂(f). For a fixed f chosen without looking at the data, R̂ is an unbiased estimate of R and the gap averages to zero. But the f we actually use was chosen because it had a small R̂, so its training loss is optimistically biased and the gap is typically positive.

The i.i.d. assumption

The argument above leans on one assumption: the examples are independent and identically distributed. Identically means training and future data come from the same P. Independent means one example tells you nothing extra about another. When this holds, a held-out set is a fair stand-in for the future, and its average loss is an unbiased estimate of R(f), with a standard error that shrinks like 1/√m for m test examples. When it fails (duplicated rows, several records per patient, data ordered by time), the held-out number is too good, which is the subject of data splits and later of data leakage.

Capacity

Capacity is how rich a family of functions the model can represent: the degree of a polynomial, the depth of a tree, the number of parameters in a network. More capacity lets the model fit more patterns, including accidental ones. Three regimes follow:

• Too little capacity (underfitting): the family can't express the real pattern, so both training and held-out error stay high.
• Enough: training error is low and held-out error is close to it.
• Too much (overfitting): training error keeps falling, often to zero, while held-out error rises, because the extra freedom is spent on noise in the sample.

Classical theory formalizes this with capacity measures such as VC dimension, which bound the gap in terms of capacity divided by the number of examples. The worked example below shows the shape without any theory.

Double descent

The picture above, held-out error falling and then rising as capacity grows, is not the whole story for modern models. Belkin and co-authors (2019) and Nakkiran and co-authors (2019) report that when capacity grows past the point where the model can exactly fit the training data (the interpolation threshold), held-out error can fall again, giving a second descent. It is observed for neural networks, random features and some linear models, and the exact behaviour depends on how the fit is chosen among the many that interpolate. This page does not compute it; see the references. The practical lesson is narrower than "bigger is always safe": a peak near the threshold is real, and which side of it you are on matters.

Distribution shift

If the data a model meets in use comes from P' ≠ P, then held-out error measured on P says little about it. Common cases: covariate shift (inputs change, the relation from x to y does not), label shift (class frequencies change) and concept drift (the relation itself changes over time). A flexible model is especially fragile outside the region its training inputs covered, because nothing constrained it there. Monitoring for this after deployment is its own topic.

Estimating the gap in scikit-learn

The tools all do the same thing: keep some data out of fitting and score on it. train_test_split makes one split. cross_val_score repeats the idea over several splits. learning_curve scores at growing training sizes and validation_curve scores while one hyperparameter, such as capacity, changes. Both return training and validation scores so you can read the gap directly.

Same ten points, three model sizes. The degree-9 curve (10 parameters for 10 points) hits every dot, so its training error is zero.

Worked example

Implementation

import numpy as np
from sklearn.model_selection import train_test_split, validation_curve
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import PolynomialFeatures
from sklearn.linear_model import LinearRegression

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=0
)

model = make_pipeline(PolynomialFeatures(), LinearRegression())
degrees = np.arange(1, 10)
train_scores, val_scores = validation_curve(
    model, X_train, y_train,
    param_name="polynomialfeatures__degree", param_range=degrees, cv=5,
    scoring="neg_mean_squared_error",
)
# train_scores, val_scores: [len(degrees), 5]. Average over axis 1.
# Training error keeps falling; validation error turns up past the best degree.
best = degrees[val_scores.mean(axis=1).argmax()]

final = model.set_params(polynomialfeatures__degree=best).fit(X_train, y_train)
final.score(X_test, y_test)   # touch the test set once, at the very end

The test set is used a single time, after every choice has been made. Choose the degree on the validation scores, not on the test split, or the test score becomes another training signal and stops being an honest estimate.

Tradeoffs

• Hold out more or fewer. A bigger test set gives a steadier estimate but leaves less to train on. With few examples, cross-validation reuses data at the price of fitting the model several times.
• The held-out estimate is noisy. With m test examples its standard error is about σ/√m. Two models within that margin are not distinguishable, and picking the best of many models on one split quietly overfits the split.
• More capacity, more data, or more constraint. A gap that shrinks as you add data (visible in a learning curve) says collect more; a gap that doesn't says simplify the model or add regularization.
• I.i.d. is an assumption, not a fact. Time series, repeated measurements and data scraped from the web break it, and the reported test score is then optimistic in ways that are hard to see.
• Interpolating is not always bad. Large neural networks routinely reach zero training error and still generalize, which the classical picture alone does not explain. Treat "zero training error means overfit" as a rule of thumb for small models, not a law.

Check yourself

Connections

References

• Hastie, Tibshirani and Friedman. The Elements of Statistical Learning, 2nd ed., chapter 7, "Model Assessment and Selection". Springer, 2009.
• Vapnik. The Nature of Statistical Learning Theory. Springer, 1995, for empirical risk minimization and VC dimension.
• Belkin, Hsu, Ma and Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. PNAS, 2019 (arXiv 1812.11118).
• Nakkiran et al. Deep Double Descent: Where Bigger Models and More Data Hurt. ICLR 2020 (arXiv 1912.02292).
• Quiñonero-Candela, Sugiyama, Schwaighofer and Lawrence (eds.). Dataset Shift in Machine Learning. MIT Press, 2009.
• scikit-learn 1.9.1: train_test_split, learning_curve, validation_curve.