Textbook of AI

9.2 The XOR crisis

The exclusive-or function, written XOR, is one of the simplest non-trivial operations in all of computing. Given two binary inputs, each either 0 or 1, it returns 1 when exactly one of the inputs is 1, and 0 otherwise. A child can compute it with two fingers; a digital logic chip from the 1960s could compute it in nanoseconds. And yet, as Marvin Minsky and Seymour Papert proved in their 1969 book Perceptrons, a single perceptron of the sort Rosenblatt had championed cannot compute XOR at all. No matter how the weights are tuned, no matter how cleverly the bias is set, the perceptron will always misclassify at least one of the four input patterns. This single negative result, fairly modest in scope, was widely read as a referendum on the entire connectionist research programme. Funding agencies retreated, doctoral students switched fields, and what is now called the first AI winter settled over the discipline. Connectionism would not fully recover until the rediscovery of backpropagation in 1986, almost two decades later.

The perceptron of §9.1 draws a single straight line through input space and labels every point on one side as positive and every point on the other as negative. This section examines the moment at which that simplicity becomes a fatal limitation, proves the limitation rigorously, and §9.3 then watches the limitation evaporate the instant we add a single hidden layer.

What XOR actually is

The exclusive-or function $\mathrm{XOR}(x_1, x_2)$ takes two binary inputs and returns a single binary output. The plain-English rule is: the output is 1 if and only if exactly one of the two inputs is 1. If both are 0 the output is 0; if both are 1 the output is also 0; only the two "mismatched" cases produce a 1. The full truth table has just four rows:

This is sometimes also called the parity function on two bits, because its output equals 1 precisely when the number of 1s in the input is odd. XOR is the workhorse of digital logic. It appears in adders, parity checkers, encryption schemes (every stream cipher and one-time pad is built around it), and error-correcting codes. Most undergraduate courses on Boolean algebra cover it in their first lecture. It is, in every important sense, an elementary function, and that is exactly what makes its impossibility for a single perceptron so striking. If a model class cannot handle a function this simple, what hope can it have for the messy, high-dimensional functions that arise in vision, language, or scientific data?

Why a single perceptron cannot compute XOR

For the rest of this section we relabel the perceptron's output from $\{-1, +1\}$, the convention used in §9.1 to keep the convergence-theorem algebra clean, to $\{0, 1\}$, the natural convention for Boolean-function inputs and outputs. The two are equivalent: the threshold $\mathrm{sign}(z) \in \{-1, +1\}$ becomes the indicator $\mathbb{1}[z \ge 0] \in \{0, 1\}$. Nothing geometric changes.

A single perceptron computes $\hat y = 1$ when $w_1 x_1 + w_2 x_2 + b \ge 0$ and $\hat y = 0$ otherwise. The boundary between the two outputs is the set of points satisfying $w_1 x_1 + w_2 x_2 + b = 0$, which in the two-dimensional input plane is a straight line. Geometrically, then, the perceptron divides the plane into two half-planes and labels each one with a class.

Now plot the four XOR inputs as points in the plane:

• $(0,0)$ in the bottom-left, labelled 0;
• $(0,1)$ in the top-left, labelled 1;
• $(1,0)$ in the bottom-right, labelled 1;
• $(1,1)$ in the top-right, labelled 0.

The two positive points, $(0,1)$ and $(1,0)$, sit at diagonally opposite corners of the unit square. The two negative points, $(0,0)$ and $(1,1)$, occupy the other diagonal. Any straight line you can draw will, at best, place three of the four points on the correct side; at least one will always land on the wrong side. Try it on paper. A horizontal line, a vertical line, a diagonal at any angle, none of them will simultaneously put $(0,1)$ and $(1,0)$ on one side while keeping $(0,0)$ and $(1,1)$ on the other. The two classes are interleaved, not separable.

It is illuminating to compare XOR with two of its near-neighbours, AND and OR. The AND function returns 1 only for $(1,1)$; the OR function returns 1 for everything except $(0,0)$. Both are linearly separable, and it is easy to write down working perceptron weights:

• For AND, set $w_1 = w_2 = 1$ and $b = -1.5$. Then the line is $x_1 + x_2 = 1.5$, which sits diagonally between $(1,1)$ on the positive side and the other three on the negative side.
• For OR, set $w_1 = w_2 = 1$ and $b = -0.5$. The line $x_1 + x_2 = 0.5$ now isolates $(0,0)$ on the negative side and groups the other three points on the positive side.

