Try first

You cannot separate XOR with one line. Can you separate it with two?

Draw the four points again and try. If you find a pair of lines that works, write down what rule combines them into an answer.

Two lines, then a decision about them

Here is one solution. Draw a line just above and right of (0,0), and another just below and left of (1,1). Now every point sits in one of three regions: below both lines, between them, or above both.

The two class 1 points are in the middle region. The two class 0 points are one in each outer region.

So the rule is: class 1 exactly when the point is on the far side of the first line and the near side of the second. Two questions, then an AND of the answers.

Say it in the language you already have. Each line is a logistic unit. The combining rule is another logistic unit taking those two answers as its input. Three units in two stages.

The classic version

The same solution is often written with two familiar operations.

XOR = (A OR B) AND NOT (A AND B)

True when at least one is true, and not both. OR is linearly separable. AND is linearly separable. XOR is the two of them combined, and the combination is where the power comes from.

Check the truth table by hand:

A B | OR  AND  NOT AND | result
0 0 |  0   0      1    |   0
0 1 |  1   0      1    |   1
1 0 |  1   0      1    |   1
1 1 |  1   1      0    |   0

The middle two columns are the first stage. Neither of them is the answer. Both are questions worth asking about the input, and the third column combines them.

Do it by hand

Weights that implement it. Nothing is trained here, they are written out so you can see that a solution exists.

function unit(w, b, x) { return sigmoid(dotProduct(w, x) + b); }

const orW  = [20, 20],   orB  = -10;   // fires unless both inputs are 0
const andW = [20, 20],   andB = -30;   // fires only when both are 1
const outW = [20, -20],  outB = -10;   // OR yes, AND no

for (const r of xor) {
  const h0 = unit(orW,  orB,  r.x);
  const h1 = unit(andW, andB, r.x);
  const p  = unit(outW, outB, [h0, h1]);
  log(r.x.join(","), " or", h0.toFixed(2), " and", h1.toFixed(2),
      " -> ", p.toFixed(3), " want", r.y);
}

All four correct. Look at how the numbers work.

orB = -10 with weights of 20 means the score is -10 with no inputs on, +10 with one on, +30 with both. The sigmoid turns those into about 0, 1 and 1. That is OR.

andB = -30 shifts the threshold so it takes both inputs to get positive. That is AND.

The output unit weights h0 at +20 and h1 at -20 with a bias of -10, so it needs the first on and the second off. That is the combining rule.

The weights are large on purpose. Large weights make the sigmoid behave almost like a hard switch, which is what makes these read as logic. Trained networks rarely look this clean.

What just happened

The first stage did not classify anything. It re-described each input as a pair of numbers, and in that new description the problem became linearly separable.

That is the same trick as adding the squared radius feature in lesson 3077. The difference is decisive: there you worked out the transformation yourself, by looking at the data and thinking. Here it is computed by units with weights, and weights can be learned.

That is the whole idea of a neural network. Stop hand designing features. Make the feature transformation part of the model and let gradient descent find it.

What to watch

We chose these weights by hand from a solution we already knew. Nothing so far shows they can be learned. Training needs a gradient for orW, which affects the loss only through h0, which affects it through the output unit. That chain is what section 8 is about, and it is the part that took the field fifteen years.

Exercises

  1. Change all the 20s to 2s and rerun. Are the four answers still correct? What happened to the confidence?
  2. Find a different set of nine numbers that also solves XOR. How different can they be?
  3. Implement XNOR by changing one number.
  4. Print h0 and h1 for the four inputs and plot them as points. Are those four points linearly separable? That is the whole explanation in one picture.
PreviousNext