Skip to main content

What one layer cannot do

A single neuron’s decision boundary is a straight line, so no neuron can classify XOR: four inequalities prove it. Stacking linear layers does not help, because they collapse into one. A hand-made feature fixes XOR and raises the question of learned features.
DL01.1.4L2 Intermediate25 min
In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: DL01.1.3 A layer of neurons

What you will be able to do
  • Show that the decision boundary of a single neuron with a step or sigmoid activation is a line, and a hyperplane in general.
  • Prove that no single neuron can classify XOR, from the four inequalities its weights would have to satisfy.
  • Show with numbers that two linear layers with nothing between them collapse into one layer, biases included.
  • Solve XOR with the hand-made feature x1 x2, and explain why that raises the question of learned features.

The question

AND and OR each fall to a single perceptron. XOR, “one or the other but not both”, is just as easy to say, and it is the pattern behind any rule of the form “these two features matter only in combination”. Why can no single neuron compute it, however long it trains? And is a stack of neurons enough?

From the last lesson

1. Write a layer’s output for a batch with rows as examples.

Show answer

\({\mat{A} = \phi(\mat{X}\mat{W}\T + \vect{1}\vect{b}\T)}\), with \(\mat{W}\) of shape \({n_{\text{out}} \times n_{\text{in}}}\).

2. How many parameters does a layer with \(n_{\text{in}}\) inputs and \(n_{\text{out}}\) neurons have?

Show answer

\({n_{\text{out}}(n_{\text{in}} + 1)}\).

Intuition

Draw the four corner points and colour them by their labels. For AND only \((1, 1)\) is class 1, and a line cuts that corner off. For OR only \((0, 0)\) is class 0, and a line cuts that corner off too. For XOR the two class-1 points sit on one diagonal and the two class-0 points on the other.

Three square panels of the four corner points, with blue circles for label 1 and sky-blue squares for label 0. AND, marked with a tick and titled one line: a vermillion line cuts off the circle at (1, 1) from the three squares, the circle's side tinted blue. OR, ticked, one line: a line cuts off the square at (0, 0) from the three circles. XOR, marked with a cross and titled no line: circles at (0, 1) and (1, 0), squares at (0, 0) and (1, 1); a dashed grey line, the OR line, leaves the square at (1, 1) on the wrong side, and that square is ringed; a note says best try, 3 of 4.
DL01.1.4-F1

AND and OR are cut apart by one line. XOR is not: any line that keeps both circles on one side also lets in a square. The best a line can do is 3 of the 4.

A single neuron answers by which side of one line a point falls. To separate XOR it would have to put \((0, 1)\) and \((1, 0)\) on one side and \((0, 0)\) and \((1, 1)\) on the other, and the two pairs are tangled across the middle of the square. No line can do it, and the formal section proves it.

Build it up

Step 1. The boundary of a step neuron is a line. A step neuron says class 1 exactly when \({z = w_1 x_1 + w_2 x_2 + b \geq 0}\). The points with \({z = 0}\) form a line (when \(\vect{w}\) is not zero), and the two classes are the two sides of it.

Step 2. So is the boundary of a sigmoid neuron. A sigmoid neuron outputs a probability, and class 1 means \({\sigma(z) \geq \frac12}\). The sigmoid is increasing and \({\sigma(0) = \frac12}\), so \({\sigma(z) \geq \frac12}\) exactly when \({z \geq 0}\): the same line. The same holds for any strictly increasing activation thresholded at its value at \(0\). The activation changes how the output varies across the plane, not where the boundary is.

Two square panels of the OR points, each coloured by a neuron's output with weights (3, 3) and bias minus 1.5. Left, titled Step, two flat regions: the lower-left corner is pale and labelled output 0, the rest is a single strong vermillion tint labelled output 1, split by a straight vermillion line. Right, titled Sigmoid, straight level lines: the tint deepens smoothly from lower left to upper right, and five parallel straight lines mark where the output equals 0.1, 0.25, 0.5, 0.75 and 0.9; a note under the panel says the thick line p equals 0.5 is the boundary.
DL01.1.4-F2

