Lecture 35 · Regression: a better estimator, and how to tune it

A Better Estimator and Cross-Validation

The ML error is $\sigma^2\sum_i 1/\lambda_i$ over the eigenvalues $\lambda_i$ of $XX^\top$, so small eigenvalues make it blow up. Adding $\lambda I$ before inverting lifts every eigenvalue by $\lambda$. For some $\lambda$, the new estimator $(XX^\top+\lambda I)^{-1}Xy$ has lower mean squared error than ML. Which $\lambda$? Pick it by cross-validation.

Source: this lecture on YouTube (≈20 min). Previous: L34.

Notation: the lecture uses λ for two things. Here $\lambda_1,\dots,\lambda_d$ (with a subscript) are eigenvalues of $XX^\top$, and plain $\lambda$ is the number we add to the diagonal.

1 · The trace is a sum of eigenvalues

The trace is the sum of the diagonal entries, $\operatorname{tr}(A)=\sum_{i=1}^d a_{ii}$, and it also equals the sum of the eigenvalues, $\sum_{i=1}^d\lambda_i(A)$ (a standard fact, from the characteristic polynomial). If $XX^\top$ has eigenvalues $\lambda_1,\dots,\lambda_d$, then $(XX^\top)^{-1}$ has eigenvalues $1/\lambda_1,\dots,1/\lambda_d$ (same eigenvectors, reciprocal eigenvalues). So L34's result becomes

$$\text{MSE}(\hat w_{\text{ML}})=\mathbb E\lVert\hat w_{\text{ML}}-w\rVert^2=\sigma^2\sum_{i=1}^{d}\frac{1}{\lambda_i}.$$

If some $\lambda_i$ is small, $1/\lambda_i$ is huge and so is the error, even with modest noise.

2 · A new estimator, pulled out of a hat

Consider, for some positive real number $\lambda$ and the $d\times d$ identity $I$,

$$\boxed{\;\hat w_{\text{new}}=\big(XX^\top+\lambda I\big)^{-1}Xy\;}\qquad\text{vs.}\qquad \hat w_{\text{ML}}=\big(XX^\top\big)^{-1}Xy .$$

Why would adding $\lambda I$ help? Look at what it does to eigenvalues.

Let $v_1$ be an eigenvector of $A$: $\;Av_1=\lambda_1v_1$.
Then $\;(A+\lambda I)v_1=Av_1+\lambda v_1=(\lambda_1+\lambda)\,v_1$.
So $v_1$ is still an eigenvector, and its eigenvalue moved up by $\lambda$. The eigenvalues of $A+\lambda I$ are $\lambda_1+\lambda,\dots,\lambda_d+\lambda$.
Hence $\;\operatorname{tr}\big((XX^\top+\lambda I)^{-1}\big)=\sum_{i=1}^{d}\dfrac{1}{\lambda_i+\lambda}$: every denominator grows, so the sum shrinks.

The intuition: the error was large because the $\lambda_i$ were small. We can't touch $\sigma^2$, but artificially raising the eigenvalues makes the feature term smaller, and we hope the mean squared error goes down with it.

3 · The existence theorem

Theorem (stated informally, not proved in the course). There exists a $\lambda$ such that $\hat w_{\text{new}}=(XX^\top+\lambda I)^{-1}Xy$ has lower mean squared error than $\hat w_{\text{ML}}$. On average, it's a better estimator.

The catch: it only says such a $\lambda$ exists. The right value depends on the data (and on the unknown $w$), so there's no formula for it.

Why only "exists", going beyond the video. The new estimator is biased: $\mathbb E[\hat w_{\text{new}}]=(XX^\top+\lambda I)^{-1}XX^\top w\neq w$, so it pays a bias price for its lower variance. Writing $u_i$ for the eigenvectors of $XX^\top$, $$\mathbb E\lVert\hat w_{\text{new}}-w\rVert^2=\underbrace{\sigma^2\sum_{i}\frac{\lambda_i}{(\lambda_i+\lambda)^2}}_{\text{variance}}+\underbrace{\lambda^2\sum_i\frac{(u_i^\top w)^2}{(\lambda_i+\lambda)^2}}_{\text{bias}^2}.$$ At $\lambda=0$ this is L34's $\sigma^2\sum_i 1/\lambda_i$. The derivative at $\lambda=0$ is negative, so a small enough $\lambda>0$ always helps; too large a $\lambda$ shrinks $\hat w$ towards 0 and the bias takes over. The demo plots both parts.

