Machines That Learned · Part 4

Who Is to Blame? Backpropagation and the Fifteen-Year Gap

The problem that stalled neural networks had an answer published in 1970, in a Finnish master's thesis, about rounding errors. It was rediscovered at least three times before anyone noticed what it was for.

The question: How can a network assign responsibility to weights it cannot directly observe at the output?

Big idea: Backpropagation sends error backward through the chain rule, but its history, compute needs, and vanishing gradients explain why the answer was not immediate.

The obstacle, stated exactly, is this.

A network guesses. The guess is wrong by some measurable amount. For the weights in the final layer this is easy to act on — you can see how each one moved the output, so you know which way to nudge it.

For a weight in the middle of the network there is no such measurement. Nobody ever told that unit what it was supposed to produce. It has no target. The only thing known is that somewhere downstream, the final answer came out wrong.

Which internal weight is to blame, and by how much?

This is the credit assignment problem, and it is the whole reason multilayer networks sat unused for fifteen years while everyone agreed that multiple layers would help.

The answer

The answer is the chain rule from calculus, applied backwards through the network.

The output error is a function of the last layer's weights, which are applied to the previous layer's outputs, which are functions of its weights, and so on back. Differentiating a composition of functions is exactly what the chain rule is for. Work backwards through the composition and each layer receives the error passed to it from the layer in front, scaled by how much it contributed.

That is all backpropagation is. It is not a new mathematical idea, which is precisely why the history is strange.

Invented, and invented, and invented

In 1970, Seppo Linnainmaa published a master's thesis at the University of Helsinki on representing the cumulative rounding error of an algorithm as a Taylor expansion of local rounding errors. It contains what is now called reverse-mode automatic differentiation — the general method, of which backpropagation in a neural network is one application. The thesis is about numerical accuracy. Neural networks are not the subject.

In 1974, Paul Werbos's Harvard doctoral thesis applied the technique to training neural networks directly. This is, as far as the record shows, the first time anyone connected the method to this problem. It attracted little attention; Werbos has said the climate for neural network research at the time made it difficult to publish.

In 1986, David Rumelhart, Geoffrey Hinton and Ronald Williams published "Learning representations by back-propagating errors" in Nature, alongside the two Parallel Distributed Processing volumes.

The 1986 paper is the one everyone cites, and the reason is in its title. The contribution was not the algorithm — the authors were aware they were not the first, and Hinton has said so repeatedly since. It was the demonstration of what the algorithm produces: hidden units that come to represent features nobody specified. Train a network on a task and the middle layers develop their own internal encoding of the structure in the data.

That is the claim that mattered. A network could invent its own representation. It reframed the whole enterprise from "fit a function" to "learn what the relevant features are", which is the thing hand-authored expert systems could never do.

Why the gap, really

Two things, and neither is about the mathematics.

Nobody was looking in the right place. Linnainmaa's thesis was in numerical analysis, in Finnish academic literature, about rounding error. There was no reason for anyone working on perceptrons to encounter it. Werbos's thesis reached the right problem but landed during the first winter, when the neural-network research community was small and dispersed.

The demonstrations were not possible yet. A learning algorithm that needs many passes over many examples needs a machine. The hardware of the mid-1970s could not show the method doing anything interesting enough to change minds. By 1986 it could — barely — and that was enough.

This is the field's most repeated pattern, and it will appear again in part 5 with different dates. The idea is usually old. What changes is the arrival of enough computation and enough data to show what the idea was worth.

The next wall, immediately

Backpropagation worked, and it worked well enough that by 1989 Yann LeCun had used it to train a convolutional network to read handwritten postal codes on real mail — a deployed application, not a demonstration.

But a new problem showed up as soon as networks got deep, and it is a direct consequence of the chain rule being a product.

The error signal arriving at an early layer is a product of many terms, one per layer it has passed through. If those terms are typically smaller than one, the product shrinks toward zero exponentially with depth. The early layers receive an error signal so small that they barely move. If the terms are larger than one, it explodes instead.

Sepp Hochreiter identified this in his 1991 diploma thesis at TU Munich, and Bengio, Simard and Frasconi analysed it formally in 1994. Deep networks were, in a specific and demonstrable sense, untrainable — and the deeper they got, the worse it was.

This is why the 1990s belonged to support vector machines. Vapnik's methods had solid theory, convex optimisation with no local minima to worry about, and they worked reliably on the dataset sizes of the era. Neural networks were finicky, slow, and had a proof against them.

The gate

The answer to vanishing gradients — the first good one — came from Hochreiter and Schmidhuber in 1997: Long Short-Term Memory.

The idea is to build an explicit memory cell whose default behaviour is to hold its value unchanged, with learned gates controlling what is written into it, what is kept, and what is read out. Because the cell's default is to preserve its contents, the error signal can travel across many time steps without being multiplied down to nothing at every one.

It is worth noticing what has happened here, because it is the thread this series has been following.

The field started with a unit that computes. It then needed a way to assign blame across layers. And when that broke over long distances, the fix was to add an explicit place to put something and explicit control over what gets written and read.

The problem had stopped being computation. It had become storage and retrieval — which is to say, memory, and specifically the question of how you get back to something you stored a long time ago.

LSTM went on to power the speech recognition and machine translation systems of the mid-2010s, nearly twenty years after it was published. Part 5 is about what happened first to computer vision, and part 6 is about the architecture that answered the retrieval question differently and replaced both.