The same neuron with two activations. The sigmoid’s output varies smoothly, but every set of points with equal output is a straight line, parallel to the boundary.

Step 3. In more dimensions, a hyperplane. With \(d\) inputs, the set \({\vect{w}\T\vect{x} + b = 0}\) is a hyperplane: a line in two dimensions, a plane in three, and a flat set of dimension \({d - 1}\) in general. Data that a hyperplane can split by class is called linearly separable. AND and OR are linearly separable; XOR is the classic example of a set that is not.

Step 4. The history in brief. Minsky and Papert’s book Perceptrons (1969) set out the limits of single-layer perceptrons, with problems of this kind as examples. They also saw that hidden layers with non-linear activations could do more, but concluded that Rosenblatt’s rule could not train them. Interest in neural networks fell sharply, and recovered only in the 1980s with a training method for hidden layers, backpropagation (DL01.5).

The formal statement

NoteTheorem: no single neuron classifies XOR

There are no weights \(w_1\), \(w_2\) and bias \(b\) for which a step neuron (or a sigmoid neuron with threshold \(\frac12\)) gives class 1 to \((0, 1)\) and \((1, 0)\) and class 0 to \((0, 0)\) and \((1, 1)\).

Proof. Suppose such weights exist. Class 1 means \({z \geq 0}\) and class 0 means \({z < 0}\), so the four points demand

\[ \begin{aligned} (0, 0) \to 0: &\quad b < 0 , \\ (0, 1) \to 1: &\quad w_2 + b \geq 0 , \\ (1, 0) \to 1: &\quad w_1 + b \geq 0 , \\ (1, 1) \to 0: &\quad w_1 + w_2 + b < 0 . \end{aligned} \]

Add the second and third inequalities: \({w_1 + w_2 + 2b \geq 0}\). Add the first and the fourth: \({w_1 + w_2 + 2b < 0}\). The same number cannot be both at least zero and below zero, so no such weights exist. \(\blacksquare\)

The sum \({w_1 + w_2 + 2b}\) has a meaning. It equals \({2z}\) at the centre \((\frac12, \frac12)\), which is the midpoint of both diagonals.

The XOR points with their diagonals drawn: a solid blue segment joins the circles at (0, 1) and (1, 0), labelled class 1 pair, and a dashed sky-blue segment joins the squares at (0, 0) and (1, 1), labelled class 0 pair. They cross at (0.5, 0.5), marked with a yellow dot and the note midpoint of both. Text beside the picture: z is affine, so at a midpoint it is the average of the ends; z at the centre equals the average of z at (0, 1) and (1, 0), which is at least 0 because both blue points need z at least 0; it also equals the average of z at (0, 0) and (1, 1), which is below 0 because both squares need z below 0. One number cannot be both.
DL01.1.4-F3

The proof as a picture. Along any segment an affine \(z\) changes evenly, so its value at the crossing point is the average of the values at either pair of ends, and the two pairs disagree.

Logistic regression does no better. Fit a sigmoid neuron to XOR with the log loss. At \({w_1 = w_2 = b = 0}\) every \(p_i\) is \(\frac12\), and the gradient, \({\frac{1}{n}\sum_i (p_i - y_i)\,\tilde{\vect{x}}_i}\), is zero in every coordinate. For \(b\), the four terms \({p_i - y_i}\) are \({\frac12, -\frac12, -\frac12, \frac12}\), which add to \(0\). For \(w_1\), only \((1, 0)\) and \((1, 1)\) have \({x_1 = 1}\), contributing \({-\frac12 + \frac12 = 0}\); \(w_2\) is the same by symmetry. The log loss of logistic regression is convex, so this is its minimum: the best logistic regression on XOR answers \(\frac12\) for every point.

Stacking linear layers collapses. Feed one layer with no activation into another:

