Try first

Four points. Two of class A, two of class B.

A: (0, 0) and (1, 1)
B: (0, 1) and (1, 0)

Draw them on paper. Now draw one straight line with both A points on one side and both B points on the other.

Spend a minute on it. The minute is the lesson.

There is no such line

The A points sit on one diagonal and the B points on the other. Any line separating the two A points from each other fails, and any line keeping them together also keeps the B points together with them. Four points, and the simplest model in machine learning cannot do it.

This arrangement is called XOR, after the logical operation it matches: true when exactly one input is true.

0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0

Compare it to two problems that do work. AND is true only at (1,1), and a line across the top right corner separates it. OR is false only at (0,0), and a line across the bottom left corner does it. Both are solvable by the model you already have. XOR is not, and it is not close.

Linear separability

A dataset is linearly separable if some straight line puts one class entirely on each side. In more than two dimensions, replace the line with a flat plane and the definition is unchanged.

Everything in sections 3 to 6 assumed this. Linear regression fits a straight relationship. Logistic regression puts a straight boundary between classes. When the data is not linearly separable, both fail, and they fail completely rather than partially.

You already met three cases in lesson 3077: the ring, the stripes, and now XOR. They look different and the reason is the same.

Check it with the code

const xor = [
  { x: [0, 0], y: 0 },
  { x: [0, 1], y: 1 },
  { x: [1, 0], y: 1 },
  { x: [1, 1], y: 0 },
];

const [w, b] = trainLogistic(xor, 0.5, 100000);
for (const r of xor) {
  log(r.x.join(","), " want", r.y, " got", predictProb(w, b, r.x).toFixed(4));
}
log("log loss", logLossAll(w, b, xor).toFixed(4));

Every output is 0.5, or very close to it. The log loss sits at 0.693, which lesson 3073 identified as the score for shrugging at everything.

Look at the weights: both near zero. Gradient descent worked perfectly and found the best line available, and the best line available is the one that gives up. The (0,0) and (1,1) points pull the boundary one way, the (0,1) and (1,0) points pull it exactly the other, and the pulls cancel.

Nothing here is broken. A hundred thousand steps confirmed there is no answer to find.

Why this mattered historically

In 1969 Minsky and Papert published a careful analyzis of what single layer networks could and could not do, with XOR as the clearest example. The result was correct and it was widely read as the end of the idea. Funding and interest in neural networks collapsed for most of the following decade.

What was already known, and got lost in the reception, is that stacking layers fixes it. What was not known was a practical way to train the stack. That arrived with backpropagation becoming widely understood in the 1980s, which is section 8.

So the gap between the problem and its fix was not a missing idea about model shape. It was a missing method for computing gradients through more than one layer.

What to watch

Failing to fit and being unable to fit look identical from the loss alone. Both give a stuck number. Before assuming a model is undertrained, ask whether the shape it can express includes the answer at all. On two features you can check by looking. On seven hundred you cannot, which is why people default to models flexible enough that the question does not arise.

Exercises

  1. Train the same model on AND and on OR. Confirm both work and note the weights each finds.
  2. Add a fifth point at (0.5, 0.5) labeled 1 and retrain. Does anything change?
  3. Find a single extra feature, computed from x0 and x1, that makes XOR separable. There is a short answer.
  4. How many of the sixteen possible labelings of these four points are linearly separable? Work it out by hand.
PreviousNext