Backpropagation

The network’s equations

The lesson’s network has inputs $x_1, x_2$, two hidden neurons, one output neuron, a sigmoid activation $\sigma(z)=1/(1+e^{-z})$, and no biases:

With $\mathbf x=(1,\,0.5)$, $t=1$, and $\mathbf w=(0.6,\,-0.3,\,0.7,\,0.5,\,0.8,\,-0.9)$ we get $\hat y\approx 0.460$ and $L\approx 0.146$. The starting weights were chosen so that every calculation shown with three decimals can be repeated by hand, using the already-rounded figures, without discrepancies (the lesson’s verify-data.ts script checks it, and compares the gradient with finite differences).

The chain rule, step by step

If $L$ depends on $\hat y$, which depends on $z$, which depends on $w_5$, the derivative of $L$ with respect to $w_5$ is the product of the derivatives of each link:

The sigmoid’s derivative is $\sigma'(z)=\sigma(z)(1-\sigma(z))$, so it is computed from the activation that was already stored. The first two factors form the neuron’s blame $\delta=\partial L/\partial z$. Going backward, layer by layer:

With the lesson’s numbers: $\delta_y=-0.540\cdot0.248\approx-0.134$; $\partial L/\partial w_5=-0.134\cdot0.611\approx-0.082$; $\delta_1=-0.134\cdot0.8\cdot0.238\approx-0.026$ and $\partial L/\partial w_1=\delta_1\,x_1\approx-0.026$. Since $w_6<0$, $\delta_2$ comes out with the opposite sign ($+0.024$). Note that the blames $\partial L/\partial w_5$ and $\partial L/\partial w_6$ do not add up to $\delta_y$: each weight gets the neuron’s blame multiplied by its own signal, not a share of it.

In layers and in matrix form

With $W^{(l)}$ the matrix that takes $\mathbf a^{(l-1)}$ to $\mathbf z^{(l)}$, the same ideas are written for any number of layers:

Each $\boldsymbol\delta^{(l)}$ is computed once from the next layer: that is what makes the method cheap. With ReLU, $\sigma'$ is replaced by $1$ if $z>0$ and $0$ otherwise.

Why it is cheap

For a scalar loss and $N$ weights, the reverse mode of automatic differentiation (the techniques for differentiating programs exactly; backpropagation is its special case for networks) delivers all $N$ derivatives in a single backward sweep. The forward mode, or probing with finite differences, needs one sweep per weight. The whole gradient costs a small constant times the cost of evaluating the function: Baydin et al. (2018), citing Griewank and Walther (2008), give $c<6$ and typically between 2 and 3, and Griewank (2012) calls it the “cheap gradient principle”.

In a large transformer, Kaplan et al. (2020) count about $2N$ FLOPs per token going forward, with $N$ the parameters excluding embeddings, and note that the backward pass costs approximately twice as much: hence their $\approx 6N$ FLOPs per training token. In exchange, the activations of the forward pass must be stored until they are used: the 1986 paper itself points out that the outputs of the intermediate layers in the forward pass are needed for the backward pass.

A limit: the blame can fade

Since $\sigma'(z)\le \tfrac14$, each layer of sigmoids contributes a factor of at most $\tfrac14$ to the blame: $(\tfrac14)^n$ after $n$ layers. The weights also multiply at every layer and could compensate, but with moderate weights the product shrinks exponentially. That is why deep networks favor other activations, residual connections, and variants such as the LSTM, topics of lessons 12 and 13.

Where it comes from, carefully

The name and the fame date from 1986, but the idea is older and had several discoverers:

• Linnainmaa. His master’s thesis (University of Helsinki, 1970, in Finnish; results in English in BIT, 1976) studies how the rounding error of an algorithm accumulates and proposes what is now called reverse mode. According to Griewank (2012), he did not present it as a way to get gradients cheaply.
• Werbos. His doctoral thesis in statistics (Harvard, August 1974) develops “ordered derivatives” and “dynamic feedback” for prediction models. He himself says (Werbos, 2006) that he wrote only a few words about neural networks, in chapter 5; Goodfellow et al. (2016) date to 1981 his proposal to apply it to training neural networks.
• Rumelhart, Hinton, and Williams (Nature, 1986). They use the same mathematics as this lesson: error $\tfrac12\sum(y-d)^2$, sigmoid, one forward pass and one backward pass that “propagates derivatives”. They acknowledge that David Parker and Yann LeCun discovered variants independently. In the paper, “back-propagation” names the whole learning procedure (with the update $\Delta w=-\varepsilon\,\partial E/\partial w$ and a variant with an acceleration term, what is now called momentum); today’s distinction, backpropagation for the gradient and another algorithm to learn with it, is the one Goodfellow et al. (2016) explain. The authors close by saying that the procedure, “in its current form, is not a plausible model of learning in brains”.

In code

import math

def sigma(z):
    return 1 / (1 + math.exp(-z))

X, T = (1.0, 0.5), 1.0

def forward(w):
    a1 = sigma(w[0] * X[0] + w[1] * X[1])
    a2 = sigma(w[2] * X[0] + w[3] * X[1])
    y = sigma(w[4] * a1 + w[5] * a2)
    return a1, a2, y, 0.5 * (y - T) ** 2

def backward(w):
    a1, a2, y, loss = forward(w)
    d_y = (y - T) * y * (1 - y)            # blame of the output neuron
    d_1 = d_y * w[4] * a1 * (1 - a1)       # blame of hidden 1
    d_2 = d_y * w[5] * a2 * (1 - a2)       # blame of hidden 2
    grad = [d_1 * X[0], d_1 * X[1], d_2 * X[0], d_2 * X[1], d_y * a1, d_y * a2]
    return loss, grad

w = [0.6, -0.3, 0.7, 0.5, 0.8, -0.9]
loss, grad = backward(w)
print(round(loss, 3), [round(g, 3) for g in grad])
# 0.146 [-0.026, -0.013, 0.024, 0.012, -0.082, -0.097]

# check: probe each weight (one extra forward pass per weight)
eps = 1e-6
check = []
for k in range(6):
    w2 = w.copy()
    w2[k] += eps
    check.append((forward(w2)[3] - loss) / eps)
print([round(c, 3) for c in check])
# [-0.026, -0.013, 0.024, 0.012, -0.082, -0.097]

# one gradient descent step: gradient descent does this, not backpropagation
eta = 1.0
w = [wk - eta * g for wk, g in zip(w, grad)]
print(round(forward(w)[3], 3))
# 0.129

What comes next

With real data the gradient is computed on a batch of examples rather than on a single one, and optimizers such as momentum or Adam transform that gradient before moving the weights. All of them receive the gradient from backpropagation. That is the topic of lesson 9.