\[ \begin{aligned} \vect{h} &= \mat{W}_1\vect{x} + \vect{b}_1 , \\ \hat{\vect{y}} &= \mat{W}_2\vect{h} + \vect{b}_2 . \end{aligned} \]

Substitute the first line into the second and multiply out:

\[ \begin{aligned} \hat{\vect{y}} &= \mat{W}_2(\mat{W}_1\vect{x} + \vect{b}_1) + \vect{b}_2 \\ &= (\mat{W}_2\mat{W}_1)\,\vect{x} + (\mat{W}_2\vect{b}_1 + \vect{b}_2) \\ &= \mat{W}\vect{x} + \vect{b} , \end{aligned} \]

with \({\mat{W} = \mat{W}_2\mat{W}_1}\) and \({\vect{b} = \mat{W}_2\vect{b}_1 + \vect{b}_2}\). Two affine layers are one affine layer, and by induction so are any number of them (M02.5.4 showed this without the biases). A step or a sigmoid on the end still gives a hyperplane boundary, so a deep stack of linear layers cannot classify XOR either. What breaks the collapse is a non-linear activation between the layers, the subject of DL01.2.

Worked example

Two linear layers on the input \({\vect{x} = (3, 2)}\), and the one layer they equal. Use the matrices of M02.5.4 with biases added:

\[ \mat{W}_1 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix}, \quad \vect{b}_1 = \begin{bmatrix} 1 \\ 0 \\ -1 \end{bmatrix}, \]

\[ \mat{W}_2 = \begin{bmatrix} 1 & 2 & 0 \\ 0 & 1 & 1 \end{bmatrix}, \quad \vect{b}_2 = \begin{bmatrix} 0 \\ 2 \end{bmatrix} . \]

Layer by layer. \(\vect{h} = {(3 + 1,\; 2 + 0,\; 3 + 2 - 1)} = {(4, 2, 4)}\). Then \({\hat{y}_1 = 4 + 2 \cdot 2 + 0 + 0 = 8}\) and \({\hat{y}_2 = 0 + 2 + 4 + 2 = 8}\).

As one layer. The product is

\[ \begin{aligned} \mat{W}_2\mat{W}_1 &= \begin{bmatrix} 1 + 0 + 0 & 0 + 2 + 0 \\ 0 + 0 + 1 & 0 + 1 + 1 \end{bmatrix} \\ &= \begin{bmatrix} 1 & 2 \\ 1 & 2 \end{bmatrix}, \end{aligned} \]

and the bias is

\[ \begin{aligned} &\mat{W}_2\vect{b}_1 + \vect{b}_2 \\ &\quad = (1 + 0 + 0,\; 0 + 0 - 1) + (0, 2) \\ &\quad = (1, -1) + (0, 2) = (1, 1) . \end{aligned} \] Then \({\hat{y}_1 = 3 + 2 \cdot 2 + 1 = 8}\) and \({\hat{y}_2 = 3 + 4 + 1 = 8}\): the same output.

Two rows. Top row, Two linear layers: a blue column x with entries 3 and 2, an arrow labelled W1 x plus b1 to a vermillion column h with entries 4, 2 and 4, an arrow labelled W2 h plus b2 to a vermillion column y-hat with entries 8 and 8; notes give h equals (4, 2, 4), y-hat 1 equals 4 plus 2 times 2 plus 0 equals 8, and y-hat 2 equals 0 plus 2 plus 4 plus 2 equals 8. Bottom row, The same map as one layer: the blue column 3, 2, the orange grid W2 W1 with rows 1, 2 and 1, 2, a plus, the orange column W2 b1 plus b2 with entries 1 and 1, an arrow to the vermillion column 8, 8; notes give 1 times 3 plus 2 times 2 plus 1 equals 8 and the same output.
DL01.1.4-F4

The worked example as a trace. The hidden values \(\vect{h}\) are computed and then thrown away; the single layer gets the same answer without them, for every input.

A feature that fixes XOR. Give a neuron three inputs, \(x_1\), \(x_2\) and the product \(x_1x_2\), with weights \({(1, 1, -2)}\) and bias \(-\frac12\). Then

