Fitting a Model by Minimizing Loss

In Probability and Statistics you met the least-squares line, the line with the smallest sum of squared residuals, and used formulas for its slope and intercept. Here you will see where those formulas come from, and a second way to find the same line: the way that scales up to models with millions of parameters.

Key idea

A model $\hat{y} = mx + b$ has two parameters, $m$ and $b$. Its loss on the data $(x_{1}, y_{1}), \ldots, (x_{n}, y_{n})$ is the mean squared error $$L(m, b) = \frac{1}{n}\sum_{i=1}^{n} \left(y_{i} - (mx_{i} + b)\right)^{2}.$$ Fitting the model means minimizing $L$: either solve $\nabla L = \mathbf{0}$ exactly, or run gradient descent on $L$.

Why it works

The data are fixed numbers; the variables are $m$ and $b$. The inside $y_{i} - mx_{i} - b$ has derivative $-x_{i}$ with respect to $m$ and $-1$ with respect to $b$, so by the chain rule $$\frac{\partial L}{\partial m} = -\frac{2}{n}\sum x_{i}\left(y_{i} - mx_{i} - b\right), \qquad \frac{\partial L}{\partial b} = -\frac{2}{n}\sum \left(y_{i} - mx_{i} - b\right).$$ Setting both to $0$ gives the normal equations $$m\sum x_{i}^{2} + b\sum x_{i} = \sum x_{i}y_{i}, \qquad m\sum x_{i} + nb = \sum y_{i}.$$ $L$ is a quadratic bowl: its second-derivative test gives $D = \frac{4}{n^{2}}\left(n\sum x_{i}^{2} - \left(\sum x_{i}\right)^{2}\right) > 0$ whenever the $x_{i}$ are not all equal. So its one critical point is the minimum, the least-squares line.

Left: the data, the line and its squared residuals. Right: the loss over the $(m, b)$-plane. Each step of gradient descent moves the red dot downhill, and the line on the left follows. Press Show the exact answer to compare.

Worked examples

Worked example: The exact answer

Find the line that minimizes $L$ for the data $(0, 1)$, $(1, 3)$, $(2, 4)$, $(3, 4)$, $(4, 6)$.

Sums: $\sum x_{i} = 10$, $\sum y_{i} = 18$, $\sum x_{i}^{2} = 30$, $\sum x_{i}y_{i} = 47$, and $n = 5$.
Normal equations: $30m + 10b = 47$ and $10m + 5b = 18$.
Double the second, $20m + 10b = 36$, and subtract: $10m = 11$, so $m = 1.1$. Then $5b = 18 - 11$, so $b = 1.4$.
The residuals are $-0.4$, $0.5$, $0.4$, $-0.7$, $0.2$, so $L = \frac{0.16 + 0.25 + 0.16 + 0.49 + 0.04}{5} = 0.22$.

Answer: $\hat{y} = 1.1x + 1.4$, with $L = 0.22$

Worked example: One step of gradient descent

Same data. Start at $(m, b) = (0, 0)$ and take one gradient descent step with $\eta = 0.05$.

At $(0, 0)$ every prediction is $0$, so the residuals are the $y_{i}$ themselves.
$\frac{\partial L}{\partial m} = -\frac{2}{5}\sum x_{i}y_{i} = -\frac{2}{5} \cdot 47 = -18.8$ and $\frac{\partial L}{\partial b} = -\frac{2}{5}\sum y_{i} = -\frac{2}{5} \cdot 18 = -7.2$.
$(0, 0) - 0.05\langle -18.8, -7.2 \rangle = (0.94, 0.36)$.
The loss falls from $L(0, 0) = 15.6$ to $L(0.94, 0.36) \approx 2.12$. More steps creep toward $(1.1, 1.4)$.

Answer: $(m, b) = (0.94, 0.36)$

Worked example: A line through the origin

Fit $\hat{y} = mx$ to $(1, 3)$, $(2, 2)$, $(3, 7)$.

With one parameter the loss is a parabola: $$L(m) = \frac{1}{3}\left[(3 - m)^{2} + (2 - 2m)^{2} + (7 - 3m)^{2}\right] = \frac{1}{3}\left(14m^{2} - 56m + 62\right).$$
$L'(m) = \frac{1}{3}(28m - 56) = 0$ gives $m = 2$, the vertex of the parabola.
In general $m = \frac{\sum x_{i}y_{i}}{\sum x_{i}^{2}}$; here $\frac{28}{14} = 2$.

Answer: $\hat{y} = 2x$

In the picture the loss map is a long, tilted valley, because $\sum x_{i}^{2} = 30$ is much bigger than $n = 5$. As in gradient descent on a long valley, a step size above about $0.15$ makes the path blow up, and a small one crawls along the valley floor. For a straight line the exact answer is easy, so why bother with steps? Because most models have no formula. A neural network's loss is also a mean of squared errors, but of a bent-line function of its weights, and there gradient descent, with derivatives from backpropagation, is the tool that works.

Common mistake

Differentiating with respect to $x$. In $L(m, b)$ the $x_{i}$ and $y_{i}$ are numbers you were given; they never change. The variables are the parameters. Check: your $\frac{\partial L}{\partial m}$ should contain data values, $m$ and $b$, and no plain $x$.

Common mistake

Dropping the minus sign. The inside $y_{i} - mx_{i} - b$ has derivative $-x_{i}$ with respect to $m$, so $\frac{\partial L}{\partial m}$ starts with $-\frac{2}{n}$. Without that sign a gradient step climbs. Check: with positive data, a step from $(0, 0)$ should raise both $m$ and $b$.

This is the same line as ordinary least squares in the Econometrics course, and the normal equations are the matrix equation of least squares in linear algebra.

Fitting a Model by Minimizing Loss

Worked examples

Practice

Builds on

Leads to

Sources and further reading