Machine Learning from First Principles

Chapter 5 · Part II: Supervised Learning

Generalization and Regularization

A model that fits its training data perfectly can still be useless. This chapter explains why, splits test error into bias, variance, and noise, and introduces the tools that keep flexible models honest: ridge, lasso, and cross-validation.

After this chapter you will be able to

  • Recognize underfitting and overfitting from training and validation curves.
  • Derive the bias–variance decomposition of the expected squared error.
  • Derive ridge regression, solve it in closed form, and interpret it as MAP estimation.
  • Explain why the lasso produces sparse solutions.
  • Choose hyperparameters with $k$-fold cross-validation.
  • Describe double descent and why very large models can still generalize.

5.1Overfitting and Underfitting

Fit polynomials of increasing degree to 20 noisy samples of a smooth curve. Training error falls steadily, since a higher degree can do everything a lower one can. Test error falls, then rises sharply.

  • Underfitting (low degree): too rigid to follow the curve; both errors high.
  • Overfitting (high degree): bends through individual noisy points; training error tiny, test error large.

The flexibility of a model family is its capacity: polynomial degree, tree depth, the number of neighbors in $k$-NN, network size. Choosing capacity is the central practical problem of machine learning.

5.2The Bias–Variance Decomposition

Imagine repeating the experiment many times: draw a fresh training set $\Data$, fit $\hat f_{\Data}$, predict at a fixed $\vx$. With $y = f(\vx) + \varepsilon$, $\Var(\varepsilon) = \sigma^2$, and average prediction $\bar f(\vx) = \E_{\Data}[\hat f_{\Data}(\vx)]$:

$$\E\big[(y - \hat f_{\Data}(\vx))^2\big] = \underbrace{(f(\vx) - \bar f(\vx))^2}_{\text{bias}^2} + \underbrace{\E_{\Data}\big[(\hat f_{\Data}(\vx) - \bar f(\vx))^2\big]}_{\text{variance}} + \underbrace{\sigma^2}_{\text{noise}}. \tag{5.1}$$
Show derivation

Write $y - \hat f = (f - \bar f) + (\bar f - \hat f) + \varepsilon$, square, and take expectations. Cross terms vanish: $\E\varepsilon = 0$ and $\varepsilon$ is independent of $\Data$; $f - \bar f$ is constant and $\E_{\Data}[\bar f - \hat f] = 0$ by definition of $\bar f$.

  • Bias: how far the average model is from the truth. A line cannot match a curve however much data you have.
  • Variance: how much the model changes between training sets. Flexible models chase each sample's noise.
  • Noise: irreducible; no model predicts the random part of $y$.

More capacity lowers bias and raises variance; more data lowers variance without changing bias.

5.3Ridge Regression

Instead of removing features, regularization keeps them but penalizes large weights:

$$\Loss_{\text{ridge}}(\vw) = \norm{\mX\vw - \vy}_2^2 + \lambda\norm{\vw}_2^2. \tag{5.2}$$

Setting the gradient $2\mX\T(\mX\vw - \vy) + 2\lambda\vw$ to zero:

$$\hat\vw_{\text{ridge}} = (\mX\T\mX + \lambda\mI)^{-1}\mX\T\vy. \tag{5.3}$$

Adding $\lambda\mI$ raises every eigenvalue by $\lambda$, so the matrix is always invertible: ridge also cures collinearity.

Show derivation: what ridge does along each direction

With the SVD $\mX = \mU\mS\mV\T$ and singular values $s_j$, the fitted values are

$$\hat\vy_{\text{ridge}} = \sum_j \vu_j\,\frac{s_j^2}{s_j^2 + \lambda}\,\vu_j\T\vy.$$

Least squares keeps every component; ridge shrinks component $j$ by $s_j^2/(s_j^2 + \lambda)$: barely along high-variance directions, strongly along low-variance directions, where noise has the most influence.

Ridge as MAP. With prior $\vw\sim\Normal(\mathbf 0, \tau^2\mI)$ and Gaussian noise $\sigma^2$, the negative log-posterior is $\frac{1}{2\sigma^2}\norm{\mX\vw - \vy}^2 + \frac{1}{2\tau^2}\norm{\vw}^2$: ridge with $\lambda = \sigma^2/\tau^2$.

Pitfall: do not penalize the intercept, and scale your features

Shrinking the intercept makes no sense; leave it out of the penalty. And $\lambda\sum_j w_j^2$ is only fair when features are on comparable scales, so standardize first.

5.4The Lasso and Sparsity

The lasso uses the $\ell_1$ norm instead: $\Loss_{\text{lasso}}(\vw) = \norm{\mX\vw - \vy}_2^2 + \lambda\norm{\vw}_1$. For moderate $\lambda$, many weights become exactly zero, so the lasso selects features automatically.

Geometry. Penalized problems are equivalent to constrained ones, $\norm{\vw}\le t$. The solution is where the smallest reachable loss ellipse touches the constraint region. The $\ell_2$ ball is round, so the contact point is almost never on an axis. The $\ell_1$ ball is a diamond whose corners lie on the axes, and an ellipse very often touches a corner first.

One dimension. Minimizing $\tfrac12(w - a)^2 + \lambda|w|$ gives the soft-thresholding operator

$$w^\star = \sign(a)\max(|a| - \lambda, 0). \tag{5.5}$$

Small effects become exactly zero and large ones shrink by $\lambda$. Ridge's analog, $w^\star = a/(1 + 2\lambda)$, shrinks everything proportionally and zeroes nothing. The lasso is solved by coordinate descent, soft-thresholding one weight at a time.

