Example: Learning XOR

The big picture

Picture a hallway light with two switches, one at each end of the hall. The light is on when exactly one switch is up. When both are up, or both are down, it is off. That rule is the XOR function, short for “exclusive or”. It takes two inputs that are each 0 or 1, and returns 1 only when exactly one of them is 1.

A neural network learns a rule like this from examples. The rule is the target function , which gives the correct output for every input. The model is a function with adjustable parameters . Learning means changing until the model’s outputs match the target.

The four possible inputs are the corners of a square. Before you test anything, make a prediction: can one straight line separate the inputs that give 1 from the inputs that give 0?

Choose an answer to see the result.

The filled points should lie on the shaded side and the hollow points off it. Whatever the setting, one point always lands on the wrong side. A set of points that no straight line can split this way is called not linearly separable. The rest of this lesson explains why XOR is one of them, and how a network with one extra layer avoids the problem.

The data and the loss

The book trains on the four inputs and nothing else. Its training set is the set of those four points. The book does not test on new inputs here, so the only question is whether the model fits these four.

To measure the fit, use the mean squared error. It averages the squared gap between the target and the model’s output over the training set:

Read it from the inside out. For each input, subtract the output from the target, and square the gap so that too high and too low count the same. Then average the four squared gaps. The loss is 0 only for a perfect fit. The book uses this loss to keep the algebra short, and it notes that squared error is not the usual choice for binary data. Section 6.2.2.2 describes better choices.

The simplest model is linear. It has one weight for each input, = (, ), and one bias :

Set the three numbers in the demo below and watch the loss change. The bars show the target and the output for each input. The purple bar is the output, and the gray bar is the target.

Why no linear model does better

The book finds the best linear model with the normal equations. The answer is weights of zero and a bias of one half. The linear model then outputs 0.5 for every input, and its loss is 0.25. No choice of weights and bias does better.

Predict before you look. What constant does the best linear model output for all four inputs?

Choose an answer.

The demo below fixes the two weights and moves the bias. The curve is the loss as a function of the bias, for the weights you choose.

The picture makes the answer visible. With both weights at zero, the lowest point is at a bias of one half, and its height is 0.25. Any non-zero weight raises the lowest point, because neither input is linearly related to the target, so a non-zero weight only adds error.

Move the bias to find the lowest point of the curve for both weights at zero. Then raise one weight and see how much higher the curve sits.

A hidden layer that bends the space

Two linear maps stacked on each other still form one linear map. A network made only of linear layers therefore stays linear, however deep it is, and cannot fit XOR. The fix is to put a nonlinear activation function between the layers. Each hidden unit takes a weighted sum of the inputs, adds a bias, and passes the result through .

The book’s default recommendation is the rectified linear unit, or ReLU. It keeps positive numbers and sets negative numbers to zero:

The number that goes into the ReLU is called the pre-activation. Here it is . The demo below shows the ReLU and its slope. The orange line is the slope, which is 0 to the left of zero and 1 to the right. The slope is what gradient descent receives, so it matters as much as the curve.

The hidden layer has two units. Their weights form the matrix , one column per unit, and their biases form the vector . The output unit has weights and bias . The complete network is

The book gives one solution to XOR. The weights and biases are

with = 0. Figure 6.2 of the book draws this network in two styles, one with every unit as a node and one with each layer as a box. The picture under the table in the next demo is the first style, and its edges show the current numbers. Build the network yourself. Keep and the first hidden bias as they are, and set the other four numbers. Each row of the table is one of the four inputs.

Walking through the batch

The four inputs can be computed in one pass. Stack them as the rows of a matrix , called the design matrix, with one input per row. Apply the network to every row at once. Press Next to move through the computation one matrix at a time, as in equations 6.7 to 6.11.

The step that matters most is the ReLU. It is the only nonlinear operation, and it is where the four points stop lying on one line. Each output is a weighted sum of the hidden values, with the weights in , plus the bias .

Figure 6.1 of the book shows the same idea. The left picture is the input square, and the right picture is the hidden space . Drag the probe point in the left picture and watch where it lands on the right. The sliders move the probe too, so the demo works from the keyboard.

What the example leaves out

The example is small on purpose, and the book is explicit about what it does not show. It trains on all four inputs and makes no claim about new inputs. It also shows one solution, but XOR has other equivalent solutions. The solution above is a global minimum of the loss, so gradient descent could converge to it. Where gradient descent ends up depends on the starting parameters, and in practice it would rarely find clean integer values like the ones here.

The book notes that in this example the hidden layer serves only to give the model enough capacity to fit the training set. In more realistic applications, learned representations can also help the model generalize.

The demo below shows one practical risk of the ReLU. A unit whose input is negative for every example outputs zero and passes no gradient back to its weights. This is a feature of the ReLU itself, and Section 6.3 returns to it. The design of this demo is ours and is not printed in the book.

• XOR is not linearly separable, so a linear model cannot fit it, and the best linear loss on these four points is 0.25.
• Stacking linear layers without a nonlinearity gives another linear map. A hidden layer with a ReLU breaks this.
• The ReLU keeps positive values and zeros negative ones. Its slope is 1 or 0, so gradients pass through active units unchanged.
• A batch is computed as matrix products. Each row is one input, and each matrix step is one layer of the computation.
• A unit that is off for every example gets no gradient, which is a risk to remember for later.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 6.1 (pages 171–176), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.