XOR and the limit of one layer

The table has four rows, two columns and a single label column. Write the rows as (0, 0), (0, 1), (1, 0) and (1, 1), and give them the labels 0, 1, 1 and 0. The label is 1 when the two entries disagree and 0 when they agree. The function has a familiar name, exclusive or, and it is the smallest interesting problem in this chapter [S:63:457].

One unit from the previous section gets three of the four rows right and fails on the last. Take weights of 1 and 1 with a threshold of 0.5, and the scores are 0, 1, 1 and 2, which the unit reports as 0, 1, 1 and 1. Raise the threshold to 1.5 and the answers become 0, 0, 0 and 1: the unit now fails on the two middle examples and on the last one, so it is wrong on three rows. Every possible threshold fails for some row, so one unit can never represent this table, whatever weights and threshold it carries, and the explanation is geometric rather than numerical. !Left: the four corners of the square, the rows labelled 1 on one diagonal and the rows labelled 0 on the other. A straight line enters and leaves through two edges, so it cannot put one diagonal on each side. Right: the same four raw scores under three thresholds. The two rows labelled 1 both score 1, so a bar between 1 and 2 loses them together, and a bar above 2 sends every row to 0, which leaves both diagonals partly on the wrong side. Status: re-simulated.

A single unit draws a straight boundary, so it separates only those classes that a line can place on opposite sides [S:63:456]. The two examples labelled 1 sit on one diagonal of the square, and the two examples labelled 0 sit on the other diagonal. A straight line crosses a square in at most two edges, and that is insufficient to separate one diagonal from the other without also cutting a corner of the same class.

Two classes that one line can separate are called linearly separable, and the table above is the standard illustration of a table that is not. The argument requires four inequalities and no diagram. Suppose that numbers w1, w2 and b exist which classify every example correctly.

$$b<0,w_1+b>0,w_2+b>0,w_1+w_2+b<0$$

That line records what each example demands of the three numbers, one inequality per row, and the four requirements cannot hold simultaneously. Adding the two middle inequalities gives w1 + w2 + 2b > 0, while the last inequality says w1 + w2 + b < 0. Subtracting w1 + w2 + b < 0 from w1 + w2 + 2b > 0 leaves b > 0. The opening inequality says b < 0, and the two conclusions contradict each other, so no such parameters exist.

Worked example. The failure is visible in three thresholds. Keep weights 1 and 1 and let the threshold be 0.5: the scores 0, 1, 1 and 2 become the answers 0, 1, 1 and 1, which is incorrect on the last example. Set the threshold to 1.5: the same scores become 0, 0, 0 and 1, which is incorrect on the two middle examples and on the last one. Set it to 2.5: every score falls below the bar, the answers are 0, 0, 0 and 0, and the two examples labelled 0 are correct while the two labelled 1 are wrong.

The first raise repairs nothing and breaks two: it turns the two correct positives into false negatives and leaves the false positive in place. The second fixes the false positive but leaves both positives wrong, so no threshold gets more than three of the four rows. The scores are identical in all three runs, and only the bar moves, which is the entire degree of freedom that a single unit possesses along this direction.

The title of this section mentions a layer, and the phrase deserves a short defence. A layer is a collection of units, and a collection can hold many of them. For a single output label, however, only the final summing junction decides the answer, and the earlier units feed it through weights of their own. Composing two such junctions without a nonlinearity between them produces another junction, so a network whose layers carry no nonlinearity is one unit wearing a longer costume, whatever its depth and however many hidden units it has [S:69:210] [S:63:458].

The history here needs one correction, because the customary version of it is incorrect. The 1969 book by Minsky and Papert proved that a single-layer perceptron cannot compute certain functions, and it also conjectured that the same limitations would apply to networks with more layers [S:67:38]. That conjecture proved to be wildly incorrect. Bishop and Bishop record the consequence: the effect of the book "was to dampen enthusiasm for neural network models, and this contributed to the lack of interest, and funding, for neural networks during the 1970s and early 1980s" [S:67:38]. What the mathematics establishes is narrower: one unit draws one line, XOR needs more than one line, and nothing whatever follows about what a stack of units can represent.

