1.1 An Algebraic View of OLS Regression

Supervised learning tries to learn a function \(f : \mathbb{R}^d \to \mathcal{Y}\) that maps an input, encoded as a \(d\)-dimensional vector, to an output in whatever space is relevant to the task. Regression is the special case where the outputs are real numbers: we want to learn \(f : \mathbb{R}^d \to \mathbb{R}\), a function that predicts a continuous quantity.

Example. Old Faithful, the geyser in Yellowstone, erupts at irregular intervals. Suppose we record, for many eruptions, how long the current eruption lasted and how long we then waited for the next one. Plotting waiting time against current eruption time shows a strong, roughly linear relationship, so a natural model is a straight line: given how long the current eruption took, predict how long until the next. Here the input is a single number, so \(d = 1\).

A linear regression model for a one-dimensional feature is \[ f(x) := w x + w_0, \] with two learnable parameters: a weight (slope) \(w \in \mathbb{R}\) and a bias (intercept) \(w_0 \in \mathbb{R}\).

Notation: :=

We write \(:=\) when we are defining the quantity on the left, rather than claiming two things are equal.

This chapter answers two questions. First, how do we write linear regression for \(d\)-dimensional features (\(d \geq 1\)), not just for data we can plot in two dimensions? Second, given data, how do we pick the best parameters? That second task, finding parameter values from data, is what we mean by a learning algorithm.

Linear algebra refresher

Linear algebra is bookkeeping: it lets us write the problem compactly, and compact notation makes it much easier to reason about what a good algorithm should be. We will use the following notation for the rest of the course.

Dot products

Definition. Given vectors \(x, w \in \mathbb{R}^d\), their dot product is \[ w \cdot x := \sum_{i=1}^d w_i x_i. \] Multiply the vectors entry by entry, then sum. Two vectors go in; a single number comes out.

The dot product gives us linear regression in \(d\) dimensions. With weights \(w \in \mathbb{R}^d\) and a bias \(w_0 \in \mathbb{R}\), the model is \[ f(x) := w \cdot x + w_0. \] The prediction is a weighted sum of the input features, plus an intercept.

Transposes and the data matrix

Definition. The transpose of an \(a \times b\) matrix \(X\) is the \(b \times a\) matrix \(X^\top\) with \((X^\top)_{ij} := X_{ji}\). Transposing swaps rows and columns.

So far we have described models but not data. Given data points \(x_1, \dots, x_n \in \mathbb{R}^d\) (inputs only, no labels yet), we stack them into a single data matrix: \[ X := \begin{bmatrix} \text{---}\; x_1^\top \;\text{---} \\ \text{---}\; x_2^\top \;\text{---} \\ \vdots \\ \text{---}\; x_n^\top \;\text{---} \end{bmatrix}. \] By convention each row is one data point, the same way each row of a spreadsheet or data frame is one sample. We treat vectors as columns, so we transpose each \(x_i\) to make it a row. \(X\) has shape \(n \times d\): one row per sample, one column per feature.

Matrix multiplication

Definition. Given matrices \(X_1 \in \mathbb{R}^{a_1 \times b_1}\) and \(X_2 \in \mathbb{R}^{a_2 \times b_2}\), the product \(X_1 X_2\) is defined only if \(b_1 = a_2\): the number of columns of \(X_1\) must equal the number of rows of \(X_2\). The \((i, k)\) entry of the product is the dot product of row \(i\) of \(X_1\) with column \(k\) of \(X_2\), and the result has shape \(a_1 \times b_2\). A useful way to remember the shape: the shared inner dimension cancels.

Order matters: \(X_2 X_1\) is generally different from \(X_1 X_2\), and may not even be defined. One way to see why is that matrices can be viewed as functions, and multiplying matrices composes those functions. You can’t swap the order of function composition either.

Example. We can write the linear regression model as a single matrix product: \[ f(x) := \begin{bmatrix} x^\top & 1 \end{bmatrix} \begin{bmatrix} w \\ w_0 \end{bmatrix} = x \cdot w + 1 \cdot w_0. \] Check the shapes: the first factor is \(1 \times (d+1)\) and the second is \((d+1) \times 1\), so the product is defined and is \(1 \times 1\), a single number.

Bias lifting

Keeping the bias as a separate parameter is untidy, since it is really just one more parameter. Bias lifting removes it. Given data \(x_1, \dots, x_n \in \mathbb{R}^d\), weights \(w \in \mathbb{R}^d\) and a bias \(w_0 \in \mathbb{R}\), we can compute all predictions with a single matrix operation: \[ \underbrace{\begin{bmatrix} x_1^\top & 1 \\ x_2^\top & 1 \\ \vdots & \vdots \\ x_n^\top & 1 \end{bmatrix}}_{n \times (d+1)} \underbrace{\begin{bmatrix} w \\ w_0 \end{bmatrix}}_{(d+1) \times 1} = \underbrace{\begin{bmatrix} f(x_1) \\ f(x_2) \\ \vdots \\ f(x_n) \end{bmatrix}}_{n}. \] The first factor is a new data matrix: the original one with a column of ones appended to account for the bias. The second stacks all the parameters we want to learn into one vector of length \(d+1\).