\[ z = x_1 + x_2 - 2x_1x_2 - \tfrac12 , \]

which is \(-\frac12\) at \((0, 0)\), \(\frac12\) at \((0, 1)\) and at \((1, 0)\), and \({1 + 1 - 2 - \frac12 = -\frac12}\) at \((1, 1)\). All four are on the correct side. In the plane the boundary \({z = 0}\) is no longer a line: it factors as \({-\frac12(1 - 2x_1)(1 - 2x_2) = 0}\), the pair of lines \({x_1 = \frac12}\) and \({x_2 = \frac12}\), a cross that no single neuron on \(x_1\) and \(x_2\) alone can draw.

Code

First, the failure in three forms: the perceptron cycles, no line on a fine grid of weights gets more than 3 of the 4 points right, and logistic regression answers one half everywhere.

import numpy as np
from sklearn.linear_model import LogisticRegression, Perceptron

X = np.array([[0.0, 0.0], [0.0, 1.0], [1.0, 0.0], [1.0, 1.0]])
y = np.array([0.0, 1.0, 1.0, 0.0])                        # XOR

def correct(w, b):
    """How many of the four points a step neuron gets right."""
    return int(np.sum((X @ w + b >= 0) == (y == 1)))

grid = np.arange(-3, 3.01, 0.25)
best = max(correct(np.array([w1, w2]), b) for w1 in grid for w2 in grid for b in grid)
print("most points any line on the grid gets right:", best)

logreg = LogisticRegression(C=np.inf).fit(X, y)
print("logistic regression:", logreg.coef_[0], logreg.intercept_, logreg.predict_proba(X)[:, 1])
most points any line on the grid gets right: 3
logistic regression: [0. 0.] [0.] [0.5 0.5 0.5 0.5]

Next, the collapse of two linear layers, on the worked example and on random matrices.

W1 = np.array([[1.0, 0.0], [0.0, 1.0], [1.0, 1.0]])
b1 = np.array([1.0, 0.0, -1.0])
W2 = np.array([[1.0, 2.0, 0.0], [0.0, 1.0, 1.0]])
b2 = np.array([0.0, 2.0])
x = np.array([3.0, 2.0])

h = W1 @ x + b1
print("two layers:", W2 @ h + b2, "  hidden:", h)
W, b = W2 @ W1, W2 @ b1 + b2
print("one layer: ", W @ x + b, "  W =", W.tolist(), " b =", b)

rng = np.random.default_rng(0)
A1, c1, A2, c2 = rng.normal(size=(5, 4)), rng.normal(size=5), rng.normal(size=(3, 5)), rng.normal(size=3)
batch = rng.normal(size=(100, 4))
stacked = (batch @ A1.T + c1) @ A2.T + c2
print("random stack equals one layer:", np.allclose(stacked, batch @ (A2 @ A1).T + (A2 @ c1 + c2)))
two layers: [8. 8.]   hidden: [4. 2. 4.]
one layer:  [8. 8.]   W = [[1.0, 2.0], [1.0, 2.0]]  b = [1. 1.]
random stack equals one layer: True

Last, the hand-made feature. With the column \(x_1x_2\) added, the neuron of the worked example gets all four points right, and so does scikit-learn’s perceptron, which finds its own weights.

F = np.column_stack([X, X[:, 0] * X[:, 1]])               # features x1, x2, x1 x2
z = F @ np.array([1.0, 1.0, -2.0]) - 0.5
print("z with the feature:", z, " classes:", (z >= 0).astype(int))

clf = Perceptron(shuffle=False, tol=None, max_iter=20).fit(F, y)
print("scikit-learn on the features: accuracy", clf.score(F, y), " weights", clf.coef_[0], clf.intercept_)
z with the feature: [-0.5  0.5  0.5 -0.5]  classes: [0 1 1 0]
scikit-learn on the features: accuracy 1.0  weights [ 2.  2. -5.] [-1.]

