1.6 — The XOR problem and why we need depth

1. Why this session exists

Minsky and Papert's 1969[1] book Perceptrons observed that the simplest non-trivial logical function — exclusive OR — cannot be computed by a single-layer perceptron. The observation effectively killed neural-network research for a decade. The fix (a hidden layer) is mathematically trivial once you know it, but conceptually it is the entire reason the rest of this course exists: adding depth strictly increases what a linear-threshold network can represent.

This session does the proof of impossibility and constructs the explicit 2-hidden-unit solution.

2. XOR

The XOR function on $\{0, 1\}^2$ takes the four input combinations to the values

Geometrically: the two diagonally opposite corners of the unit square share a label; the two off-diagonal corners share the other label.

3. Impossibility for a single linear unit

Claim. No affine function $f(x) = w_1 x_1 + w_2 x_2 + b$ classifies all four points correctly under the encoding $\{0 \mapsto -1,\ 1 \mapsto +1\}$ via $\operatorname{sign}(f(x))$.

Proof. Suppose for contradiction such $(w_1, w_2, b)$ exist. The four required sign conditions read

Add the middle two:

Add the first and the last:

The two sums are the same number but are required to be both positive and negative. Contradiction. $\blacksquare$

4. The solution: one hidden layer

XOR is not a half-space. But it is the symmetric difference of two half-spaces. We compute it as a small linear combination of thresholded sums.

Let

Read off:

• $h_1(x) = 1$ iff at least one input is on. (Logical OR.)
• $h_2(x) = 1$ iff both inputs are on. (Logical AND.)

Then

where the subtraction works because $h_1 \ge h_2$ pointwise on $\{0, 1\}^2$.

So XOR is computed by the two-layer network

Two hidden units with hard-threshold activations, one output unit with linear activation. Walk the four inputs:

• $(x_1, x_2) = (0, 0)$: $h_1 = 0,\ h_2 = 0,\ o = 0$. ✅
• $(x_1, x_2) = (0, 1)$: $h_1 = 1,\ h_2 = 0,\ o = 1$. ✅
• $(x_1, x_2) = (1, 0)$: $h_1 = 1,\ h_2 = 0,\ o = 1$. ✅
• $(x_1, x_2) = (1, 1)$: $h_1 = 1,\ h_2 = 1,\ o = 0$. ✅

Exactly XOR.

5. What this teaches us about depth

The XOR result is the simplest piece of evidence for two structural truths in deep learning.

1. Depth ≠ width. A wide single-layer perceptron — no matter how many parameters — can only carve $\mathbb{R}^n$ into two half-spaces. It cannot compute the intersection of two half-spaces, which is what XOR requires.
2. Composition is the source of expressivity. Composing two threshold functions yields a non-convex decision region. Iterating composition (the MLP of Chapter 2) yields arbitrarily complex piecewise-affine regions; in the limit, MLPs can approximate any continuous function on a compact set — the universal approximation theorem (Cybenko 1989; Hornik 1991), which we'll prove in Chapter 3.

The hidden layer is the new primitive. It is the difference between fitting a half-space and fitting a polyhedron, and it is the difference between linear regression and "deep learning". Everything else in this course is engineering on top of that insight.

6. Takeaways

• A single linear classifier cannot solve XOR (the contradiction in §3).
• Two hidden units plus one output unit do solve XOR (the construction in §4).
• Cause: XOR is not a half-space; it is the symmetric difference of two half-spaces.
• This is the prototype demonstration that depth strictly enlarges the function class.