The XOR problem: four dots no straight line can separate

What the XOR problem is

XOR is short for exclusive or: the answer is yes when exactly one of two things is true, and no when both are true or neither is. Take two inputs that can each be 0 or 1 (off or on). XOR gives:

| Input A | Input B | Answer | |---|---|---| | 0 | 0 | no | | 0 | 1 | yes | | 1 | 0 | yes | | 1 | 1 | no |

It looks trivial. Yet a single perceptron (a very simple learning program, which sorts examples by drawing one straight line between two groups) can never solve it, whatever numbers it tries. The course describes this as the failure that closed the first era of neural networks.

What the video shows

The video draws the four cases as four dots: the two yes answers on one diagonal, the two no answers on the other. No single straight line can put both yes dots on one side and both no dots on the other, however you tilt it. Getting past that wall required stacking layers of these simple learners, one feeding the next.

An everyday example

Think of a staircase light with one switch at the bottom and one at the top. Flip either switch and the light changes. With one common wiring, the light is on when the two switches point different ways and off when they match. That is XOR in your hallway.

Notice that knowing the position of one switch tells you nothing about the light. Only the combination of both does.

Why no line works

A perceptron gives each input a weight (how strongly it pushes the score up or down), adds a starting value called the bias (a constant it also learns), and answers yes when the total is high enough. Follow the four rows:

• Both inputs off must be "no", so the starting value alone has to land on the no side.
• Either input on by itself must be "yes", so each input has to push the score up, and strongly enough on its own.
• Turn both on and both pushes add up, so the score lands even further on the yes side.
• But XOR needs both-on to be "no". There is no way out.

The course writes this as four short inequalities and shows they would need the bias to be positive and negative at the same time. No choice of numbers escapes it.

What the learner does anyway

Train it regardless. Its numbers do not blow up, and it does not creep toward a decent answer. It goes round in circles, looping through the same few settings forever and getting 2 of the 4 rows right, which is what guessing would give you. After 100 passes through the data or 100,000, the result is identical.

Compare that with the slow run from the convergence theorem, which looked stuck at 200 passes but was quietly heading to a real answer. From outside the two look alike at first; knowing the theory is how you tell slow from hopeless.

How to spot it

Switching input A on turns a no into a yes when B is off, but a yes into a no when B is on. A straight line gives each input one fixed push, always in the same direction. So when the effect of one input flips depending on another, like one staircase switch, a single line cannot capture it.

Why it matters

XOR showed that one line, however well trained, has a hard limit. The way out was to stack layers, so that later units can combine what earlier ones found. The course builds that in Chapter 5; this chapter shows why it is needed.

Learn it step by step in Chapter 1 of our free course AI From Scratch: The Perceptron From Scratch: What a Neuron Computes.