Perceptron and backpropagation

Forty-three people wrote digits on forms; the forms were scanned and every digit was shrunk to an 8 × 8 picture where a cell holds how many of its sixteen dots are black. Thirty people gave 3823 digits for training, thirteen others 1797 for testing. The perceptron, a linear rule invented in 1958, recognises 94.6 out of a hundred test digits after four passes over the training ones. A network with a hidden layer of 32 neurons, trained by backpropagation, gets about 96. Both models below learn right in the browser, in a second. Draw a digit, or take a test one.

The drawing is prepared the way the data were: the ink is cropped to its box, stretched into a 32 × 32 square and counted in 4 × 4 blocks; the middle shows what the model gets.

The idea of the perceptron

Every digit has its own vector of 64 weights and a bias. The answer is the digit whose sum “weight × cell” is the largest. The perceptron learns only from mistakes: if on a picture x it said p while the right answer is t, x is added to the weights of t and subtracted from the weights of p. Next time the sum of t on this picture will be larger and that of p smaller. Everything is in integers, there is no learning rate.

This is a linear classifier: the boundary between two digits is a hyperplane in the 64-dimensional space of pictures. If such a boundary exists with a margin, the perceptron finds it after a finite number of mistakes, however many pictures there are.

The digits do not satisfy these conditions: the training digits of ten classes apparently cannot be separated linearly, and the perceptron keeps making mistakes, 530 on the first pass and 196 on the fourth. And its test accuracy jumps: 92.2 %, 89.6 %, 92.0 %, 89.6 %, as the weights swing after the latest mistakes. The cure is averaging: the answer comes not from the last weight vector but from the mean of all vectors during training (Yoav Freund and Robert Schapire, 1999). The mean is kept without storing the history: a sum of the updates, each multiplied by its step number, is accumulated. The averaged perceptron gives 93.3, 94.3, 94.5 and 94.6 %, steadily and better.

What one boundary cannot do

On exclusive or the perceptron errs in every pass; in the listing it still makes four mistakes after the hundredth. Marvin Minsky and Seymour Papert showed in their 1969 book that such limits of one layer are fundamental: it cannot check whether the number of dots is even or whether a figure is connected. The way out is an intermediate layer: neurons each drawing its own boundary, and a next layer combining their answers. Two hidden neurons are enough for exclusive or: one draws the boundary “at least one 1”, the other “both are 1”.

Training a hidden layer

A hidden neuron has no right answer: nobody knows what it should output. So instead of the rule “wrong, move it” the network is trained by gradient descent: the step function is replaced by a smooth one (tanh, the sigmoid), the error by a smooth loss, and all weights move against its gradient. The question is how to compute the gradient over all weights quickly. It is worked through in detail, with an autograd of your own, in the chapter “Following the gradient backwards” of the course “Your own LLM from scratch”; here is why it is cheap.

A finite-difference derivative (move a weight by ±10⁻⁵ and recompute the loss) needs two passes per weight. For a 64 → 16 → 10 network with 1210 weights that is 2420 passes against one forward and one backward.

Code

The listing shows three things. The averaged perceptron on digits runs in integers, so Python and Go compute the same thing to the bit. Exclusive or with two hidden neurons was learned from five random starts out of ten; the others got stuck halfway. With eight neurons, from ten out of ten: spare neurons give the descent more ways. And the gradient check: finite differences over all 1210 weights agreed with the backward pass to 10⁻⁷.

The perceptron's weights are pictures: orange cells vote for their digit, blue ones against. They read worse than one would like: the zero has a blue middle (ink in the centre says “this is not a zero”), and the other pictures are mottled. The perceptron learns not to draw the digits but to tell them apart, and a cell's weight depends on which digits it is most often confused with. The network's hidden neurons are more mottled still: each reacts to some combination of cells, and meaning appears only in how the last layer adds them up. The chart below shows the test accuracy pass by pass: the perceptron's jumps, the averaged one's grows steadily, and the network goes higher, to 96.3 %.

What it costs

The time of the backward pass grows in proportion to the number of weights, that of finite differences in proportion to its square. At 1210 weights in Python the difference is already almost a hundredfold, at 4810 in Go more than a thousandfold. For a network with a billion weights, a finite-difference gradient would take two billion forward passes per training step; the backward pass costs about two.

Easy mistakes

• The last vector instead of the mean. Without averaging the perceptron answers with weights fitted to its latest mistakes, and its accuracy on new data jumps by a few percent from pass to pass.
• Equal initial weights. If all hidden neurons start with the same weights, their gradients are the same, and they stay copies of one another forever. Initial weights are random.
• Too few neurons. Two neurons for exclusive or are just enough, and the descent does not find the solution from every start. Networks are made with room to spare.
• Check the gradient with a tolerance and by absolute difference. The relative difference of tiny derivatives drowns in the rounding noise of the difference scheme; compare the absolute difference with the scale of the derivatives themselves.
• The scale of the inputs. Numbers 0…16 saturate tanh at once: the derivative 1 − tanh² is almost zero and learning stalls. The inputs are divided by 16.

Where it is used

Neural networks. Every modern network is trained by gradient descent, and the gradient is computed by backpropagation; in PyTorch, JAX and TensorFlow it is a backward pass over the recorded graph of the computation.

Linear models for text. The averaged perceptron was long a standard for tagging text (parts of speech, names) after Michael Collins's work of 2002: fast, simple and almost as accurate as the more complex models of the time.

Scientific computing. Backpropagation is a special case of reverse-mode automatic differentiation, which computes the derivatives of complex models in optimisation, mechanics and climate computations without deriving formulas.

Recognition. Digits and letters on envelopes, cheques and forms: the task on which neural networks first worked in large production systems, in the 1990s.

History

Frank Rosenblatt described the perceptron in 1958 and built the Mark I Perceptron machine: 400 photocells, the weights potentiometers turned by motors. Albert Novikoff proved the theorem on the finite number of mistakes in 1962. Marvin Minsky and Seymour Papert worked out in 1969 what one layer cannot do, and interest in neural networks fell for a long time. Reverse-mode differentiation was described by Seppo Linnainmaa in 1970, Paul Werbos suggested applying it to networks in 1974, and the method became widely known through the 1986 paper by David Rumelhart, Geoffrey Hinton and Ronald Williams. The handwritten digits of this article were collected by Ethem Alpaydın and Cenk Kaynak in 1998.

Problems

Compute all the derivatives of a small network in one backward pass.