How did Yann LeCun's team teach a neural network to read handwritten ZIP codes in 1989?

Much of today's computer vision, from photo apps that sort pictures to machines that read checks, traces back to a short paper from 1989. In it, a team at AT&T Bell Laboratories showed that a neural network could learn to read messy, handwritten digits straight from the pixels, with no human telling it which strokes or curves to look for.

The paper, "Backpropagation Applied to Handwritten Zip Code Recognition," appeared in the journal Neural Computation in 1989. Its first author, Yann LeCun, had joined the Adaptive Systems Research Department at Bell Labs in Holmdel, New Jersey, in October 1988. The department was led by Lawrence Jackel, one of the six co-authors.

What the team built

The problem came from the US Postal Service. Sorting mail by machine means reading ZIP codes, and people write digits in endless ways: big, small, slanted, careful or rushed, with pens, pencils and markers. The team worked with 9,298 single digits cut out of ZIP codes on envelopes that had passed through the post office in Buffalo, New York. They used 7,291 to train the network and kept 2,007 aside to test it on digits it had never seen. Some of those digits were so badly written that even a person would hesitate.

Contractors for the Postal Service had already found the ZIP code on each envelope and split it into separate digits, which is a hard job in itself. Each digit was then shrunk to a small 16 by 16 grid of gray pixels. From there, one network did everything else: it took the 256 pixel values in and produced ten outputs, one for each digit from 0 to 9. The highest output was the answer.

That was the bold part. A few months earlier, a Bell Labs system for the same task by John Denker and colleagues had used first layers whose settings were worked out by hand. In the new network, every connection was learned by backpropagation, the method for adjusting a network's weights by sending its errors backward through the layers.

How it worked

A network that connects every pixel to every unit has far too many knobs to tune from a few thousand examples. It tends to memorize the training digits instead of learning what makes a 3 a 3. LeCun's team built knowledge about images into the shape of the network instead.

The first hidden layer, called H1, held 12 small "feature maps," each an 8 by 8 grid of units. Each unit looked only at a 5 by 5 patch of the input image. And every unit in the same map used the exact same 25 weights. So a whole map acted like one small stencil slid across the picture, lighting up wherever its pattern appeared: perhaps a vertical stroke in one map, a curve's edge in another. Sliding one stencil over an image this way is what mathematicians call a convolution, which is where the name "convolutional network" comes from.

A second layer, H2, did the same thing on the maps from H1, combining simple features into more complex ones. Both layers also stepped across the image two pixels at a time, which kept the rough position of a feature while throwing away precise detail that does not matter for telling digits apart. A third layer of 30 units, and then the 10 outputs, were fully connected in the usual way.

Here is what weight sharing saved:

The network had 1,256 units in all. It was trained on a Sun workstation using software written by Léon Bottou and LeCun, and training took about three days.

The results

After 23 passes through the training set, the network got 0.14 percent of the training digits wrong (10 mistakes) and 5.0 percent of the test digits wrong (102 mistakes). In practice, a postal machine can refuse to guess when it is unsure; to reach a 1 percent error rate, the network had to set aside about 12 percent of the test digits for a human. Most of its errors came from digits that had been split badly from their neighbors, or from writing styles absent from the training set.

The team also tried an ordinary fully connected network with one hidden layer. It made 8.1 percent errors on the test set, far worse. The constrained design was also slightly better than the previous system with hand-designed first layers, even though much less knowledge about digits had been built into it. Some of the learned stencils even looked like the edge detectors found in animal vision.

To show it could work in the real world, they ran the trained network on an off-the-shelf AT&T DSP-32C signal-processing board inside a personal computer with a camera. The whole system read 10 to 12 digits per second, image capture included.

Why it matters

The idea of layered feature maps was not entirely new. Kunihiko Fukushima's neocognitron of 1980 had layers of shared-weight detectors, but its weights were not learned by backpropagation, and Alex Waibel's 1987 time delay network had shared weights across time for speech. What the 1989 paper did was combine shared-weight image layers with end-to-end backpropagation and prove it on a real industrial task. This network is now seen as the first of the LeNet family, which led to LeNet-5 and the MNIST digit benchmark in 1998.

Convolutional networks of this kind now power most computer vision. By 2014, almost every leading entry in the large ImageNet image-recognition challenge was built on one.

Why did sharing weights make such a difference?

Sharing weights does two jobs at once. First, it cuts the number of numbers to learn: about 65,000 connections, but fewer than 10,000 adjustable weights. With fewer knobs, a network trained on a few thousand examples is far less likely to memorize them and far more likely to handle new handwriting well. The paper puts this in the language of learning theory, but the everyday version is simple: a smaller set of choices needs less evidence.

Second, sharing builds in a fact about pictures: a stroke is still a stroke whether it sits on the left or the right of the image. One stencil that works everywhere means the network does not have to learn "vertical line, top left" and "vertical line, bottom right" as separate ideas.

That combination, fewer parameters plus a sensible assumption about the data, is still the core reason convolutional networks work so well on images, from digits on envelopes to photographs.