Image: National Museum of the U.S. Navy, public domainThe XOR problem and the book that cooled a field
Exclusive or is the simplest function that no single artificial neuron can compute. It takes two inputs that are each 0 or 1 and returns 1 when exactly one of them is 1. Four cases: (0, 0) gives 0, (1, 0) gives 1, (0, 1) gives 1, (1, 1) gives 0. A child can learn it in a minute. The perceptron, the learning machine that the New York Times had described in 1958 as the embryo of a computer that would walk, talk, and be conscious of its existence, cannot learn it at all, and in 1969 two mathematicians at MIT proved why.
What a single neuron can do
An artificial neuron takes its inputs \(x_1, x_2\), multiplies each by a weight, adds a bias, and fires if the sum is positive:
\[ \hat{y} = \text{step}(w_1 x_1 + w_2 x_2 + b), \]where the step function returns 1 for a positive argument and 0 otherwise. Frank Rosenblatt's perceptron of 1958 was this neuron with a learning rule: show it an example, and if it fires when it should not, subtract the input from the weights; if it stays silent when it should fire, add the input. Rosenblatt proved that if a set of weights exists that gets every example right, the rule finds one in a finite number of corrections. His Mark I machine had 400 photocells and stored its weights in motor-driven potentiometers that turned after each mistake.
The geometry is the key. The condition \(w_1 x_1 + w_2 x_2 + b = 0\) is a straight line in the plane of the two inputs. The neuron fires on one side of the line and not on the other. So a single neuron can compute exactly those functions whose 1s and 0s can be separated by a line. AND is one: the point (1, 1) alone on one side, the other three on the other. OR is another. Draw the four points of XOR and try: the two 1s sit at opposite corners, (1, 0) and (0, 1), and the two 0s at the other two corners. No straight line puts the first pair on one side and the second pair on the other. The function is not linearly separable, and Rosenblatt's convergence theorem has nothing to say, because the weights it promises to find do not exist.
The book
Marvin Minsky and Seymour Papert published Perceptrons in 1969. The XOR argument is the easy part of it. The hard part is a proof that a perceptron whose inputs are local patches of an image cannot tell whether a shape is connected, however the weights are set, and a careful account of which predicates a single layer can and cannot compute. The book was right. The reaction to it was that funding for neural network research in the United States fell for more than a decade, a period that overlaps with the first AI winter of about 1974 to 1980, and the field turned to symbolic methods.
What the book did not settle, and said so in places, was what networks with a hidden layer could do. Everyone knew that adding a layer of neurons between the inputs and the output made more functions computable. What nobody had was a way to train the hidden layer: the perceptron rule corrects the weights of a neuron from its own error, and a hidden neuron has no error of its own, because nobody told it what it should have output. That is the credit assignment problem, and it is the reason the hidden layer waited.
The two neurons that answer it
Here is a network that computes XOR. Two hidden neurons, each with the same two inputs:
\[ h_1 = \text{step}(x_1 + x_2 - 0.5), \qquad h_2 = \text{step}(x_1 + x_2 - 1.5). \]The first fires when at least one input is 1 (it computes OR); the second fires only when both are (AND). An output neuron reads the two:
\[ \hat{y} = \text{step}(h_1 - h_2 - 0.5). \]Check the four cases. For (0, 0): \(h_1 = 0\), \(h_2 = 0\), output step(\(-0.5\)) = 0. For (1, 0): \(h_1 = 1\), \(h_2 = 0\), output step(0.5) = 1. The same for (0, 1). For (1, 1): \(h_1 = 1\), \(h_2 = 1\), output step(\(-0.5\)) = 0. The hidden layer has drawn two lines in the input plane, and the output neuron fires for the strip between them. The two 1s of XOR lie in the strip; the two 0s lie outside it on either side. What one line could not do, two lines and a second layer can.
Nine numbers, and they were set by hand. The question of 1969 was never whether such numbers exist. It was whether a machine could find them from examples.
The four pages of 1986
The answer came in a paper of four pages in Nature on 9 October 1986, by David Rumelhart, Geoffrey Hinton, and Ronald Williams, "Learning representations by back-propagating errors". Replace the step function by a smooth one, such as the sigmoid, so that the output changes gradually with the weights. Then the error at the output has a derivative with respect to every weight in the network, including the hidden ones, and the chain rule computes it layer by layer, backwards from the output. Each weight moves a small step against its derivative. The hidden neurons are never told what they should output; they are told how the final error would change if they output a little more or a little less, and that is enough.
The method had been found before, by Seppo Linnainmaa in 1970 as a general technique for computing derivatives of programs and by Paul Werbos in 1974 in a thesis on neural networks, and the 1986 paper says as much in its citations. What the paper added was the demonstration that networks trained this way learned useful internal representations, XOR among the examples, and the audience that Nature gave it. Every network trained today, from the one that reads cheques to the one that writes paragraphs, is trained by this procedure.
What the episode teaches
Two things. A counterexample, however small, is decisive against a claim as broad as the ones made for the perceptron, and a field that ignores the proof will pay for it. And a proof about one architecture says nothing about the next one; the book's theorems are still true of single-layer networks and have been irrelevant to practice since 1986. Minsky and Papert were right about what they proved and wrong, as it turned out, about how much it would matter, and the moral for a student is to read what a theorem actually says before deciding what it means.
Unit 6 of the AI Masterclass runs the perceptron rule on AND by hand, draws the four XOR points and the two lines, and then derives backpropagation on a 2-2-1 network with every partial derivative written out, so that the hidden layer's weights are found rather than set. Unit 8 places the book and the paper in the history of the field's booms and winters.


