Linear Regression

Topics We'll Cover

• The model and its assumptions
• Maximum-likelihood = least squares
• Least squares as orthogonal projection
• Ridge regression = MAP under a Gaussian prior
• Feature maps
• Bayesian linear regression: prior & posterior
• Posterior predictive distribution
• Interactive: posterior shrink as data arrives
• Marginal likelihood & model selection
• Cheat sheet

The Model and Its Assumptions

$$y_n = \boldsymbol\theta^\top \boldsymbol\phi(\mathbf{x}_n) + \varepsilon_n, \qquad \varepsilon_n \overset{\text{iid}}{\sim} \mathcal{N}(0, \sigma^2).$$

• $\boldsymbol\phi:\mathbb{R}^D\to\mathbb{R}^M$ is a fixed feature map;
• $\boldsymbol\theta\in\mathbb{R}^M$ are the parameters we'll learn;
• $\varepsilon_n$ is independent Gaussian noise.

"Linear" refers to linearity in $\boldsymbol\theta$, not in $\mathbf{x}$. Quadratic, sinusoidal and RBF regression all sit inside this model with the right $\boldsymbol\phi$.

Vector form

Stack the data: $\mathbf{y} = (y_1,\dots,y_N)^\top$, $\Phi = [\boldsymbol\phi(\mathbf{x}_1)^\top; \dots; \boldsymbol\phi(\mathbf{x}_N)^\top]\in\mathbb{R}^{N\times M}$. Then

$$\mathbf{y} = \Phi\boldsymbol\theta + \boldsymbol\varepsilon, \qquad \boldsymbol\varepsilon\sim\mathcal{N}(\mathbf{0}, \sigma^2 I).$$

$\Phi$ is the design matrix. The entire chapter is a study of this single equation.

Maximum-Likelihood = Least Squares

Under the Gaussian noise model the log-likelihood is

$$\log p(\mathbf{y}\mid\boldsymbol\theta) = -\frac{1}{2\sigma^2}\|\mathbf{y}-\Phi\boldsymbol\theta\|^2 + \text{const.}$$

So maximising likelihood is exactly minimising the sum of squared residuals. Setting the gradient (deck 05) to zero:

$$\nabla_{\boldsymbol\theta}\|\mathbf{y}-\Phi\boldsymbol\theta\|^2 = -2\Phi^\top(\mathbf{y}-\Phi\boldsymbol\theta) = 0 \;\Longrightarrow\; \Phi^\top\Phi\,\boldsymbol\theta = \Phi^\top\mathbf{y}.$$

This is the normal equation. If $\Phi^\top\Phi$ is invertible (columns of $\Phi$ independent):

$$\hat{\boldsymbol\theta}_{\text{ML}} = (\Phi^\top\Phi)^{-1}\Phi^\top\mathbf{y}.$$

Least Squares as Orthogonal Projection

The fitted values are

$$\hat{\mathbf{y}} = \Phi\hat{\boldsymbol\theta}_{\text{ML}} = \Phi(\Phi^\top\Phi)^{-1}\Phi^\top \mathbf{y}.$$

The matrix in the middle is exactly the projection onto $\mathrm{Col}(\Phi)$ from deck 03. So:

Once you see this, every property of linear regression follows by reading the deck-03 picture:

• $\hat{\mathbf{y}}$ is unique even when $\hat{\boldsymbol\theta}$ isn't;
• The "hat matrix" $H = \Phi(\Phi^\top\Phi)^{-1}\Phi^\top$ is idempotent ($H^2 = H$) and symmetric;
• $\mathrm{tr}(H) = \mathrm{rank}(\Phi)$ — the number of "effective degrees of freedom".

Ridge Regression = MAP under a Gaussian Prior

Place a prior $\boldsymbol\theta \sim \mathcal{N}(\mathbf{0}, \tau^2 I)$. The MAP estimator (deck 08) is

$$\hat{\boldsymbol\theta}_{\text{MAP}} = \arg\min_{\boldsymbol\theta}\;\frac{1}{2\sigma^2}\|\mathbf{y}-\Phi\boldsymbol\theta\|^2 + \frac{1}{2\tau^2}\|\boldsymbol\theta\|^2.$$

Setting the gradient to zero:

$$\hat{\boldsymbol\theta}_{\text{MAP}} = \Bigl(\Phi^\top\Phi + \frac{\sigma^2}{\tau^2} I\Bigr)^{-1}\Phi^\top\mathbf{y}.$$

This is ridge regression with $\lambda = \sigma^2/\tau^2$. Three observations:

• The added $\lambda I$ guarantees invertibility — even when $\Phi^\top\Phi$ is singular.
• The Gaussian prior shrinks $\boldsymbol\theta$ toward $\mathbf{0}$; the strength $\lambda$ is the ratio of likelihood vs prior precision.
• As $N\to\infty$ the data overwhelms the prior and $\hat{\boldsymbol\theta}_{\text{MAP}}\to\hat{\boldsymbol\theta}_{\text{ML}}$.

Feature Maps

The same machinery works for any $\boldsymbol\phi$. Three useful choices:

Kernel ridge regression

Ridge regression with feature map $\boldsymbol\phi$ has the dual form (Woodbury identity):

$$\hat{\mathbf{y}}_\star = K(\mathbf{x}_\star, X)\,(K(X,X) + \lambda I)^{-1}\mathbf{y},$$

where $K(\mathbf{x}, \mathbf{x}') = \boldsymbol\phi(\mathbf{x})^\top\boldsymbol\phi(\mathbf{x}')$ is the kernel. This is the road into kernel methods and Gaussian process regression — the SVM (deck 12) is the classification analogue.

Bayesian Linear Regression: Prior & Posterior

Prior $\boldsymbol\theta\sim\mathcal N(\mathbf m_0, S_0)$; likelihood $\mathbf y\mid\boldsymbol\theta\sim\mathcal N(\Phi\boldsymbol\theta, \sigma^2 I)$. Both Gaussian, in $\boldsymbol\theta$ — the posterior is Gaussian (deck 06 conjugacy).

$$\boldsymbol\theta\mid\mathbf{y}\sim\mathcal N(\mathbf m_N, S_N), \qquad S_N^{-1} = S_0^{-1} + \frac{1}{\sigma^2}\Phi^\top\Phi,$$

$$\mathbf m_N = S_N\Bigl(S_0^{-1}\mathbf m_0 + \frac{1}{\sigma^2}\Phi^\top \mathbf{y}\Bigr).$$

Two specialisations:

• Zero-mean isotropic prior $\mathbf m_0=\mathbf 0$, $S_0 = \tau^2 I$: $\mathbf m_N = (\Phi^\top\Phi + (\sigma^2/\tau^2)I)^{-1}\Phi^\top\mathbf{y}$. MAP = ridge above.
• Flat prior ($S_0\to\infty I$): $\mathbf m_N$ → $\hat{\boldsymbol\theta}_{\text{ML}}$.

Posterior Predictive Distribution

For a new input $\mathbf{x}_\star$, integrating out $\boldsymbol\theta$ under the posterior yields a Gaussian predictive distribution:

$$p(y_\star\mid\mathbf{x}_\star, \mathbf{y}) = \mathcal N\bigl(\boldsymbol\phi(\mathbf{x}_\star)^\top\mathbf m_N,\; \sigma^2 + \boldsymbol\phi(\mathbf{x}_\star)^\top S_N \boldsymbol\phi(\mathbf{x}_\star)\bigr).$$

Mean and variance split cleanly:

• $\boldsymbol\phi(\mathbf{x}_\star)^\top\mathbf m_N$ — the posterior mean prediction, same as plug-in MAP.
• $\sigma^2$ — aleatoric uncertainty: irreducible noise.
• $\boldsymbol\phi(\mathbf{x}_\star)^\top S_N \boldsymbol\phi(\mathbf{x}_\star)$ — epistemic uncertainty: how much we still don't know about $\boldsymbol\theta$. This term grows at inputs far from any training point and shrinks toward zero where data is plentiful.

Interactive: Posterior Shrink as Data Arrives

Click on the canvas to add a $(x, y)$ point. The black curve is the posterior mean; the purple band is the 95% predictive interval. Each point pulls the mean toward itself and narrows the band locally. Use RBF features by default; switch to polynomial in the dropdown.

With no data, the prior dominates: the band is uniformly wide. With many points, the band collapses toward $2\sigma$ — the irreducible noise from slide 07.

Marginal Likelihood & Model Selection

The Bayesian evidence (deck 08, slide 10) for linear regression is in closed form:

$$p(\mathbf{y}\mid \Phi, \sigma^2, \tau^2) = \mathcal N\bigl(\mathbf{0},\, \sigma^2 I + \tau^2 \Phi\Phi^\top\bigr).$$

This is a Gaussian on $\mathbf{y}$ with covariance $K + \sigma^2 I$ where $K = \tau^2 \Phi\Phi^\top$ — the kernel matrix again. Maximising the log-evidence over $\sigma^2, \tau^2$ does model selection automatically — this is the type-II maximum likelihood or empirical Bayes, the engine behind Gaussian process hyperparameter learning.

Cheat Sheet