XOR has no such clean choice. It is, in fact, the simplest possible function on binary inputs that is not linearly separable, which is why Minsky and Papert chose it as their counter-example. Of the sixteen possible Boolean functions of two binary inputs, fourteen are linearly separable; only XOR and its negation, the equivalence function, escape. If you wanted a clean, irreducible obstacle to single-layer learning, XOR is the obvious choice.

Algebraic proof of impossibility

The geometric argument can be made airtight with a few lines of algebra. Suppose, for the sake of contradiction, that a single perceptron with weights $w_1, w_2$ and bias $b$ correctly computes XOR on all four inputs. We translate each row of the truth table into an inequality.

1. Input $(0,0)$ must produce output 0, so $0 \cdot w_1 + 0 \cdot w_2 + b < 0$. This gives $b < 0$.
2. Input $(0,1)$ must produce output 1, so $0 \cdot w_1 + 1 \cdot w_2 + b \ge 0$. This gives $w_2 \ge -b$. Because $b < 0$ we have $-b > 0$, hence $w_2 > 0$.
3. Input $(1,0)$ must produce output 1, so $1 \cdot w_1 + 0 \cdot w_2 + b \ge 0$. This gives $w_1 \ge -b > 0$.
4. Input $(1,1)$ must produce output 0, so $1 \cdot w_1 + 1 \cdot w_2 + b < 0$. This gives $w_1 + w_2 + b < 0$.

Now add the inequalities from steps 2 and 3:

$$w_1 + w_2 \;\ge\; -b + (-b) \;=\; -2b.$$

Add $b$ to both sides:

$$w_1 + w_2 + b \;\ge\; -2b + b \;=\; -b \;>\; 0,$$

where the final strict inequality comes from $b < 0$ (step 1). But step 4 demands $w_1 + w_2 + b < 0$, which directly contradicts $w_1 + w_2 + b > 0$. Our assumption that the perceptron exists is therefore false. $\square$

This proof is short but complete. There is no trick, no edge case, no clever choice of weights; the four inequalities are simply inconsistent. Whatever weights you pick, at least one of the four XOR rows will come out wrong. The same style of argument generalises: any function in which the positive class and the negative class cannot be separated by a single hyperplane is provably outside the reach of a perceptron, and the proof in each case reduces to a small system of incompatible linear inequalities of exactly this kind.

Minsky and Papert (1969) and the first AI winter

The XOR result is the most famous theorem in Perceptrons, but the book contains many more. Minsky and Papert worked out the order of a perceptron, roughly, the largest neighbourhood any single threshold unit must read, and proved that several intuitively simple problems require unbounded order. The parity function on $n$ bits requires order $n$, ruling out fixed-receptive-field perceptrons for that family. The image-processing problem of connectedness (deciding whether the pixels of a black region in a binary image form a single connected blob) is similarly out of reach for any bounded-order perceptron. These results were rigorous, important, and absolutely correct.

What was not rigorous, and what the book pointedly did not claim, was the conclusion that the field as a whole then drew. In their 1969 epilogue, Minsky and Papert acknowledged explicitly that multilayer networks would almost certainly be able to overcome the XOR limitation. Their critique was not that connectionism was impossible in principle but that no efficient training algorithm for multilayer networks was then known. That cautious, well-hedged claim was widely flattened into "neural networks don't work." Funding agencies, most importantly DARPA, withdrew support, and a generation of graduate students chose symbolic AI, expert systems, or logic programming instead.

Connectionist research did not stop entirely. In the Soviet Union, Aleksei Ivakhnenko developed the Group Method of Data Handling, an early form of trainable multilayer network, in the late 1960s and 1970s. In Japan, Kunihiko Fukushima built the Cognitron (1975) and later the Neocognitron (1980), the direct ancestor of the modern convolutional neural network. John Hopfield revitalised interest in associative-memory networks in 1982. Paul Werbos's 1974 Harvard PhD thesis already contained the modern backpropagation algorithm, but it sat unread by the connectionist community until Rumelhart, Hinton and Williams independently rediscovered it and published their landmark 1986 Nature paper. Parker (1985) and LeCun (in his 1987 PhD) reached the same algorithm by yet other routes. The lesson is twofold: an existence proof of a model class can take decades to translate into practical algorithms, and ideas can lie dormant in adjacent fields for years until communication catches up with invention.

How a hidden layer fixes XOR

The fix is short. Place a single hidden layer of two ReLU neurons between the input and the output, and the impossibility melts away. Here is one such network, with weights chosen by hand to make the construction transparent.

The hidden layer computes two activations:

