Backpropagation: the full derivation

Everything backpropagation does, it does with the chain rule, and the chain rule is already differentiated. The previous lesson left it in its vector form (Jacobians multiplying together, a gradient coming in at one end and leaving converted into that of the layer before) and, with it, the reason why, as it stands, it can't actually be run: applying it parameter by parameter costs a complete run over the network for every single number there is to adjust. What's missing isn't new mathematics. It's an order of operations.

And that order is easier to see on a small network than a large one. Take the smallest network that still has a hidden layer: two inputs, two hidden neurons, one output. It has nine parameters (four input weights, two hidden biases, two output weights and one bias), so nine derivatives need computing. Behind those nine sit three numbers, one per pre-activation in the network. Once those three are known, each of the nine derivatives is a product of two factors, and neither factor has to be fetched from far away.

One number per pre-activation, and the derivatives that hang off it

Fix a layer $l$ and a single example. Differentiating with respect to a weight is already settled; what needs deciding is with respect to what it pays off to differentiate first, and the answer is the pre-activation. Call the error of layer $l$ the gradient of that example's loss with respect to $\mathbf{z}^{(l)}$, and write $\boldsymbol{\delta}^{(l)}$ for it:

one coordinate per neuron in the layer, and a column, the transpose of the one-row Jacobian the previous lesson used to write the gradient of a scalar. It's $\ell$ and not $\mathcal{L}$: the loss of one example, as everywhere in this block since the lesson on loss functionsBlock 2 · Lesson 5Loss functions: MSE and cross-entropyA loss sums up in one number how badly the network is doing, and between two candidates its derivative is what decides. Mean squared error hands over its smallest correction exactly where the network is wrong with the most confidence; cross-entropy, which comes from reading the output as a probability, leaves that derivative at the plain difference between what was predicted and the label..

With that vector in hand, the parameters of layer $l$ come out without any walking at all. Its pre-activation is

or, coordinate by coordinate,

Look at where any particular weight shows up: $\mathbf{W}^{(l)}_{jk}$ appears in exactly one of the $d_l$ coordinates, the $j$-th, so only one summand of the previous lesson's sum over paths survives:

because $\partial z^{(l)}_i / \partial \mathbf{W}^{(l)}_{jk}$ equals $h^{(l-1)}_k$ when $i = j$ and zero in the other $d_l - 1$ cases, and the bias derivative is the same computation with a $1$ in place of an activation. Stacked, the $d_l \times d_{l-1}$ entries form an outer product:

A column of $d_l$ by a row of $d_{l-1}$, exactly the shape of $\mathbf{W}^{(l)}$, and that match is the cheapest check there is: if an outer product doesn't come out with the shape of the matrix it's differentiating, something along the way got transposed.

Now count what happened here, because it's the whole argument. Layer $l$ has $d_l \cdot d_{l-1} + d_l$ parameters, and every one of its derivatives comes out of only $d_l + d_{l-1}$ numbers: the coordinates of $\boldsymbol{\delta}^{(l)}$ and those of $\mathbf{h}^{(l-1)}$, which the forward pass has already computed. In the first layer of the previous lesson's network, that's thirty-six derivatives read off twelve numbers. One question remains, and it takes up the rest of this lesson: where does $\boldsymbol{\delta}^{(l)}$ actually come from?

Where that number comes from: the backward recurrence

The value of $\boldsymbol{\delta}^{(l)}$ comes from the layer next door. A layer's error is computed out of the error of the layer after it, which is exactly why the journey runs from the end back to the beginning.

Start at the end, where there's nothing left to do. The last layer delivers $\mathbf{z}^{(L)}$, softmax turns it into $\hat{\mathbf{y}}$, and cross-entropy compares that with the label; the lesson on loss functionsBlock 2 · Lesson 5Loss functions: MSE and cross-entropyA loss sums up in one number how badly the network is doing, and between two candidates its derivative is what decides. Mean squared error hands over its smallest correction exactly where the network is wrong with the most confidence; cross-entropy, which comes from reading the output as a probability, leaves that derivative at the plain difference between what was predicted and the label. already differentiated that entire pair, and out of the two together came

