The Room Nobody Ever Entered

The job you cannot do

It is late. Behind the mirrored glass of the Bell Labs building at Holmdel, a screen is glowing, and on that screen there is you: a straight line, drawn in light. You have exactly two adjustable parts — how steeply you tilt, and how far you sit from the middle. That is your entire vocabulary.

Your job is to be a border. Everything on one side of you should be coral. Everything on the other side should be blue. Do that, and you have classified the data — the oldest job in machine learning, the job the Perceptron was built for in 1958.

So go on. Tilt. Slide. Try every angle you have.

You can search all night. In 1969, two of the sharpest minds in the field — Marvin Minsky and Seymour Papert — wrote a book proving, with cold arithmetic, that a single straight border simply cannot do certain jobs. Funding dried up. An AI winter set in. For a while, this looked like a ceiling on what machines could ever learn.

It was not a ceiling. It was a doorway, and nobody had noticed it was there.

Lift the floor and the problem falls apart

Here is the idea that breaks the ceiling, and it is so simple that people who meet it for the first time often laugh out loud.

Your dots live on a flat table: each one has two numbers, x and y. Give each dot a third number — how far it sits from the centre, squared: z = x² + y². Now every dot has an altitude. The dots near the middle stay low. The dots in the outer ring float up.

Slide the lever. Watch the ring rise into the air. And then look for the thing that was impossible thirty seconds ago: a perfectly flat sheet that has all the coral above it and all the blue below.

This was not a trick invented at Bell Labs. In 1965, a young Stanford engineer named Thomas Cover proved it as a theorem, and even counted it. Scatter points at random and label them any way you like; the fraction of labellings a flat sheet can handle depends only on how many points you have and how many dimensions they live in. His conclusion, in his own words:

T. M. Cover, “Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition,” IEEE Transactions on Electronic Computers EC-14 (1965), 326–334.

In plain speech: crowded rooms are hard; roomy rooms are easy. If your problem is impossible in the room you are in, move to a bigger room. Below is Cover's own counting formula, running live. Notice where the curve crosses one half — it happens exactly when you have twice as many points as dimensions. That number, N = 2d, is the capacity of a flat border, and it is not a matter of opinion.

Ten thousand million dimensions you cannot afford

Lifting works. Now try it on something real. A scanned postal digit at Bell Labs was a tiny grey picture, 16 pixels by 16 — 256 numbers. To give a machine the room it needs, you don't just add one dimension; you add every product of every pair of pixels, and every product of every triple, and so on. Take those products up to degree four and the new room has roughly a thousand million dimensions. Take it to degree seven and it has about 10¹⁶ — ten thousand million million.

Writing down one digit's coordinates in that room would take longer than the lifetime of the machine. There were seven thousand three hundred digits. It is not slow. It is impossible.

And here is where the summer of 1992 turns on a hinge. Bernhard Boser, a hardware engineer between jobs, had been coding up an old algorithm of Vladimir Vapnik's from the 1960s. Vapnik wanted it made curved by writing out those products. Isabelle Guyon suggested something else — an old Soviet idea about “potential functions,” from a rival team at Vapnik's own Moscow institute. Vapnik, by Guyon's account, resisted; Boser tried it anyway.

The idea is this. Look closely at what the algorithm actually asks for. It never once needs a point's coordinates in the big room. It only ever asks: how much do these two points agree? — a single number, the dot product. And for these particular liftings, that single number has a shortcut. You can compute it down here, in the small room, in a handful of multiplications, and get exactly — exactly, to the last decimal place — what you would have got up there.

The rule they wrote down is not fussy. Any function K(u, v) that behaves like a dot product — the condition was proved by James Mercer in 1909, decades before there were computers to use it — is a legal door into some room. Change the door, change the room, change the shape of the border, and the algorithm underneath never notices. It is still, dumbly and happily, drawing a straight line.

• K(u,v) = u·v — no lifting at all. Your border stays straight.
• K(u,v) = (u·v + 1)^d — the polynomial door. Borders become curves, bowls and saddles.
• K(u,v) = exp(−γ‖u−v‖²) — the Gaussian or RBF door, descended straight from those Soviet “potential functions.” Its room has infinitely many dimensions. You will use it in a minute, and it will cost you nothing.

Of all the borders that work, which one is right?

