ML Methods

Linear Regression

Ordinary least squares as projection, the normal equations, the hat matrix, Gauss-Markov optimality, and the connection to maximum likelihood under Gaussian noise.

CoreTier 1Stable~50 min

Prerequisites

Matrix Operations and Properties Maximum Likelihood Estimation

Quiz (7)Pulse Check

Why This Matters

Linear regression is the most fundamental supervised learning method. Every idea in regression (projection, residuals, bias-variance, regularization) generalizes directly to more complex models. If you understand linear regression at the level of linear algebra (not just "fit a line"), you have the skeleton key for half of statistical learning.

Mental Model

You have data points in a high-dimensional space. The columns of your design matrix $X$ span a subspace. OLS finds the point in that subspace closest to your target vector $y$ . This is an orthogonal projection. The residuals are the component of $y$ orthogonal to the column space of $X$ .

Formal Setup

We observe $n$ input-output pairs. Stack the inputs into a design matrix $X \in \mathbb{R}^{n \times d}$ and responses into $y \in \mathbb{R}^n$ . We seek a weight vector $w \in \mathbb{R}^d$ minimizing the sum of squared residuals.

Definition

Ordinary Least Squares

The OLS estimator minimizes the squared loss:

$\hat{w}_{\text{OLS}} = \arg\min_{w \in \mathbb{R}^d} \|y - Xw\|_2^2$

Setting the gradient to zero yields the normal equations:

$X^\top X \hat{w} = X^\top y$

When $X^\top X$ is invertible, the closed-form solution is:

$\hat{w}_{\text{OLS}} = (X^\top X)^{-1} X^\top y$

Definition

Hat Matrix

The hat matrix (or projection matrix) is:

$H = X(X^\top X)^{-1} X^\top$

It projects $y$ onto the column space of $X$ : the fitted values are $\hat{y} = Hy$ . The matrix "puts the hat on $y$ ."

Key properties: $H$ is symmetric and idempotent ( $H^2 = H$ ), $\text{tr}(H) = d$ , and eigenvalues are all 0 or 1.

Definition

Residuals

The residual vector is:

$e = y - \hat{y} = (I - H)y$

By the normal equations, $X^\top e = 0$ . residuals are orthogonal to every column of $X$ . This is the geometric content of OLS.

The Projection Interpretation

The OLS solution has a direct geometric meaning. The column space of $X$ , denoted $\text{col}(X)$ , is a $d$ -dimensional subspace of $\mathbb{R}^n$ . The fitted vector $\hat{y} = Xw$ must lie in $\text{col}(X)$ .

OLS finds the point in $\text{col}(X)$ closest to $y$ in Euclidean distance. By the projection theorem in linear algebra, this is the orthogonal projection of $y$ onto $\text{col}(X)$ . The residual $e = y - \hat{y}$ is perpendicular to $\text{col}(X)$ , which is exactly the statement $X^\top e = 0$ .

Ridge Regression as Regularized OLS

Definition

Ridge Regression

Ridge regression adds an $\ell_2$ penalty:

$\hat{w}_{\text{ridge}} = \arg\min_w \|y - Xw\|_2^2 + \lambda \|w\|_2^2$

The closed-form solution is:

$\hat{w}_{\text{ridge}} = (X^\top X + \lambda I)^{-1} X^\top y$

The addition of $\lambda I$ ensures invertibility and shrinks the estimate toward zero, trading bias for reduced variance.

Main Theorems

Theorem

Gauss-Markov Theorem

Statement

Under the linear model $y = Xw + \varepsilon$ where $\mathbb{E}[\varepsilon] = 0$ and $\text{Var}(\varepsilon) = \sigma^2 I$ , the OLS estimator $\hat{w}_{\text{OLS}}$ is the Best Linear Unbiased Estimator (BLUE). That is, among all unbiased estimators that are linear in $y$ , OLS has the smallest variance (in the matrix sense):

$\text{Var}(\tilde{w}) - \text{Var}(\hat{w}_{\text{OLS}}) \succeq 0$

for any other linear unbiased estimator $\tilde{w}$ .

Intuition

OLS is not just an unbiased linear estimator. It is the best one. You cannot reduce variance by using a different linear combination of $y$ without introducing bias. If you want lower variance, you must either accept bias (ridge regression) or use nonlinear methods.

Proof Sketch

