Chapter 4 · Part II: Supervised Learning
Linear Regression
The oldest and still the most useful learning algorithm. It has a closed-form solution, a clean geometric picture, and a probabilistic justification, and every one of those ideas comes back in later chapters.
After this chapter you will be able to
- Write the linear regression model and its squared-error loss in matrix form.
- Derive the normal equations and solve them stably in code.
- Interpret least squares as an orthogonal projection onto the column space of $\mX$.
- Show that least squares is maximum likelihood under Gaussian noise.
- Extend linear regression to nonlinear relationships with feature maps.
- Train the same model with gradient descent and compare it with the closed form.
4.1The Model
Linear regression predicts a real number as a weighted sum of features plus an intercept:
$$\hat y = w_1x_1 + \dots + w_dx_d + b = \vw\T\vx + b. \tag{4.1}$$Each weight is the change in the prediction when its feature rises by one unit with the others held fixed. That interpretability, plus speed, makes linear regression the baseline every fancier model must beat. With the bias trick, all predictions are $\hat\vy = \mX\vw$ and the loss is
$$\Loss(\vw) = \frac1n\norm{\mX\vw - \vy}_2^2. \tag{4.2}$$4.2The Normal Equations
$\Loss$ is a convex quadratic (its Hessian $\frac2n\mX\T\mX$ is PSD), so setting the gradient $\frac2n\mX\T(\mX\vw - \vy)$ to zero finds the global minimum:
These are the normal equations. With one feature they reduce to the covariance-over-variance formula of Chapter 1.
Pitfall: do not invert the matrix
Forming $\mX\T\mX$ squares the condition number, amplifying rounding errors. Use np.linalg.lstsq(X, y), which factors $\mX$ directly (QR or SVD) and also handles the rank-deficient case.
If one feature is a linear combination of others (height in cm and in inches), $\mX\T\mX$ is singular and infinitely many $\vw$ fit equally well. Nearly dependent features (multicollinearity) make individual weights wildly sensitive to the data. Regularization (Chapter 5) fixes both.
4.3The Geometry of Least Squares
Treat $\vy$ as a single point in $\R^n$, one coordinate per example. As $\vw$ varies, $\mX\vw$ sweeps out the column space of $\mX$. Least squares picks the point of that subspace closest to $\vy$: the orthogonal projection.
Orthogonality of the residual to every column, $\mX\T(\vy - \mX\hat\vw) = \mathbf 0$, is the normal equations, derived without calculus. Two consequences: with a column of ones in $\mX$, residuals sum to zero; and by Pythagoras, variance splits into explained and unexplained parts, giving the coefficient of determination
$$R^2 = 1 - \frac{\sum_i(y^{(i)} - \hat y^{(i)})^2}{\sum_i(y^{(i)} - \bar y)^2}. \tag{4.4}$$$R^2 = 1$ is a perfect fit; $R^2 = 0$ is no better than predicting the mean; on test data it can be negative.
4.4The Probabilistic View
Assume the data come from a line plus Gaussian noise, $y = \vw\T\vx + \varepsilon$ with $\varepsilon\sim\Normal(0, \sigma^2)$. The log-likelihood is
$$\sum_i\log p(y^{(i)}\mid\vx^{(i)},\vw) = -\frac n2\log(2\pi\sigma^2) - \frac{1}{2\sigma^2}\sum_i\big(y^{(i)} - \vw\T\vx^{(i)}\big)^2,$$so maximizing likelihood over $\vw$ is exactly minimizing squared error.
Key idea: squared error assumes Gaussian noise
Least squares is the MLE under constant-variance Gaussian noise. With heavy-tailed noise, it is dragged around by outliers; Laplace noise leads to absolute error, which is far more robust. Choosing a loss is choosing a noise model.
4.5Nonlinear Features
"Linear" means linear in the parameters. Replace $\vx$ by features $\boldsymbol\phi(\vx)$ and fit $\hat y = \vw\T\boldsymbol\phi(\vx)$; all the math is unchanged. Polynomials $\boldsymbol\phi(x) = (1, x, x^2, \dots, x^p)$, logarithms of prices, one-hot indicators, and radial basis functions $\exp(-\norm{\vx - \vc_k}^2/2s^2)$ are common choices. With enough features a linear model fits almost any shape, which raises the question of fitting the noise too (Chapter 5). Neural networks learn the feature map (Chapter 15).
4.6Solving by Gradient Descent
For huge problems we skip the factorization and run gradient descent with $\nabla\Loss = \frac2n\mX\T(\mX\vw - \vy)$. The Hessian $\frac2n\mX\T\mX$ is constant, so from Chapter 3 GD converges for $\eta < 2/\lambda_{\max}$ at a speed set by the condition number of $\mX\T\mX$. Features on very different scales make that condition number large, which is why feature scaling matters for gradient-based training.
The LMS rule. With one example per step, SGD on $\frac12(y^{(i)}-\vw\T\vx^{(i)})^2$ gives $\vw\gets\vw+\eta\,(y^{(i)}-\vw\T\vx^{(i)})\,\vx^{(i)}$, the least mean squares (Widrow–Hoff) rule: a step proportional to the error, in the direction of the input. The same “error times input” update reappears in logistic regression, every GLM (Chapter 7), and the perceptron (Section 6.6).
4.7Locally Weighted Regression
Linear regression is parametric: after training, a fixed vector $\hat\vw$ summarizes everything and the data can be discarded. Locally weighted regression (LWR, or LOESS; Cleveland 1979) is nonparametric: for every query $\vx$ it fits a fresh line that weights nearby training points most:
$$\hat\vw(\vx)=\argmin_{\vw}\sum_{i=1}^n\omega^{(i)}(\vx)\big(y^{(i)}-\vw\T\vx^{(i)}\big)^2,\qquad \omega^{(i)}(\vx)=\exp\Big(-\frac{\norm{\vx^{(i)}-\vx}^2}{2\tau^2}\Big), \tag{4.6}$$and predicts $\hat y=\hat\vw(\vx)\T\vx$. The closed form is the weighted normal equations $\hat\vw(\vx)=(\mX\T\boldsymbol\Omega\mX)^{-1}\mX\T\boldsymbol\Omega\vy$ with $\boldsymbol\Omega=\diag(\omega^{(i)})$.
The bandwidth $\tau$ is a bias–variance knob (Chapter 5): small $\tau$ follows the noise, large $\tau$ recovers ordinary least squares. Every prediction solves a weighted problem over the whole training set, which must be kept. LWR is the regression cousin of nearest neighbors (Chapter 8) and kernel methods (Chapter 9), and like them works best in low dimensions.
import numpy as np
def lwr_predict(X, y, x_query, tau):
# locally weighted linear regression at one query point (Eq. 4.6)
Xb = np.column_stack([np.ones(len(X)), X]) # intercept column
xq = np.r_[1.0, np.atleast_1d(x_query)]
w = np.exp(-np.sum((X - x_query) ** 2, axis=1) / (2 * tau**2))
A = Xb.T @ (w[:, None] * Xb) # X^T Omega X
theta = np.linalg.solve(A, Xb.T @ (w * y)) # X^T Omega y
return xq @ theta
rng = np.random.default_rng(0)
X = rng.uniform(0, 6, (60, 1))
y = np.sin(1.3 * X[:, 0]) + 0.25 * X[:, 0] + 0.25 * rng.standard_normal(60)
for tau in [0.1, 0.5, 5.0]:
pred = np.array([lwr_predict(X, y, x, tau) for x in X])
print(f"tau={tau}: training RMSE {np.sqrt(np.mean((pred - y) ** 2)):.3f}")
4.8Implementation
import numpy as np
rng = np.random.default_rng(0)
n, d = 500, 3
X_raw = rng.normal(size=(n, d))
w_true = np.array([2.0, -1.0, 0.5])
y = X_raw @ w_true + 4.0 + rng.normal(0, 0.3, size=n) # intercept 4
X = np.hstack([X_raw, np.ones((n, 1))]) # bias trick
w_normal = np.linalg.solve(X.T @ X, X.T @ y) # normal equations
w_lstsq, *_ = np.linalg.lstsq(X, y, rcond=None) # preferred
w = np.zeros(d + 1) # gradient descent
for step in range(500):
w -= 0.1 * (2 / n) * X.T @ (X @ w - y)
print(np.round(w_normal, 3)) # approximately [ 2. -1. 0.5 4. ]
print(np.allclose(w_normal, w_lstsq), np.allclose(w_normal, w, atol=1e-4))
r2 = 1 - np.sum((X @ w_lstsq - y)**2) / np.sum((y - y.mean())**2)
print(f"R^2 = {r2:.4f}")
from sklearn.linear_model import LinearRegression
model = LinearRegression().fit(X_raw, y) # adds the intercept for you
print(model.coef_, model.intercept_)
4.9Common Pitfalls
Pitfall: reading weights as importances
Weights depend on units. Standardize before comparing them, and remember that correlated features share credit unpredictably.
Pitfall: extrapolation
A linear model predicts confidently far outside the training range, where the relationship may not hold. Polynomials extrapolate even worse.
Pitfall: outliers
Squared errors let one extreme point dominate. Plot residuals; consider a robust loss such as Huber.
4.10Summary
- Linear regression predicts $\mX\vw$ and minimizes mean squared error.
- The minimizer solves $\mX\T\mX\vw = \mX\T\vy$; use a least-squares routine, not an inverse.
- Least squares projects $\vy$ onto the column space of $\mX$; the residual is orthogonal to every feature.
- It is the MLE under Gaussian noise with constant variance.
- Feature maps give nonlinear fits while staying linear in $\vw$.
- Gradient descent reaches the same answer; its speed depends on the conditioning of $\mX\T\mX$.
- Locally weighted regression fits a weighted line around each query; the bandwidth $\tau$ trades bias against variance.
4.11Exercises
- MathShow that the hat matrix $\mathbf H = \mX(\mX\T\mX)^{-1}\mX\T$ is symmetric and idempotent, and that $\mI - \mathbf H$ is also a projection. Onto what?
- MathWith a column of ones in $\mX$, prove that residuals sum to zero and the fit passes through $(\bar\vx, \bar y)$.
- MathWith noise $\varepsilon^{(i)}\sim\Normal(0,\sigma_i^2)$, derive the MLE of $\vw$ (weighted least squares).
- MathIf $\vy = \mX\vw^\star + \vepsilon$ with $\Cov(\vepsilon) = \sigma^2\mI$, show $\E\hat\vw = \vw^\star$ and $\Cov(\hat\vw) = \sigma^2(\mX\T\mX)^{-1}$. Why do collinear features make weights unreliable?
- CodingAdd a feature equal to the first plus $10^{-6}$ noise. Compare
solveon the normal equations withlstsq, and printnp.linalg.cond(X.T @ X). - CodingFit polynomials of degree 1–12 to 30 noisy samples of $\sin 2x$ on $[0,3]$ using
np.vander. Plot training and test MSE against degree; you will explain the shape in Chapter 5. - MathDerive the weighted normal equations for Equation (4.6) and show that they reduce to ordinary least squares as $\tau\to\infty$.
- CodingChoose $\tau$ for LWR by leave-one-out cross-validation on the data above and plot the CV error against $\tau$ on a log axis.