← All notes · ML revision (DA5400)

Lecture 29 · Regression

Solving Linear Regression in Closed Form

Write the problem with matrices, set the gradient to zero, and linear regression has an exact formula for the best weights: $w^\star=(XX^\top)^{+}Xy$. It looks a lot like PCA's covariance matrix, except the labels come in too. The lecture ends with four questions that the next lectures answer.

Source: this lecture on YouTube (≈13 min). Previous: L28 · Next: L30.

1 · The same problem, with matrices

Stack the data points as columns of a $d\times n$ matrix $X$, so $X^\top$ has one point per row. Put the labels in an $n\times1$ vector $y$ and the weights in a $d\times1$ vector $w$. Then $X^\top w$ is the vector of all predictions $(x_1^\top w,\dots,x_n^\top w)$, and the total squared error is a squared length:

$$\sum_{i=1}^{n}(w^\top x_i-y_i)^2=\lVert X^\top w-y\rVert^2=(X^\top w-y)^\top(X^\top w-y).$$

This is an unconstrained (any $w\in\mathbb R^d$ allowed), quadratic (from the squared error) minimisation problem: a bowl with a single bottom.

2 · Find the bottom: gradient = 0

  1. Take the gradient, the vector of partial derivatives with respect to each $w_j$ (a good exercise to verify): $\;\nabla_w=2XX^\top w-2Xy.$
  2. Set it to zero to get the normal equations: $\;XX^\top w=Xy.$
  3. Solve: $\;\boxed{w^\star=(XX^\top)^{+}\,Xy}$

Here $^{+}$ is the pseudo-inverse. If $XX^\top$ is invertible, it's just the ordinary inverse. If not (some features are redundant, so the matrix isn't full rank), many $w$ fit equally well, and the pseudo-inverse picks the one with the smallest length, the "least-norm solution".

One feature, no intercept, so $w$ is a single number and the error is a parabola in $w$. Drag $w$: the left chart shows the line and its errors (the red segments), the right shows where you are on the error bowl.

–
total squared error
–
w* = Σxᵢyᵢ / Σxᵢ²

With one feature, $XX^\top=\sum_i x_i^2$ and $Xy=\sum_i x_iy_i$ are plain numbers, so $w^\star=\sum_i x_iy_i/\sum_i x_i^2$.

3 · A connection to PCA

$XX^\top$ is a $d\times d$ matrix: a (scaled) covariance-like matrix, the same object PCA's eigenvectors come from. So the regression solution also involves this matrix, here through its inverse. The key difference: PCA is unsupervised, while regression must match the labels, and $y$ enters through the $Xy$ term.

4 · Four questions for the next lectures

  1. Geometry: what does $w^\star=(XX^\top)^+Xy$ mean geometrically? → L30
  2. Computation: is it expensive to compute, like the eigenvectors in PCA? → L31
  3. Non-linear relationships: what if the features relate to the label quadratically, cubically and so on? → L32
  4. A probabilistic view: what exactly is the "noise"? → a later lecture

Key takeaways

  1. Matrix form: minimise $\lVert X^\top w-y\rVert^2$, an unconstrained quadratic.
  2. Gradient $2XX^\top w-2Xy=0$ gives the normal equations, so $w^\star=(XX^\top)^+Xy$.
  3. The pseudo-inverse handles a non-invertible $XX^\top$ by choosing the least-norm solution.
  4. Like PCA, it involves the covariance-like $XX^\top$; unlike PCA, the labels $y$ matter too.