Nothing that follows depends on it being that particular vector. Change the loss or the output activation and that vector changes; the rest of the algorithm never even finds out, since it only ever receives it. The small network from the opening is the running example, and this is the place to say what hasn't been said about it yet: it carries a sigmoid in both layers and the loss $\tfrac{1}{2}\left(\hat{y} - y\right)^{2}$ (the $\tfrac{1}{2}$ is the convention the lesson on loss functionsBlock 2 · Lesson 5Loss functions: MSE and cross-entropyA loss sums up in one number how badly the network is doing, and between two candidates its derivative is what decides. Mean squared error hands over its smallest correction exactly where the network is wrong with the most confidence; cross-entropy, which comes from reading the output as a probability, leaves that derivative at the plain difference between what was predicted and the label. chose not to adopt, kept here only so the numbers come out short), so its output layer enters with $\delta^{(2)}_1 = \left(\hat{y} - y\right)\hat{y}\left(1 - \hat{y}\right)$ rather than $\hat{y} - y$: the extra factor is the sigmoid, which here has nothing to cancel against. Everything else stays identical.

Now for the backward step. Let $l < L$. The pre-activation of the next layer is built out of this one's in two moves:

and the previous lesson already has the Jacobian of both pieces: an affine map's Jacobian is its own matrix, and a $\varphi$ applied coordinate by coordinate has a diagonal one. Compose them,

and that same lesson said exactly what to do with a Jacobian when what's being propagated is the gradient of a scalar: transpose it, and multiply the gradient in from the right. Since $\text{diag}$ is symmetric and transposing a product reverses the order of its factors,

which, rewritten with the Hadamard product so the diagonal is never actually built, is the form that reaches real code:

Read it as two separate moves, because they do two different jobs. The first, $\left(\mathbf{W}^{(l+1)}\right)^{\top}\boldsymbol{\delta}^{(l+1)}$, transports: it shares the error from the $d_{l+1}$ neurons above out among the $d_l$ below, each according to the weight it used to feed them on the forward pass. Same weights, no new parameter anywhere. The second masks: it multiplies whatever reaches each neuron by that neuron's own slope. With ReLU (rectified linear unit), that slope is $0$ or $1$, so a neuron with a negative pre-activation receives a zero and cuts off everything that was coming down from above.

The whole algorithm, written out for two hidden layers

With $L = 3$ it fits whole, with no ellipses needed. Forwards, which is the lesson on the forward passBlock 2 · Lesson 4The forward pass in matrix formA whole layer collapses into one matrix product, and a whole batch fits into that same product with one row per example. That is where the transpose comes from (examples stack as rows, but an example itself is a column), and chaining those products from input to output gives you the forward pass, whose parameter cost never depends on how many examples go through at once.:

keeping the $\mathbf{h}^{(l-1)}$ and the $\mathbf{z}^{(l)}$ along the way. Backwards, from the end back to the beginning:

and out of those three vectors come all six gradients:

That's backpropagation, complete. Three errors, six gradients, and not one step more than that.

What it costs can be read straight off the shapes. The backward pass does one matrix-by-vector product at each layer, using the same matrices as the forward one: the same order of operations, done once, no matter what $L$ is. Probing the parameters one at a time costs two forward passes per parameter, and nothing bounds how many parameters there might be. In the network from the code cell below that's $63$ parameters, $126$ passes against a single one; with the twenty-thousand-entry vocabulary from the lesson on the forward passBlock 2 · Lesson 4The forward pass in matrix formA whole layer collapses into one matrix product, and a whole batch fits into that same product with one row per example. That is where the transpose comes from (examples stack as rows, but an example itself is a column), and chaining those products from input to output gives you the forward pass, whose parameter cost never depends on how many examples go through at once., the ratio never changes shape, only size.

There is a price, and it's worth naming, because it isn't time. The backward pass needs the $\mathbf{h}^{(l-1)}$ and the $\mathbf{z}^{(l)}$ of every layer, so all of them have to stay in memory while the forward computation runs. A network that only predicts can throw each layer away the moment it's used; one that's about to train cannot, and that memory grows with both depth and batch size.

