Chapter 14: Backpropagation: passing the blame backwards
The one algorithm that trains every network, stepped through with real numbers.
Chapter 13 boiled all of training down to one line: new_weight = old_weight − (learning_rate × gradient). Find the slope for every weight, take a small step downhill, repeat. But it skipped the hard part. A network's mistake only shows up at the very end, at the output. So how do you find the slope for a weight buried in the middle?
The answer is backpropagation ("backprop" for short): one sweep from the output back toward the inputs that tells every weight how much of the mistake was its fault. Every network in this book is trained with it. You pressed buttons that ran it in chapter 8. Now you're going to run it yourself, one multiplication at a time.
Nine numbers, one mistake
Here is the smallest network that can solve the secret-door puzzle from chapter 7: two inputs (the left and right buttons), two hidden neurons, one output neuron. It has six wires, each with a weight, and three neurons, each with a bias. Nine adjustable numbers in all.
Show it one example: left button pressed, right button not. The door should open, so the right answer is 1. Our untrained network says 0.485. Too low.
Now the awkward question. Which of the nine numbers should change, and by how much? The weights right next to the output are obvious suspects. But the weight on the wire from the left button into the first hidden neuron had a hand in it too, from two steps away. Should it go up or down? A lot or a little?
Picture a soccer team that loses 3–2. Whose fault was it? The goalkeeper is the obvious suspect, but maybe the real trouble was a sloppy pass in midfield three moves earlier. Everyone on the field touched the result, some of them from a long way off. In machine learning this puzzle is called credit assignment: many numbers worked together to produce one answer, and you have to work out each one's share of the credit or the blame.
There is a slow, obvious way to find out, and you have been doing it with sliders since chapter 3: wiggle one number a tiny bit, run the network again, and see whether the answer got better or worse. Put it back. Wiggle the next one. That really does work. Hold on to it: later in this chapter it becomes our lie detector for backprop, and then you'll see why no real network could ever be trained that way.
The chain rule: multiply along the chain
Backprop is built on one idea from math, and you can borrow it from a bicycle.
Say your bike is in a gear where one full turn of the pedals spins the back wheel 3 times, and each spin of the wheel rolls you 2 meters down the road. How far does one turn of the pedals take you? You don't need a tape measure. It's 3 × 2 = 6 meters.
That's the whole idea. When one thing drives a second, and the second drives a third, the overall rate is the two rates multiplied. Add another link (say a fitness app gives you 5 points per meter) and you keep multiplying: 3 × 2 × 5 = 30 points per turn of the pedals. This is the chain rule: to find how strongly the start of a chain affects the end, multiply the rates of all the links in between.
The bike numbers are made up to keep the arithmetic easy. Real gears have messier ratios.
A network is a chain too. Here is everything that happens, in order, when you change the weight on the wire from the left button to the first hidden neuron, H1:
Five links, each with its own rate. Multiply the five rates together and you know exactly how fast the loss changes when that one weight changes. In this chapter we call that number the weight's blame: how fast the loss goes up as the number goes up. Positive blame means raising the number makes the mistake worse, so it should come down. Negative blame means it should go up.
Honesty note: "blame" is this book's nickname. The official word is the one from chapter 13, gradient. Same number.
Where do the rates come from? There are only three kinds of link.
- A wire. A neuron's total is a sum of signal × weight. Nudge the weight, and the total moves by the size of the signal. Nudge the signal, and the total moves by the size of the weight. So a wire's rate is whatever sits on the other side of the multiplication sign.
- A squish. Its rate is the slope of the sigmoid curve at that point, the slope you watched in chapter 11. For sigmoid there is a neat shortcut: slope = output × (1 − output). At an output of 0.5 that is 0.5 × 0.5 = 0.25, the steepest it ever gets.
- The loss. We measure the mistake the standard way. The miss is prediction − target, where the target is the right answer. The loss is half of the miss squared. Squaring makes a miss count the same whether it is too high or too low, and makes big misses count for much more than small ones. The "half" keeps the next step tidy: with it, when the prediction changes, the loss changes at a rate of exactly the miss.
Honesty note: chapter 4 measured the error the other way round, truth − prediction, and added its nudges. Here the miss is prediction − target and we subtract. Flip both signs and you land on the same nudge.
Why the blame travels backwards
You could multiply out those five links separately for each of the nine numbers. But look at the right-hand end of the chain: × slope of out's squish × the miss. Every one of the nine numbers has a chain that ends with those same two links, because every path through the network ends at the output.
So do the shared part once. Start at the loss, multiply back as far as the output neuron, and save the answer. That saved number is the blame at the output. Every wire feeding the output now needs just one more multiplication. Then hand the blame one layer further back, save it again, and every wire feeding the hidden neurons needs just one more multiplication too.
That is the whole algorithm. The blame moves from the back of the network to the front, one layer at a time, and nothing is ever worked out twice. It's also where the name comes from: the error is propagated back.
One round, four moves
A round of learning on one example starts with two moves you know: a forward pass to get a prediction, then the loss to score it. The third move is the new one. In the backward pass you start at the loss and hand the blame back through the network, layer by layer, until every number has its share. The fourth move nudges every number a little, against its blame.
The example is left = 1, right = 0. Backprop is about to hand out blame to all nine numbers. Which of them will get exactly zero?
A wire's blame gets multiplied by the signal it carried, and the right button sent a 0. Changing those two weights would not have changed the prediction at all, so they are not to blame. Step through below and watch them come out as 0.0000.
Step through one round of learning
A real network with real numbers. Pick an example, then keep pressing next step and read the panel under the diagram each time: it shows that step's arithmetic. On the diagram, blue wires have positive weights and red wires have negative ones, as in chapter 8. Anything orange is blame. After one full round, press train 2,000 more rounds and watch three things at once: the wires, the four answers, and the loss.
→ target 0
→ target 1
→ target 1
→ target 0
All four examples right now
The computer keeps about 16 digits; we show 3 or 4. If you check a line with a calculator, the last digit can be off by one.
What just happened
Two rules did all the work, used over and over:
- Blame for a wire = blame at the neuron it feeds × the signal it carried. (A bias counts as a wire that always carries 1.)
- Blame for a neuron = blame arriving × the weight on the wire it came back along × the slope of the neuron's own squish.
If you stepped through the first round on left = 1, right = 0, four things were worth catching:
- The idle wires got nothing. Both wires leaving the right button came out with a blame of exactly 0. They were carrying a 0, so nothing they could have done would have changed the answer. Chapter 4 said you can't blame a weight that wasn't involved. Now you've seen the multiplication that enforces it.
- The blame shrank on its way back. At the output it was −0.1286. One layer back it was −0.0151 at H1 and 0.0191 at H2, roughly seven to nine times smaller.
- One blame flipped sign. The wire from H2 to the output starts out negative (−0.6), so when H2 fires it pushes the prediction down. The prediction was too low. So the message that reaches H2 is the opposite of the one that reaches H1: fire less.
- One nudge is a small thing. The prediction moved from 0.485 to 0.591. Closer to 1, but nowhere near it. Learning is that, thousands of times.
Then you let it run. For roughly the first 250 rounds the loss sat on a shelf near 0.12, with every row's answer hovering around 0.5. That is the laziest way to be only half wrong about everything. Then, as the two hidden neurons settled into two different jobs, the loss fell off a cliff between roughly round 400 and round 700. After 2,001 rounds the two "door opens" rows come out at about 0.96 and the two "door stays shut" rows at about 0.05.
Look at the trained numbers on the diagram. H1 ended up with a big positive weight from the left button and a big negative one from the right: it fires for "left but not right". H2 is its mirror image, "right but not left". The output fires if either of them does. That is one of the solutions chapter 8 described, and nobody typed it in. Training even flipped the sign of the wire from H2 to the output: it started at −0.6 and ended near +7.5.
Honesty notes. (1) This widget nudges after every single example. Real training usually adds up the blame from a mini-batch of examples first, as in chapter 13, and then nudges once. (2) In a bigger network a hidden neuron feeds several neurons, not one. Blame then arrives along several wires, and the neuron simply adds it up. (3) The nine starting numbers were picked by hand, so that everyone sees the same walk-through and so that training reliably works. Two hidden neurons is the bare minimum for this puzzle, and from an unlucky start the network gets stuck. When we tried 20,000 random starting points (every number somewhere between −1 and 1), about 58% learned all four rows within 2,000 rounds. Nearly all the rest stalled with three rows right.
Is backprop telling the truth?
All that multiplying produced nine confident-looking numbers. How do you know they're right?
Use the slow, obvious method from the start of the chapter as a referee. If a weight's blame really is "how fast the loss changes when this weight changes", you can measure that directly: change the weight a tiny bit and watch the loss. Programmers who write backprop code by hand use exactly this test. It's called a gradient check: wiggle one number, measure how far the loss actually moves, and compare that with what backprop claimed.
For the example left = 1, right = 0, backprop says the blame for the wire left→H1 is −0.0151. Suppose you raise that weight by 0.001 and run the network again. What should happen to the loss?
Blame is a rate: loss change per unit of weight change. Multiply it by the size of the wiggle: −0.0151 × 0.001 = −0.0000151. Negative means the loss goes down. Check it below.
Check it by wiggling
The same network with its nine starting numbers. Choose a number (click it on the diagram or in the row below), press the wiggle button, and compare what the loss really did with what backprop said it would do. Then try a different wiggle size, and a different example.
→ target 0
→ target 1
→ target 1
→ target 0
They match, to about four decimal places. Not because backprop does any wiggling in secret, but because both methods measure the same thing: the slope of the loss, one number at a time. Wiggling finds the slope by trying it. Backprop works it out with the chain rule.
The small gaps come from the wiggle, not from backprop. A wiggle of 0.001 is small, but the loss still curves a little over that distance. Make the wiggle ten times smaller and the gap gets about ten times smaller with it. Backprop's number is the exact slope the wiggles are closing in on.
Why wiggling can't train a real network
Both methods gave the same nine numbers. So why bother with the chain rule at all? Count the work.
Wiggling needs one forward pass to get the starting loss, then one more forward pass for every number in the network. Backprop needs one forward pass and one backward pass, and the backward pass is about as much work as the forward one. That's it, however many numbers there are.
| Numbers in the network | Wiggling: passes for one nudge | Backprop: passes for one nudge |
|---|---|---|
| 9 (this chapter's network) | 10 | 1 forward + 1 backward |
| 1,000,000 | 1,000,001 | 1 forward + 1 backward |
| 1,000,000,000 | 1,000,000,001 | 1 forward + 1 backward |
Now put a clock on it. Suppose a single pass through a billion-weight network took one second. Finding every weight's blame by wiggling would take a billion seconds, which is almost 32 years, for one nudge. Backprop would take about two seconds. And training needs many thousands of nudges.
That is why this one algorithm made deep learning possible. The idea of rolling downhill is old and simple. What was missing was an affordable way to find out which way is downhill for millions of weights at once.
Backpropagation: run the example forward, measure the mistake, pass the blame backwards one layer at a time using the chain rule, and nudge every number in proportion to its share. One forward pass and one backward pass give the blame for every weight at once, whether there are nine of them or nine billion.
Run the same round in Python
This is backprop.py: the same network, the same nine starting numbers, the same first example. It prints every blame from the walk-through, runs the wiggle check on all nine numbers with the two columns side by side, then trains for 2,000 more rounds. If you step through one round on left=1, right=0 in the widget and then press train once, the widget and this script show the same numbers, digit for digit.
If you ran the script in chapter 8, you scrolled past two lines that probably looked like gibberish: d_o = err * dsigmoid(o) and d_h = (d_o @ w2.T) * dsigmoid(h). Read them again. The first is "blame at the output = miss × slope". The second is "hand it back along the weights, then multiply by the slope". It's the same two moves, written for a whole layer at once. (That script measures its miss as truth − prediction, so it adds its nudges where we subtract.)
Who thought of it?
Not one person. The 1986 paper you met in chapter 7, by David Rumelhart, Geoffrey Hinton and Ronald Williams, is the one that made backpropagation famous. It showed hidden neurons working out useful jobs for themselves, just like H1 and H2 did above, and its title says what it does: "Learning representations by back-propagating errors".
But the method underneath is older. In 1970 a Finnish student named Seppo Linnainmaa described it in his master's thesis, as a general way to get every slope of a long calculation in one backward sweep. He wasn't writing about neural networks at all. In 1974 Paul Werbos worked out the same backward method in his PhD thesis at Harvard, and in 1982 he showed how to use it on neural networks. Others found pieces of it too. People still argue about who deserves how much of the credit, which is a nice joke for an algorithm about credit assignment. Wikipedia's history of backpropagation has the longer story.
When the blame fades
You watched the blame shrink as it went back one layer. Every hop back multiplies it by a weight and by the slope of a squish, and for sigmoid that slope is never more than 0.25. One hop is no problem. But stack up many sigmoid layers and the blame picks up another small slope at every one of them. By the time it reaches the earliest wires there is almost nothing left, and those wires stop learning. This is the vanishing gradient problem from chapter 11: blame that fades to nearly zero on its way back through a deep network. It's also why that chapter's ReLU matters so much. ReLU's slope is exactly 1 wherever the neuron is switched on, so the blame passes through at full strength.
Nobody does this by hand
You just did backprop by hand for nine numbers. Nobody does that for nine million. But notice something about the two rules: neither one needed to know what the network was for, or how big it was. Each step only looked at its next-door neighbors. That means a program can do the whole backward pass for any network automatically, as long as it keeps notes on what happened on the way forward. In chapter 32 you'll build a tiny engine that does exactly that, and then meet the one professionals use.
In backprop.py, change all nine starting numbers to 0.5 and run it. One row never comes out right, however long you train. Look at the blame the script prints for H1's wires and for H2's wires. What do you notice, and why does it mean the two hidden neurons can never become different from each other? (This is why real networks always start from random weights.)
Why does backprop start at the output and work backwards, instead of starting at the inputs?
Every path through the network finishes at the output and the loss. Work that shared end out first, save it, and each earlier number needs only a multiplication or two more.
A hidden neuron is connected to the output by a wire with a negative weight. The prediction came out too low. What message does backprop send that hidden neuron?
The blame is multiplied by the weight on the wire it travels back along. A negative weight flips its sign, which is exactly right: that neuron's firing was dragging the prediction down.
A network has one million weights. You want every weight's blame for one example. Roughly how much work is that?
Wiggling has to rerun the whole network once per weight. Backprop reuses the saved blame at each layer, so one sweep back covers every weight.