Backpropagation: learning XOR by gradient descent

Compute gradients with the chain rule, verify them numerically, and train a small network on XOR.

import math

DATA = [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 0)]
HIDDEN = 3
LEARNING_RATE = 1.0
w1 = [[0.5, -0.4], [-0.3, 0.8], [0.9, 0.2]]
b1 = [0.1, -0.1, 0.05]
w2 = [0.7, -0.6, 0.4]
b2 = [0.0]


def sigmoid(z):
    return 1 / (1 + math.exp(-z))


def forward(x):
    h = [sigmoid(sum(w1[j][k] * x[k] for k in range(2)) + b1[j]) for j in range(HIDDEN)]
    y = sigmoid(sum(w2[j] * h[j] for j in range(HIDDEN)) + b2[0])
    return h, y


def loss():
    return sum(0.5 * (forward(x)[1] - t) ** 2 for x, t in DATA)


def gradients():
    gw1 = [[0.0, 0.0] for _ in range(HIDDEN)]
    gb1 = [0.0] * HIDDEN
    gw2 = [0.0] * HIDDEN
    gb2 = 0.0
    for x, t in DATA:
        h, y = forward(x)
        dz2 = (y - t) * y * (1 - y)
        gb2 += dz2
        for j in range(HIDDEN):
            gw2[j] += dz2 * h[j]
            dz1 = dz2 * w2[j] * h[j] * (1 - h[j])
            gb1[j] += dz1
            for k in range(2):
                gw1[j][k] += dz1 * x[k]
    return gw1, gb1, gw2, gb2


analytic = gradients()[0][1][0]
eps = 1e-6
w1[1][0] += eps
up = loss()
w1[1][0] -= 2 * eps
down = loss()
w1[1][0] += eps
print(abs((up - down) / (2 * eps) - analytic) < 1e-8)

for _ in range(10000):
    gw1, gb1, gw2, gb2 = gradients()
    for j in range(HIDDEN):
        for k in range(2):
            w1[j][k] -= LEARNING_RATE * gw1[j][k]
        b1[j] -= LEARNING_RATE * gb1[j]
        w2[j] -= LEARNING_RATE * gw2[j]
    b2[0] -= LEARNING_RATE * gb2

print(round(loss(), 4))
print([round(forward(x)[1], 2) for x, _ in DATA])

True
0.0004
[0.0, 0.99, 0.99, 0.02]

Explanation

Training a neural network means adjusting its weights to reduce a loss. Gradient descent needs the gradient of the loss with respect to every weight. Backpropagation computes all of them efficiently with the chain rule: after a forward pass stores each layer's activations, a backward pass starts at the output and works toward the input, reusing results from later layers. It is a special case of reverse-mode automatic differentiation and was popularized for neural networks by Rumelhart, Hinton, and Williams in 1986.

For this network the output y = σ(z₂) with z₂ = Σ w₂ⱼ hⱼ + b₂ and each hidden unit hⱼ = σ(z₁ⱼ). With the loss ½(y − t)², the error signal at the output is (y − t)·y·(1 − y). The gradient for each output weight is that signal times the hidden activation hⱼ. The signal passes back to the hidden unit multiplied by the weight w₂ⱼ and the slope hⱼ(1 − hⱼ), and the gradient of each first-layer weight is that signal times the input.

A bug in a hand-written gradient is easy to make and hard to see, so the program first checks one gradient against a finite-difference estimate, (L(w + ε) − L(w − ε)) / 2ε. They agree to better than 10⁻⁸. Then it trains with full-batch gradient descent for 10000 steps from fixed starting weights, which makes the run reproducible. The final loss is tiny and the outputs are close to 0, 1, 1, 0. Unlike the previous lesson, the weights were learned, not chosen by hand.

—

—

True

True

True
0.0004

True
0.0004
[0.0, 0.99, 0.99, 0.02]

Cost and common mistakes

One forward-and-backward pass costs about the same as a few forward passes, O(W) for W weights. Backpropagation makes the gradient of all W weights cost O(W) instead of O(W²).

• Always check hand-written gradients numerically at least once. Sign and indexing mistakes are common.
• Initial weights must differ between neurons. If all start equal, hidden units compute the same thing and stay identical.
• Training on XOR with few hidden units can stall depending on the start. Larger networks and good initialization, such as Xavier or He, make this less likely.

Try it yourself

Why is the gradient check run with centred differences instead of a one-sided difference?

Further reading

• Rumelhart, Hinton, and Williams (1986): Learning representations by back-propagating errors (external)
• Stanford CS231n: Deep Learning for Computer Vision (external)
• Deep Learning (Goodfellow, Bengio, Courville) (external)