Regularization
Chapter Fifty
Syllabus topic Module 2, "regularization"
Pages 271 to 276 of 591
In one line
Regularization adds a charge for using large coefficients, so a fit that has to contort itself to pass through every point becomes too expensive to choose.
In the wording a student can write in an examination: regularization adds a penalty term to the loss function, penalising the complexity of the model rather than its error, so that training minimises
total loss = error on the training data + lambda * penalty(model)
where lambda is a hyperparameter controlling the strength. Ridge regression, or L2 regularization, penalises the sum of the squared coefficients; lasso, or L1, penalises the sum of the absolute values. Regularization reduces variance at the cost of some bias, and so combats overfitting.
The idea
Overfitting and Underfitting ended with six cures and this is the one that does not require throwing anything away.
The usual response to overfitting is to use a smaller model: fewer parameters, fewer features, a lower degree. That works and it is blunt, because the decision has to be made before seeing how the fit behaves.
Regularization does something different. Keep the flexible model, and make the flexible fits expensive. The optimisation then chooses for itself how much of the available flexibility to use, and it uses less where the data does not support more.
Why coefficient size is the right thing to charge for: a curve that passes through every one of twelve scattered points has to swing violently between them, and swinging violently requires enormous coefficients that nearly cancel. Penalising their size makes exactly that kind of fit unaffordable, while a gentle curve with small coefficients pays almost nothing.
It measured
The same degree 10 polynomial, the same twelve training points, at five penalty strengths.
# Regularization: add a penalty on the SIZE of the coefficients, and watch the
# wild degree-10 fit be tamed. Ridge regression, solved by the normal equations.
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_ridge(points, degree, lam):
"""Least squares plus lam times the sum of squared coefficients."""
m = degree + 1
A = [[sum((x / 10.0) ** (i + j) for x, _ in points) + (lam if i == j else 0.0)
for j in range(m)] for i in range(m)]
b = [sum(y * (x / 10.0) ** 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 / 10.0) ** 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)])
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("a degree 10 polynomial on 12 points, at five penalty strengths.")
print("the penalty is lambda times the sum of the squared coefficients.")
print()
print(" lambda | training error | test error | size of the coefficients")
print(" -------|----------------|------------|-------------------------")
for lam in (0.0, 1e-6, 1e-4, 1e-2, 1.0):
coef = fit_ridge(train, 10, lam)
size = sum(c * c for c in coef) ** 0.5
print(" %6g | %14.3f | %10.3f | %23.1f"
% (lam, mse(coef, train), mse(coef, test), size))
print()
print("with no penalty the coefficients are enormous and the test error is")
print("ruinous. the penalty makes large coefficients expensive, so the fit stops")
print("using them, and the SAME degree 10 model becomes usable.")
print()
print("the model was never made less flexible. only the fits it is willing to")
print("choose were restricted, which is the whole idea.")Regularization
a degree 10 polynomial on 12 points, at five penalty strengths.
the penalty is lambda times the sum of the squared coefficients.
lambda | training error | test error | size of the coefficients
-------|----------------|------------|-------------------------
0 | 0.360 | 757.507 | 51902164.0
1e-06 | 4.830 | 29.904 | 1632.7
0.0001 | 5.952 | 22.463 | 235.2
0.01 | 8.672 | 20.213 | 67.4
1 | 40.799 | 41.336 | 47.4
with no penalty the coefficients are enormous and the test error is
ruinous. the penalty makes large coefficients expensive, so the fit stops
using them, and the SAME degree 10 model becomes usable.
the model was never made less flexible. only the fits it is willing to
choose were restricted, which is the whole idea.Read the last column first, because it is the mechanism. With no penalty the coefficients have a combined size of 51,902,164. They are enormous and they nearly cancel, which is what a curve forced through twelve scattered points has to do. At lambda of 0.01 the size is 67.4, and the test error has gone from 757.507 to 20.213.
Regularization
Three things in the table are worth naming.
The training error rises as lambda rises, 0.360 to 40.799, and that is correct. Regularization is not supposed to fit the training data better; it is supposed to stop fitting it so well.
The test error falls, reaches its least, and then rises again. 757.507, 29.904, 22.463, 20.213, 41.336. So lambda has its own U-shape, exactly as the degree did in the previous chapter. Too little penalty and the fit overfits; too much and it underfits.
At lambda of 1 the two errors are almost equal, 40.799 and 41.336. That is the signature of underfitting from Overfitting and Underfitting: both high and close together. The penalty has overwhelmed the data.
And the comparison across chapters: the best degree 2 model in the previous chapter scored 17.434. This regularised degree 10 model scores 20.213, close to it, from a model family that without the penalty was eighty times worse than a flat line.
The two penalties
MU's own label is Overfitting & regularization and a paper asks for both by name.
Ridge, or L2. Penalise the sum of the squared coefficients.
loss = sum over i of (y_i - prediction_i)2 + lambda * sum over j of w_j2
It shrinks every coefficient towards zero without reaching zero. It has a closed-form solution, the one the program uses: add lambda down the diagonal of the normal equations. That single line is worth remembering as what ridge regression IS computationally.
Lasso, or L1. Penalise the sum of the absolute values.
loss = sum over i of (y_i - prediction_i)**2 + lambda * sum over j of |w_j|
It drives some coefficients exactly to zero, so it performs feature selection as a side effect: the features whose coefficients vanish are simply dropped. That is its distinctive property and it is the reason to choose it.
Why L1 reaches zero and L2 does not, in one sentence: the squared penalty's gradient is proportional to the coefficient, so it becomes vanishingly weak as the coefficient approaches zero, while the absolute penalty's gradient has constant size all the way in and pushes the coefficient through.
Elastic net uses both together, and is the usual answer when features are correlated, where lasso alone picks one of a correlated group arbitrarily.
Two practical rules that cost marks if forgotten
The intercept is not penalised. Shrinking it towards zero would say the output ought to be near zero, which is a statement about the units the data happens to be measured in and not about complexity.
The features must be standardised first. The penalty charges by coefficient size, and a coefficient's size depends on its feature's units. A feature measured in metres has a coefficient a thousand times larger than the same feature in millimetres, so it would be penalised a thousand times more heavily for no reason at all. Standardising each feature to zero mean and unit spread removes the arbitrariness. The program above divides x by 10 for exactly this reason, so the powers of a number near 1 stay comparable.
Regularization
Choosing lambda
Lambda is a hyperparameter, so it is chosen the way Overfitting and Underfitting says hyperparameters are chosen: on a validation set or by cross-validation, never on the test set and never on the training error.
The training error cannot choose it, because the training error always prefers lambda equal to zero: that is what the first row of the table shows.
In practice lambda is searched over a wide range on a logarithmic scale, which is why the table's values are 0, 0.000001, 0.0001, 0.01 and 1 rather than 0.1, 0.2, 0.3. The right value can be very small, and a linear search would miss it.
The same idea under other names
Regularization is a family rather than one technique, and recognising it elsewhere is worth a Q.3 answer.
| Where | What is penalised or restricted |
|---|---|
| Ridge and lasso | the size of the coefficients |
| Pruning a decision tree, chapter 58 | the number of leaves |
| Early stopping, chapter 63 | how far the weights are allowed to move from their starting point |
| Dropout in a neural network | reliance on any single unit, by removing units at random during training |
| A prior in Bayesian estimation, chapter 68 | a belief about the parameters before the data, which pulls the estimate towards it |
| Laplace smoothing, chapter 59 | a zero count, by adding one |
The last two rows are worth pausing on. Ridge regression is exactly maximum a posteriori estimation with a normal prior on the coefficients, and lasso with a double-exponential prior. So the penalty is not an arbitrary charge: it is a prior belief that the coefficients are small, expressed as arithmetic. A paper asking for the Bayesian interpretation of regularization wants that sentence.
Distinctions
| Ridge, L2 | Lasso, L1 | |
|---|---|---|
| Penalises | the sum of squared coefficients | the sum of absolute values |
| Coefficients reach exactly zero | no | yes |
| Performs feature selection | no | yes |
| Closed-form solution | yes, lambda on the diagonal | no, needs an iterative method |
| With correlated features | shares the weight between them | picks one arbitrarily |
| Reducing the degree | Regularization | |
|---|---|---|
| Decided | before fitting | by the optimisation, given lambda |
| The model family | is made smaller | is unchanged |
| Flexibility | removed | made expensive |
| Lambda too small | Lambda too large | |
|---|---|---|
| Behaviour | overfits | underfits |
| Training error | very low | high |
| Test error | very high | high, and close to the training error |
| In the table | 757.507 at lambda 0 | 41.336 at lambda 1 |
Regularization
What it does not mean
Regularization does not improve the training error. It makes it worse on purpose, from 0.360 to 8.672 in the table.
It does not make the model smaller. The degree 10 polynomial still has eleven coefficients; they are merely small. Only lasso removes any of them.
Lambda is not chosen from the training error. The training error always prefers lambda of zero.
It is not a substitute for more data. More data reduces variance without raising bias; regularization trades a little bias for a larger reduction in variance.
Ridge does not set coefficients to zero. It shrinks them towards zero and they arrive only in the limit.
The features must be standardised. Without it the penalty charges by the accident of units.
Quick revision
- Regularization: minimise
training error + lambda * penalty(model), so complex fits become expensive. It trades a little bias for a larger reduction in variance. - Mechanism: a curve forced through scattered points needs enormous, nearly cancelling coefficients. Penalising their size makes that fit unaffordable.
- Measured on the degree 10 polynomial: coefficient size 51,902,164 at lambda 0 with test error 757.507, against size 67.4 at lambda 0.01 with test error 20.213.
- The training error rises with lambda; the test error is a U, least at lambda 0.01 here.
- Ridge (L2) penalises squared coefficients, shrinks towards zero without reaching it, has a closed-form solution: add lambda to the diagonal of the normal equations. Lasso (L1) penalises absolute values, drives coefficients exactly to zero, and so performs feature selection. Elastic net uses both.
- Do not penalise the intercept. Standardise the features first, or the penalty charges by the accident of units.
- Choose lambda on a validation set or by cross-validation, searched on a logarithmic scale. The training error always prefers zero.
- The same idea appears as pruning, early stopping, dropout, a prior, and Laplace smoothing. Ridge is exactly maximum a posteriori estimation with a normal prior on the coefficients.
Test yourself
1. Write the regularized loss and say what each part does. Total loss equals the error on the training data plus lambda times a penalty on the model's complexity. The first term pulls the fit towards the data, the penalty pulls it towards simplicity, and lambda sets the exchange rate between them.
2. Why is the size of the coefficients the right thing to penalise? Because a curve that passes through every one of a set of scattered points must swing violently between them, and doing so requires very large coefficients that nearly cancel. Charging for their size makes exactly that kind of fit unaffordable while leaving a gentle fit almost untouched.
Regularization
3. In the measured table, what happened between lambda 0 and lambda 0.01? The combined size of the coefficients fell from 51,902,164 to 67.4, the training error rose from 0.360 to 8.672, and the test error fell from 757.507 to 20.213. The same degree 10 model went from being eighty times worse than a flat line to being close to the best model of the previous chapter.
4. Distinguish ridge from lasso. Ridge penalises the sum of the squared coefficients, shrinks them all towards zero without any reaching it, and has a closed-form solution obtained by adding lambda to the diagonal of the normal equations. Lasso penalises the sum of the absolute values, drives some coefficients exactly to zero and thereby selects features, and requires an iterative solver.
5. Why does lasso reach exactly zero when ridge does not? Because the gradient of a squared penalty is proportional to the coefficient and so becomes vanishingly weak near zero, while the gradient of an absolute-value penalty keeps a constant size all the way in and pushes the coefficient through to zero.
6. Give the two practical rules that are easy to forget, with reasons. Do not penalise the intercept, because shrinking it towards zero asserts that the output should be near zero, which depends only on the units. And standardise the features before fitting, because a coefficient's size depends on its feature's units, so an unstandardised feature would be penalised according to whether it was measured in metres or millimetres.
7. How is lambda chosen, and why not from the training error? On a validation set or by cross-validation, searched over a wide range on a logarithmic scale. It cannot be chosen from the training error because that always improves as lambda falls, so it would always select lambda of zero, which is the unregularized fit.
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.