Overfitting and Underfitting
Chapter Forty-Nine
Syllabus topic Module 2, "Overfitting"
Pages 265 to 270 of 591
In one line
Underfitting is a model too rigid to follow the pattern; overfitting is a model flexible enough to follow the noise as though it were the pattern.
In the wording a student can write in an examination: a model underfits when it is too simple to capture the structure in the data, so both training and test error are high; this is high bias. A model overfits when it fits the particular training sample so closely that it captures its noise, so training error is low while test error is high; this is high variance. Generalisation is performance on data not used in training, and it is the only thing that matters.
Both errors, measured
One training set of twelve points, and 1800 points from the same process that the model never sees. Polynomials of degree 0 to 10 are fitted to the twelve and scored on both.
# Overfitting, measured: fit polynomials of nine degrees to ONE training set and
# report the error on that set and on data the model has never seen.
def lcg(seed):
x = seed
while True:
x = (1664525 * x + 1013904223) % (2 ** 32)
yield x / 2 ** 32
def truth(x):
return 40 + 6.0 * x - 0.30 * x * x
def sample(rng, xs):
return [(x, truth(x) + (rng() + rng() + rng() - 1.5) * 8) for x in xs]
def fit_poly(points, degree):
m = degree + 1
A = [[sum(x ** (i + j) for x, _ in points) for j in range(m)] for i in range(m)]
b = [sum(y * x ** i for x, y in points) for i in range(m)]
for c in range(m):
piv = max(range(c, m), key=lambda r: abs(A[r][c]))
A[c], A[piv] = A[piv], A[c]
b[c], b[piv] = b[piv], b[c]
for r in range(m):
if r == c or A[c][c] == 0:
continue
f = A[r][c] / A[c][c]
for k in range(c, m):
A[r][k] -= f * A[c][k]
b[r] -= f * b[c]
return [b[i] / A[i][i] if A[i][i] else 0.0 for i in range(m)]
def predict(coef, x):
return sum(c * x ** i for i, c in enumerate(coef))
def mse(coef, points):
return sum((y - predict(coef, x)) ** 2 for x, y in points) / len(points)
gen = lcg(99)
rng = lambda: next(gen) # noqa: E731
train = sample(rng, [float(i) for i in range(1, 13)]) # 12 points
# WARNING: 11 test points is TOO FEW: the test error is then itself noisy and its
# minimum lands in a different place on every run, which hides the U-shape the
# chapter is about. 600 unseen points give a stable measurement.
test = []
for _ in range(50):
test += sample(rng, [i + 0.25 * k for i in range(1, 13) for k in (0, 1, 2)])
print("12 training points, and %d test points the model never sees." % len(test))
print()
print("degree | training error | test error | verdict")
print("-------|----------------|------------|--------")
best = None
for d in range(0, 11):
coef = fit_poly(train, d)
tr, te = mse(coef, train), mse(coef, test)
if best is None or te < best[1]:
best = (d, te)
print(" %2d | %14.3f | %10.3f |" % (d, tr, te))
print()
print("read the two columns in opposite directions.")
print(" the TRAINING error falls all the way to degree 10: a more flexible model")
print(" always fits the data it was given better. it is not a measure of anything.")
print(" the TEST error falls, reaches its least at degree %d, and then RISES." % best[0])
print()
print(" degree 0 and 1 UNDERFIT: too rigid to follow the curve, so both errors")
print(" are high. degree 8 and above OVERFIT: they have learned the NOISE in the")
print(" 12 training points, which the unseen points do not share.")Overfitting and Underfitting
12 training points, and 1800 test points the model never sees.
degree | training error | test error | verdict
-------|----------------|------------|--------
0 | 91.775 | 69.758 |
1 | 26.603 | 27.998 |
2 | 10.351 | 17.434 |
3 | 9.837 | 17.812 |
4 | 7.913 | 21.725 |
5 | 7.906 | 21.590 |
6 | 4.512 | 24.438 |
7 | 4.395 | 27.636 |
8 | 2.474 | 47.920 |
9 | 1.802 | 236.085 |
10 | 0.373 | 1374.908 |
read the two columns in opposite directions.
the TRAINING error falls all the way to degree 10: a more flexible model
always fits the data it was given better. it is not a measure of anything.
the TEST error falls, reaches its least at degree 2, and then RISES.
degree 0 and 1 UNDERFIT: too rigid to follow the curve, so both errors
are high. degree 8 and above OVERFIT: they have learned the NOISE in the
12 training points, which the unseen points do not share.The two columns go in opposite directions, and that is the whole chapter.
The training error falls monotonically, 91.775 down to 0.373. It never rises, and it never can: a more flexible model family contains every simpler one, so it can always do at least as well on the data it was fitted to. Training error is therefore not a measure of anything. A model reporting a low training error has reported that it is flexible, not that it is good.
The test error is a U. It falls from 69.758 to 17.434 at degree 2 and then rises, gently at first and then catastrophically: 47.920 at degree 8, 236.085 at degree 9, 1374.908 at degree 10.
Overfitting and Underfitting
Degree 10 has twelve points and eleven coefficients. It very nearly passes through every one, so its training error is 0.373, and it is worse on unseen data than the flat line that predicted the mean. A model with a training error near zero and a test error eighty times worse than a constant is the clearest picture of overfitting there is.
Reading the two failures
| Underfitting | Overfitting | |
|---|---|---|
| Training error | high | low |
| Test error | high | high |
| The two errors are | close together | far apart |
| Bias and variance | high bias, low variance | low bias, high variance |
| In the table | degrees 0 and 1 | degrees 8, 9, 10 |
| The model has learned | too little | the noise |
| The cure | more flexibility, better features | less flexibility, more data, regularization |
The diagnostic is the gap between the two errors, and it is what a paper wants when it asks how you would tell. Both high and close: underfitting. Training low and test far above it: overfitting. Both low: you are finished.
At degree 2 the errors are 10.351 and 17.434, still not equal. That gap never closes entirely, because the training points were used to choose the fit and the test points were not. A small persistent gap is normal; a large and growing one is the warning.
Why more flexibility eventually hurts
The mechanism, stated once so it can be repeated in an answer.
Each observation is the truth plus noise. A model flexible enough to pass through the observations must reproduce the noise, and the noise in the training sample has nothing to do with the noise anywhere else. So every bit of that fit is not merely useless on new data, it is actively wrong: the curve is bent away from the truth to reach a point that was only there by chance.
And the bending compounds. Between two training points, a high-degree polynomial forced through both swings violently, which is why the test error at degree 10 is not a little worse but eighty times worse. The model is not merely uninformative off the training points; it is confidently wrong.
How overfitting is detected
Three methods, in increasing order of reliability, and a paper may ask for two of them.
A held-out test set. Split the data, fit on one part, measure on the other. This is what the program does. The test set must be used once, to report a final number. Tuning a choice by looking at the test error makes the test set part of the training process, and its error then understates the true error, sometimes badly.
Overfitting and Underfitting
A validation set. A third split, used for choosing hyperparameters such as the degree, so the test set stays untouched. The right procedure is: fit on training, choose the degree on validation, report on test.
Cross-validation. Split into k folds, train on k - 1 and measure on the remaining one, k times, and average. It uses all the data for both purposes and gives a more stable estimate, at k times the cost. Evaluating a Model sets it out properly.
How overfitting is prevented
Six devices, and every one of them is somewhere else in this module, which is worth noticing.
| Device | What it does | Where in this book |
|---|---|---|
| More data | the noise averages out; the model cannot fit all of it | Bias and Variance |
| A simpler model | fewer parameters to bend | this chapter |
| Regularization | penalise large coefficients, so extreme fits are expensive | Regularization |
| Early stopping | stop training when validation error starts rising | The Multilayer Network and Backpropagation |
| Pruning | cut back a tree grown too far | Reading, Drawing and Pruning a Decision Tree |
| Averaging models | unsystematic errors cancel | Ensemble Methods, Bagging and the Random Forest |
And the one that is not on that list: feature selection. Fewer, better features shrink the hypothesis space directly. It is cheap and it is often the largest single improvement available.
Occam's razor, and the honest version of it
The principle usually quoted here is that the simplest hypothesis fitting the data should be preferred. It is a good working rule and it is worth being precise about why.
The justification is not that the world is simple. It is a counting argument: there are far fewer simple hypotheses than complex ones, so a simple hypothesis that fits a large dataset is unlikely to have done so by chance, while among the vast number of complex hypotheses some will fit any dataset by accident.
So the principle is about evidence, not aesthetics, and it has a limit: if the truth is genuinely complicated, the simplest hypothesis fitting the data will be wrong. Degree 0 is the simplest model in the table and it is not the best.
Distinctions
| Training error | Test error | |
|---|---|---|
| Measured on | the data fitted to | data never seen |
| As flexibility rises | falls, always | falls then rises |
| Useful as a measure of quality | no | yes |
| In the table at degree 10 | 0.373 | 1374.908 |
| Validation set | Test set | |
|---|---|---|
| Used for | choosing hyperparameters | the final report |
| Used how often | many times | once |
| If confused | the reported error is optimistic |
| Occam's razor, as usually stated | Its justification | |
|---|---|---|
| Prefer the simplest hypothesis that fits | there are fewer simple hypotheses, so one fitting a large dataset is unlikely to fit by chance | |
| Fails when | the truth is genuinely complex |
Overfitting and Underfitting
What it does not mean
Low training error is not success. Degree 10 has the lowest training error in the table and by far the worst test error.
Overfitting is not a bug in the algorithm. The fit is the correct least-squares answer. The mistake is choosing a model family too flexible for the data available.
Underfitting is not caused by too little data. It is caused by too little flexibility, and more data does not fix it.
A gap between the two errors is not always overfitting. A small persistent gap is expected, since the training points were used to choose the fit.
The test set is not for tuning. Used more than once it stops measuring generalisation, and the reported figure becomes optimistic.
Simpler is not always better. Occam's razor prefers the simplest hypothesis that fits, and degree 0 does not fit.
Quick revision
- Underfitting: too rigid, high bias, both errors high and close. Overfitting: too flexible, high variance, training low and test far above it.
- Measured: training error falls monotonically 91.775 to 0.373; test error falls to 17.434 at degree 2 and rises to 1374.908 at degree 10.
- Training error is not a measure of quality. A more flexible family always fits its own data at least as well.
- The diagnostic is the gap between the two errors. A small persistent gap is normal.
- The mechanism: a model flexible enough to pass through the observations must reproduce their noise, which is unrelated to any other sample, so the curve is bent away from the truth.
- Detected by a held-out test set (used once), a validation set for choosing hyperparameters, or cross-validation.
- Prevented by more data, a simpler model, regularization, early stopping, pruning, averaging models, and feature selection.
- Occam's razor is justified by counting: there are fewer simple hypotheses, so one that fits a large dataset is unlikely to have done so by chance. It fails when the truth is genuinely complex.
Test yourself
1. Define underfitting and overfitting in terms of the two errors. A model underfits when it is too simple to capture the structure, so training and test error are both high and close together. It overfits when it fits the particular training sample so closely that it captures its noise, so training error is low while test error is much higher.
2. Why does the training error never rise as the degree increases? Because a more flexible model family contains every simpler one as a special case, so the best fit within it can never be worse on the data it was fitted to. The training error therefore falls monotonically and measures flexibility rather than quality.
Overfitting and Underfitting
3. At degree 10 the training error is 0.373 and the test error 1374.908. Explain both numbers. With twelve points and eleven coefficients the polynomial almost passes through every training point, which drives the training error to nearly zero. Doing so requires reproducing the noise in those twelve points, which the unseen points do not share, and the curve swings violently between them, so on new data it is far worse than even the flat line that predicts the mean.
4. How do you tell underfitting from overfitting in practice? By the gap between the two errors. Both high and close together indicates underfitting. A low training error with a test error far above it indicates overfitting. A small persistent gap is normal, since the training data was used to choose the fit.
5. Why must a test set be used only once? Because using it to choose between models makes it part of the training process. The chosen model is then the one that happened to suit that particular held-out sample, and its measured error understates the true error on genuinely new data.
6. Name four ways of preventing overfitting. More training data, a simpler model family, regularization which penalises large coefficients, early stopping when validation error begins to rise, pruning a tree that has been grown too far, averaging several models, and reducing the number of features.
7. State Occam's razor and give its real justification. Prefer the simplest hypothesis consistent with the data. The justification is a counting argument rather than a claim that the world is simple: there are far fewer simple hypotheses than complex ones, so a simple one fitting a large dataset is unlikely to have done so by accident, whereas among the vast number of complex hypotheses some will fit any dataset by chance.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.