Backpropagation and gradient descent

What it is

A neural network is a set of simple units joined by connections. Each connection carries a number called a weight, which sets how strongly one unit influences another. Learning means finding weights that make the network’s outputs right for the examples it is shown. Backpropagation is a learning procedure for multilayer networks, which have hidden layers between the inputs and the outputs. Its name refers to sending the output error backward through the network. The method was presented in a Nature paper by David Rumelhart, Geoffrey Hinton and Ronald Williams, dated 9 October 1986.^[1]

The goal is to adjust the weights repeatedly so as to shrink the gap between the network’s actual output and the desired output. In the 1986 paper, that gap is measured as half the sum of squared differences over all cases and output units.^[1]

How it works

Picture a network that guesses too high. Every weight has some effect on that guess. The procedure works out how much each weight contributed to the error, then nudges each one a little in the direction that reduces the error. Repeating this over many examples gradually improves the network.

The procedure has two passes. In the forward pass, the state of each layer is computed from the layer below it. In the backward pass, the procedure starts at the output units and uses the chain rule to pass error derivatives back through the network. The chain rule is a calculus rule for quantities linked by a chain of steps: the effects of the steps multiply. At the end of the backward pass, every weight has a partial derivative, which says how a small change in that weight would change the error.^[1]

Gradient descent then changes each weight by an amount proportional to the negative of that derivative. The name describes the picture: the error is treated as the height of a landscape, and the weights are adjusted so that each step goes downhill. The 1986 paper also added an acceleration term that reuses part of the previous weight change, a device later commonly called momentum.^[1]

Where it came from

The key claim of the 1986 paper is that hidden units, which are neither inputs nor outputs, learn to represent important features of the task by themselves. The authors contrast this with the earlier perceptron-convergence procedure, which lacked the ability to create useful new features.^[1]

The idea was not the work of one person. The 1986 paper notes that variants of the procedure were discovered independently by David Parker and by Yann Le Cun. It also says the method can train recurrent networks by unrolling them into equivalent layered networks.^[1]

Where it is used today

ACM’s 2018 Turing Award citation says that the backpropagation algorithm is standard in most neural networks today. It credits Yann LeCun and Léon Bottou with the idea, used in modern deep learning software, of building learning systems as networks of modules trained by backpropagation through automatic differentiation.^[3]

In practice, most training uses stochastic gradient descent, which updates the weights after each training example rather than averaging over the whole training set. LeCun and colleagues reported in 1989 that this approach converged much faster than the true gradient on large, redundant datasets.^[2]

Limits

The error surface may contain local minima, so gradient descent is not guaranteed to find the best possible set of weights. The 1986 authors noted this, but they found that their networks very rarely got stuck in poor local minima.^[1]

Other limits are practical. Training usually needs many labelled examples and a large amount of computation, and a network trained this way is only as good as the examples it learns from.