Backpropagation: learning XOR by gradient descent
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.
Python
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])