From now on, we assume the bias has been lifted. The data matrix is \(X \in \mathbb{R}^{n \times (d+1)}\), each \(x_i \in \mathbb{R}^{d+1}\) ends in a 1, and the weight vector \(w \in \mathbb{R}^{d+1}\) includes the bias as its last entry.

Squared norms

Definition. Given a vector \(v \in \mathbb{R}^d\), its squared norm is \[ \|v\|^2 := v^\top v = \sum_{i=1}^d v_i^2. \] This measures the size of a vector, much like the absolute value does for a number. The shapes work out: \(v^\top\) is \(1 \times d\) and \(v\) is \(d \times 1\), so \(v^\top v\) is a single number.

Measuring how good a model is

Suppose someone hands us weights \(w \in \mathbb{R}^{d+1}\) and labels \(y_1, \dots, y_n \in \mathbb{R}\). How do we decide whether the model is any good? For each data point, the model predicts \(w \cdot x_i\), and the ground truth is \(y_i\); we want these to be close.

A first idea is to add up the deviations \(w \cdot x_i - y_i\). That fails: a positive error and a negative error can cancel, so a bad model could score zero. Squaring each deviation fixes this, which gives the total squared error: \[ \sum_{i=1}^n (w \cdot x_i - y_i)^2. \]

Why squares rather than absolute values? You could use absolute values, and other error measures exist. But squared error makes finding the best parameters much easier, as we will see below.

Check yourself. Which expression, written using the squared norm, equals the total squared error?

Answer

Build it up in three steps:

Applying the definition of the squared norm to the deviation vector squares each entry and sums them, which is exactly the total squared error.

Ordinary least squares

Training always follows the same pattern: labeled training data goes into a learning algorithm, which selects a trained model \(\hat f\) from a pool of models \(\mathcal{F}\). For linear regression, the setup is:

The name explains itself. Least because we minimize, squares because we minimize squared error, and ordinary because next week we will meet non-ordinary variants of this loss.

In general, choosing a learning objective does not guarantee an explicit formula for its minimizer. OLS is a fortunate exception.

Remark. \(L(w)\) is convex and differentiable. Differentiable means we can compute its gradient. Convex means that any \(w\) with \(\nabla L(w) = 0\) is a global minimizer. For a convex function, every stationary point sits at the bottom of the bowl. A general function can have many stationary points, only one of which is the global minimum. So to find \(w_{\text{OLS}}\), we just need to compute the gradient and find where it is zero.

We will use two gradient identities:

\(f(w)\) \(\nabla f(w)\)
\(w^\top b\) \(b\)
\(w^\top B w\) \(2Bw\), for symmetric \(B\)
Theorem

If \(X^\top X\) is invertible, then \[ w_{\text{OLS}} = (X^\top X)^{-1} X^\top y. \]

\(X^\top X\) is not always invertible. Even a real number can’t always be inverted (you can’t divide by zero), and for matrices non-invertibility is much more common. When \(X^\top X\) is invertible, though, everything on the right-hand side can be computed from the data matrix and the labels.

Proof. We want to minimize \(L(w) = \|Xw - y\|^2\). First rewrite the loss using the definition of the squared norm, then the transpose rules \((A - B)^\top = A^\top - B^\top\) and \((AB)^\top = B^\top A^\top\): \[ \begin{aligned} L(w) &= (Xw - y)^\top (Xw - y) = (w^\top X^\top - y^\top)(Xw - y) \\ &= w^\top X^\top X w - y^\top X w - w^\top X^\top y + y^\top y. \end{aligned} \] The two middle terms are transposes of each other, and each is a single number. A number equals its own transpose, so the two terms are equal and \[ L(w) = w^\top X^\top X w - 2\, w^\top X^\top y + y^\top y. \]

Step 1: compute the gradient. \(X^\top X\) is symmetric, so the gradient identities above give \[ \nabla L(w) = 2 X^\top X w - 2 X^\top y. \]

Step 2: find stationary points. Setting the gradient to zero: \[ 2 X^\top X\, w_{\text{OLS}} - 2 X^\top y = 0 \quad\Longrightarrow\quad X^\top X\, w_{\text{OLS}} = X^\top y. \]

Step 3: solve for \(w_{\text{OLS}}\). If \(X^\top X\) is invertible, meaning there is a unique matrix \((X^\top X)^{-1}\) with \((X^\top X)^{-1}(X^\top X) = I\), multiply both sides on the left by it: \[ (X^\top X)^{-1}(X^\top X)\, w_{\text{OLS}} = (X^\top X)^{-1} X^\top y \quad\Longrightarrow\quad w_{\text{OLS}} = (X^\top X)^{-1} X^\top y. \qquad \blacksquare \]

Practice

Before reading Step 1, expand \(L(w)\) yourself and check that the two middle terms are equal.