The feature worked because we knew which one to add. For four points that is easy. For an image of 64 pixels there are 2,016 products of two different pixels, and nobody knows in advance which combinations matter. The question for DL01.2 is whether a network can learn its own features.

Explore

Open the neuron playground in lesson 2 and choose XOR. Try to place a line that gets all four points right; the read-out never passes 3 of 4. Then press Start from zero and Train: the mistakes per epoch go 3, 3 and then 4 in every epoch, and never reach 0.

Pitfalls

Two panels of the XOR points. Left, marked with a cross and titled Two linear layers: a single straight vermillion line, the boundary of the collapsed stack, leaves two points on the wrong side, both ringed; the note says still one straight line. Right, marked with a tick and titled Feature x1 x2: the boundary, x1 plus x2 minus 2 x1 x2 equals one half as the note under the panel says, is a cross made of the lines x1 equals 0.5 and x2 equals 0.5; the two quadrants holding the circles at (0, 1) and (1, 0) are tinted blue and the quadrants holding the squares are pale, so all four points are on their correct side.
DL01.1.4-F5

Wrong beside right. Left: any stack of linear layers ends in a straight boundary. Right: with the feature \(x_1x_2\) the boundary bends into a cross and separates XOR.

“Add more layers and XOR becomes possible.”

Not if the layers are linear. Two affine layers multiply out to one, so their boundary is still a single hyperplane, as on the left of the figure. Depth only helps when a non-linear activation sits between the layers.

“A sigmoid is curved, so a sigmoid neuron draws a curved boundary.”

The curve is in the output, not in the boundary. The class changes where \({\sigma(z) = \frac12}\), which is where \({z = 0}\), a straight line. Every level set of a single neuron’s output is a straight line parallel to it.

“XOR proved that neural networks are a dead end.”

It proved that one layer is limited. Minsky and Papert themselves noted that hidden layers with non-linear activations would be more expressive; what was missing was a way to train them. The next module solves XOR with one hidden layer.

“Hand-made features solve everything.”

They solve problems whose structure you already know. For images, sound or text the right combinations are unknown and far too many to list. Learning the features from data is the point of hidden layers.

Check yourself

Recall

1. Why is the decision boundary of a sigmoid neuron with threshold \(\frac12\) a straight line?

Show answer

Because \({\sigma(z) \geq \frac12}\) exactly when \({z \geq 0}\), and \({z = \vect{w}\T\vect{x} + b = 0}\) is a line (a hyperplane in general).

2. Write the four inequalities a single neuron would need to classify XOR.

Show answer

\({b < 0}\), \({w_2 + b \geq 0}\), \({w_1 + b \geq 0}\) and \({w_1 + w_2 + b < 0}\).

3. How do you get the contradiction from those four inequalities?

Show answer

The middle two add to \({w_1 + w_2 + 2b \geq 0}\), and the first and last add to \({w_1 + w_2 + 2b < 0}\).

4. Two layers \({\vect{h} = \mat{W}_1\vect{x} + \vect{b}_1}\) and \({\hat{\vect{y}} = \mat{W}_2\vect{h} + \vect{b}_2}\) are one layer. What are its weights and bias?

Show answer

\({\mat{W} = \mat{W}_2\mat{W}_1}\) and \({\vect{b} = \mat{W}_2\vect{b}_1 + \vect{b}_2}\).

5. Which extra input lets one neuron classify XOR, and with what weights?

Show answer

The product \(x_1x_2\), with weights \({(1, 1, -2)}\) on \({(x_1, x_2, x_1x_2)}\) and bias \(-\frac12\).

Exercises

1. ★ Find a step neuron for “\(x_1\) and not \(x_2\)”, which is 1 only at \((1, 0)\), and check all four points.

Show solution

Take \({\vect{w} = (1, -1)}\), \({b = -\frac12}\). Then \({z = -\frac12}\) at \((0, 0)\), \({-\frac32}\) at \((0, 1)\), \({\frac12}\) at \((1, 0)\) and \({-\frac12}\) at \((1, 1)\). Only \((1, 0)\) has \({z \geq 0}\), as required.