Exact mean squared error of $(XX^\top+\lambda I)^{-1}Xy$ as $\lambda$ varies (log scale), for two features with correlation ρ, n = 30, true $w=(1,\,-0.5)$. The dashed line is the ML error, $\lambda=0$.

noise σ = feature correlation ρ =

MSE of ŵ_newvariance partbias² partMSE of ŵ_ML

–

MSE of ŵ_ML

–

best MSE of ŵ_new

–

at λ =

4 · Finding λ in practice: validation

We want the $\lambda$ that does well on test data we don't have yet. So mimic it: hold back part of the training data.

Split the $n$ training points into a train set (say 80%) and a validation set (20%).
For each candidate $\lambda$: compute $\hat w_{\text{new}}=(XX^\top+\lambda I)^{-1}Xy$ using only the train set.
Predict the labels of the validation points and measure the error against their true labels.
Pick the $\lambda$ with the least validation error.

The validation set is a proxy for the test data. The weak spot: with one random split you may be unlucky, and that 20% may not represent the data well, so the error you measure for each $\lambda$ isn't the true error.

5 · K-fold cross-validation

Do the validation several times and average.

Divide the data into $K$ equal parts, folds $F_1,\dots,F_K$ (10,000 points and 10 folds: 1,000 points each).
For each $i$: train on all folds except $F_i$, validate on $F_i$. With $K=3$: train on $F_1,F_2$ and validate on $F_3$; train on $F_1,F_3$ and validate on $F_2$; train on $F_2,F_3$ and validate on $F_1$.
For every $\lambda$, average the $K$ validation errors, and pick the $\lambda$ with the least average error.

Choice of K	Trade-off
Larger $K$	Generally better, because it averages over more train/validation splits.
$K=n$: leave-one-out (LOOCV)	Train on $n-1$ points, test on the one left out, for every point. The extreme case.
Huge $n$ (a billion points)	LOOCV means a billion fits, which is a computational nightmare. Choose $K$ by the time and resources you have.

30 noisy points, 10 strongly correlated features (more features relative to points makes ML shaky). The strip shows how the points are split into folds. The curve is the $K$-fold cross-validation error for each $\lambda$; the faint curve is the true error on 2,000 fresh test points, which cross-validation never sees.

K-fold CV errortrue test errorλ chosen by CV

–

λ chosen by CV

–

its test error

–

test error of ŵ_ML (λ = 0)

–

fits computed

6 · Still open: where does this estimator come from?

We argued for $\hat w_{\text{new}}$ by intuition and an existence theorem, and tuned $\lambda$ by cross-validation. Is there a principled way to arrive at it? Yes, and we've met the tool before: the alternative to maximum likelihood from unsupervised estimation (L21). Applied to supervised learning, it gives this estimator, which is the subject of L36.

Key takeaways

$\operatorname{tr}(A)=\sum_i\lambda_i(A)$, and $A^{-1}$ has eigenvalues $1/\lambda_i$, so $\text{MSE}(\hat w_{\text{ML}})=\sigma^2\sum_i 1/\lambda_i$. Small eigenvalues hurt.
$A+\lambda I$ has the same eigenvectors and eigenvalues $\lambda_i+\lambda$.
$\hat w_{\text{new}}=(XX^\top+\lambda I)^{-1}Xy$: for some $\lambda$ its MSE beats $\hat w_{\text{ML}}$ (existence only).
Choose $\lambda$ by validation: train on part of the data, evaluate on the held-out part, keep the best $\lambda$.
$K$-fold CV averages over $K$ splits; LOOCV is $K=n$. Bigger $K$ is better but costs more.