Part I · Foundations of supervised learning | least squares, the normal equations and projection, Gaussian likelihood, standard errors, Gauss–Markov, basis expansions and splines, ridge and lasso, Bayesian linear regression, omitted variables and Frisch–Waugh–Lovell | reading: James et al., ISLP, ch. 3 and 6; Hastie, Tibshirani & Friedman, ESL, ch. 3
Linear regression is the oldest method in this course and still among the most used. It is also the cleanest place to see, with nothing hidden, ideas that return in every later lecture. Fitting a model is minimising a loss. The minimiser has a geometric meaning, here a projection. The same estimate can be read as a maximum-likelihood estimate or as a Bayesian posterior. Penalising complexity trades bias for variance. And a coefficient that predicts well need not tell you what would happen if you intervened.
By the end of this lecture you should be able to derive the least-squares estimate from the normal equations and explain it as an orthogonal projection; state the Gaussian model behind it, compute standard errors and confidence intervals, and state and prove the Gauss–Markov theorem; build non-linear fits from linear models with basis expansions; explain ridge and lasso as penalised least squares, derive the soft-thresholding formula, and say why the lasso produces exact zeros; derive the posterior of Bayesian linear regression and connect it to ridge; and use the omitted-variable-bias formula and the Frisch–Waugh–Lovell theorem to reason about what a regression coefficient means.
Start with one feature. Given pairs \((x_i,y_i)\), we want the line \(y=b_0+b_1x\) that best predicts \(y\) from \(x\). Following Lecture 1, "best" means smallest empirical risk under squared loss: choose \(b_0,b_1\) to minimise the residual sum of squares
$$\mathrm{RSS}(b_0,b_1)=\sum_{i=1}^n\big(y_i-b_0-b_1x_i\big)^2.$$Each term is the area of a square drawn on the vertical gap between a point and the line. Try it yourself before any formula.
However you move it, your total area stays above the least-squares value. For one feature the minimiser has a familiar closed form: setting both partial derivatives of RSS to zero gives
$$\hat b_1=\frac{\sum_i(x_i-\bar x)(y_i-\bar y)}{\sum_i(x_i-\bar x)^2},\qquad\hat b_0=\bar y-\hat b_1\bar x.$$The slope is the projection coefficient of Lecture 2 applied to the centred data, and the line always passes through the point of means \((\bar x,\bar y)\).
20,640 census block groups in California, each with the median income, median house age, total rooms and bedrooms, population, number of households, latitude, longitude and median house value. Collected from the 1990 US census by Pace & Barry (1997); we use the copy distributed with Géron's Hands-On Machine Learning. We drop the 207 rows with missing bedroom counts (20,433 remain) and, as in scikit-learn's version, convert totals to per-household averages. Values are in units of $100,000. Note that values were capped at $500,001 when the data were collected (965 block groups sit at the cap), a common kind of quirk in real data.
import numpy as np import pandas as pd raw = pd.read_csv('data/housing.csv').dropna() # 1990 census: one row per California block group cal = pd.DataFrame({ 'MedInc': raw.median_income, # median household income, in $10,000s 'HouseAge': raw.housing_median_age, 'AveRooms': raw.total_rooms / raw.households, 'AveBedrms': raw.total_bedrooms / raw.households, 'Population': raw.population, 'AveOccup': raw.population / raw.households, 'Latitude': raw.latitude, 'Longitude': raw.longitude, 'Value': raw.median_house_value / 1e5}) # median house value, in $100,000s print(cal.shape) x, y = cal['MedInc'].to_numpy(), cal['Value'].to_numpy() X1 = np.column_stack([np.ones_like(x), x]) # intercept column + income b = np.linalg.solve(X1.T @ X1, X1.T @ y) # the normal equations r2 = 1 - np.sum((y - X1 @ b) ** 2) / np.sum((y - y.mean()) ** 2) print('intercept, slope =', np.round(b, 4), ' R^2 =', round(r2, 4))
(20433, 9) intercept, slope = [0.4491 0.4184] R^2 = 0.4738
Each extra $10,000 of median income goes with about $41,800 of extra median house value, and income alone explains 47% of the variation (\(R^2=0.474\)). The coefficient of determination \(R^2=1-\mathrm{RSS}/\sum_i(y_i-\bar y)^2\) compares the model's squared error with that of the best constant, the mean (Lecture 1, Example 1.1).
Using the fitted line (intercept 0.4491, slope 0.4184), what median house value does it predict for a block group with median income $50,000 (that is, MedInc = 5)?
Adrien-Marie Legendre published the method of least squares in 1805, in an appendix to a book on computing the orbits of comets. Carl Friedrich Gauss published it in 1809, claimed to have used it since 1795, and gave it a probabilistic justification (Section 3). Gauss had used it to predict where the dwarf planet Ceres, discovered in January 1801 and then lost behind the Sun, would reappear; astronomers found it that December almost exactly where he said. The word "regression" came later, from Francis Galton's 1886 study of the heights of parents and children: very tall parents tended to have children closer to average height, which he called "regression towards mediocrity". (Galton also founded the eugenics movement; the statistical idea long outlived its original motivation.)
With \(p\) features, collect them into an \(n\times p\) design matrix \(X\) (its first column is usually all ones, for the intercept). The model predicts \(\hat y=X\beta\), and least squares minimises \(\|y-X\beta\|^2\). Lecture 2 projected a vector onto a line. Here the predictions \(X\beta\) range over the whole column space of \(X\), a \(p\)-dimensional flat subspace of \(\mathbb R^n\), and the best prediction is the point of that subspace closest to \(y\).
\(\hat\beta\) minimises \(\|y-X\beta\|^2\) if and only if it solves the normal equations
$$X^\top X\,\hat\beta=X^\top y,$$equivalently, the residual \(r=y-X\hat\beta\) is orthogonal to every column of \(X\).
If \(X\) has full column rank, the solution is unique,
$$\hat\beta=(X^\top X)^{-1}X^\top y,$$and the fitted values are \(\hat y=Hy\) with the hat matrix
$$H=X(X^\top X)^{-1}X^\top,$$the orthogonal projection onto the column space of \(X\).
Suppose \(X^\top(y-X\hat\beta)=0\). For any \(\beta\), write
$$y-X\beta=(y-X\hat\beta)+X(\hat\beta-\beta).$$The two pieces are orthogonal, because the first is orthogonal to every column of \(X\) and the second is a combination of them. So by Pythagoras
$$\|y-X\beta\|^2=\|y-X\hat\beta\|^2+\|X(\hat\beta-\beta)\|^2\ \ge\ \|y-X\hat\beta\|^2.$$Hence \(\hat\beta\) is a minimiser.
Conversely, at a minimiser the gradient \(-2X^\top(y-X\beta)\) (Lecture 2, Example 2.1) must vanish. If \(X\) has full column rank then \(X^\top X\) is invertible (Exercise 6 of Lecture 2), so the solution is unique, and \(\hat y=X\hat\beta=Hy\).
\(H\) is symmetric and
$$H^2=X(X^\top X)^{-1}X^\top X(X^\top X)^{-1}X^\top=H:$$an orthogonal projection. \(\square\)
Now all eight California features. In practice nobody inverts \(X^\top X\): numerical libraries solve least squares through a QR or singular value decomposition, which avoids squaring the condition number (Lecture 2, Section 3).
from sklearn.model_selection import train_test_split feats = ['MedInc', 'HouseAge', 'AveRooms', 'AveBedrms', 'Population', 'AveOccup', 'Latitude', 'Longitude'] tr, te = train_test_split(cal, test_size=0.2, random_state=0) Xtr = np.column_stack([np.ones(len(tr)), tr[feats]]) Xte = np.column_stack([np.ones(len(te)), te[feats]]) ytr, yte = tr['Value'].to_numpy(), te['Value'].to_numpy() beta = np.linalg.lstsq(Xtr, ytr, rcond=None)[0] # least squares (via the SVD, numerically safe) resid = ytr - Xtr @ beta print('largest |X^T r| =', f'{np.abs(Xtr.T @ resid).max():.1e}', ' (residuals orthogonal to every column)') print(pd.Series(beta, index=['intercept'] + feats).round(4).to_string()) rmse = lambda X, t: np.sqrt(np.mean((X @ beta - t) ** 2)) print(f'train RMSE {rmse(Xtr, ytr):.4f} test RMSE {rmse(Xte, yte):.4f} (in $100,000s)')
largest |X^T r| = 4.9e-06 (residuals orthogonal to every column) intercept -37.4077 MedInc 0.4325 HouseAge 0.0095 AveRooms -0.1010 AveBedrms 0.6106 Population -0.0000 AveOccup -0.0034 Latitude -0.4252 Longitude -0.4397 train RMSE 0.7239 test RMSE 0.7263 (in $100,000s)
The first line of output checks Theorem 3.1: the residuals are orthogonal to every column, up to rounding in sums of 16,000 terms. Training and test errors are almost equal: with 16,346 rows and 9 parameters there is little room to overfit. Now look at the coefficients, and at one pair in particular.
The coefficient of AveRooms is negative (−0.10), while AveBedrms is positive (+0.61). Bigger homes are worth more. What does the negative sign mean?
Least squares reduces to solving a linear system, \(X^\top X\beta=X^\top y\). In 2009 Harrow, Hassidim and Lloyd (HHL) gave a quantum algorithm that "solves" an \(N\times N\) system \(Ax=b\) in time growing only like \(\log N\), and Wiebe, Braun and Lloyd (2012) adapted it to least-squares fitting. This looked like an exponential speed-up for regression. Scott Aaronson's 2015 essay "Read the fine print" lists the catches:
Later work found classical randomised algorithms that match some of these quantum algorithms when the data matrix has low rank ("dequantisation", Lecture 16). Quantum linear algebra remains an active field, but the honest summary is that a speed-up for practical regression has not been demonstrated.
So far least squares is a recipe. Gauss's justification was a model of where the data come from: the truth is linear, and each observation adds independent Gaussian noise,
$$y=X\beta+\varepsilon,\qquad\varepsilon_1,\dots,\varepsilon_n\overset{\text{iid}}{\sim}\mathcal N(0,\sigma^2).$$Under the Gaussian linear model, the maximum-likelihood estimate of \(\beta\) is the least-squares estimate, and the maximum-likelihood estimate of \(\sigma^2\) is \(\mathrm{RSS}/n\).
The density of \(y_i\) is
$$(2\pi\sigma^2)^{-1/2}\exp\!\big(-(y_i-x_i^\top\beta)^2/2\sigma^2\big),$$so the log-likelihood is
$$\ell(\beta,\sigma^2)=-\frac n2\log(2\pi\sigma^2)-\frac1{2\sigma^2}\|y-X\beta\|^2.$$For every fixed \(\sigma^2\), maximising over \(\beta\) means minimising \(\|y-X\beta\|^2\), so \(\hat\beta\) is the least-squares estimate. Setting
$$\partial\ell/\partial\sigma^2=-\frac n{2\sigma^2}+\frac{\mathrm{RSS}}{2\sigma^4}=0$$gives \(\hat\sigma^2=\mathrm{RSS}/n\). \(\square\)
The model also tells us how much \(\hat\beta\) would vary if we collected new data, which is what a standard error measures.
Under the linear model with \(\mathbb E[\varepsilon]=0\) and \(\mathrm{Cov}(\varepsilon)=\sigma^2I\), and \(X\) fixed with full column rank:
$$\mathbb E[\hat\beta]=\beta,\qquad\mathrm{Cov}(\hat\beta)=\sigma^2(X^\top X)^{-1},\qquad\mathbb E\Big[\frac{\mathrm{RSS}}{n-p}\Big]=\sigma^2.$$If the noise is Gaussian,
$$\hat\beta\sim\mathcal N\big(\beta,\sigma^2(X^\top X)^{-1}\big),$$and \((\hat\beta_j-\beta_j)/\widehat{\mathrm{se}}_j\) has a \(t\) distribution with \(n-p\) degrees of freedom, where
$$\widehat{\mathrm{se}}_j^2=\hat\sigma^2\big[(X^\top X)^{-1}\big]_{jj}.$$Substitute \(y=X\beta+\varepsilon\):
$$\hat\beta=(X^\top X)^{-1}X^\top(X\beta+\varepsilon)=\beta+(X^\top X)^{-1}X^\top\varepsilon.$$So \(\mathbb E[\hat\beta]=\beta\), and with \(A=(X^\top X)^{-1}X^\top\),
$$\mathrm{Cov}(\hat\beta)=A\,\sigma^2I\,A^\top=\sigma^2(X^\top X)^{-1}.$$For the residuals, \(r=(I-H)y=(I-H)\varepsilon\) because \((I-H)X=0\). So \(\mathrm{RSS}=\varepsilon^\top(I-H)\varepsilon\) (using \((I-H)^2=I-H\)), and
$$\mathbb E[\mathrm{RSS}]=\sigma^2\operatorname{tr}(I-H)=\sigma^2\big(n-\operatorname{tr}H\big)=\sigma^2(n-p),$$since \(\mathbb E[\varepsilon^\top M\varepsilon]=\sigma^2\operatorname{tr}M\) and
$$\operatorname{tr}H=\operatorname{tr}\big((X^\top X)^{-1}X^\top X\big)=p.$$Dividing by \(n-p\) removes the bias: each fitted parameter uses up one dimension of the noise.
The \(t\) distribution follows from the independence of \(\hat\beta\) and RSS under Gaussian noise (see ESL, Section 3.2). \(\square\)
from scipy import stats n, p = Xtr.shape sigma2 = resid @ resid / (n - p) # unbiased estimate of the noise variance cov = sigma2 * np.linalg.inv(Xtr.T @ Xtr) # Cov(beta-hat) = sigma^2 (X^T X)^{-1} se = np.sqrt(np.diag(cov)) t_crit = stats.t.ppf(0.975, n - p) table = pd.DataFrame({'coef': beta, 'se': se, 't': beta / se, 'ci_low': beta - t_crit * se, 'ci_high': beta + t_crit * se}, index=['intercept'] + feats) print('noise sd estimate:', round(np.sqrt(sigma2), 4)) print(table.loc[['MedInc', 'AveRooms', 'AveBedrms', 'Latitude']].round(4).to_string())
noise sd estimate: 0.7241
coef se t ci_low ci_high
MedInc 0.4325 0.0047 92.2814 0.4233 0.4417
AveRooms -0.1010 0.0065 -15.4192 -0.1138 -0.0881
AveBedrms 0.6106 0.0312 19.6004 0.5496 0.6717
Latitude -0.4252 0.0081 -52.5442 -0.4410 -0.4093
These intervals are narrow because \(n\) is large. They are honest only to the extent that the model's assumptions hold, and here they do not quite: house values are capped, errors are larger for expensive areas, and nearby block groups share unmeasured features, so the noise is neither constant nor independent. The point estimates may still predict well; the standard errors are too optimistic. This gap between "good predictor" and "trustworthy inference" is a theme of the course.
A coefficient of 0.6106 has standard error 0.0312. What is its \(t\)-statistic?
Least squares has a second justification that does not need Gaussian noise at all.
Under the linear model with \(\mathbb E[\varepsilon]=0\), \(\mathrm{Cov}(\varepsilon)=\sigma^2I\) and \(X\) of full column rank, the least-squares estimate is the best linear unbiased estimator: for any other estimator \(\tilde\beta=Cy\) that is linear in \(y\) and unbiased for every \(\beta\),
$$\mathrm{Cov}(\tilde\beta)-\mathrm{Cov}(\hat\beta)$$is positive semi-definite.
In particular every coefficient, and every linear combination \(a^\top\beta\), has variance at least as large under \(\tilde\beta\).
Write
$$C=(X^\top X)^{-1}X^\top+D.$$Unbiasedness for every \(\beta\) means \(\mathbb E[Cy]=CX\beta=\beta\) for all \(\beta\), so \(CX=I\), which forces \(DX=0\). Then
$$\mathrm{Cov}(\tilde\beta)=\sigma^2CC^\top=\sigma^2\Big[(X^\top X)^{-1}+(X^\top X)^{-1}X^\top D^\top+DX(X^\top X)^{-1}+DD^\top\Big]$$ $$=\sigma^2(X^\top X)^{-1}+\sigma^2DD^\top,$$since the cross terms contain \(DX=0\). \(DD^\top\) is positive semi-definite (\(a^\top DD^\top a=\|D^\top a\|^2\ge0\)), which proves the claim. \(\square\)
"Best" here is within a restricted class: linear and unbiased. Section 5 shows that giving up unbiasedness can reduce the overall error, which is the whole point of regularisation.
"Linear" in linear regression refers to the parameters, not the features. Any fixed transformations \(\phi_1(x),\dots,\phi_m(x)\) of the inputs can be used as columns of the design matrix, and the model \(\hat y=\sum_j\beta_j\phi_j(x)\) is still fitted by least squares. Common choices:
Given knots \(\kappa_1<\dots<\kappa_K\), a cubic spline is a function that is a cubic polynomial on each interval between consecutive knots, with the function and its first two derivatives continuous at each knot.
Cubic splines with \(K\) knots form a vector space of dimension \(K+4\) (or \(K+2\) once the outermost knots are treated as boundaries, as scikit-learn does), with a convenient basis of local "bump" functions called B-splines, each non-zero on only a few intervals.
Polynomials are global: changing the data near \(t=50\) ms changes the fit near \(t=5\) ms, which is why the high-degree polynomials of Lecture 1 swung wildly. A spline is local: each B-spline basis function lives on a few neighbouring intervals, so the fit can bend sharply where the data bend and stay flat elsewhere.
from sklearn.preprocessing import SplineTransformer from sklearn.linear_model import LinearRegression from sklearn.pipeline import make_pipeline from sklearn.model_selection import KFold, cross_val_score mc = pd.read_csv('../mcycle.csv') # the crash-helmet data of Lecture 1 t, a = mc[['times']].to_numpy(), mc['accel'].to_numpy() perm = np.random.default_rng(0).permutation(len(t)) trn, tst = perm[:40], perm[40:] # the same 40 / 93 split as Lecture 1 cv = KFold(5, shuffle=True, random_state=0) scores = {} for k in range(4, 13): # cubic splines with k equally spaced knots model = make_pipeline(SplineTransformer(n_knots=k, degree=3), LinearRegression()) scores[k] = -cross_val_score(model, t[trn], a[trn], cv=cv, scoring='neg_root_mean_squared_error').mean() k_best = min(scores, key=scores.get) model = make_pipeline(SplineTransformer(n_knots=k_best, degree=3), LinearRegression()).fit(t[trn], a[trn]) print('5-fold CV RMSE by number of knots:', {k: round(float(v), 1) for k, v in scores.items()}) print(f'chosen {k_best} knots; test RMSE {np.sqrt(np.mean((model.predict(t[tst]) - a[tst]) ** 2)):.1f} g')
5-fold CV RMSE by number of knots: {4: 39.1, 5: 42.6, 6: 47.6, 7: 28.6, 8: 183.5, 9: 903.2, 10: 27.7, 11: 37.8, 12: 44.6}
chosen 10 knots; test RMSE 35.7 g
That is disappointing, and instructive. The cross-validation errors jump around (183 at 8 knots, 903 at 9) because with only 32 points per fold, some intervals between knots contain one point or none, and the coefficients there are barely determined. Test RMSE 35.7 g is no better than the best polynomial (34.3 g) and worse than kNN (25.5 g). A flexible basis needs something to stop it fitting noise. That something is a penalty, and with it this same spline basis beats both (Section 5).
The model \(\hat y=\beta_0+\beta_1x+\beta_2x^2+\beta_3\log x\) is , so it can be fitted .
When there are many features relative to the number of observations, or when features are strongly correlated, least squares becomes unstable: \(X^\top X\) is nearly singular, coefficients become huge and of opposite signs, and the variance of \(\hat\beta\) (Theorem 3.3) explodes. Regularisation adds a penalty on the size of the coefficients.
For a penalty level \(\lambda\ge0\),
$$\hat\beta^{\text{ridge}}=\operatorname*{arg\,min}_\beta\ \frac12\|y-X\beta\|^2+\frac\lambda2\|\beta\|_2^2,$$ $$\hat\beta^{\text{lasso}}=\operatorname*{arg\,min}_\beta\ \frac12\|y-X\beta\|^2+\lambda\|\beta\|_1.$$The intercept is usually left unpenalised, and features are standardised first so that one penalty treats them alike.
Software scales these objectives differently (scikit-learn's Lasso divides the squared error by \(n\)), so always check the convention before comparing values of \(\lambda\).
For every \(\lambda>0\),
$$\hat\beta^{\text{ridge}}=(X^\top X+\lambda I)^{-1}X^\top y,$$which exists even when \(X^\top X\) is singular.
In terms of the SVD \(X=\sum_i\sigma_iu_iv_i^\top\),
$$\hat\beta^{\text{ridge}}=\sum_i\frac{\sigma_i}{\sigma_i^2+\lambda}\,(u_i^\top y)\,v_i,$$so ridge shrinks the least-squares solution most in the directions where \(X\) has small singular values, the poorly determined directions.
The gradient of the objective is \(-X^\top(y-X\beta)+\lambda\beta\); setting it to zero gives
$$(X^\top X+\lambda I)\beta=X^\top y.$$The matrix \(X^\top X+\lambda I\) has eigenvalues \(\sigma_i^2+\lambda>0\), so it is invertible, and the objective is strictly convex, so this is the unique minimiser.
In the SVD basis,
$$X^\top X+\lambda I=V(\Sigma^2+\lambda I)V^\top$$and
$$X^\top y=V\Sigma U^\top y,$$which gives the sum. Least squares is the case \(\lambda=0\), with factors \(1/\sigma_i\), which blow up when \(\sigma_i\) is small. \(\square\)
The lasso has no closed form in general, but in one special case it does, and the formula shows why the lasso sets coefficients exactly to zero.
Suppose \(X^\top X=I\), and let \(z=X^\top y\) be the least-squares solution. Then
$$\hat\beta^{\text{ridge}}_j=\frac{z_j}{1+\lambda},\qquad\hat\beta^{\text{lasso}}_j=S_\lambda(z_j)=\operatorname{sign}(z_j)\,\max\big(|z_j|-\lambda,\,0\big).$$Ridge shrinks every coefficient by the same factor and never reaches zero. The lasso subtracts \(\lambda\) from each coefficient's size and sets any coefficient smaller than \(\lambda\) to exactly zero.
Since \(X^\top X=I\), the projection identity from Theorem 3.1 gives
$$\frac12\|y-X\beta\|^2=\frac12\|y-Xz\|^2+\frac12\|\beta-z\|^2.$$The first term does not depend on \(\beta\), so both problems separate into one-dimensional problems, one per coordinate.
Ridge: minimise \(\tfrac12(b-z_j)^2+\tfrac\lambda2b^2\); setting the derivative to zero gives \(b=z_j/(1+\lambda)\).
Lasso: minimise
$$g(b)=\frac12(b-z_j)^2+\lambda|b|.$$The three cases together are \(S_\lambda(z_j)\). \(\square\)
With an orthonormal design and \(\lambda=1\), a least-squares coefficient of \(-2.5\) becomes what lasso coefficient? (And what happens to a coefficient of 0.7?)
Geometrically, each penalised problem is equivalent to minimising the squared error inside a budget: \(\|\beta\|_2\le t\) for ridge (a disc) or \(\|\beta\|_1\le t\) for the lasso (a diamond). The solution is where the smallest contour of the squared error touches the budget region. A diamond has corners on the axes, and contours often touch there first, which puts the solution exactly on an axis: one coefficient is zero.
Now the real data. With all 16,346 training rows and 8 features, penalties hardly matter: there is enough data to pin down 9 coefficients. Regularisation earns its keep when the number of features is large relative to the number of observations. So take only 200 training rows, log the four skewed features, and add all squares and pairwise products: 44 features.
import warnings from sklearn.preprocessing import PolynomialFeatures, StandardScaler from sklearn.linear_model import RidgeCV, LassoCV warnings.filterwarnings('ignore') # silence lasso convergence chatter at tiny penalties def logged(df): # log the four skewed features d = df[feats].copy() for c in ['AveRooms', 'AveBedrms', 'Population', 'AveOccup']: d[c] = np.log(d[c]) return d small = tr.sample(200, random_state=1) # a small training set ... poly = make_pipeline(PolynomialFeatures(2, include_bias=False), StandardScaler()) Ps, Pt = poly.fit_transform(logged(small)), poly.transform(logged(te)) # ... with 44 features print('features:', Ps.shape[1], ' training rows:', Ps.shape[0]) models = {'least squares': LinearRegression(), 'ridge': RidgeCV(alphas=np.logspace(-3, 4, 60), cv=5), 'lasso': LassoCV(alphas=np.logspace(-3, 0, 50), cv=5, max_iter=100_000, random_state=0)} for name, m in models.items(): m.fit(Ps, small['Value']) err = np.sqrt(np.mean((m.predict(Pt) - yte) ** 2)) print(f'{name:14s} test RMSE {err:.4f} non-zero coefficients {np.sum(m.coef_ != 0):2d} largest |coef| {np.abs(m.coef_).max():6.2f}') print('penalties chosen by CV: ridge', round(models['ridge'].alpha_, 2), ' lasso', round(models['lasso'].alpha_, 4)) base = LinearRegression().fit(logged(small), small['Value']) print('for comparison, 8 features, least squares: test RMSE', round(np.sqrt(np.mean((base.predict(logged(te)) - yte) ** 2)), 4))
features: 44 training rows: 200 least squares test RMSE 1.0307 non-zero coefficients 44 largest |coef| 50.58 ridge test RMSE 0.7023 non-zero coefficients 44 largest |coef| 0.24 lasso test RMSE 0.7086 non-zero coefficients 9 largest |coef| 0.65 penalties chosen by CV: ridge 18.67 lasso 0.0339 for comparison, 8 features, least squares: test RMSE 0.6909
Unpenalised least squares on 44 features overfits badly (test RMSE 1.03, with a coefficient of size 50). Ridge pulls every coefficient towards zero, and its largest becomes 0.24; the lasso keeps only 9 of the 44. Both cut the test error by about a third. Neither beats the plain 8-feature model (0.69): 200 rows are not enough to learn interactions, and the honest conclusion is that the extra features were not worth having. Regularisation protected us from a bad modelling choice; cross-validation would have warned us against it.
Under the lasso, income enters first and dominates; occupancy and house age follow. Latitude and longitude, whose coefficients in the unpenalised fit are as large as income's, enter late. They are strongly correlated with each other (California runs diagonally from north-west to south-east), and individually each says little; together they locate a block group along or away from the coast. The lasso tends to pick one variable from a correlated group and ignore the rest, while ridge spreads weight across them. Neither is "right"; they encode different assumptions about how the truth is built.
Back to the crash-helmet data. A cubic spline with 15 knots and a ridge penalty chosen by cross-validation (a penalised regression spline):
from sklearn.linear_model import Ridge from sklearn.model_selection import GridSearchCV pspline = make_pipeline(SplineTransformer(n_knots=15, degree=3), Ridge()) # many knots, plus a ridge penalty search = GridSearchCV(pspline, {'ridge__alpha': np.logspace(-4, 2, 40)}, cv=cv, scoring='neg_root_mean_squared_error').fit(t[trn], a[trn]) pred = search.predict(t[tst]) print('alpha chosen by CV:', round(search.best_params_['ridge__alpha'], 4)) print(f'penalised spline: CV RMSE {-search.best_score_:.1f} g, test RMSE {np.sqrt(np.mean((pred - a[tst]) ** 2)):.1f} g')
alpha chosen by CV: 0.0588 penalised spline: CV RMSE 24.7 g, test RMSE 24.4 g
Test RMSE 24.4 g, better than kNN (25.5), the best polynomial (34.3) and the unpenalised spline (35.7). Rich basis plus penalty is a pattern worth remembering: smoothing splines, kernel methods (Lecture 7) and heavily over-parameterised neural networks with weight decay (Lecture 10) all follow it.
Why does the lasso produce coefficients that are exactly zero, while ridge does not?
Penalising the size of a solution goes back to Andrey Tikhonov's work in the 1940s and 1960s on "ill-posed" inverse problems in physics, where tiny measurement errors produce huge errors in the solution. Arthur Hoerl and Robert Kennard introduced ridge regression to statistics in 1970, for regressions with highly correlated predictors; the name echoes Hoerl's earlier "ridge analysis" of response surfaces. Robert Tibshirani's lasso (1996) arrived when statisticians began to face data with more variables than observations, such as gene-expression arrays. A decade later Emmanuel Candès, Justin Romberg, Terence Tao and David Donoho showed that \(\ell_1\) penalties can recover sparse signals from far fewer measurements than classical theory required ("compressed sensing"), an idea now used to speed up MRI scans.
The Bayesian view treats \(\beta\) as uncertain and describes that uncertainty with a probability distribution: a prior before seeing data, updated by Bayes' theorem into a posterior. With a Gaussian prior and Gaussian noise everything stays Gaussian, and the update has a closed form.
Let \(y\mid\beta\sim\mathcal N(X\beta,\sigma^2I)\) with \(\sigma^2\) known, and prior \(\beta\sim\mathcal N(0,\tau^2I)\). Then the posterior is \(\beta\mid y\sim\mathcal N(m,S)\) with
$$S=\Big(\frac{X^\top X}{\sigma^2}+\frac{I}{\tau^2}\Big)^{-1},\qquad m=\frac{S\,X^\top y}{\sigma^2}.$$The posterior mean equals the ridge estimate with \(\lambda=\sigma^2/\tau^2\).
For a new input \(x_*\), the posterior predictive distribution of \(y_*\) is
$$\mathcal N\big(x_*^\top m,\ \sigma^2+x_*^\top Sx_*\big):$$noise plus parameter uncertainty.
By Bayes' theorem the posterior density is proportional to likelihood times prior, so its log is, up to a constant,
$$-\frac1{2\sigma^2}\|y-X\beta\|^2-\frac1{2\tau^2}\|\beta\|^2=-\frac12\beta^\top\Big(\frac{X^\top X}{\sigma^2}+\frac I{\tau^2}\Big)\beta+\frac{y^\top X\beta}{\sigma^2}+\text{const}.$$A log-density that is a quadratic in \(\beta\) with matrix \(-\tfrac12S^{-1}\) and linear term \(b^\top\beta\) belongs to \(\mathcal N(Sb,S)\) (complete the square: \(-\tfrac12(\beta-Sb)^\top S^{-1}(\beta-Sb)\) expands to the same thing). Here \(b=X^\top y/\sigma^2\), giving \(m\).
Multiplying \(S^{-1}m=X^\top y/\sigma^2\) by \(\sigma^2\) gives
$$(X^\top X+\frac{\sigma^2}{\tau^2}I)m=X^\top y,$$the ridge equations.
For prediction, \(y_*=x_*^\top\beta+\varepsilon_*\) is a sum of independent Gaussians:
$$x_*^\top\beta\sim\mathcal N(x_*^\top m,x_*^\top Sx_*)$$and
$$\varepsilon_*\sim\mathcal N(0,\sigma^2).\qquad\square$$With no data the lines fan out in every direction (the prior). Each penguin rules out lines far from it, and the fan narrows; far from the data the band widens again, because the slope is uncertain and errors in slope grow with distance. Make the prior tight (small \(\tau\)) and the lines are held near zero slope until a lot of data arrives: a strong prior is a heavy penalty.
from palmerpenguins import load_penguins pg = load_penguins().dropna(subset=['flipper_length_mm', 'body_mass_g']) fx = (pg.flipper_length_mm - pg.flipper_length_mm.mean()) / pg.flipper_length_mm.std() fy = (pg.body_mass_g - pg.body_mass_g.mean()) / pg.body_mass_g.std() Xall, yall = np.column_stack([np.ones(len(fx)), fx]), fy.to_numpy() def posterior(X, t, tau2=1.0, sigma2=0.25): # prior w ~ N(0, tau2 I), noise variance sigma2 S = np.linalg.inv(X.T @ X / sigma2 + np.eye(X.shape[1]) / tau2) m = S @ X.T @ t / sigma2 return m, S idx = np.random.default_rng(3).permutation(len(yall)) for n_obs in [2, 10, 342]: m, S = posterior(Xall[idx[:n_obs]], yall[idx[:n_obs]]) print(f'n = {n_obs:3d}: posterior mean slope {m[1]:.4f}, posterior sd of slope {np.sqrt(S[1, 1]):.4f}') lam = 0.25 / 1.0 # sigma2 / tau2 ridge_w = np.linalg.solve(Xall.T @ Xall + lam * np.eye(2), Xall.T @ yall) print('ridge with lambda = sigma^2/tau^2:', np.round(ridge_w, 4), ' posterior mean:', np.round(posterior(Xall, yall)[0], 4))
n = 2: posterior mean slope 0.7956, posterior sd of slope 0.6290 n = 10: posterior mean slope 1.1541, posterior sd of slope 0.1892 n = 342: posterior mean slope 0.8706, posterior sd of slope 0.0271 ridge with lambda = sigma^2/tau^2: [0. 0.8706] posterior mean: [0. 0.8706]
The posterior standard deviation of the slope falls from 0.63 with 2 penguins to 0.027 with all 342, roughly like \(1/\sqrt n\). At 10 penguins the posterior mean (1.15) is still well away from its final value (0.87), but the posterior sd (0.19) says so honestly. The last line confirms Theorem 3.7: the posterior mean is the ridge estimate with \(\lambda=\sigma^2/\tau^2\).
A one-parameter model \(y_i=wx_i+\varepsilon_i\) with \(\sigma^2=1\), prior \(w\sim\mathcal N(0,1)\), and data \(x=(1,2,2)\). What is the posterior variance of \(w\)?
Theorem 3.7 is one instance of a general dictionary. Maximising a posterior is minimising \(-\log p(y\mid\beta)-\log p(\beta)\): negative log-likelihood plus a penalty equal to the negative log prior. A Gaussian prior gives the ridge penalty \(\|\beta\|_2^2/2\tau^2\). A Laplace prior, with density proportional to \(e^{-|\beta_j|/b}\), gives the lasso penalty \(\|\beta\|_1/b\), so the lasso is the MAP estimate under a Laplace prior (\(\lambda=\sigma^2/b\)). There is a twist: the full posterior under a Laplace prior puts zero probability on any coefficient being exactly zero, so "the lasso is Bayesian" is true of its mode only. Bayesians who want genuine sparsity use priors with a spike at zero, or heavy-tailed shrinkage priors such as the horseshoe (Carvalho, Polson & Scott, 2010).
A regression coefficient \(\hat\beta_j\) compares units that differ in feature \(j\) but agree in the other features in the model. It is tempting to read it as "the effect of changing \(x_j\)". That reading is justified only when every other cause of \(y\) that is related to \(x_j\) is in the model. The algebra of what happens otherwise is exact.
Let \(\hat\beta,\hat\gamma\) be the least-squares coefficients from regressing \(y\) on \(X\) and \(Z\) together (the "long" regression), and \(\tilde\beta\) the coefficients from regressing \(y\) on \(X\) alone (the "short" regression).
Let \(\hat\delta=(X^\top X)^{-1}X^\top Z\) be the coefficients from regressing \(Z\) on \(X\). Then, exactly,
$$\tilde\beta=\hat\beta+\hat\delta\,\hat\gamma.$$Leaving out \(Z\) shifts the coefficient on \(X\) by (how \(Z\) moves with \(X\)) times (how \(y\) moves with \(Z\)).
The long fit gives \(y=X\hat\beta+Z\hat\gamma+e\) with \(X^\top e=0\). Then
$$\tilde\beta=(X^\top X)^{-1}X^\top y=(X^\top X)^{-1}X^\top\big(X\hat\beta+Z\hat\gamma+e\big)$$ $$=\hat\beta+(X^\top X)^{-1}X^\top Z\,\hat\gamma+0.\qquad\square$$The penguins of Lecture 1 illustrate it. Regress bill depth on bill length, with and without indicators for species:
pen = load_penguins().dropna(subset=['bill_length_mm', 'bill_depth_mm']) L = pen['bill_length_mm'].to_numpy(); Dp = pen['bill_depth_mm'].to_numpy() G = pd.get_dummies(pen['species'], drop_first=True).to_numpy(float) # Chinstrap, Gentoo indicators one = np.ones(len(L)) short = np.linalg.lstsq(np.column_stack([one, L]), Dp, rcond=None)[0] long = np.linalg.lstsq(np.column_stack([one, L, G]), Dp, rcond=None)[0] delta = np.linalg.lstsq(np.column_stack([one, L]), G, rcond=None)[0][1] # regress each omitted dummy on length print('slope without species:', round(short[1], 4)) print('slope with species :', round(long[1], 4)) print('OVB formula: long slope + sum(gamma * delta) =', round(long[1] + long[2:] @ delta, 4))
slope without species: -0.085 slope with species : 0.1999 OVB formula: long slope + sum(gamma * delta) = -0.085
Without species the slope is −0.085; with species it is +0.200; and the formula reproduces the short slope exactly from the long one. Species is correlated with bill length (Gentoos and Chinstraps have longer bills) and affects depth (Gentoos have much shallower bills), so omitting it drags the slope negative.
The next theorem explains what "holding the other features fixed" means operationally, and it is the backbone of modern causal machine learning.
In the regression of \(y\) on \([X_1,X_2]\), the coefficient vector on \(X_2\) equals the coefficient from regressing \(M_1y\) on \(M_1X_2\), where
$$M_1=I-X_1(X_1^\top X_1)^{-1}X_1^\top$$replaces a vector by its residuals after regressing on \(X_1\).
In words: partial \(X_1\) out of both \(y\) and \(X_2\), then regress residual on residual.
Write the full fit as
$$y=X_1\hat\beta_1+X_2\hat\beta_2+e$$with \(e\) orthogonal to every column of \(X_1\) and \(X_2\). Apply \(M_1\), which kills \(X_1\) (\(M_1X_1=0\)) and leaves \(e\) unchanged (\(e\) is already orthogonal to \(X_1\)):
$$M_1y=M_1X_2\,\hat\beta_2+e.$$The columns of \(M_1X_2=X_2-X_1(\cdots)\) lie in the span of \(X_1,X_2\), so \(e\) is orthogonal to them. By Theorem 3.1, \(\hat\beta_2\) therefore satisfies the normal equations for regressing \(M_1y\) on \(M_1X_2\). \(\square\)
By Frisch–Waugh–Lovell, the coefficient on MedInc in the California regression can be computed by regressing on .
Now a question where the answer matters. In the 1970s the National Supported Work (NSW) program gave disadvantaged workers guaranteed jobs and counselling, and assigned eligible applicants to the program or a control group at random. Randomisation makes the difference in mean 1978 earnings an unbiased estimate of the program's effect. Robert LaLonde (1986) asked a sharp question: if we had only observational data, comparing participants with non-participants from a national survey and adjusting by regression, would we recover the experimental answer?
The Dehejia–Wahba (1999) subsample of LaLonde's (1986) data: 185 men assigned to the program and 260 to the control group, with age, years of education, race and ethnicity indicators, marital status, high-school degree, and real earnings in 1974, 1975 and 1978 (dollars). The observational comparison group is 15,992 men from the Current Population Survey (CPS-1). We use the copies in the R package causaldata (nsw_mixtape, cps_mixtape), prepared for Cunningham's Causal Inference: The Mixtape, via the Rdatasets collection.
nsw = pd.read_csv('data/nsw_mixtape.csv') # the randomised experiment (Dehejia-Wahba sample) cps = pd.read_csv('data/cps_mixtape.csv') # a survey sample of non-participants exp_effect = nsw.loc[nsw.treat == 1, 're78'].mean() - nsw.loc[nsw.treat == 0, 're78'].mean() obs = pd.concat([nsw[nsw.treat == 1], cps]) # treated workers vs survey controls: no randomisation naive = obs.loc[obs.treat == 1, 're78'].mean() - obs.loc[obs.treat == 0, 're78'].mean() obs = obs.assign(age2=obs.age ** 2, u74=(obs.re74 == 0) * 1.0, u75=(obs.re75 == 0) * 1.0) covs = ['age', 'age2', 'educ', 'black', 'hisp', 'marr', 'nodegree', 're74', 're75', 'u74', 'u75'] Z = np.column_stack([np.ones(len(obs)), obs[covs]]) d, yy = obs['treat'].to_numpy(float), obs['re78'].to_numpy() full = np.linalg.lstsq(np.column_stack([d, Z]), yy, rcond=None)[0][0] d_res = d - Z @ np.linalg.lstsq(Z, d, rcond=None)[0] # Frisch-Waugh-Lovell: partial Z out of treat ... y_res = yy - Z @ np.linalg.lstsq(Z, yy, rcond=None)[0] # ... and out of earnings, fwl = (d_res @ y_res) / (d_res @ d_res) # then regress residual on residual print(f'experimental benchmark (randomised) : {exp_effect:8.0f} dollars') print(f'observational, difference in means : {naive:8.0f}') print(f'observational, regression on covariates : {full:8.0f}') print(f'observational, FWL residual regression : {fwl:8.0f}')
experimental benchmark (randomised) : 1794 dollars observational, difference in means : -8498 observational, regression on covariates : 1137 observational, FWL residual regression : 1137
The experiment says the program raised 1978 earnings by about $1,794. The naive observational comparison says it lowered them by $8,498, because program participants were far poorer to begin with than typical survey respondents: the comparison is mostly measuring who enrolled. Adjusting for prior earnings and demographics by regression moves the estimate to $1,137, the right sign and the right ballpark, but still well short of the truth, and sensitive to which covariates and which functional form you choose. FWL confirms that "adjusting" is residual-on-residual regression.
Regression adjustment estimates a causal effect only under two assumptions: no unmeasured confounding (every variable that affects both treatment and outcome is in the model) and a correct functional form for how the covariates enter. The first is a claim about the world that no amount of data can confirm; the second is where machine learning helps. FWL suggests a recipe: predict the treatment from covariates, predict the outcome from covariates, and regress residual on residual. Double/debiased machine learning (Chernozhukov et al., 2018) does exactly this with flexible models (lasso, random forests, boosting, neural networks) for the two predictions, fitted on separate folds of the data, and shows that the final residual-on-residual coefficient is approximately normal with valid confidence intervals. Lecture 4 adds the propensity score, Lecture 8 causal forests, and Lecture 20 the question of how to find the confounders in the first place.
Why is the naive observational estimate (−$8,498) so far from the experimental one (+$1,794)?
Linear regression is everywhere in modern data science, often unannounced. Online experiments at technology companies use regression adjustment on pre-experiment behaviour to cut the variance of A/B-test estimates (the "CUPED" method of Deng et al., 2013), which lets them run shorter experiments. Interpretability research reads what a neural network has learned by fitting linear "probes" from its internal activations to properties of the input. The final layer of almost every neural network is a linear model on learned features. And the scaling laws that guide how large language models are trained (Kaplan et al., 2020) are straight lines fitted to log-loss against log-compute.
Next: Lecture 4 moves from predicting numbers to predicting classes: the perceptron, logistic regression and its cross-entropy loss, softmax, discriminant analysis, and how to evaluate a classifier.
\(\bar x=2.5\), \(\bar y=4\), \(\sum(x_i-\bar x)(y_i-\bar y)=7\), \(\sum(x_i-\bar x)^2=5\), so \(\hat b_1=1.4\) and \(\hat b_0=4-1.4\times2.5=0.5\). Fitted values \(1.9,3.3,4.7,6.1\); residuals \(0.1,-0.3,0.3,-0.1\), which sum to 0, and \(\sum x_ir_i=0.1-0.6+0.9-0.4=0\). \(\mathrm{RSS}=0.2\), total sum of squares 10, \(R^2=0.98\).
Symmetry and idempotence are in the proof of Theorem 3.1. \(\operatorname{tr}H=\operatorname{tr}\big(X(X^\top X)^{-1}X^\top\big)=\operatorname{tr}\big((X^\top X)^{-1}X^\top X\big)=\operatorname{tr}I_p=p\), using \(\operatorname{tr}(AB)=\operatorname{tr}(BA)\). For a projection the eigenvalues are 0 and 1, so the trace counts the dimension of the space projected onto. For ridge, \(\operatorname{tr}\big(X(X^\top X+\lambda I)^{-1}X^\top\big)=\sum_i\sigma_i^2/(\sigma_i^2+\lambda)\) is called the effective degrees of freedom: it falls smoothly from \(p\) to 0 as \(\lambda\) grows.
The normal equations say \(X^\top r=0\); the row corresponding to the column of ones reads \(\sum_ir_i=0\). Dividing \(\sum_i(y_i-\hat b_0-\hat b_1x_i)=0\) by \(n\) gives \(\bar y=\hat b_0+\hat b_1\bar x\).
\(\mathbb E[(cz-\beta)^2]=(c\beta-\beta)^2+c^2\sigma^2\): squared bias plus variance (Lecture 1, Proposition 1.2). Minimising over \(c\) gives \(c^*=\beta^2/(\beta^2+\sigma^2)\), always less than 1. Gauss–Markov only compares unbiased estimators; ridge is biased, and accepting a little bias buys a larger drop in variance, especially when \(\beta\) is small relative to the noise.
Ridge divides by \(1+\lambda=2\): \((1.5,-0.25,0.6)\). Lasso subtracts 1 from each size and floors at zero: \((2,0,0.2)\). Ridge keeps all three; the lasso drops the second.
\(\sum x_i^2=9\), \(\sum x_iy_i=11\). Posterior variance \(1/(9+1)=0.1\), posterior mean \(11/10=1.1\). Least squares gives \(11/9\approx1.222\): the prior pulls the estimate towards 0, by the factor \(9/10\).
With \(Z\) = ability: \(\hat\delta>0\) (more able people get more schooling) and \(\hat\gamma>0\) (ability raises wages), so \(\tilde\beta=\hat\beta+\hat\delta\hat\gamma\) is biased upwards: the schooling coefficient overstates the return to schooling. This is the classic "ability bias" argument in labour economics, and one reason economists look for natural experiments.
The residual-on-residual slope is 0.4325, equal to the multiple-regression coefficient. (Regressing raw Value on the MedInc residuals gives the same slope too, because the MedInc residuals are orthogonal to the other columns; but the residuals of that regression are not the model's residuals, so its standard errors would be wrong.)
Least squares is not unique: only \(\beta_1+\beta_2\) is determined. Ridge, minimising \(\beta_1^2+\beta_2^2\) for a fixed sum, splits the weight equally. The lasso's \(|\beta_1|+|\beta_2|\) is the same for any split with both coefficients of the same sign, so the lasso solution is not unique either, and algorithms return one arbitrary split (often putting all the weight on one copy). This is why the lasso "picks one of a correlated group", and why the elastic net (a mix of both penalties) was invented.
With \(\tau\to\infty\), \(S=\sigma^2(X^\top X)^{-1}\). For centred \(x\), \(X^\top X=\operatorname{diag}(n,\sum x_i^2)\), so the predictive variance at \(x_*\) is \(\sigma^2\big(1+\tfrac1n+\tfrac{x_*^2}{\sum x_i^2}\big)\). The intercept is uncertain by \(\sigma^2/n\) everywhere; the slope's uncertainty contributes a term growing with \(x_*^2\), the squared distance from the centre of the data.
Each project uses this lecture's methods on public data and has a clear result.
causaldata R package, or Dehejia's and LaLonde's original files).Data. California housing: R. K. Pace, R. Barry, "Sparse spatial autoregressions", Statistics & Probability Letters 33(3), 291–297 (1997); copy from A. Géron, Hands-On Machine Learning with Scikit-Learn, Keras and TensorFlow (2nd ed., O'Reilly, 2019), github.com/ageron/handson-ml2. NSW and CPS samples: LaLonde (1986) and Dehejia & Wahba (1999) as above, via N. Huntington-Klein, M. Barrett, causaldata R package, and S. Cunningham, Causal Inference: The Mixtape (Yale, 2021); accessed through V. Arel-Bundock, Rdatasets. Palmer penguins and the motorcycle data: see Lecture 1. Software: scikit-learn (Pedregosa et al., JMLR 12, 2825–2830, 2011).
every number in the text and widgets is computed in verify_L03.py; code-box outputs are pasted from actual runs