2. ★★ XNOR has labels \(1, 0, 0, 1\) at \((0, 0)\), \((0, 1)\), \((1, 0)\), \((1, 1)\). Prove that no single neuron classifies it.

Show solution

The conditions are \({b \geq 0}\), \({w_2 + b < 0}\), \({w_1 + b < 0}\) and \({w_1 + w_2 + b \geq 0}\). The middle two add to \({w_1 + w_2 + 2b < 0}\); the first and last add to \({w_1 + w_2 + 2b \geq 0}\). That is a contradiction, so no weights exist.

3. ★★★ Show that every affine function \({z = w_1x_1 + w_2x_2 + b}\) satisfies \({z(0, 0) + z(1, 1) = z(0, 1) + z(1, 0)}\), and use it to give a one-line proof of the XOR theorem. Then show that \({z = x_1 + x_2 - 2x_1x_2 - \frac12}\) breaks the identity.

Show solution

The left side is \(b + {(w_1 + w_2 + b)} = w_1 + w_2 + 2b\), and the right side is \({(w_2 + b)} + {(w_1 + b)} = w_1 + w_2 + 2b\). They are equal.

For XOR the right side would be a sum of two numbers that are at least \(0\), so at least \(0\), and the left side a sum of two negative numbers, so negative. They cannot be equal.

For \({z = x_1 + x_2 - 2x_1x_2 - \frac12}\) the left side is \({-\frac12 - \frac12 = -1}\) and the right side is \({\frac12 + \frac12 = 1}\). The product term is what lets \(z\) escape the identity.

Summary card

One neuron draws one straight line, and XOR needs more than a line.

The anchor figure again: AND and OR each split by one line; XOR with its two pairs on crossing diagonals, where the best line gets 3 of 4.
DL01.1.4-F1

AND, OR: one line. XOR: none.

  • Boundary. \({\vect{w}\T\vect{x} + b = 0}\), a hyperplane, for a step or a sigmoid neuron.
  • XOR. \({b < 0}\), \({w_1 + b \geq 0}\), \({w_2 + b \geq 0}\), \({w_1 + w_2 + b < 0}\) cannot all hold.
  • Collapse. Two linear layers are one: \({\mat{W} = \mat{W}_2\mat{W}_1}\) and \({\vect{b} = \mat{W}_2\vect{b}_1 + \vect{b}_2}\).
  • Feature. With \(x_1x_2\): weights \({(1, 1, -2)}\), bias \(-\frac12\).

Sources and next steps

Sources. Each was opened and checked against this lesson on 15 November 2026.

  • Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, Section 6.1, “Example: Learning XOR”. Figure 6.1 explains why a linear model cannot implement XOR, and the section notes that without a non-linear function a stack of linear layers remains a linear function of its input. Section 1.2.1 of the introduction states that linear models cannot learn XOR and that critics of these flaws (Minsky and Papert, 1969) caused the first major dip in the popularity of neural networks.
  • Simon J. D. Prince, Understanding Deep Learning (MIT Press, 2023), notes to Chapter 3: Minsky and Papert argued that the linear function was inadequate for general classification, that hidden layers with non-linear activations could learn more general relations, and that Rosenblatt’s algorithm could not learn the parameters of such models; a practical algorithm, backpropagation, came in the 1980s.
  • David Chiang, Theory of Neural Networks, Chapter 2: Perceptrons, University of Notre Dame CSE 60963, version of 4 September 2024. Theorem 2.4, attributed to Minsky and Papert (1969), states that no perceptron computes XOR; the notes add that multilayer perceptrons could express XOR but it was not known how to train them.

Next. DL01.2, Multilayer perceptrons and universal approximation, puts a hidden layer of ReLU neurons in front of the output neuron and solves XOR with features the network computes itself.

This lesson unlocks

DL01.2 Multilayer perceptrons and universal approximation

Your progress is saved in this browser only. No account, no tracking.
Back to top