Where One Perceptron Fails

We have seen that a perceptron draws a straight line. So what kind of function can it never compute?

XOR

XOR (exclusive or) outputs 1 when exactly one input is 1:

Plot the four points. The two 1-outputs are at opposite corners of the square, and so are the two 0-outputs. There is no straight line with both 1-corners on one side and both 0-corners on the other.

The algebra agrees

Suppose some $w_0, w_1, w_2$ did compute XOR. The four rows would require:

1. $w_0 < 0$
2. $w_0 + w_2 \ge 0$
3. $w_0 + w_1 \ge 0$
4. $w_0 + w_1 + w_2 < 0$

Add rows 2 and 3: $2w_0 + w_1 + w_2 \ge 0$, so $w_1 + w_2 \ge -2w_0$. Row 4 says $w_1 + w_2 < -w_0$.

Together, $-2w_0 \le w_1 + w_2 < -w_0$, which forces $-2w_0 < -w_0$, that is, $w_0 > 0$. But row 1 says $w_0 < 0$. Contradiction, so no such weights exist. No learning algorithm can find them either.

How common is this?

Two binary inputs give $2^4 = 16$ possible Boolean functions. Of these, 14 are linearly separable, and only XOR and its opposite XNOR are not. So the failure is rare among two-input functions. It becomes far more common as inputs grow.

In general, $n$ binary inputs give $2^n$ possible input rows, and each row can output 0 or 1, so there are $2^{2^n}$ Boolean functions. That is 16 for $n = 2$, 256 for $n = 3$, and over 4 billion for $n = 5$. How many of them are linearly separable has no simple formula. Counting them is a hard problem that researchers have worked out only for small $n$. What we can say is that some are not separable, and that is enough to need something more than one perceptron.

Real data rarely separates cleanly

The film example has the same flavour. Real preferences are messy: you might like a thriller only when it is by a particular director, or a comedy only when a certain actor is in it. Interactions like this are exactly what a single straight line cannot capture. A dataset of past films will usually not be linearly separable.

Two common reasons:

• Outliers. Among people who fit the profile of someone who enjoys machine learning, a few still do not. Among the people of one neighbourhood who mostly speak one language, a few speak another.
• Genuinely curved boundaries. Picture one group forming an inner ring and another an outer ring around it. There are no outliers at all, yet no straight line separates them.

A way out

The problem was not perceptrons. It was using one. Stacking several perceptrons, where some feed into another, changes what can be computed. The next lesson shows a network that solves XOR and, in fact, any Boolean function.