From the explorable to a network with two hidden layers

Every symbol is now defined, so here's the whole algorithm walked through slowly on the small network from the opening: the sixteen steps that run from the loss to the nine derivatives, one by one, with their actual numbers.

The first cell is that same network with those same weights, so you can compare the two figure by figure. Run it and read the output against the explorable's steps: the three errors first, then the nine gradients. The last line probes all nine parameters one at a time, the previous lesson's check applied here.

The numbers match the explorable's to three figures, and so do the names, so you can read the two side by side. The third line shows the two moves separately. The transport leaves $\partial \ell / \partial \mathbf{h}^{(1)} = (-0.079,\ 0.068)$: a single error, $-0.113$, shared between the two hidden neurons according to their weights $0.7$ and $-0.6$, which is why the second coordinate flips sign. The masking is the $(0.238,\ 0.222)$ right beside it, the derivative of the sigmoid at each pre-activation.

Now look at $\nabla_{\mathbf{W}^{(1)}}\ell$, which reads $(-0.019,\ -0.009)$ on top and $(0.015,\ 0.008)$ below. Its first column is $\boldsymbol{\delta}^{(1)}$ untouched, since $x_1 = 1$; the second is $\boldsymbol{\delta}^{(1)}$ halved, since $x_2 = 0.5$. That's an outer product seen up close, and it's the whole reason nine derivatives collapse into three numbers and two inputs.

The second cell is the reviews network with one extra hidden layer, where the recurrence applies twice instead of once: eight inputs, four hidden neurons, three more, and three outputs with softmax. I chose the weights so the pre-activations would come out round. Run it and watch for two things: where zeros appear, and the last two lines.

The zeros are ReLU at work, and there are two of them. The fourth neuron of the first hidden layer has $z^{(1)}_4 = -1.5$, and the second neuron of the second layer has $z^{(2)}_2 = -1.25$: both are switched off for this review, and both assign a zero to their $\boldsymbol{\delta}$. That zero shows up twice in $\nabla_{\mathbf{W}^{(2)}}\ell$, and for two different reasons. Its second row is null because $\delta^{(2)}_2 = 0$, meaning none of that neuron's four weights gets corrected; its fourth column is null because $h^{(1)}_4 = 0$, meaning the input those weights read contributes nothing at all. Row and column are the two halves of the outer product, and each vanishes for its own reason.

The last two lines are really the whole lesson. The $63$ gradients agree with the probe to $10^{-10}$, which is the probe's own error and not the algorithm's. And getting them by probing cost $126$ forward passes against the single one backpropagation needs. That's in a toy network, with three layers and eight inputs: the ratio is the number of parameters times two, so it only grows as weights get added, and it never stops growing.

Test your intuition

Four questions (a gradient read off an error, what exactly gets reused, the shapes of the backward pass, and what happens if the forward one is thrown away), plus a challenge that is the whole algorithm.

The algorithm is complete, and it hasn't trained anything yet. The two cells compute the gradient of one example with weights I supplied, print it, and stop there: nobody has subtracted anything, and nobody has started over. What's missing to close the circle has already been written down, back in the lesson on gradient descentBlock 2 · Lesson 6Gradient descentThe gradient gathers one partial derivative per parameter and points, among all possible directions, at the one that raises the loss the most; subtracting a little of it each time is the entire method. How much "a little" turns out to be decides between converging, bouncing and diverging, and the whole sum can be worked out on a parabola. ($\theta_{t+1} = \theta_t - \eta\,\nabla_{\theta}\mathcal{L}$), waiting for exactly the gradient this lesson has now produced.

Putting the two halves together calls for three decisions neither lesson has made yet. Examples arrive $B$ at a time, so the errors stop being columns and $\mathcal{L}$ goes back to being the mean of the $\ell$. The weights have to start somewhere, and the obvious choice, all of them at zero, fails for a reason you can read straight off the formula for $\boldsymbol{\delta}$ derived above. And when to stop has to be decided too. Making those three calls, mounting them on a multilayer perceptron (MLP) written from scratch, and watching the loss actually fall, is the next lesson, on implementing an MLP.