5.5Validation and Cross-Validation

Hyperparameters such as degree and $\lambda$ cannot be chosen by training loss (it always prefers maximum capacity) or by test loss (that spoils the test set). $k$-fold cross-validation splits the training data into $k$ folds (usually 5 or 10), fits on $k-1$ folds, evaluates on the remaining one, rotates, and averages. Every example is validated exactly once. After choosing, refit on all training data.

Algorithm 5.1  $k$-fold cross-validation for a hyperparameter $\lambda$
  1. Shuffle and split the training data into folds $F_1,\dots,F_k$.
  2. for each candidate $\lambda$:
    1. for $j = 1..k$: fit on all folds except $F_j$; $e_j \gets$ error on $F_j$
    2. $\mathrm{CV}(\lambda) \gets \frac1k\sum_j e_j$
  3. $\lambda^\star \gets \argmin_\lambda \mathrm{CV}(\lambda)$; refit on all training data.

The one-standard-error rule picks the simplest model within one standard error of the best CV score, trading negligible accuracy for stability.

5.6Beyond the Classical Picture

Deep networks have far more parameters than training examples, can fit randomly shuffled labels perfectly, and still generalize on real labels. Part of the explanation is double descent: as capacity grows past the interpolation threshold where training error hits zero, test error peaks and then falls again. Beyond the threshold many models fit the data exactly, and the optimizer picks a particular one. Gradient descent from zero on least squares, for example, converges to the minimum-norm interpolating solution. The optimizer itself regularizes (implicit regularization).

Frontier note

The U-curve describes the regime below the interpolation threshold; double descent extends the picture beyond it. Why overparameterized networks generalize is still an active research question. In practice, large models use explicit regularization (weight decay, augmentation, dropout; Chapter 16) and their size is set by validation performance and compute budget (Chapter 24).

5.7Implementation

import numpy as np
from sklearn.preprocessing import StandardScaler, PolynomialFeatures
from sklearn.linear_model import RidgeCV, LassoCV
from sklearn.pipeline import make_pipeline

rng = np.random.default_rng(1)
x = rng.uniform(0, 3, size=40)
y = np.sin(2 * x) + rng.normal(0, 0.2, size=40)
Phi = PolynomialFeatures(degree=12, include_bias=False).fit_transform(x[:, None])
Phi = StandardScaler().fit_transform(Phi)          # scale before penalizing

def ridge_fit(X, y, lam):
    Xc, yc = X - X.mean(0), y - y.mean()           # center: intercept unpenalized
    w = np.linalg.solve(Xc.T @ Xc + lam * np.eye(X.shape[1]), Xc.T @ yc)
    return w, y.mean() - X.mean(0) @ w

def cv_error(X, y, lam, k=5):
    folds = np.array_split(rng.permutation(len(y)), k)
    errs = []
    for j in range(k):
        val = folds[j]
        tr = np.concatenate([folds[i] for i in range(k) if i != j])
        w, b = ridge_fit(X[tr], y[tr], lam)
        errs.append(np.mean((X[val] @ w + b - y[val])**2))
    return np.mean(errs)

lams = 10.0 ** np.arange(-4, 3)
scores = [cv_error(Phi, y, lam) for lam in lams]
print("best lambda:", lams[int(np.argmin(scores))])

lasso = make_pipeline(PolynomialFeatures(12, include_bias=False),
                      StandardScaler(), LassoCV(cv=5, max_iter=50000)).fit(x[:, None], y)
print("lasso nonzero weights:", np.sum(lasso[-1].coef_ != 0), "of 12")

5.8Common Pitfalls

Pitfall: tuning on the test set

Choosing $\lambda$ by test error makes the reported test error optimistic. Cross-validate on training data; look at the test set once.

Pitfall: preprocessing outside the cross-validation loop

Standardizing with statistics of the whole data set lets every validation fold influence preprocessing. Fit preprocessing inside each fold; scikit-learn pipelines do this for you.

5.9Summary

  • Training error always falls with capacity; test error is U-shaped below the interpolation threshold.
  • Expected test error = bias² + variance + noise.
  • Ridge: $(\mX\T\mX + \lambda\mI)^{-1}\mX\T\vy$; shrinks low-variance directions most; MAP with a Gaussian prior.
  • Lasso: $\ell_1$ penalty, exact zeros via soft-thresholding.
  • Choose hyperparameters by $k$-fold cross-validation with preprocessing inside the loop.
  • Past the interpolation threshold, test error can fall again; optimizers regularize implicitly.

5.10Exercises

  1. MathFill in the cross-term argument for Equation (5.1). Where is the independence of $\varepsilon$ and $\Data$ used?
  2. MathShow $\hat\vw = \mX\T(\mX\mX\T + \lambda\mI)^{-1}\vy$. When is this form cheaper?
  3. MathDerive the SVD shrinkage formula and the effective degrees of freedom $\mathrm{df}(\lambda) = \sum_j s_j^2/(s_j^2 + \lambda)$.
  4. MathDerive soft-thresholding carefully, using subgradients at $w = 0$.
  5. CodingImplement lasso by coordinate descent and compare with sklearn.linear_model.Lasso (which minimizes $\frac{1}{2n}\norm{\mX\vw-\vy}^2 + \alpha\norm{\vw}_1$).
  6. CodingReproduce double descent with minimum-norm least squares (np.linalg.pinv) on random ReLU features, $p = 5..400$, and 40 training points.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.