Study guide · Computer vision · 1998

Gradient-Based Learning Applied to Document Recognition

Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner · Proceedings of the IEEE

Can a machine learn to read handwriting from examples alone, instead of relying on features that engineers design by hand? This long paper says yes: a convolutional network trained end to end with gradient descent beats every other method on handwritten digits, and the same idea, scaled up into a whole trainable system, was reading bank cheques commercially.

The paper in four sentences

Older handwriting readers had two parts: a feature extractor that engineers designed by hand, and a learning part that only saw those features. The quality of the hand-made part limited everything.

A convolutional network instead learns its own features, using small pattern detectors that are slid across the whole image, so the same detector works wherever the pattern appears.

Layers of detectors alternate with layers that shrink the image, so small shifts and wobbles in the handwriting matter less and less as the signal moves up.

The network, LeNet-5, made fewer mistakes on the MNIST digits than any hand-designed method tested, and joined to other trainable parts it was reading millions of cheques for banks.

Idea · §I · Fig. 1

Stop hand-designing the features

Before this work, a typical character reader was built from two separate pieces. First, a feature extractor, written by engineers, turned the raw pixels into a short list of measurements: how many loops, where the strokes end, how slanted the character is. Second, a classifier, which could learn from examples, looked at those measurements and named the character.

Only the second piece learned. If the engineers forgot a useful measurement, the classifier could never recover it. And every new problem (a new alphabet, a new kind of form) meant designing the features again.

The paper's argument is that we now have enough data, fast enough computers, and good enough learning methods to let the machine learn all of it, straight from the pixels. The learning method is the one from backpropagation: measure the error, work out how each adjustable number contributed to it, and nudge each one to reduce it. This is called gradient-based learning, and "end to end" means it is applied to the whole system at once.

Everyday pictureImagine teaching someone to sort post. One way is to hand them a checklist ("look for a loop at the top; check if the bottom is flat") and let them learn only how to combine your checklist answers. The other way is to show them thousands of envelopes and let them work out for themselves what to look at. The second way can discover clues you never thought of.

TakeawayLet learning reach all the way down to the pixels, rather than only adjusting a final classifier on top of hand-made features.

Check yourself
In the old two-part design, which part learned from examples?
Only the classifier. The feature extractor was fixed and designed by hand, so its blind spots could not be fixed by training.

Idea · §II-A

One small detector, slid everywhere

Why not just connect every pixel to every unit of a big network? The paper gives two reasons. A 32 by 32 image has 1,024 pixels, so a first layer of even 100 units would need over 100,000 connections, and it would need huge amounts of data to learn them. Worse, such a network has no idea that a stroke shifted one pixel to the right is still the same stroke; it would have to learn that separately for every position.

A convolutional layer fixes both. Each unit looks only at a small patch of the image, its receptive field (5 by 5 pixels in LeNet-5). And all the units in one layer map use the same weights: one small detector, copied to every position. The result is a feature map that shows where in the image the detector's pattern appears. Several detectors give several feature maps.

Try it below. Click pixels to draw, pick a detector, and watch the feature map. Hover over the feature map to see which patch each value came from.

A toy with a 3 by 3 detector on a 12 by 12 image (LeNet-5 uses 5 by 5 detectors that it learns; these three are set by hand for illustration). In the feature map, amber means the pattern is present, blue means its opposite is. Draw the same stroke in two different places: the detector fires in both.

TakeawaySharing one detector across all positions means far fewer numbers to learn, and a pattern is recognised wherever it appears.

Check yourself
If you move your drawing two pixels to the right, what happens to the feature map?
It moves two positions to the right as well, but otherwise looks the same. The layer reacts to shifts by shifting its output.
Why does weight sharing reduce the amount of training data needed?
There are far fewer independent weights to pin down, and every position in every image provides evidence about the same shared detector.

Idea · §II-A

Blur the details, keep the gist

Once a detector has found, say, an edge, its exact position does not matter much. What matters is roughly where it is compared with other features: a 7 has a horizontal bar near the top-left of a diagonal stroke. Exact positions are also unreliable, because every writer is different.

