Backpropagation

Why groping about is impossible

The readiest way to find the slope of a dial is to move it a very little to the right and measure how much the total error changes. The method is perfectly logical and intuitive: it is exactly what we do when adjusting the shower until we find a pleasant temperature.

But here is the hidden problem: for every single dial you have to run the network from end to end on all your training data! In a tiny network with 37 dials, that calls for some 70 passes for a single step of learning. In a modern model with tens or hundreds of billions of parameters, trying the dials one at a time would take thousands of years just to take one small step on the mountain of error!

We need an astoundingly fast method, able to compute the slope of every dial at once. Such a method exists; it is called backpropagation (or backpropagation) and it is the true invisible engine that made modern artificial intelligence possible.

Apportioning the blame: an inquiry from tail to head

At the output of the network everything is clear: we know what answer the machine gave, we know what the correct answer was, and we can measure the mistake (the cost) precisely. The question is: who is to blame for this error, and by how much?

For the final neuron at the output the calculation is simple: the blame of each connection entering it depends on how strong the signal was that passed along that wire. But what do we do with the hidden neurons in the earlier layers, which do not see the final output at all?

Here the analogy of the assembly line in a factory comes in. When a faulty part comes off the end of the line, the engineer works backwards: each workshop receives a share of the responsibility proportional to the influence it had on the final product. A neuron in the hidden layer that contributed heavily to the wrong decision will receive a large “blame”; a neuron that all but kept silent will receive a negligible one. Once the blame of each hidden neuron is settled, we pass it further back to the earlier layers, until we reach the raw input data.

The chain rule: the cause of causes

Beneath the mathematical dome of this inquiry lies a rule of disarming simplicity, known since the dawn of differential calculus: the chain rule. It says that if event A influences B, and B in its turn influences C, then the total influence of A on C is simply the product of the two partial influences.

Think of a series of cogwheels: if turning the first wheel by one millimetre turns the second by 3 millimetres, and the second turns the third by 2 millimetres, then turning the first wheel will move the third by 6 millimetres ($3 \times 2$). Backpropagation applies this multiplication systematically along every wire of the network.

The beauty of backpropagation lies not in some unheard-of mathematical formula but in impeccable bookkeeping: we compute the effects from the end towards the beginning and store the partial results, so that we never compute the same stretch of road twice!

Why it is astoundingly cheap

The magic of its efficiency comes from a geometric property of the network: thousands of different connections pass through the same intermediate neurons. Instead of computing the influence of every connection from scratch, we compute the intermediate neuron’s blame once and share it instantly among all the connections entering it.

The result is a colossal technological victory: the pass backwards through the whole network takes about as long as a single pass forwards! However great the number of dials — dozens, millions or billions — the cost stays unchanged: only two passes per step (one forward to compute the answer and one back to compute the slopes).

If one pass through the network took a thousandth of a second, computing by groping on a model with a billion dials would take nearly 32 years for a single step of learning! By backpropagation the same step takes only two thousandths of a second. That is the difference between the impossible and the achievable.

The hidden price: the memory training needs

There is nevertheless a price to be paid for this astonishing speed: an enormous consumption of memory. To compute the blame of a connection on the way back, the algorithm absolutely must know what signal passed through it during the forward pass. That means all the intermediate values of every neuron have to be kept in the graphics card’s memory until the returning wave reaches them.

Here is a practical distinction the wider public rarely knows: to use a trained model (to put a question to an AI assistant, say) is several times cheaper in memory than to train that model! When using it you can throw away the values of the earlier layers as you advance; when training, though, you are forced to retain the whole history of the forward pass, alongside complete copies of all the slopes.

The safety test: checking the slopes

How can we be sure that the mathematical formulas of backpropagation are correctly implemented in code and that no hidden error lurks there? Here the slow method of groping returns as an irreplaceable tool of control!

Although it is far too slow to train a large network, moving each dial slightly gives the true mathematical slope, free of any ambiguity. Engineers compare the slopes computed by backpropagation with those obtained by this method on a small test network. If the figures agree to the fifth decimal (as you can see in the table below), we have proof that the algorithm works impeccably.

Without this check, a mistake slipped into a minus sign or a multiplication could let the network go on training, but wretchedly and without showing any error message on the screen.

A rekindled spark: the history of backpropagation

The idea of sending errors back through a chain of equations was discovered independently by several researchers as early as the 1960s. But its fame and its present form exploded in 1986, thanks to a resounding paper by David Rumelhart, Geoffrey Hinton and Ronald Williams.

The great contribution of that moment was not the pure mathematics alone but a firm conviction that shattered the general scepticism: neural networks with many layers really can be trained in practice! The nearly twenty years of apathy that followed the book about exclusive-or were swept away, opening the road to the future.

Once we have backpropagation, we know how to train any network, however large. But when we try to apply this general structure to images with millions of pixels, we run into an explosion in the number of connections. To see the world truly, we need an architecture designed specially for space: in the next lesson we discover convolution.