What a neuron cannot do

Why XOR is not linearly separable

A two-input neuron answers $f(x,y)=1$ if $w_1x+w_2y+b>0$ and $0$ otherwise. For XOR we would need all of these at once:

Adding the two middle inequalities: $w_1+w_2+2b>0$, that is, $w_1+w_2+b>-b\ge 0$, which contradicts the last one. No weights work: it is the same geometric argument about the diagonals, in algebra. It is also the argument Minsky and Papert use in Perceptrons (§2.1) to show that the equivalence $x\equiv y$, the complement of XOR, cannot be computed by a single neuron; the book notes (§1.4) that, of the 16 Boolean functions of two variables, these are the only two with that limitation. We checked it by brute force: over a fine grid of $(w_1,w_2,b)$, 14 of the 16 truth tables are reachable, and the two missing ones are XOR and its complement.

The solution with a hidden layer

With the step function $H$ (1 if the argument is positive, 0 otherwise), these weights solve XOR:

$h_1$ is OR, $h_2$ is AND, and the output is “OR and not AND,” which is XOR. In the $(h_1,h_2)$ plane the four points become $(0,0)$, $(1,0)$, $(1,0)$, and $(1,1)$: the ones merge at $(1,0)$ and a line now separates the classes.

What Minsky and Papert proved, and what they did not

In Perceptrons (1969), a perceptron “of order $k$” is a threshold neuron whose inputs are predicates, each of which depends on at most $k$ inputs. Among other results, they proved that the parity of $n$ bits has order $n$ (theorem 3.1.1): at least one predicate that looks at all the inputs is required. With $n=2$, parity is XOR.

On multi-layer networks, the book says (§13.2) that they considered “Gamba machines,” described as “two layers of perceptron,” and found no other really interesting class of multilayered machine; and it adds: “we consider it to be an important research problem to elucidate (or reject) our intuitive judgment that the extension is sterile.” They present it as a conjecture to be tested, not as a theorem.

In code

import numpy as np

H = lambda z: (z > 0).astype(int)       # step

def xor_net(x, y):
    h1 = H(x + y - 0.5)                  # OR
    h2 = H(x + y - 1.5)                  # AND
    return H(h1 - h2 - 0.5)              # OR and not AND

for x in (0, 1):
    for y in (0, 1):
        print(x, y, "->", int(xor_net(np.array(x), np.array(y))))
# 0 0 -> 0 | 0 1 -> 1 | 1 0 -> 1 | 1 1 -> 0

What comes next

The weights in this example were chosen by hand. In a real network they are learned with gradient descent, which needs the gradient of every weight, including those of hidden layers: backpropagation solves that (lesson 8), which Rumelhart, Hinton, and Williams described in 1986, showing how hidden units come to represent new features of the task. First, lesson 7 shows why layers need a nonlinear activation function.