So LeNet follows each convolutional layer with a subsampling layer (today usually called pooling). It averages each 2 by 2 block of the feature map into one number, halving the width and height. After this step, a feature that moved by a pixel produces almost the same output.

Slide the shift below and compare how similar the shifted digit is to the original at each stage. Raw pixels change a lot; the averaged maps much less.

Similarity is measured as the cosine between the shifted and unshifted versions (1.00 means identical). The edge map uses the vertical-edge detector from the figure above, made non-negative; each averaging stage takes 2 by 2 blocks. Illustrative toy, not LeNet's learned weights.
Everyday pictureRecognising a friend's face from across a room, you don't check the exact pixel position of their nose. You notice there is a nose roughly below two eyes. Pooling throws away the precise positions and keeps the arrangement.

TakeawayAlternating detection with shrinking gives features that are increasingly tolerant of shifts and distortions as you go up the network.

Check yourself
What does the network lose by subsampling, and why is that acceptable?
It loses the exact location of each feature. For recognising a character, the rough relative positions of features are what matter, and exact positions vary between writers anyway.

Idea · §II-B · §III · Fig. 2

LeNet-5 and the MNIST test

LeNet-5 stacks these ideas: detect (6 feature maps), shrink, detect again (16 maps, each combining several of the first ones), shrink, then a few ordinary layers that make the final decision among the ten digits. Not counting the input it has seven layers, and about 60,000 adjustable numbers in total, because sharing keeps the count small.

To test it fairly the authors built a new dataset, MNIST, by mixing two collections of digits from the US National Institute of Standards and Technology: one written by Census Bureau employees and one by high-school students. It has 60,000 training digits and 10,000 test digits, with the people who wrote the test digits kept separate from those who wrote the training ones. MNIST went on to become the most famous small benchmark in machine learning.

LeNet-5 misread 0.95% of the test digits, about one in a hundred, and 0.8% when the training set was enlarged with artificially distorted copies of the digits. For comparison, a simple linear classifier got 12% wrong, and comparing each new digit with its few most similar training examples got 5% wrong.

input32×32 C1: 6 maps28×28 S2: 614×14 C3: 1610×10 S4: 165×5 C5: 120 F6: 84 out: 10 C = convolutionS = subsamplingF = full layer feature extraction (learned)classifier (learned)
Redrawn after the paper's Fig. 2. Every layer is trained; nothing is hand-designed except the shape of the network.

TakeawayA small, carefully shaped network that learns everything from pixels made fewer errors than every hand-engineered approach the authors tested.

Check yourself
Why did the authors make sure different people wrote the training and test digits?
Otherwise a method could score well by memorising particular writers' styles, which says little about reading new people's handwriting.
Why did adding distorted copies of the training digits help?
It showed the network more of the natural variety in handwriting (slants, squashes, stretches), so it learned to ignore those variations.

Idea · §IV–end

From single digits to reading cheques

Reading a real cheque is harder than reading a single neat digit. You have to find the amount, cut it into characters (where does one end and the next begin?), recognise each one, and check that the result makes sense as an amount of money. Usually each of these steps was a separate program, tuned separately.

The second half of the long paper extends "learn everything" to the whole pipeline. It introduces Graph Transformer Networks: a way of describing a multi-step system in which every step passes along a set of possible interpretations (for example, several possible ways to cut a word into letters, each with a score), and the whole chain can be trained together by gradient descent, so the error at the end improves every step.

The paper's abstract reports that the resulting cheque reader was deployed commercially and "reads several million checks per day". This was one of the first large-scale commercial uses of neural networks.

Later refinementFor over a decade convolutional networks stayed a niche tool for things like digits and documents. In 2012 AlexNet used the same basic design, made much bigger, trained on graphics cards, with a simpler activation function and new tricks against overfitting, and won the ImageNet photo-recognition challenge by a wide margin. The convolution-plus-pooling recipe from this paper is still the backbone of many vision systems, though Vision Transformers later showed that it is not the only way.

TakeawayThe paper's bigger idea is not just one network, but training a whole recognition system end to end so every part serves the final goal.

Follow the idea

Built on: Backpropagation (1986)

Led to: AlexNet (2012)