$$h_1 \;=\; \mathrm{ReLU}(x_1 + x_2 + 0), \qquad h_2 \;=\; \mathrm{ReLU}(x_1 + x_2 - 1).$$

Recall that $\mathrm{ReLU}(z) = \max(0, z)$, so each hidden unit outputs its argument when the argument is positive and 0 otherwise. The output layer then forms a simple linear combination:

$$\hat y \;=\; h_1 - 2 h_2.$$

Let us verify, row by row, that this two-layer network reproduces the XOR truth table exactly.

• Input $(0,0)$. The first hidden unit computes $h_1 = \mathrm{ReLU}(0 + 0 + 0) = \mathrm{ReLU}(0) = 0$. The second computes $h_2 = \mathrm{ReLU}(0 + 0 - 1) = \mathrm{ReLU}(-1) = 0$. The output is $\hat y = 0 - 2 \cdot 0 = 0$. Correct.
• Input $(0,1)$. We get $h_1 = \mathrm{ReLU}(0 + 1 + 0) = \mathrm{ReLU}(1) = 1$ and $h_2 = \mathrm{ReLU}(0 + 1 - 1) = \mathrm{ReLU}(0) = 0$. The output is $\hat y = 1 - 2 \cdot 0 = 1$. Correct.
• Input $(1,0)$. Symmetrically, $h_1 = \mathrm{ReLU}(1 + 0 + 0) = \mathrm{ReLU}(1) = 1$ and $h_2 = \mathrm{ReLU}(1 + 0 - 1) = \mathrm{ReLU}(0) = 0$. The output is $\hat y = 1 - 2 \cdot 0 = 1$. Correct.
• Input $(1,1)$. Now $h_1 = \mathrm{ReLU}(1 + 1 + 0) = \mathrm{ReLU}(2) = 2$ and $h_2 = \mathrm{ReLU}(1 + 1 - 1) = \mathrm{ReLU}(1) = 1$. The output is $\hat y = 2 - 2 \cdot 1 = 0$. Correct.

All four rows agree with XOR. The network has exactly six parameters in the hidden layer (four weights and two biases) and two parameters in the output layer (two weights, no bias), for a total of eight, barely more than the three parameters of a single perceptron, yet the qualitative leap in expressive power is total.

The geometric intuition is worth pausing on. Each hidden ReLU draws a bent boundary in the input plane: flat on one side of the kink, linear on the other. Two such bent boundaries, combined linearly, can fold the input space in a way that no single straight line can. In the new $(h_1, h_2)$ space, the four XOR points map to $(0,0)$, $(1,0)$, $(1,0)$, and $(2,1)$. The two positive cases, $(0,1)$ and $(1,0)$, both land on the point $(1,0)$ in hidden-space, while the negative cases land at $(0,0)$ and $(2,1)$. In this transformed space the positives and negatives are now linearly separable, and the output layer is doing nothing more sophisticated than drawing a straight line through that re-shaped landscape. The hidden layer has, in effect, constructed a new feature representation in which the original problem becomes easy.

This is the central trick of every modern neural network, from a two-neuron XOR solver to a 70-billion-parameter language model. Each hidden layer learns features that make the next layer's job easier. What was impossible at the input becomes routine after a re-representation. A modern image classifier folds raw pixels into edges, then edges into textures, then textures into object parts, then parts into objects, and only the very last layer needs to draw a straight line through that final, well-shaped feature space. The XOR construction above is, in miniature, the entire research programme of deep learning.

It is worth flagging one small subtlety. The construction we wrote down has weights chosen by hand, and we treated $\hat y$ as a real-valued output that happens to equal 0 or 1 on these four inputs. In practice we would train the weights by gradient descent (the subject of §9.6), and we would pass $\hat y$ through a final sigmoid to keep it bounded between 0 and 1. The qualitative point is unchanged: a hidden layer is what makes the difference between possible and impossible, and the rest is engineering.

What you should take away

1. XOR is the simplest function that defeats a single perceptron. Its four points sit on the two diagonals of the unit square, so no straight line separates the positives from the negatives.
2. The proof is an elementary contradiction in four inequalities. No assumption about magnitudes or architectures is needed; the four XOR rows are simply incompatible with a single linear threshold.
3. The 1969 result triggered the first AI winter, but the inference was overdrawn. Minsky and Papert never claimed multilayer networks were doomed; the field misread their cautious epilogue as a death sentence and lost almost two decades.
4. A single hidden layer of two ReLU neurons resolves XOR exactly. The hidden layer folds the input space into a new feature space in which the problem is linearly separable, foreshadowing the role of every hidden layer in every deep network you will meet for the rest of this book.