Once you are in a roomy enough room, a new problem appears: many flat sheets separate the colours. Which do you pick? Vapnik had answered that in Moscow in 1963, with Alexey Lerner, in a paper on what they called the “generalised portrait.” Pick the border with the widest empty corridor around it — the maximum margin. Push the walls of a corridor apart until they jam against the data. Wherever they jam, those points are the support vectors.

And then comes the second astonishment of this story. Every other point — the comfortable ones, far from the border, the overwhelming majority of your expensive, painstakingly labelled data — could be deleted, and the machine would come out bit for bit identical. The border is held up by a handful of awkward cases sitting right on the edge. That is where the name comes from: those few points are the ones that support it.

Press “Delete every quiet point.” Watch what the border does. It does not flinch. You just threw away most of the training set and the machine did not notice, because it never knew about those points in the first place — it knew about the handful sitting on the corridor walls, and the number it was told at the door.

Seven thousand three hundred pieces of somebody's handwriting

In July 1992, at the Fifth Annual Workshop on Computational Learning Theory in Pittsburgh, Boser, Guyon and Vapnik published nine pages titled “A Training Algorithm for Optimal Margin Classifiers.” Three years later Corinna Cortes and Vapnik added the soft margin — the tolerance for messy data — in a paper called “Support-Vector Networks.”

Their test was the US Postal Service database: 7,300 handwritten digits to learn from, 2,000 to be examined on, each one a 16 × 16 grey square. Their results, straight from the 1995 paper, are the charts below. Read the last column of the first chart slowly. As the room grows from 256 dimensions to ten thousand million million, the error does not get worse. It gets slightly better, and then it just sits there.

Every instinct trained on statistics says that should be a catastrophe. More dimensions than data points is supposed to mean the machine memorises the training set and learns nothing. It didn't happen. The corridor is why: a machine that insists on the widest possible empty corridor is not free to wiggle, no matter how many dimensions it is given.

C. Cortes and V. Vapnik, “Support-Vector Networks,” Machine Learning 20(3), 1995, 273–297.

It did not know it was looking at pictures. It did not know a digit has a top and a bottom, or that a stroke is continuous, or that ink is dark. It was handed 256 numbers per example and it beat a system that had been taught what a picture is.

Now do it yourself. The bench below invents its own handwriting — a fresh crowd of 3s and 8s, wobbled and slanted, drawn from scratch every time you press the button — flattens each one into 256 numbers, and trains a support vector machine on them right here in your browser. Then look at the gallery of support vectors it keeps. They are never the tidy ones.

The machine that memorised everything and understood nothing

The Gaussian door has a dial on it: γ, the reach. It decides how far a training point's influence travels. Turn it down and every point can feel every other point; the border goes smooth and lazy. Turn it up and each point can only feel its immediate neighbourhood.

Turn it up far enough and something disturbing happens. The machine scores one hundred per cent on everything it has studied. It has drawn a tiny private island around every single training point. Ask it about a point it has never seen — a point standing two centimetres away from one it knows perfectly — and it shrugs.

This is overfitting, and this bench is the cleanest place in the whole of machine learning to see it, because you can watch the islands form. Every number below is measured live on points the machine was never trained on.

Two men, one witness, and a very long lunch

By 1995 the corridor between the offices at Holmdel had become the most interesting argument in the field. On one side: Vapnik, kernels, theorems, corridors you could measure. On the other: Yann LeCun and his convolutional neural networks, which worked beautifully and which nobody could fully explain.

In March 1995 Vapnik and his boss Larry Jackel wrote two bets down on a sheet of paper and signed them, with LeCun signing underneath as witness. Jackel's bet: within five years, somebody would have a real mathematical theory explaining why big neural networks work so well. Vapnik's bet: within ten years, nobody in their right mind would still be using neural networks of the 1995 kind. The stake was a fancy dinner.

Jackel lost his. There was still no clean theory in 2000 — arguably there still isn't. Vapnik lost his too; in 2005 people were absolutely still using neural networks, and seven years after that a convolutional network won ImageNet and the whole field tilted. Two brilliant men made opposite predictions and both were wrong, and the witness ate twice.

So the kernel era ended. Not because the trick stopped being true — it is a theorem; it cannot stop being true — but because of one stubborn number. To use kernels you must ask the door about every pair of your training points. A thousand points is a million questions. A million points is a million million. Neural networks, whatever else you say about them, do not have that problem.

And yet. Open any modern scientific toolkit and the support vector machine is right there, quietly winning on the problems where you have two hundred examples and forty measurements each — medicine, chemistry, geology, the small awkward datasets that make up most of real science. The trick did not lose. It found its room.