Nor does the result say anything about usefulness: a single unit with weights 1 and 1 and a threshold of 0.5 still classifies three of these four examples correctly. The perceptron will not settle on that unit, because XOR is not separable and the loop of §19.1 never terminates; a procedure given a fixed budget can [S:58:214].

The formal statement. Let a finite set of labelled points be given, with labels in $\{-1,+1\}$. The set is linearly separable when some vector $w$ and scalar $b$ satisfy $y_i(w\cdot x_i+b)>0$ for every $i$. Two facts turn that definition into a tool. First, a finite set is separable exactly when the convex hulls of its two label classes are disjoint [S:58:240]. Second, the class of halfspaces in ${\mathbb{R}}^d$ has VC dimension $d+1$ [S:79:122].

VC dimension is the size of the largest point set that the class can label in every possible way [S:75:53]. In the plane the value is three, so four points can always be labelled in a way no line realizes. The XOR table is one such labelling: a positive diagonal against a negative diagonal [S:75:54].

The derivation. Suppose a line separates the classes. Every convex combination of positive points keeps a positive score, because the score is linear, and every combination of negative points keeps a negative score. So the hulls cannot share a point. For the converse, two disjoint compact convex sets admit a separating hyperplane, and the sign of that hyperplane gives $w$ and $b$. The upper bound on VC dimension is Radon's theorem: any $d+2$ points in ${\mathbb{R}}^d$ split into two groups whose hulls intersect [S:75:55]. Intersecting hulls rule out separation, so no set of $d+2$ points is shattered. In the plane, some labelling of any four points fails, and the alternating diagonal is the standard witness.

The edge case. The Core now calls XOR the smallest Boolean function of two inputs that no halfspace computes, and the one-dimensional witness shows why the qualifier matters. Three points on a line, labelled positive, negative, positive, already defeat a threshold in one dimension, because a threshold is a half-line and its boundary cuts the line at one point. The labels there change sign twice. The precise claim is about Boolean functions of two inputs, not about the smallest configuration that no halfspace separates.

What the Core hid. The historical perceptron had several layers of processing, and only one of them was learnable from data [S:67:38]. Calling it a single-layer network is a statement about trainable parameters, not about wiring. The Core also let the failure look like weakness. A class with VC dimension $d+1$ still shatters every set of $d+1$ points in general position, which is a large amount of expressive power for one line.

Where the analogy breaks. The Core argues that a line crosses a square in at most two edges. That counting needs the four points to sit in convex position, with none on an edge and none repeated. Move one point inside the triangle of the other three and the edge count still gives the right verdict, but for a different reason: one class now surrounds the other.

Original sources. The XOR example and its hidden-unit solution are in Murphy's chapter on networks for tabular data, which names the 1969 book as the source of the example [S:63:456] [S:63:457]. Bishop and Bishop state what that book proved and what it only conjectured [S:67:38]. The convex-hull criterion and the dimension count come from the statistical learning literature [S:58:240] [S:79:122].

An open question. Separability is settled and learnability is not. Depth separation results show that some functions need exponentially many units at shallow depth and few at greater depth [S:66:178-179]. Nothing in this corpus says that gradient descent finds the deeper representation in polynomial time. The unsettled question is whether training from a random start can learn a depth-separated family efficiently. The question has a clean shape: pick a family, fix an algorithm, and ask for a time bound. Evidence that would settle it: a polynomial-time guarantee for a named family and a stated algorithm, or a lower bound against a stated class of algorithms.

A frontier result. The depth separation for rectifier networks rests on counting linear regions: a deeper network folds its input space more times than a shallow one with the same number of units [S:66:178-179]. The folding picture is the Core's bend, repeated. Each hidden layer adds folds, and the count of regions grows with depth rather than with width alone.

What to read next. Read Murphy 13.2 for the construction you did by hand, then close the book and rebuild it [S:63:456] [S:63:457]. Read Goodfellow's section on architecture design for the approximation argument and the depth argument on facing pages [S:66:177] [S:66:178]. Read Shalev-Shwartz and Ben-David 9.1.3 for the VC-dimension proof that turns the four-point argument into a theorem about every dimension [S:79:122]. Read the exercise in Bishop that states the convex-hull criterion, and prove it in both directions [S:58:240].