6.6 Machine learning and linear models

Big idea

A data set is a list of observations, each pairing some inputs with an output. A model proposes that the output is a combination of known functions of the inputs, with unknown weights. Plug every observation into the model and you get one equation per observation, all sharing the same unknown weights.

Stack those equations and you have a matrix equation. The matrix, built from the inputs, is called the design matrix; the unknown weights are the parameter vector; the outputs are the right-hand side. With more observations than parameters the system is almost always inconsistent, so it gets solved by least squares, and the fitted values are the projection of the output vector onto the column space of the design matrix.

That is the whole of supervised linear learning. Training a model means solving normal equations. The vocabulary changes between a statistics course, a regression textbook, and a machine learning library, but the matrix is the same matrix.

Decoder

“Linear model” does not mean the graph is a straight line. It means the model is linear in the parameters. Fitting a parabola $y = \beta_0 + \beta_1 x + \beta_2 x^2$ is a linear model, because the unknowns enter as multipliers of known numbers: once you have the data, $x^2$ is just another column of numbers.

That is why one method covers straight lines, polynomials, several predictors at once, and combinations of sines and cosines. The work is always the same: decide which known functions of the inputs get a weight, evaluate them at every data point to build the columns, and solve.

A model that is not linear in the parameters, such as $y = \beta_0 e^{\beta_1 x}$ with $\beta_1$ in the exponent, falls outside this method entirely.

Definitions and results

Design matrix and parameter vector. For $n$ observations and $p$ model terms, the design matrix $X$ is $n \times p$: row $i$ holds the values of the $p$ model terms at observation $i$. The parameter vector $\beta$ is in $\mathbb{R}^p$, and the observation vector $\mathbf{y}$ is in $\mathbb{R}^n$. The model asserts $\mathbf{y} = X\beta + \epsilon$, where $\epsilon$ is the vector of residuals.

Fitting by least squares. The fitted parameters $\hat{\beta}$ solve the normal equations $X^TX\hat{\beta} = X^T\mathbf{y}$. The fitted values are $X\hat{\beta}$, the orthogonal projection of $\mathbf{y}$ onto $\text{Col}\,X$, and the residual vector is $\mathbf{y} - X\hat{\beta}$.

Least-squares line. With model terms $1$ and $x$, the design matrix has a column of ones and a column of the input values. The fitted line $y = \hat{\beta}_0 + \hat{\beta}_1 x$ is the one minimizing the sum of squared vertical distances from the data points to the line. Vertical, not perpendicular: the residual is measured in the output direction only.

Several predictors. With two inputs and model terms $1$, $x$, and $y$, the same machinery fits a plane $z = \beta_0 + \beta_1 x + \beta_2 y$ in three dimensions. Adding predictors adds columns and nothing else changes.

Curves. Terms $1$, $x$, $x^2$ fit a parabola; adding $x^3$ fits a cubic. Each new power is one more column of the design matrix, evaluated at the same input values.

Residuals are orthogonal to the columns. Since the fitted values are a projection, $X^T(\mathbf{y} - X\hat{\beta}) = \mathbf{0}$. When the model includes a constant term, the first of those equations says the residuals sum to zero. That is a free check on every fit you compute.

Independent columns. The fit is unique exactly when the columns of $X$ are independent. Two predictors that are scalar multiples of each other, or a polynomial fitted through fewer distinct input values than it has terms, make $X^TX$ singular and the parameters undetermined.

Worked examples

A least-squares line

Fit $y = \beta_0 + \beta_1 x$ to the four points $(0, 1)$, $(1, 2)$, $(2, 4)$, $(3, 7)$. The design matrix and observation vector are

$$ X = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}, \qquad \mathbf{y} = \begin{bmatrix} 1 \\ 2 \\ 4 \\ 7 \end{bmatrix} $$

Compute the normal equations. $X^TX$ holds the count, the sum of the inputs, and the sum of their squares:

$$ X^TX = \begin{bmatrix} 4 & 6 \\ 6 & 14 \end{bmatrix}, \qquad X^T\mathbf{y} = \begin{bmatrix} 1 + 2 + 4 + 7 \\ 0 + 2 + 8 + 21 \end{bmatrix} = \begin{bmatrix} 14 \\ 31 \end{bmatrix} $$

Divide the first equation by $2$: $2\beta_0 + 3\beta_1 = 7$. Multiply that by $3$ and subtract from the second: $5\beta_1 = 10$, so $\beta_1 = 2$ and $\beta_0 = (7 - 6)/2 = 0.5$. The fitted line is $y = 0.5 + 2x$.

Check with the residuals. The fitted values at $x = 0, 1, 2, 3$ are $0.5$, $2.5$, $4.5$, $6.5$, so the residuals are $0.5$, $-0.5$, $-0.5$, $0.5$. They sum to zero, as the constant column requires. Dotted with the input column they give $0(0.5) + 1(-0.5) + 2(-0.5) + 3(0.5) = -0.5 - 1 + 1.5 = 0$, as the second column requires. The sum of squared residuals is $4(0.25) = 1$.

Two predictors at once

Fit $z = \beta_0 + \beta_1 x + \beta_2 y$ to the four observations $(x, y, z)$ equal to $(0,0,1)$, $(1,0,2)$, $(0,1,4)$, $(1,1,7)$. The design matrix carries a column of ones, a column of $x$ values, and a column of $y$ values:

$$ X = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \qquad \mathbf{z} = \begin{bmatrix} 1 \\ 2 \\ 4 \\ 7 \end{bmatrix} $$

Then

$$ X^TX = \begin{bmatrix} 4 & 2 & 2 \\ 2 & 2 & 1 \\ 2 & 1 & 2 \end{bmatrix}, \qquad X^T\mathbf{z} = \begin{bmatrix} 14 \\ 9 \\ 11 \end{bmatrix} $$

Halve the first equation to get $2\beta_0 + \beta_1 + \beta_2 = 7$. Subtracting it from the second equation leaves $\beta_1 = 2$; subtracting it from the third leaves $\beta_2 = 4$. Then $2\beta_0 + 6 = 7$ gives $\beta_0 = 0.5$. The fitted plane is $z = 0.5 + 2x + 4y$.

Check: the fitted values are $0.5$, $2.5$, $4.5$, $6.5$, so the residuals are again $0.5$, $-0.5$, $-0.5$, $0.5$. Their sum is zero, their dot product with the $x$ column is $-0.5 + 0.5 = 0$, and with the $y$ column is $-0.5 + 0.5 = 0$. All three orthogonality conditions hold.

Building a design matrix for a curve

Suppose the same four inputs $x = 0, 1, 2, 3$ are to be fitted with a parabola $y = \beta_0 + \beta_1 x + \beta_2 x^2$. The design matrix is

$$ X = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{bmatrix} $$

with the third column holding the squared inputs. Nothing about the solving method changes: form $X^TX$ and $X^T\mathbf{y}$, solve the $3 \times 3$ system, read off three parameters instead of two.

Notice what the columns are. Column $j$ is one model function sampled at the four inputs, so $X\beta$ is a linear combination of those sampled functions. Fitting a curve is choosing the combination of sampled functions closest to the sampled data, which is a projection onto a three-dimensional subspace of $\mathbb{R}^4$. The curve language and the projection language describe one computation.

Practice

The fitted values are a projection onto the column space of the design matrix, so the projection drill is the core skill here.

Evaluating a model at the data means multiplying the design matrix by a parameter vector, and checking a fit means doing that quickly and correctly.

Quiz

Five items on design matrices, fitted parameters, and residuals.