Let $\tilde{w} = Cy$ be any linear unbiased estimator. Unbiasedness requires $CX = I$ . Write $C = (X^\top X)^{-1}X^\top + D$ where $DX = 0$ . Then $\text{Var}(\tilde{w}) = \sigma^2(X^\top X)^{-1} + \sigma^2 DD^\top \succeq \sigma^2(X^\top X)^{-1} = \text{Var}(\hat{w}_{\text{OLS}})$ .

Why It Matters

The Gauss-Markov theorem tells you exactly what you give up by regularizing. Ridge regression is biased, so it falls outside the Gauss-Markov scope. But the bias-variance tradeoff can still make it better in terms of mean squared error. The theorem defines the frontier of what unbiased linear estimation can achieve.

Failure Mode

If errors are heteroscedastic or correlated (violating $\text{Var}(\varepsilon) = \sigma^2 I$ ), OLS is no longer BLUE. Generalized least squares (GLS) reclaims optimality by accounting for the error covariance structure.

Connection to Maximum Likelihood

Under the Gaussian noise model $y = Xw + \varepsilon$ with $\varepsilon \sim \mathcal{N}(0, \sigma^2 I)$ , the log-likelihood is:

$\log p(y \mid X, w, \sigma^2) = -\frac{n}{2}\log(2\pi\sigma^2) - \frac{1}{2\sigma^2}\|y - Xw\|_2^2$

Maximizing over $w$ is equivalent to minimizing $\|y - Xw\|_2^2$ , which is exactly OLS. So OLS = MLE under Gaussian noise. This also means ridge regression corresponds to MAP estimation with a Gaussian prior on $w$ .

Canonical Examples

Example

Simple linear regression in 2D

With a single feature and intercept, $X = [\mathbf{1}, x]$ where $x$ is the feature vector. The normal equations give the familiar slope and intercept:

$\hat{\beta}_1 = \frac{\sum_i (x_i - \bar{x})(y_i - \bar{y})}{\sum_i (x_i - \bar{x})^2}, \quad \hat{\beta}_0 = \bar{y} - \hat{\beta}_1 \bar{x}$

The hat matrix $H$ has diagonal entries $h_{ii}$ called leverages. Points with high leverage (far from $\bar{x}$ ) have outsized influence on the fit.

Example

Polynomial regression as linear regression

Fitting a polynomial $y = \beta_0 + \beta_1 x + \beta_2 x^2 + \cdots$ is still linear regression. The design matrix has columns $[1, x, x^2, \ldots]$ . The model is linear in the parameters, not the features. This is why the term "linear" in linear regression refers to linearity in $w$ , not in $x$ .

Common Confusions

Watch Out

OLS minimizes squared residuals, not perpendicular distances

A frequent misconception is that OLS minimizes the perpendicular (orthogonal) distance from each point to the regression line. It does not. OLS minimizes the vertical distances (residuals in $y$ ). Minimizing perpendicular distances gives total least squares (or orthogonal regression), which is a different estimator. The distinction matters when both $x$ and $y$ have measurement error.

Watch Out

Invertibility of X^T X is not guaranteed

The normal equations require $X^\top X$ to be invertible, which happens when $X$ has full column rank ( $\text{rank}(X) = d$ ). This fails when features are linearly dependent or when $n < d$ . Ridge regression fixes this: $X^\top X + \lambda I$ is always invertible for $\lambda > 0$ .

Summary

The normal equations $X^\top X w = X^\top y$ are the first-order optimality conditions for least squares
OLS is an orthogonal projection of $y$ onto the column space of $X$
The hat matrix $H = X(X^\top X)^{-1}X^\top$ maps $y$ to fitted values
Gauss-Markov: OLS is BLUE under homoscedastic uncorrelated errors
OLS = MLE under Gaussian noise; ridge = MAP with Gaussian prior
Residuals are orthogonal to every predictor: $X^\top e = 0$

Exercises

ExerciseCore

Problem

Show that the residual vector $e = y - X\hat{w}$ satisfies $X^\top e = 0$ . What does this mean geometrically?

ExerciseCore

Problem

For ridge regression with penalty $\lambda$ , show that the solution can be written as $\hat{w}_{\text{ridge}} = (X^\top X + \lambda I)^{-1} X^\top y$ . What happens as $\lambda \to 0$ and $\lambda \to \infty$ ?

ExerciseAdvanced

Problem

Prove that if $\varepsilon \sim \mathcal{N}(0, \sigma^2 I)$ and $y = Xw + \varepsilon$ , then the MLE for $w$ is exactly $\hat{w}_{\text{OLS}}$ . What is the MLE for $\sigma^2$ ?