Neural networks all 4 written
A neuron, a layer, backpropagation, and a network that really trains.
13 One neuron, and what a layer is
A neuron multiplies each input by a weight, adds a bias, and passes the result through one function that bends. Everything in this part of the course is that, repeated and wired together. This lesson builds one, trains it to do two useful things, then shows the third thing it can never do — and that failure is what layers exist to fix.
The whole of a neuron
Three steps, none of them new. The weighted sum is the dot product from lesson 5. The
bias is the same intercept as lesson 7's b. The only addition is the
activation, a function applied to the result, and three of them cover almost everything you
will meet.
# One neuron: multiply, add, squash. There is nothing else in it.
import math
def sigmoid(z):
"""Squashes any real number into the open interval from zero to one."""
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z) # the same function, rearranged so exp cannot overflow
return ez / (1.0 + ez)
def tanh(z):
"""The same S shape, centred on zero and running from minus one to one."""
return math.tanh(z)
def relu(z):
"""Positives pass through untouched, negatives become zero. One comparison."""
return z if z > 0.0 else 0.0
def neuron(weights, bias, inputs, activation):
"""A neuron, entire: a dot product, plus a bias, through an activation."""
z = sum(w * x for w, x in zip(weights, inputs)) + bias
return activation(z)
print(" z sigmoid tanh relu")
table = []
for z in (-3.0, -1.0, -0.25, 0.0, 0.25, 1.0, 3.0):
row = (sigmoid(z), tanh(z), relu(z))
table.append(row)
print(" {:5.2f} {:9.6f} {:9.6f} {:9.6f}".format(z, *row))
# One neuron, one input pair, three activations. Same z, three different answers.
W = [0.5, -1.5]
B = 0.25
X = [2.0, 1.0]
z = sum(w * x for w, x in zip(W, X)) + B
print()
print("weights {}, bias {}, inputs {}".format(W, B, X))
print("weighted sum + bias z = 0.5*2 + -1.5*1 + 0.25 =", z)
print("through sigmoid {:.6f} <- a weak yes".format(neuron(W, B, X, sigmoid)))
print("through tanh {:.6f} <- a weak no".format(neuron(W, B, X, tanh)))
print("through relu {:.6f} <- silent".format(neuron(W, B, X, relu)))
# The overflow every hand-written sigmoid meets eventually.
print()
print("guarded sigmoid(-800) =", sigmoid(-800.0))
try:
1.0 / (1.0 + math.exp(800.0))
overflowed = False
except OverflowError as error:
overflowed = True
print("the naive one raises : OverflowError:", error)
# The derivatives, needed from the next lesson onwards.
s = sigmoid(0.7)
analytic = s * (1.0 - s)
numeric = (sigmoid(0.7 + 1e-5) - sigmoid(0.7 - 1e-5)) / 2e-5
print()
print("sigmoid'(0.7) by the identity s*(1-s) : {:.10f}".format(analytic))
print("sigmoid'(0.7) by a central difference : {:.10f}".format(numeric))
test("sigmoid of zero is a half", close(sigmoid(0.0), 0.5), True)
test("tanh is zero at zero and odd either side",
[close(tanh(0.0), 0.0), close(tanh(-1.3), -tanh(1.3))], [True, True])
test("relu passes a positive through and flattens a negative",
[relu(2.0), relu(-2.0)], [2.0, 0.0])
test("the weighted sum plus bias comes to minus a quarter", close(z, -0.25), True)
test("so the sigmoid neuron half fires while the relu neuron says nothing",
[close(neuron(W, B, X, sigmoid), 0.437823499, 1e-6), close(neuron(W, B, X, relu), 0.0)],
[True, True])
test("sigmoid stays strictly inside zero and one for every row of the table",
all(0.0 < row[0] < 1.0 for row in table), True)
test("the guarded sigmoid handles minus eight hundred where the naive form overflows",
[close(sigmoid(-800.0), 0.0), overflowed], [True, True])
test("the sigmoid derivative identity matches a central difference",
close(analytic, numeric, 1e-8), True)What it printed, when the build ran it
z sigmoid tanh relu -3.00 0.047426 -0.995055 0.000000 -1.00 0.268941 -0.761594 0.000000 -0.25 0.437823 -0.244919 0.000000 0.00 0.500000 0.000000 0.000000 0.25 0.562177 0.244919 0.250000 1.00 0.731059 0.761594 1.000000 3.00 0.952574 0.995055 3.000000 weights [0.5, -1.5], bias 0.25, inputs [2.0, 1.0] weighted sum + bias z = 0.5*2 + -1.5*1 + 0.25 = -0.25 through sigmoid 0.437823 <- a weak yes through tanh -0.244919 <- a weak no through relu 0.000000 <- silent guarded sigmoid(-800) = 0.0 the naive one raises : OverflowError: math range error sigmoid'(0.7) by the identity s*(1-s) : 0.2217128733 sigmoid'(0.7) by a central difference : 0.2217128733 ok sigmoid of zero is a half ok tanh is zero at zero and odd either side ok relu passes a positive through and flattens a negative ok the weighted sum plus bias comes to minus a quarter ok so the sigmoid neuron half fires while the relu neuron says nothing ok sigmoid stays strictly inside zero and one for every row of the table ok the guarded sigmoid handles minus eight hundred where the naive form overflows ok the sigmoid derivative identity matches a central difference
Which activation, and why:
- sigmoid — output between 0 and 1, so it reads as a probability. Its
derivative peaks at 0.25 and is nearly zero once
zis past about 5, which is where vanishing gradients come from. Now used almost only on a final output. - tanh — the same shape centred on zero, so a layer's outputs average near zero and the next layer gets a better-behaved input. Still a reasonable default in a small hidden layer.
- relu — one comparison, derivative exactly 0 or 1, no saturation on the positive side. What almost every large network actually uses, and the reason deep networks became trainable.
The if z >= 0.0 in that sigmoid is not style. Written the obvious way,
1 / (1 + exp(-z)) calls exp(800) when z is
-800, and Python raises OverflowError: math range error rather
than returning zero. Real activations get large arguments the moment a learning rate is
slightly too high, so the panel above proves the guarded form survives it.
A single neuron learning AND, and learning OR
Training is lesson 7's loop unchanged: compute the loss, compute the gradient, step against it. The only new part is one extra link in the chain rule, because the output now passes through the sigmoid on its way to the loss.
# One neuron, trained. AND and OR are both one straight line away.
import math
import random
def sigmoid(z):
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z)
return ez / (1.0 + ez)
ROWS = [(0.0, 0.0), (0.0, 1.0), (1.0, 0.0), (1.0, 1.0)]
AND = [0.0, 0.0, 0.0, 1.0]
OR = [0.0, 1.0, 1.0, 1.0]
def predict(params, x):
w1, w2, b = params
return sigmoid(w1 * x[0] + w2 * x[1] + b)
def loss(params, targets):
"""Mean squared error, the same loss as lesson 7."""
return sum((predict(params, x) - y) ** 2 for x, y in zip(ROWS, targets)) / len(ROWS)
def gradient(params, targets):
"""The chain rule, with one more link than lesson 7 had.
L = mean((a - y) ** 2) where a = sigmoid(z)
dL/da = 2 * (a - y) / n
da/dz = a * (1 - a) the identity from the panel above
dz/dw1 = x1, dz/dw2 = x2, dz/db = 1
"""
n = len(ROWS)
dw1 = dw2 = db = 0.0
for x, y in zip(ROWS, targets):
a = predict(params, x)
dz = 2.0 * (a - y) * a * (1.0 - a) / n
dw1 += dz * x[0]
dw2 += dz * x[1]
db += dz
return (dw1, dw2, db)
def train(targets, lr=2.0, epochs=4000, seed=42):
rng = random.Random(seed) # seeded, so this page prints the same numbers twice
params = (rng.uniform(-1.0, 1.0), rng.uniform(-1.0, 1.0), rng.uniform(-1.0, 1.0))
history = [loss(params, targets)]
for _ in range(epochs):
g = gradient(params, targets)
params = tuple(p - lr * d for p, d in zip(params, g))
history.append(loss(params, targets))
return params, history
runs = {}
for name, targets in (("AND", AND), ("OR", OR)):
runs[name] = train(targets)
params, history = runs[name]
print("{} starting loss {:.6f}".format(name, history[0]))
for epoch in (100, 500, 1000, 4000):
print(" epoch {:5} loss {:.8f}".format(epoch, history[epoch]))
print(" w1 = {:.4f} w2 = {:.4f} b = {:.4f}".format(*params))
print(" outputs:", " ".join("{:.4f}".format(predict(params, x)) for x in ROWS))
print(" rounded:", [1 if predict(params, x) > 0.5 else 0 for x in ROWS],
" wanted", [int(y) for y in targets])
print()
and_params, and_history = runs["AND"]
or_params, or_history = runs["OR"]
and_rounded = [1 if predict(and_params, x) > 0.5 else 0 for x in ROWS]
or_rounded = [1 if predict(or_params, x) > 0.5 else 0 for x in ROWS]
w1, w2, b = and_params
print("AND put its line out near the far corner: it takes both inputs to clear a bias")
print("of {:.2f}. OR put its line near the origin, where either input alone is enough.".format(b))
test("the AND neuron gets all four rows right", and_rounded, [0, 0, 0, 1])
test("the OR neuron gets all four rows right", or_rounded, [0, 1, 1, 1])
test("the AND loss fell below a hundredth", and_history[-1] < 0.01, True)
test("the loss fell on every one of the four thousand AND epochs",
all(and_history[i + 1] < and_history[i] for i in range(len(and_history) - 1)), True)
test("AND ended with two positive weights and a bias neither can clear alone",
[w1 > 0.0, w2 > 0.0, w1 + b < 0.0, w2 + b < 0.0, w1 + w2 + b > 0.0],
[True, True, True, True, True])
test("OR ended with a bias that either input on its own does clear",
[or_params[0] + or_params[2] > 0.0, or_params[1] + or_params[2] > 0.0], [True, True])What it printed, when the build ran it
AND starting loss 0.242175
epoch 100 loss 0.03266743
epoch 500 loss 0.00572054
epoch 1000 loss 0.00264707
epoch 4000 loss 0.00059429
w1 = 7.0383 w2 = 7.0383 b = -10.6454
outputs: 0.0000 0.0264 0.0264 0.9687
rounded: [0, 0, 0, 1] wanted [0, 0, 0, 1]
OR starting loss 0.414594
epoch 100 loss 0.01822851
epoch 500 loss 0.00290060
epoch 1000 loss 0.00134743
epoch 4000 loss 0.00030739
w1 = 7.7045 w2 = 7.7045 b = -3.6153
outputs: 0.0262 0.9835 0.9835 1.0000
rounded: [0, 1, 1, 1] wanted [0, 1, 1, 1]
AND put its line out near the far corner: it takes both inputs to clear a bias
of -10.65. OR put its line near the origin, where either input alone is enough.
ok the AND neuron gets all four rows right
ok the OR neuron gets all four rows right
ok the AND loss fell below a hundredth
ok the loss fell on every one of the four thousand AND epochs
ok AND ended with two positive weights and a bias neither can clear alone
ok OR ended with a bias that either input on its own does clear
And now XOR, which it cannot do
XOR is one or the other but not both. Same neuron, same loop, twice as many epochs. Watch the loss stop.
# XOR. Same neuron, same training loop, more effort. It cannot be done.
import math
import random
def sigmoid(z):
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z)
return ez / (1.0 + ez)
ROWS = [(0.0, 0.0), (0.0, 1.0), (1.0, 0.0), (1.0, 1.0)]
XOR = [0.0, 1.0, 1.0, 0.0] # one or the other, but not both
def predict(params, x):
w1, w2, b = params
return sigmoid(w1 * x[0] + w2 * x[1] + b)
def loss(params, targets):
return sum((predict(params, x) - y) ** 2 for x, y in zip(ROWS, targets)) / len(ROWS)
def train(targets, lr=2.0, epochs=8000, seed=42):
rng = random.Random(seed)
params = (rng.uniform(-1.0, 1.0), rng.uniform(-1.0, 1.0), rng.uniform(-1.0, 1.0))
history = [loss(params, targets)]
for _ in range(epochs):
n = len(ROWS)
dw1 = dw2 = db = 0.0
for x, y in zip(ROWS, targets):
a = predict(params, x)
dz = 2.0 * (a - y) * a * (1.0 - a) / n
dw1 += dz * x[0]
dw2 += dz * x[1]
db += dz
params = (params[0] - lr * dw1, params[1] - lr * dw2, params[2] - lr * db)
history.append(loss(params, targets))
return params, history
params, history = train(XOR)
outputs = [predict(params, x) for x in ROWS]
print("XOR, eight thousand epochs, twice as long as AND needed")
for epoch in (0, 100, 1000, 4000, 8000):
print(" epoch {:5} loss {:.8f}".format(epoch, history[epoch]))
print()
print(" w1 = {:.6f} w2 = {:.6f} b = {:.6f}".format(*params))
print(" outputs:", " ".join("{:.6f}".format(a) for a in outputs))
print(" rounded:", [1 if a > 0.5 else 0 for a in outputs], " wanted [0, 1, 1, 0]")
print()
print("The loss stops at a quarter and the weights collapse to zero. The neuron has")
print("no opinion left, which for mean squared error is the best a straight line can")
print("manage here. It is not undertrained. It is finished.")
def separates_xor(w1, w2, b):
"""Does the line w1*x1 + w2*x2 + b = 0 put XOR's ones on one side?"""
return (b < 0.0 # (0,0) must land as a zero
and w1 + b > 0.0 # (1,0) must land as a one
and w2 + b > 0.0 # (0,1) must land as a one
and w1 + w2 + b < 0.0) # (1,1) must land as a zero
def separates_and(w1, w2, b):
"""The same four rows, for AND, so the search can be trusted."""
return (b < 0.0 and w1 + b < 0.0 and w2 + b < 0.0 and w1 + w2 + b > 0.0)
GRID = [i * 0.2 - 6.0 for i in range(61)]
xor_hits = sum(1 for a in GRID for c in GRID for d in GRID if separates_xor(a, c, d))
and_hits = sum(1 for a in GRID for c in GRID for d in GRID if separates_and(a, c, d))
print()
print("brute force over {} candidate lines".format(len(GRID) ** 3))
print(" lines that separate AND :", and_hits)
print(" lines that separate XOR :", xor_hits)
print()
print("And searching harder would not help. Add the two middle requirements:")
print(" (w1 + b) + (w2 + b) > 0, so w1 + w2 + 2b > 0")
print("The first requirement says b < 0, so -b > 0, and therefore")
print(" w1 + w2 + b = (w1 + w2 + 2b) - b > -b > 0")
print("The fourth demanded that same quantity be negative. No line exists, for any")
print("weights, at any learning rate, after any amount of training.")
test("the XOR loss sticks at a quarter", close(history[-1], 0.25, 0.005), True)
test("nothing much happened after the first hundred epochs",
history[100] - history[-1] < 0.01, True)
test("all four outputs are a half, so the neuron is guessing",
all(close(a, 0.5, 0.002) for a in outputs), True)
test("it therefore scores two of four, the same as always saying no",
[1 if a > 0.5 else 0 for a in outputs], [0, 0, 0, 0])
test("not one of the 226981 candidate lines separates XOR", xor_hits, 0)
test("the same search finds thousands for AND, so it is not a broken test",
and_hits > 1000, True)
test("and the trained weights fail the four requirements too",
separates_xor(*params), False)What it printed, when the build ran it
XOR, eight thousand epochs, twice as long as AND needed epoch 0 loss 0.28750100 epoch 100 loss 0.25000006 epoch 1000 loss 0.25000000 epoch 4000 loss 0.25000000 epoch 8000 loss 0.25000000 w1 = 0.000000 w2 = 0.000000 b = -0.000000 outputs: 0.500000 0.500000 0.500000 0.500000 rounded: [0, 0, 0, 0] wanted [0, 1, 1, 0] The loss stops at a quarter and the weights collapse to zero. The neuron has no opinion left, which for mean squared error is the best a straight line can manage here. It is not undertrained. It is finished. brute force over 226981 candidate lines lines that separate AND : 4429 lines that separate XOR : 0 And searching harder would not help. Add the two middle requirements: (w1 + b) + (w2 + b) > 0, so w1 + w2 + 2b > 0 The first requirement says b < 0, so -b > 0, and therefore w1 + w2 + b = (w1 + w2 + 2b) - b > -b > 0 The fourth demanded that same quantity be negative. No line exists, for any weights, at any learning rate, after any amount of training. ok the XOR loss sticks at a quarter ok nothing much happened after the first hundred epochs ok all four outputs are a half, so the neuron is guessing ok it therefore scores two of four, the same as always saying no ok not one of the 226981 candidate lines separates XOR ok the same search finds thousands for AND, so it is not a broken test ok and the trained weights fail the four requirements too
This is the whole argument for layers, and it is worth being precise about what failed. Nothing was undertrained, badly initialised or unlucky. A single neuron computes one weighted sum, so the set of inputs it answers yes to is whatever lies on one side of one straight line. XOR's two yes corners sit diagonally opposite, with a no corner on either side of them. No line has that shape. The fix is not a bigger neuron or a better optimiser — it is a first layer that redraws the input into coordinates where one line is enough.
What a layer is
Less than the word suggests. A layer is a list of neurons that all read the same inputs
and each produce one number, and the list of those numbers is the layer's output. The neurons
never consult each other. Everything a framework calls a Linear or a
Dense layer is the loop below.
# A layer is a list of neurons that all read the same inputs. That is all it is.
import math
import random
def sigmoid(z):
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z)
return ez / (1.0 + ez)
def make_layer(n_in, n_out, rng):
"""n_out neurons, each with n_in weights and one bias of its own."""
weights = [[rng.uniform(-1.0, 1.0) for _ in range(n_in)] for _ in range(n_out)]
biases = [rng.uniform(-1.0, 1.0) for _ in range(n_out)]
return (weights, biases)
def layer_forward(layer, inputs, activation):
"""One dot product per neuron. The neurons never look at each other."""
weights, biases = layer
return [activation(sum(w * x for w, x in zip(row, inputs)) + b)
for row, b in zip(weights, biases)]
def count_params(layer):
weights, biases = layer
return sum(len(row) for row in weights) + len(biases)
rng = random.Random(42)
hidden = make_layer(2, 3, rng)
output = make_layer(3, 1, rng)
x = [1.0, 0.0]
h = layer_forward(hidden, x, sigmoid)
y = layer_forward(output, h, sigmoid)
print("hidden layer weights, one row per neuron")
for i, row in enumerate(hidden[0]):
print(" neuron {} w = [{: .6f}, {: .6f}] b = {: .6f}".format(
i, row[0], row[1], hidden[1][i]))
print()
print("input x =", x)
print("hidden h =", ["{:.6f}".format(v) for v in h], " <- three numbers, one per neuron")
print("output y =", ["{:.6f}".format(v) for v in y], " <- one number")
print()
print("hidden layer parameters : 3 neurons * 2 weights + 3 biases =", count_params(hidden))
print("output layer parameters : 1 neuron * 3 weights + 1 bias =", count_params(output))
print("the whole 2-3-1 network :", count_params(hidden) + count_params(output))
# The claim that a layer is only bookkeeping, checked instead of asserted in prose:
# run each neuron on its own and compare.
one_at_a_time = [sigmoid(sum(w * v for w, v in zip(row, x)) + b)
for row, b in zip(hidden[0], hidden[1])]
print()
print("the same three numbers, computed one neuron at a time:")
print(" ", ["{:.6f}".format(v) for v in one_at_a_time])
# Width is a dial, and its cost is a straight line.
print()
print(" width parameters in a layer taking 2 inputs")
widths = {}
for width in (1, 3, 8, 64, 512):
widths[width] = count_params(make_layer(2, width, random.Random(7)))
print(" {:5} {}".format(width, widths[width]))
test("a layer of three neurons returns three numbers", len(h), 3)
test("stacked on a one-neuron layer it returns one number", len(y), 1)
test("the hidden layer holds nine parameters, the whole network thirteen",
[count_params(hidden), count_params(hidden) + count_params(output)], [9, 13])
test("a layer is only bookkeeping: neuron by neuron gives the same numbers",
all(close(a, b) for a, b in zip(h, one_at_a_time)), True)
test("every sigmoid output sits between zero and one",
all(0.0 < v < 1.0 for v in h + y), True)
test("parameter count is width times inputs plus one, so it grows in a straight line",
[widths[8], widths[512], widths[512] == 64 * widths[8]], [24, 1536, True])What it printed, when the build ran it
hidden layer weights, one row per neuron
neuron 0 w = [ 0.278854, -0.949978] b = 0.784359
neuron 1 w = [-0.449941, -0.553579] b = -0.826122
neuron 2 w = [ 0.472942, 0.353399] b = -0.156156
input x = [1.0, 0.0]
hidden h = ['0.743304', '0.218221', '0.578541'] <- three numbers, one per neuron
output y = ['0.146473'] <- one number
hidden layer parameters : 3 neurons * 2 weights + 3 biases = 9
output layer parameters : 1 neuron * 3 weights + 1 bias = 4
the whole 2-3-1 network : 13
the same three numbers, computed one neuron at a time:
['0.743304', '0.218221', '0.578541']
width parameters in a layer taking 2 inputs
1 3
3 9
8 24
64 192
512 1536
ok a layer of three neurons returns three numbers
ok stacked on a one-neuron layer it returns one number
ok the hidden layer holds nine parameters, the whole network thirteen
ok a layer is only bookkeeping: neuron by neuron gives the same numbers
ok every sigmoid output sits between zero and one
ok parameter count is width times inputs plus one, so it grows in a straight line
Why the activation has to bend
Here is the trap that makes the previous panel worth reading carefully. If the activation is the identity — no bend at all — then two layers are not two layers. They are one layer written expensively, and the second one contributes nothing that the first could not have done alone. This is provable in one line of matrix algebra, and checkable in one panel.
# Why the activation has to bend. Two linear layers are one linear layer.
import math
def matvec(m, v):
return [sum(a * b for a, b in zip(row, v)) for row in m]
def matmul(a, b):
"""a is p by q, b is q by r, the answer is p by r."""
return [[sum(a[i][k] * b[k][j] for k in range(len(b))) for j in range(len(b[0]))]
for i in range(len(a))]
W1 = [[0.5, -1.0], [2.0, 0.25], [-0.75, 1.5]] # 3 neurons, 2 inputs each
B1 = [0.1, -0.2, 0.3]
W2 = [[1.0, -0.5, 2.0], [0.25, 1.0, -1.0]] # 2 neurons, 3 inputs each
B2 = [-0.4, 0.6]
def stacked(x, activation):
"""Two layers: weights, bias, activation, then weights and bias again."""
pre = [a + b for a, b in zip(matvec(W1, x), B1)]
h = [activation(v) for v in pre]
return [a + b for a, b in zip(matvec(W2, h), B2)]
def identity(z):
return z
# With the identity in the middle, the two layers collapse. By hand:
# layer 2 (layer 1 (x)) = W2 (W1 x + b1) + b2 = (W2 W1) x + (W2 b1 + b2)
W = matmul(W2, W1) # a single 2 by 2 matrix
B = [a + b for a, b in zip(matvec(W2, B1), B2)] # a single bias of length 2
def collapsed(x):
return [a + b for a, b in zip(matvec(W, x), B)]
print("the stack: 2 inputs -> 3 -> 2, with no activation")
print("W2 @ W1 =", [["{: .4f}".format(v) for v in row] for row in W])
print("W2 @ b1 + b2 =", ["{: .4f}".format(v) for v in B])
print()
print(" input two linear layers one linear layer")
inputs = [[1.0, 0.0], [0.0, 1.0], [2.0, -3.0], [-0.7, 0.4], [11.0, 5.0]]
agreements = []
for x in inputs:
a = stacked(x, identity)
b = collapsed(x)
agreements.append(all(close(p, q) for p, q in zip(a, b)))
print(" {:>12} [{: 10.6f}, {: 10.6f}] [{: 10.6f}, {: 10.6f}]".format(
str(x), a[0], a[1], b[0], b[1]))
print()
print("stack parameters : 3*2 + 3 + 2*3 + 2 =", 3 * 2 + 3 + 2 * 3 + 2)
print("collapsed parameters : 2*2 + 2 =", 2 * 2 + 2)
print("Eleven of the seventeen bought nothing whatsoever.")
# An affine map sends the midpoint of two inputs to the midpoint of their outputs.
# That is a complete test for "is this secretly just one matrix and one bias".
p = [1.5, -0.5]
q = [-2.0, 3.0]
mid = [(a + b) / 2.0 for a, b in zip(p, q)]
def midpoint_holds(activation):
fp = stacked(p, activation)
fq = stacked(q, activation)
fmid = stacked(mid, activation)
return all(close(m, (a + b) / 2.0) for m, a, b in zip(fmid, fp, fq))
lin_mid = stacked(mid, identity)
tanh_mid = stacked(mid, math.tanh)
print()
print("midpoint test, no activation :", midpoint_holds(identity))
print("midpoint test, tanh :", midpoint_holds(math.tanh))
print()
print("f(midpoint) with no activation: [{: .6f}, {: .6f}]".format(*lin_mid))
print("f(midpoint) with tanh : [{: .6f}, {: .6f}]".format(*tanh_mid))
print()
print("So depth on its own buys nothing. The activation is not a finishing touch")
print("applied to a layer, it is the only reason the second layer exists.")
test("two linear layers agree with one linear layer on every input", agreements, [True] * 5)
test("seventeen parameters did the work of six",
[3 * 2 + 3 + 2 * 3 + 2, 2 * 2 + 2], [17, 6])
test("the collapsed matrix is exactly W2 times W1",
[close(W[0][0], 1.0 * 0.5 + -0.5 * 2.0 + 2.0 * -0.75),
close(W[1][1], 0.25 * -1.0 + 1.0 * 0.25 + -1.0 * 1.5)], [True, True])
test("a linear stack sends midpoints to midpoints, as any affine map must",
midpoint_holds(identity), True)
test("with tanh in the middle it does not, so it is no longer one matrix",
midpoint_holds(math.tanh), False)
test("and the two networks really do disagree on that midpoint",
close(lin_mid[0], tanh_mid[0], 0.01), False)What it printed, when the build ran it
the stack: 2 inputs -> 3 -> 2, with no activation
W2 @ W1 = [['-2.0000', ' 1.8750'], [' 2.8750', '-1.5000']]
W2 @ b1 + b2 = [' 0.4000', ' 0.1250']
input two linear layers one linear layer
[1.0, 0.0] [ -1.600000, 3.000000] [ -1.600000, 3.000000]
[0.0, 1.0] [ 2.275000, -1.375000] [ 2.275000, -1.375000]
[2.0, -3.0] [ -9.225000, 10.375000] [ -9.225000, 10.375000]
[-0.7, 0.4] [ 2.550000, -2.487500] [ 2.550000, -2.487500]
[11.0, 5.0] [-12.225000, 24.250000] [-12.225000, 24.250000]
stack parameters : 3*2 + 3 + 2*3 + 2 = 17
collapsed parameters : 2*2 + 2 = 6
Eleven of the seventeen bought nothing whatsoever.
midpoint test, no activation : True
midpoint test, tanh : False
f(midpoint) with no activation: [ 3.243750, -2.468750]
f(midpoint) with tanh : [ 0.894284, -0.965404]
So depth on its own buys nothing. The activation is not a finishing touch
applied to a layer, it is the only reason the second layer exists.
ok two linear layers agree with one linear layer on every input
ok seventeen parameters did the work of six
ok the collapsed matrix is exactly W2 times W1
ok a linear stack sends midpoints to midpoints, as any affine map must
ok with tanh in the middle it does not, so it is no longer one matrix
ok and the two networks really do disagree on that midpoint
This is a bug people ship. Build a model, forget the activation between two
Linear layers, and nothing raises: the shapes are fine, the loss falls, the
thing trains. It just trains to the accuracy of a linear model no matter how many layers
you add, and the parameter count in the summary looks impressively unrelated to that. If a
deep model performs suspiciously like linear regression, count the non-linearities before
you touch anything else.
The same three ideas, in a framework
Every line above has a one-line equivalent. Worth seeing side by side, so the framework reads as shorthand for something you have already written rather than as machinery you have to trust.
# A neuron, a layer, and the missing activation - in torch.
# NOT RUN HERE - torch is not installed in this environment.
import torch
import torch.nn as nn
# nn.Linear(2, 3) IS make_layer(2, 3): a 3 by 2 weight matrix and 3 biases.
layer = nn.Linear(2, 3)
print(layer.weight.shape, layer.bias.shape) # torch.Size([3, 2]) torch.Size([3])
print(sum(p.numel() for p in layer.parameters())) # 9, the same nine
x = torch.tensor([1.0, 0.0])
layer(x) # layer_forward, with no activation
torch.sigmoid(x) # the same three functions
torch.tanh(x)
torch.relu(x)
# The single neuron that failed XOR. It fails here too, for the same reason.
one_neuron = nn.Sequential(nn.Linear(2, 1), nn.Sigmoid())
# The network lesson 15 trains. Take out the nn.Tanh() and the two Linear layers
# collapse into one, exactly as the panel above proved - and nothing will warn you.
net = nn.Sequential(
nn.Linear(2, 4),
nn.Tanh(),
nn.Linear(4, 1),
nn.Sigmoid(),
)
print(sum(p.numel() for p in net.parameters())) # 4*2 + 4 + 1*4 + 1 = 17
# Initialisation is seeded the same way, and for the same reason lesson 15 gives.
torch.manual_seed(42)torch is not installed in this environment, so this panel was never executed and its printed comments are expectations, not captured output. Every construct in it has a plain-Python counterpart above that did run and did assert: nn.Linear is make_layer, calling a layer is layer_forward, and the collapse warning is the panel that proved it.
Where this leaves you. A neuron is a dot product, a bias and a bend. A layer is a list of neurons, and its parameter count is width times inputs plus width. One neuron draws one straight line, which is enough for AND and OR and provably not enough for XOR. Depth fixes that only if something non-linear sits between the layers, or the whole stack folds back into a single matrix. What is still missing is how to compute the gradient once there is a hidden layer in the way, because the chain rule now has to run backwards through the network. That is the next lesson, worked through by hand.
14 Backpropagation, worked through by hand
Backpropagation is the chain rule run backwards through a network, reusing every number the forward pass already produced. There is no second idea in it. What makes it worth a lesson is that doing it by hand once, on a network you can see all of, permanently removes the mystery from every autodiff library you will ever use — and teaches you how to check that a gradient is right.
The chain rule, on a chain
If y depends on v, which depends on u, which
depends on x, then the slope from x to y is the
product of the three local slopes. Compute the values forwards, keep them, then multiply the
derivatives backwards.
# The chain rule, on a chain short enough to see all of at once.
import math
def square(t):
return t * t
def d_square(t):
return 2.0 * t
def tanh_(t):
return math.tanh(t)
def d_tanh(t):
return 1.0 - math.tanh(t) ** 2
def triple_plus_one(t):
return 3.0 * t + 1.0
def d_triple_plus_one(t):
return 3.0
X = 0.4
# Forward: each step keeps the number it produced, because the backward pass needs it.
u = triple_plus_one(X)
v = tanh_(u)
y = square(v)
print("forward, one step at a time")
print(" x = {:.10f}".format(X))
print(" u = 3x + 1 = {:.10f}".format(u))
print(" v = tanh(u) = {:.10f}".format(v))
print(" y = v * v = {:.10f}".format(y))
# Backward: start with dy/dy = 1 and multiply by one local derivative per step.
g_y = 1.0
g_v = g_y * d_square(v)
g_u = g_v * d_tanh(u)
g_x = g_u * d_triple_plus_one(X)
print()
print("backward, one local derivative per step")
print(" dy/dy = {:.10f}".format(g_y))
print(" dy/dv = 2v = {:.10f}".format(g_v))
print(" dy/du = dy/dv * (1 - tanh(u)^2) = {:.10f}".format(g_u))
print(" dy/dx = dy/du * 3 = {:.10f}".format(g_x))
# The same number, the long way: multiply the three local derivatives together.
product = d_square(v) * d_tanh(u) * d_triple_plus_one(X)
def whole(x):
return square(tanh_(triple_plus_one(x)))
numeric = (whole(X + 1e-5) - whole(X - 1e-5)) / 2e-5
print()
print("2v * (1 - tanh(u)^2) * 3 = {:.10f}".format(product))
print("central difference on the whole = {:.10f}".format(numeric))
print()
print("Backpropagation is that backward column, run on a network instead of a chain.")
print("Nothing in it is cleverer than 'multiply by the local derivative'.")
test("the forward pass ends just short of one", close(y, 0.95207466, 1e-6), True)
test("the backward pass gives dy/dx = 0.2806", close(g_x, 0.28057695, 1e-6), True)
test("going backwards step by step equals multiplying the three local derivatives",
close(g_x, product), True)
test("and it agrees with a central difference on the whole composition",
close(g_x, numeric, 1e-6), True)
test("the backward pass reused u and v, so it needed no new forward work",
[close(g_v, 2.0 * v), close(g_u, g_v * (1.0 - v * v))], [True, True])What it printed, when the build ran it
forward, one step at a time x = 0.4000000000 u = 3x + 1 = 2.2000000000 v = tanh(u) = 0.9757431300 y = v * v = 0.9520746558 backward, one local derivative per step dy/dy = 1.0000000000 dy/dv = 2v = 1.9514862601 dy/du = dy/dv * (1 - tanh(u)^2) = 0.0935256507 dy/dx = dy/du * 3 = 0.2805769521 2v * (1 - tanh(u)^2) * 3 = 0.2805769521 central difference on the whole = 0.2805769523 Backpropagation is that backward column, run on a network instead of a chain. Nothing in it is cleverer than 'multiply by the local derivative'. ok the forward pass ends just short of one ok the backward pass gives dy/dx = 0.2806 ok going backwards step by step equals multiplying the three local derivatives ok and it agrees with a central difference on the whole composition ok the backward pass reused u and v, so it needed no new forward work
Two habits in that panel are the whole algorithm. The forward pass keeps
u and v instead of throwing them away, and the backward pass
starts from dy/dy = 1 and multiplies by exactly one local derivative per step.
Every framework's .backward() is those two habits applied to a graph rather
than a line. The stored values even have a name — the activations — and the reason a big
model runs out of memory during training and not during inference is that training has to
keep all of them.
The forward pass, with nothing thrown away
Lesson 13's 2-2-1 network: two inputs, two hidden units with tanh, one
sigmoid output, squared error. Nine parameters, chosen by hand so you can check the
arithmetic yourself. Every intermediate value is returned rather than discarded.
# The forward pass of a 2-2-1 network, with every intermediate value kept.
import math
def sigmoid(z):
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z)
return ez / (1.0 + ez)
# Nine parameters, chosen by hand so the arithmetic is checkable on paper.
W1 = [[0.50, -0.50], # hidden neuron 0 reads x0 and x1
[0.25, 0.75]] # hidden neuron 1 reads the same two
B1 = [0.10, -0.20]
W2 = [1.50, -1.00] # the output neuron reads both hidden units
B2 = 0.30
X = [1.0, 2.0]
Y = 1.0 # what we wanted the network to say
def forward(W1, B1, W2, B2, x, y):
"""Every intermediate value, returned. The backward pass needs all of them."""
z1 = [W1[j][0] * x[0] + W1[j][1] * x[1] + B1[j] for j in (0, 1)]
h = [math.tanh(v) for v in z1]
z2 = W2[0] * h[0] + W2[1] * h[1] + B2
a = sigmoid(z2)
loss = (a - y) ** 2
return {"z1": z1, "h": h, "z2": z2, "a": a, "loss": loss}
f = forward(W1, B1, W2, B2, X, Y)
print("input x = {} target y = {}".format(X, Y))
print()
print("z1[0] = 0.50*1 + -0.50*2 + 0.10 = {: .10f}".format(f["z1"][0]))
print("z1[1] = 0.25*1 + 0.75*2 + -0.20 = {: .10f}".format(f["z1"][1]))
print("h[0] = tanh(z1[0]) = {: .10f}".format(f["h"][0]))
print("h[1] = tanh(z1[1]) = {: .10f}".format(f["h"][1]))
print("z2 = 1.50*h[0] + -1.00*h[1] + 0.30 = {: .10f}".format(f["z2"]))
print("a = sigmoid(z2) = {: .10f}".format(f["a"]))
print("loss = (a - y)^2 = {: .10f}".format(f["loss"]))
print()
print("parameters: 2*2 weights + 2 biases + 2 weights + 1 bias =", 4 + 2 + 2 + 1)
print()
print("Six numbers came out of that pass and every one of them is needed again on the")
print("way back. Keeping them is not an optimisation, it is what makes backprop cheap.")
test("the first hidden pre-activation is minus four tenths", close(f["z1"][0], -0.4), True)
test("the second is one and fifty five hundredths", close(f["z1"][1], 1.55), True)
test("tanh squashed both into minus one to one",
all(-1.0 < v < 1.0 for v in f["h"]), True)
test("the output pre-activation is negative, so the network says probably not",
[f["z2"] < 0.0, f["a"] < 0.5], [True, True])
test("the output lands at 0.2344", close(f["a"], 0.23438598, 1e-6), True)
test("the loss is the squared gap to the target we wanted",
close(f["loss"], (f["a"] - 1.0) ** 2), True)
test("the network has nine parameters in total", 4 + 2 + 2 + 1, 9)What it printed, when the build ran it
input x = [1.0, 2.0] target y = 1.0 z1[0] = 0.50*1 + -0.50*2 + 0.10 = -0.4000000000 z1[1] = 0.25*1 + 0.75*2 + -0.20 = 1.5500000000 h[0] = tanh(z1[0]) = -0.3799489623 h[1] = tanh(z1[1]) = 0.9137854901 z2 = 1.50*h[0] + -1.00*h[1] + 0.30 = -1.1837089335 a = sigmoid(z2) = 0.2343859756 loss = (a - y)^2 = 0.5861648344 parameters: 2*2 weights + 2 biases + 2 weights + 1 bias = 9 Six numbers came out of that pass and every one of them is needed again on the way back. Keeping them is not an optimisation, it is what makes backprop cheap. ok the first hidden pre-activation is minus four tenths ok the second is one and fifty five hundredths ok tanh squashed both into minus one to one ok the output pre-activation is negative, so the network says probably not ok the output lands at 0.2344 ok the loss is the squared gap to the target we wanted ok the network has nine parameters in total
The backward pass, gradient by gradient
Now the same numbers in reverse. Read the panel below from the top of its output downwards: each line is the line above it multiplied by one local derivative. Then every one of the nine gradients is checked by nudging that parameter and watching the loss — lesson 7's gradient check, applied to a network.
# The backward pass, every gradient printed, then checked against a nudge.
import math
def sigmoid(z):
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z)
return ez / (1.0 + ez)
W1 = [[0.50, -0.50], [0.25, 0.75]]
B1 = [0.10, -0.20]
W2 = [1.50, -1.00]
B2 = 0.30
X = [1.0, 2.0]
Y = 1.0
def forward(p, x, y):
w1, b1, w2, b2 = p
z1 = [w1[j][0] * x[0] + w1[j][1] * x[1] + b1[j] for j in (0, 1)]
h = [math.tanh(v) for v in z1]
z2 = w2[0] * h[0] + w2[1] * h[1] + b2
a = sigmoid(z2)
return z1, h, z2, a, (a - y) ** 2
def loss_only(p):
return forward(p, X, Y)[4]
def backward(p, x, y):
"""The chain rule, right to left. Each line is one local derivative times what
already came back from the layer above it."""
w1, b1, w2, b2 = p
z1, h, z2, a, loss = forward(p, x, y)
g_a = 2.0 * (a - y) # d loss / d a
g_z2 = g_a * a * (1.0 - a) # through the sigmoid
g_w2 = [g_z2 * h[0], g_z2 * h[1]] # d z2 / d w2[j] is h[j]
g_b2 = g_z2 # d z2 / d b2 is 1
g_h = [g_z2 * w2[0], g_z2 * w2[1]] # d z2 / d h[j] is w2[j]
g_z1 = [g_h[j] * (1.0 - h[j] ** 2) for j in (0, 1)] # through tanh
g_w1 = [[g_z1[j] * x[0], g_z1[j] * x[1]] for j in (0, 1)]
g_b1 = [g_z1[0], g_z1[1]]
return {"a": g_a, "z2": g_z2, "w2": g_w2, "b2": g_b2,
"h": g_h, "z1": g_z1, "w1": g_w1, "b1": g_b1, "loss": loss}
P = (W1, B1, W2, B2)
g = backward(P, X, Y)
print("loss {:.10f}, and now backwards from it".format(g["loss"]))
print()
print("d loss / d a = 2(a - y) = {: .10f}".format(g["a"]))
print("d loss / d z2 = above * a(1 - a) = {: .10f}".format(g["z2"]))
print("d loss / d w2[0] = above * h[0] = {: .10f}".format(g["w2"][0]))
print("d loss / d w2[1] = above * h[1] = {: .10f}".format(g["w2"][1]))
print("d loss / d b2 = above * 1 = {: .10f}".format(g["b2"]))
print("d loss / d h[0] = d/dz2 * w2[0] = {: .10f}".format(g["h"][0]))
print("d loss / d h[1] = d/dz2 * w2[1] = {: .10f}".format(g["h"][1]))
print("d loss / d z1[0] = above * (1 - h[0]^2) = {: .10f}".format(g["z1"][0]))
print("d loss / d z1[1] = above * (1 - h[1]^2) = {: .10f}".format(g["z1"][1]))
print("d loss / d W1[0] = [dz1[0]*x0, dz1[0]*x1] = [{: .8f}, {: .8f}]".format(*g["w1"][0]))
print("d loss / d W1[1] = [dz1[1]*x0, dz1[1]*x1] = [{: .8f}, {: .8f}]".format(*g["w1"][1]))
print("d loss / d b1 = [dz1[0], dz1[1]] = [{: .8f}, {: .8f}]".format(*g["b1"]))
# ---- gradient checking, exactly as lesson 7 did it, for all nine parameters ----
def nudged(index, delta):
"""A fresh copy of the parameters with parameter number index moved by delta."""
w1 = [row[:] for row in W1]
b1 = B1[:]
w2 = W2[:]
b2 = B2
if index < 4:
w1[index // 2][index % 2] += delta
elif index < 6:
b1[index - 4] += delta
elif index < 8:
w2[index - 6] += delta
else:
b2 += delta
return (w1, b1, w2, b2)
NAMES = ["W1[0][0]", "W1[0][1]", "W1[1][0]", "W1[1][1]",
"b1[0]", "b1[1]", "W2[0]", "W2[1]", "b2"]
ANALYTIC = [g["w1"][0][0], g["w1"][0][1], g["w1"][1][0], g["w1"][1][1],
g["b1"][0], g["b1"][1], g["w2"][0], g["w2"][1], g["b2"]]
H = 1e-5
print()
print(" parameter backprop nudge the parameter difference")
gaps = []
for i, name in enumerate(NAMES):
numeric = (loss_only(nudged(i, H)) - loss_only(nudged(i, -H))) / (2.0 * H)
gaps.append(abs(numeric - ANALYTIC[i]))
print(" {:9} {: .12f} {: .12f} {:.2e}".format(
name, ANALYTIC[i], numeric, gaps[-1]))
worst = max(gaps)
print()
print("worst disagreement anywhere in the network: {:.2e}".format(worst))
step = 0.5
stepped = (
[[W1[j][i] - step * g["w1"][j][i] for i in (0, 1)] for j in (0, 1)],
[B1[j] - step * g["b1"][j] for j in (0, 1)],
[W2[j] - step * g["w2"][j] for j in (0, 1)],
B2 - step * g["b2"],
)
after = loss_only(stepped)
print("loss before one step against the gradient: {:.10f}".format(g["loss"]))
print("loss after : {:.10f}".format(after))
test("every one of the nine analytic gradients matches a nudge",
all(gap < 1e-6 for gap in gaps), True)
test("the worst disagreement in the whole network is under a millionth",
worst < 1e-6, True)
test("the bias gradient is exactly the pre-activation gradient it sits on",
[close(g["b2"], g["z2"]), close(g["b1"][0], g["z1"][0])], [True, True])
test("a weight gradient is the incoming activation times the outgoing gradient",
close(g["w2"][0], g["z2"] * math.tanh(-0.4)), True)
test("the two hidden gradients have opposite signs, because W2 does",
[g["h"][0] < 0.0, g["h"][1] > 0.0], [True, True])
test("W1[0][1] gets twice the gradient of W1[0][0], because x1 is twice x0",
close(g["w1"][0][1], 2.0 * g["w1"][0][0]), True)
test("one step against the gradient lowers the loss", after < g["loss"], True)What it printed, when the build ran it
loss 0.5861648344, and now backwards from it d loss / d a = 2(a - y) = -1.5312280489 d loss / d z2 = above * a(1 - a) = -0.2747776331 d loss / d w2[0] = above * h[0] = 0.1044014766 d loss / d w2[1] = above * h[1] = -0.2510878141 d loss / d b2 = above * 1 = -0.2747776331 d loss / d h[0] = d/dz2 * w2[0] = -0.4121664497 d loss / d h[1] = d/dz2 * w2[1] = 0.2747776331 d loss / d z1[0] = above * (1 - h[0]^2) = -0.3526656007 d loss / d z1[1] = above * (1 - h[1]^2) = 0.0453372318 d loss / d W1[0] = [dz1[0]*x0, dz1[0]*x1] = [-0.35266560, -0.70533120] d loss / d W1[1] = [dz1[1]*x0, dz1[1]*x1] = [ 0.04533723, 0.09067446] d loss / d b1 = [dz1[0], dz1[1]] = [-0.35266560, 0.04533723] parameter backprop nudge the parameter difference W1[0][0] -0.352665600655 -0.352665600650 4.81e-12 W1[0][1] -0.705331201310 -0.705331201262 4.85e-11 W1[1][0] 0.045337231799 0.045337231791 8.08e-12 W1[1][1] 0.090674463598 0.090674463626 2.82e-11 b1[0] -0.352665600655 -0.352665600645 1.04e-11 b1[1] 0.045337231799 0.045337231791 8.08e-12 W2[0] 0.104401476551 0.104401476558 7.13e-12 W2[1] -0.251087814145 -0.251087814129 1.58e-11 b2 -0.274777633110 -0.274777633114 3.30e-12 worst disagreement anywhere in the network: 4.85e-11 loss before one step against the gradient: 0.5861648344 loss after : 0.1432483369 ok every one of the nine analytic gradients matches a nudge ok the worst disagreement in the whole network is under a millionth ok the bias gradient is exactly the pre-activation gradient it sits on ok a weight gradient is the incoming activation times the outgoing gradient ok the two hidden gradients have opposite signs, because W2 does ok W1[0][1] gets twice the gradient of W1[0][0], because x1 is twice x0 ok one step against the gradient lowers the loss
Three patterns in that output are worth memorising, because they hold for every layer of every network you will ever write:
- a bias gradient is the pre-activation gradient, unchanged, because
d z / d bis 1; - a weight gradient is the incoming activation times the outgoing gradient
— so
d loss / d W2[0]ish[0]times what came back throughz2; - the gradient sent back to an input is the weight times the outgoing gradient, which is how the signal reaches the layer below.
Run the gradient check on any backward pass you write yourself, once, before you trust
it. A gradient with a sign error or a missing term does not raise, does not produce
nan, and does not obviously fail — the loss still falls, because a wrong
direction that happens to be within ninety degrees of the right one still goes downhill.
You get a model that trains to a mediocre score and no clue why. The check is the nine
lines above and it is the cheapest hour you will ever spend.
Why one backward pass costs about one forward pass
Lesson 7 priced the alternative: two forward passes per parameter, every step. This panel counts the multiplications in both directions so the comparison is measured rather than claimed.
# Why one backward pass is affordable and 2P forward passes are not. Counted.
import math
MULS = {"forward": 0, "backward": 0}
def fmul(a, b):
MULS["forward"] += 1
return a * b
def bmul(a, b):
MULS["backward"] += 1
return a * b
W1 = [[0.50, -0.50], [0.25, 0.75]]
B1 = [0.10, -0.20]
W2 = [1.50, -1.00]
B2 = 0.30
X = [1.0, 2.0]
Y = 1.0
PARAMS = 9
def forward():
z1 = [fmul(W1[j][0], X[0]) + fmul(W1[j][1], X[1]) + B1[j] for j in (0, 1)]
h = [math.tanh(v) for v in z1]
z2 = fmul(W2[0], h[0]) + fmul(W2[1], h[1]) + B2
a = 1.0 / (1.0 + math.exp(-z2))
return z1, h, z2, a, fmul(a - Y, a - Y)
def backward():
z1, h, z2, a, loss = forward()
g_z2 = bmul(bmul(2.0, a - Y), bmul(a, 1.0 - a))
g_w2 = [bmul(g_z2, h[0]), bmul(g_z2, h[1])]
g_h = [bmul(g_z2, W2[0]), bmul(g_z2, W2[1])]
g_z1 = [bmul(g_h[j], 1.0 - bmul(h[j], h[j])) for j in (0, 1)]
g_w1 = [[bmul(g_z1[j], X[0]), bmul(g_z1[j], X[1])] for j in (0, 1)]
return g_w1, g_z1, g_w2, g_z2
forward()
forward_muls = MULS["forward"]
MULS["forward"] = 0
MULS["backward"] = 0
backward()
one_pass_forward = MULS["forward"]
one_pass_backward = MULS["backward"]
print("one forward pass : {} multiplications".format(forward_muls))
print("backprop = one forward + one backward: {} + {} = {}".format(
one_pass_forward, one_pass_backward, one_pass_forward + one_pass_backward))
print()
print("The backward column has one multiplication per multiplication on the way in,")
print("plus one more to turn each into a weight gradient. That is a small constant")
print("factor - never the parameter count.")
# The alternative, priced. Two forward passes per parameter, every time.
numeric_passes = 2 * PARAMS
print()
print("numerical gradient of {} parameters : {} forward passes".format(PARAMS, numeric_passes))
print("backprop : 1 forward, 1 backward")
def count(sizes):
"""Parameters in a fully connected stack, e.g. (2, 64, 64, 1)."""
return sum(sizes[i] * sizes[i + 1] + sizes[i + 1] for i in range(len(sizes) - 1))
SHAPES = ((2, 2, 1), (2, 64, 64, 1), (784, 256, 128, 10), (4096, 4096, 4096, 4096))
print()
print(" network shape parameters forward passes a numerical")
print(" gradient would need")
rows = {}
for shape in SHAPES:
p = count(shape)
rows[shape] = p
print(" {:24} {:11,} {:20,}".format(str(shape), p, 2 * p))
big = 175000000000 # roughly GPT-3
print()
print("At {:,} parameters the numerical gradient needs {:,} forward".format(big, 2 * big))
print("passes for one training step. Backprop needs one of each, and there are")
print("hundreds of thousands of steps in a training run.")
test("the forward pass does one multiplication per weight, plus one for the loss",
forward_muls, 7)
test("the backward pass is a small constant multiple of the forward one",
one_pass_backward < 4 * one_pass_forward, True)
test("that multiple does not depend on the parameter count, which is the whole point",
one_pass_backward / float(one_pass_forward) < 4.0, True)
test("a numerical gradient of nine parameters costs eighteen forward passes",
numeric_passes, 18)
test("a 2-64-64-1 network has 4417 parameters and would cost 8834 of them",
[rows[(2, 64, 64, 1)], 2 * rows[(2, 64, 64, 1)]], [4417, 8834])
test("the gap grows exactly in step with the model, so it never gets better",
2 * rows[(4096, 4096, 4096, 4096)] > 100000000, True)What it printed, when the build ran it
one forward pass : 7 multiplications
backprop = one forward + one backward: 7 + 15 = 22
The backward column has one multiplication per multiplication on the way in,
plus one more to turn each into a weight gradient. That is a small constant
factor - never the parameter count.
numerical gradient of 9 parameters : 18 forward passes
backprop : 1 forward, 1 backward
network shape parameters forward passes a numerical
gradient would need
(2, 2, 1) 9 18
(2, 64, 64, 1) 4,417 8,834
(784, 256, 128, 10) 235,146 470,292
(4096, 4096, 4096, 4096) 50,343,936 100,687,872
At 175,000,000,000 parameters the numerical gradient needs 350,000,000,000 forward
passes for one training step. Backprop needs one of each, and there are
hundreds of thousands of steps in a training run.
ok the forward pass does one multiplication per weight, plus one for the loss
ok the backward pass is a small constant multiple of the forward one
ok that multiple does not depend on the parameter count, which is the whole point
ok a numerical gradient of nine parameters costs eighteen forward passes
ok a 2-64-64-1 network has 4417 parameters and would cost 8834 of them
ok the gap grows exactly in step with the model, so it never gets better
The reason is worth stating plainly, because it is the one interview answer people fumble. A numerical gradient asks one question per parameter — what happens to the loss if I move this one? — and each question needs its own forward pass. Backpropagation asks the question once, from the other end: it starts at the loss and pushes a single gradient backwards, and every parameter picks up its own answer as that gradient passes through the layer it lives in. One traversal, all P answers. That is what reverse mode means, and it is the only reason a model with billions of parameters can be trained at all.
The cost that does grow is memory, not arithmetic. The backward pass needs the
activations the forward pass stored, so training holds every intermediate value for every
item in the batch, while inference can throw each one away as soon as the next layer has
read it. That is why a model you can happily run for inference will not train on the same
card, and why torch.no_grad() around an evaluation loop is not a
micro-optimisation — it stops the graph being built at all. Gradient checkpointing trades
this back the other way: store fewer activations, recompute them during the backward pass,
pay roughly 30% more time for a large drop in memory.
The same thing, with autodiff doing the bookkeeping
A framework does not know anything the panels above do not. It records the operations as
you perform them, and when you call .backward() it walks that recording in
reverse applying the same local derivatives. The value it adds is that you no longer maintain
the backward pass by hand when the architecture changes.
# The same 2-2-1 network, with autograd keeping the backward pass for you.
# NOT RUN HERE - torch is not installed in this environment.
import torch
W1 = torch.tensor([[0.50, -0.50], [0.25, 0.75]], requires_grad=True)
b1 = torch.tensor([0.10, -0.20], requires_grad=True)
W2 = torch.tensor([1.50, -1.00], requires_grad=True)
b2 = torch.tensor(0.30, requires_grad=True)
x = torch.tensor([1.0, 2.0])
y = torch.tensor(1.0)
z1 = W1 @ x + b1 # the same z1 as the forward panel
h = torch.tanh(z1) # the same h
z2 = W2 @ h + b2 # the same z2
a = torch.sigmoid(z2)
loss = (a - y) ** 2
loss.backward() # the whole of the backward panel, in one call
print(W1.grad) # [[-0.3527, -0.7053], [ 0.0453, 0.0907]]
print(b1.grad) # [-0.3527, 0.0453]
print(W2.grad) # [ 0.1044, -0.2511]
print(b2.grad) # -0.2748
# Two things the panels above make obvious and the API hides:
#
# .grad ACCUMULATES. Call backward() twice without optimiser.zero_grad() and you
# get the sum of two gradients, which trains a model to nothing in particular.
#
# The graph is the stored activations. torch.no_grad() during evaluation stops it
# being recorded, which is the memory point in the callout above.
torch.autograd.gradcheck(
lambda w: ((torch.sigmoid(W2 @ torch.tanh(w @ x + b1) + b2) - y) ** 2),
(W1.double(),),
) # the nine-line nudge check, packagedtorch is not installed in this environment, so this panel was never executed and the gradients in its comments are the ones the plain-Python panel above printed, not captured output. Every derivative torch would compute here was written out and checked against a numerical nudge above.
Where this leaves you. Backpropagation is: run forwards keeping every intermediate value, start at the loss with a gradient of 1, and walk back multiplying by one local derivative at a time. A bias gradient is what arrives; a weight gradient is what arrives times what went in; and what gets passed further back is what arrives times the weight. One backward pass produces every partial derivative for a small constant multiple of one forward pass, which is why the numerical version in lesson 7 is a debugging tool and never a training method. The next lesson takes this loop and puts it to work on the problem lesson 13 proved a single neuron cannot solve.
15 A network that learns something
Everything needed is now on the table: a layer from lesson 13, a gradient from lesson 14, a loop from lesson 7. Put them together and the problem that defeated a single neuron takes a few hundred epochs. The interesting part of this lesson is not that it works — it is the two ways it silently does not.
XOR, this time with a hidden layer
Two inputs, four hidden units with tanh, one sigmoid output. Seventeen
parameters against the three that failed. The backward pass is lesson 14's three rules
written as a loop over layers instead of by hand, so it works for any depth.
# A 2-4-1 network learning XOR, which lesson 13 proved one neuron cannot.
import math
import random
def sigmoid(z):
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z)
return ez / (1.0 + ez)
ROWS = [([0.0, 0.0], [0.0]),
([0.0, 1.0], [1.0]),
([1.0, 0.0], [1.0]),
([1.0, 1.0], [0.0])]
def make_net(sizes, rng, scale=1.0):
"""One [weights, biases] pair per layer. Seeded, so this page is reproducible."""
net = []
for n_in, n_out in zip(sizes, sizes[1:]):
weights = [[rng.uniform(-scale, scale) for _ in range(n_in)] for _ in range(n_out)]
biases = [rng.uniform(-scale, scale) for _ in range(n_out)]
net.append([weights, biases])
return net
def forward(net, x):
"""Every layer's activations, kept, because the backward pass needs them."""
acts = [x]
for index, layer in enumerate(net):
weights, biases = layer
z = [sum(w * v for w, v in zip(row, acts[-1])) + b for row, b in zip(weights, biases)]
last = index == len(net) - 1
acts.append([sigmoid(v) for v in z] if last else [math.tanh(v) for v in z])
return acts
def backward(net, acts, y):
"""Lesson 14's three rules, in a loop over layers instead of written out."""
grads = [None] * len(net)
out = acts[-1]
delta = [2.0 * (out[k] - y[k]) * out[k] * (1.0 - out[k]) for k in range(len(out))]
for index in range(len(net) - 1, -1, -1):
weights, biases = net[index]
prev = acts[index]
grads[index] = [[[d * p for p in prev] for d in delta], delta[:]]
if index > 0:
back = [sum(weights[j][i] * delta[j] for j in range(len(delta)))
for i in range(len(prev))]
delta = [back[i] * (1.0 - prev[i] ** 2) for i in range(len(prev))]
return grads
def loss(net, rows):
total = 0.0
for x, y in rows:
out = forward(net, x)[-1]
total += sum((out[k] - y[k]) ** 2 for k in range(len(y)))
return total / len(rows)
def train(net, rows, lr, epochs):
history = [loss(net, rows)]
n = float(len(rows))
for _ in range(epochs):
totals = [[[[0.0] * len(row) for row in layer[0]], [0.0] * len(layer[1])]
for layer in net]
for x, y in rows:
grads = backward(net, forward(net, x), y)
for layer_total, layer_grad in zip(totals, grads):
for j in range(len(layer_grad[1])):
for i in range(len(layer_grad[0][j])):
layer_total[0][j][i] += layer_grad[0][j][i] / n
layer_total[1][j] += layer_grad[1][j] / n
for layer, total in zip(net, totals):
for j in range(len(layer[1])):
for i in range(len(layer[0][j])):
layer[0][j][i] -= lr * total[0][j][i]
layer[1][j] -= lr * total[1][j]
history.append(loss(net, rows))
return history
rng = random.Random(42)
net = make_net([2, 4, 1], rng)
history = train(net, ROWS, lr=2.0, epochs=4000)
outputs = [forward(net, x)[-1][0] for x, _ in ROWS]
rounded = [1 if v > 0.5 else 0 for v in outputs]
print("a 2-4-1 network on XOR, learning rate 2.0")
for epoch in (0, 100, 500, 1000, 2000, 4000):
print(" epoch {:5} loss {:.10f}".format(epoch, history[epoch]))
print()
print(" inputs wanted got")
for (x, y), out in zip(ROWS, outputs):
print(" {} {:.0f} {:.6f}".format(x, y[0], out))
print()
print(" rounded:", rounded, " wanted [0, 1, 1, 0]")
print()
hidden = forward(net, [1.0, 1.0])[1]
print("the four hidden units on input [1, 1]:", ["{: .4f}".format(v) for v in hidden])
print("Each one draws its own line. The output neuron then draws one more line")
print("through the space those four created, and in there XOR is separable.")
params = sum(len(row) for layer in net for row in layer[0]) + sum(len(layer[1]) for layer in net)
test("the network gets all four XOR rows right", rounded, [0, 1, 1, 0])
test("the loss fell below a thousandth", history[-1] < 0.001, True)
test("it started above a fifth and finished four orders of magnitude lower",
[history[0] > 0.2, history[-1] < history[0] / 1000.0], [True, True])
test("the loss never went up, over four thousand epochs",
all(history[i + 1] <= history[i] + 1e-12 for i in range(len(history) - 1)), True)
test("seventeen parameters did what three could not", params, 17)
test("the two ones and the two zeros end up far apart, not near the halfway line",
[outputs[0] < 0.05, outputs[1] > 0.95, outputs[2] > 0.95, outputs[3] < 0.05],
[True, True, True, True])What it printed, when the build ran it
a 2-4-1 network on XOR, learning rate 2.0 epoch 0 loss 0.2694938411 epoch 100 loss 0.0132440610 epoch 500 loss 0.0008787379 epoch 1000 loss 0.0003742082 epoch 2000 loss 0.0001700572 epoch 4000 loss 0.0000802179 inputs wanted got [0.0, 0.0] 0 0.003901 [0.0, 1.0] 1 0.990277 [1.0, 0.0] 1 0.990996 [1.0, 1.0] 0 0.011404 rounded: [0, 1, 1, 0] wanted [0, 1, 1, 0] the four hidden units on input [1, 1]: ['-0.9998', '-0.9987', ' 0.9610', '-0.9675'] Each one draws its own line. The output neuron then draws one more line through the space those four created, and in there XOR is separable. ok the network gets all four XOR rows right ok the loss fell below a thousandth ok it started above a fifth and finished four orders of magnitude lower ok the loss never went up, over four thousand epochs ok seventeen parameters did what three could not ok the two ones and the two zeros end up far apart, not near the halfway line
What the hidden layer bought is worth being concrete about. The output neuron is still a single straight line — nothing about lesson 13's proof was wrong. The difference is that it no longer draws that line in the input space. It draws it in the four-dimensional space the hidden units produce, and those units have folded the input so that XOR's two yes corners now sit on the same side of one plane. Depth does not add lines. It changes the coordinates the line is drawn in.
The initialisation that cannot work
All weights zero looks like the choice with no bias in it, which is exactly why people try it. It is the one setting that provably cannot learn, and the reason has nothing to do with the size of the numbers. Two runs below: everything zero, then everything non-zero but identical across the hidden units.
# Symmetry. Identical neurons receive identical gradients and stay identical.
import math
import random
def sigmoid(z):
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z)
return ez / (1.0 + ez)
ROWS = [([0.0, 0.0], 0.0), ([0.0, 1.0], 1.0), ([1.0, 0.0], 1.0), ([1.0, 1.0], 0.0)]
WIDTH = 4
def forward(net, x):
w1, b1, w2, b2 = net
z1 = [sum(w * v for w, v in zip(row, x)) + b for row, b in zip(w1, b1)]
h = [math.tanh(v) for v in z1]
a = sigmoid(sum(w * v for w, v in zip(w2, h)) + b2)
return h, a
def loss(net):
return sum((forward(net, x)[1] - y) ** 2 for x, y in ROWS) / len(ROWS)
def train(net, lr=2.0, epochs=3000):
w1, b1, w2, b2 = net
history = [loss(net)]
n = float(len(ROWS))
for _ in range(epochs):
g_w1 = [[0.0] * 2 for _ in range(WIDTH)]
g_b1 = [0.0] * WIDTH
g_w2 = [0.0] * WIDTH
g_b2 = 0.0
for x, y in ROWS:
h, a = forward(net, x)
d_out = 2.0 * (a - y) * a * (1.0 - a) / n
g_b2 += d_out
for j in range(WIDTH):
g_w2[j] += d_out * h[j]
d_hidden = d_out * w2[j] * (1.0 - h[j] ** 2)
g_b1[j] += d_hidden
g_w1[j][0] += d_hidden * x[0]
g_w1[j][1] += d_hidden * x[1]
for j in range(WIDTH):
w1[j][0] -= lr * g_w1[j][0]
w1[j][1] -= lr * g_w1[j][1]
b1[j] -= lr * g_b1[j]
w2[j] -= lr * g_w2[j]
b2 -= lr * g_b2
net = (w1, b1, w2, b2)
history.append(loss(net))
return net, history
# Run one: every weight starts at exactly zero, which looks like the neutral choice.
zeros = ([[0.0, 0.0] for _ in range(WIDTH)], [0.0] * WIDTH, [0.0] * WIDTH, 0.0)
zeros, zero_history = train(zeros)
zero_outputs = [forward(zeros, x)[1] for x, _ in ROWS]
print("initialised to all zeros, {} hidden units, 3000 epochs".format(WIDTH))
print(" loss at the start : {:.10f}".format(zero_history[0]))
print(" loss at the end : {:.10f}".format(zero_history[-1]))
print(" first layer weights after training:", zeros[0])
print(" second layer weights after training:", zeros[2])
print(" outputs:", ["{:.6f}".format(v) for v in zero_outputs])
print(" output bias after training: {:.6f}".format(zeros[3]))
print(" Nothing moved at all. Only the output bias had any gradient, and XOR's")
print(" targets average exactly a half, which is what sigmoid(0) already says.")
# Run two: not zero, but every hidden unit given the same weights as its neighbours.
same = ([[0.4, -0.7] for _ in range(WIDTH)], [0.2] * WIDTH, [0.9] * WIDTH, -0.1)
same, same_history = train(same)
same_outputs = [forward(same, x)[1] for x, _ in ROWS]
rows_identical = all(close(same[0][j][i], same[0][0][i]) for j in range(WIDTH) for i in (0, 1))
print()
print("initialised so every hidden unit is a copy of its neighbour")
print(" loss at the end : {:.10f}".format(same_history[-1]))
print(" first layer weights after training:")
for row in same[0]:
print(" [{: .8f}, {: .8f}]".format(row[0], row[1]))
print(" rounded outputs:", [1 if v > 0.5 else 0 for v in same_outputs], " wanted [0, 1, 1, 0]")
# Run three: the same code, the same width, seeded random weights.
rng = random.Random(42)
lucky = ([[rng.uniform(-1.0, 1.0) for _ in range(2)] for _ in range(WIDTH)],
[rng.uniform(-1.0, 1.0) for _ in range(WIDTH)],
[rng.uniform(-1.0, 1.0) for _ in range(WIDTH)],
rng.uniform(-1.0, 1.0))
lucky, lucky_history = train(lucky)
lucky_outputs = [forward(lucky, x)[1] for x, _ in ROWS]
print()
print("the same network, same width, seeded random weights")
print(" loss at the end : {:.10f}".format(lucky_history[-1]))
print(" rounded outputs:", [1 if v > 0.5 else 0 for v in lucky_outputs], " wanted [0, 1, 1, 0]")
print()
print("Randomness is not decoration. It is the only thing telling the four hidden")
print("units apart, and without it the width on your model summary is a fiction.")
test("from all zeros, every first-layer weight is still exactly zero",
all(v == 0.0 for row in zeros[0] for v in row), True)
test("so all four outputs are the same number: the network predicts the average",
all(close(v, zero_outputs[0]) for v in zero_outputs), True)
test("and the loss sticks at a quarter, exactly where lesson 13's single neuron stuck",
close(zero_history[-1], 0.25, 0.005), True)
test("identical non-zero weights stay identical for all three thousand epochs",
rows_identical, True)
test("so four hidden units did the work of one, and XOR is still unsolved",
[1 if v > 0.5 else 0 for v in same_outputs] == [0, 1, 1, 0], False)
test("seeded random weights break the symmetry and the same code solves it",
[1 if v > 0.5 else 0 for v in lucky_outputs], [0, 1, 1, 0])What it printed, when the build ran it
initialised to all zeros, 4 hidden units, 3000 epochs
loss at the start : 0.2500000000
loss at the end : 0.2500000000
first layer weights after training: [[0.0, 0.0], [0.0, 0.0], [0.0, 0.0], [0.0, 0.0]]
second layer weights after training: [0.0, 0.0, 0.0, 0.0]
outputs: ['0.500000', '0.500000', '0.500000', '0.500000']
output bias after training: 0.000000
Nothing moved at all. Only the output bias had any gradient, and XOR's
targets average exactly a half, which is what sigmoid(0) already says.
initialised so every hidden unit is a copy of its neighbour
loss at the end : 0.1673674912
first layer weights after training:
[ 3.46667505, -3.79577573]
[ 3.46667505, -3.79577573]
[ 3.46667505, -3.79577573]
[ 3.46667505, -3.79577573]
rounded outputs: [0, 0, 1, 0] wanted [0, 1, 1, 0]
the same network, same width, seeded random weights
loss at the end : 0.0001092056
rounded outputs: [0, 1, 1, 0] wanted [0, 1, 1, 0]
Randomness is not decoration. It is the only thing telling the four hidden
units apart, and without it the width on your model summary is a fiction.
ok from all zeros, every first-layer weight is still exactly zero
ok so all four outputs are the same number: the network predicts the average
ok and the loss sticks at a quarter, exactly where lesson 13's single neuron stuck
ok identical non-zero weights stay identical for all three thousand epochs
ok so four hidden units did the work of one, and XOR is still unsolved
ok seeded random weights break the symmetry and the same code solves it
The mechanism is three lines of lesson 14. The gradient reaching hidden unit
j is d_out * W2[j]. If every W2[j] holds the same
number, every hidden unit receives the same gradient; if every hidden unit also starts with
the same weights, they all take the same step and remain copies of each other forever. With
zeros it is worse, because W2[j] is zero, so the gradient reaching the first
layer is zero and that layer never moves at all. Nothing raises. The model summary still says
four hidden units.
Biases are the exception, and it is why you will see zeros_ next to
xavier_uniform_ in real initialisation code and wonder if it is a mistake. A
bias is not multiplied by anything shared, so two units with different weights already have
different gradients on their biases. Zero biases are fine, and usually preferred. Zero
weights are the bug. And the scale matters as well as the randomness: too small and
the signal fades layer by layer, too large and tanh saturates immediately,
which is what Xavier and He initialisation compute for you from the layer widths.
What too high a learning rate does here
Lesson 7 showed a learning rate past its threshold sending the loss to 1e30.
With bounded activations the failure looks completely different, and much more innocent.
# The learning rate, on a network. The failure does not look like an error.
import math
import random
def sigmoid(z):
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z)
return ez / (1.0 + ez)
ROWS = [([0.0, 0.0], 0.0), ([0.0, 1.0], 1.0), ([1.0, 0.0], 1.0), ([1.0, 1.0], 0.0)]
WIDTH = 4
def forward(net, x):
w1, b1, w2, b2 = net
h = [math.tanh(sum(w * v for w, v in zip(row, x)) + b) for row, b in zip(w1, b1)]
return h, sigmoid(sum(w * v for w, v in zip(w2, h)) + b2)
def loss(net):
return sum((forward(net, x)[1] - y) ** 2 for x, y in ROWS) / len(ROWS)
def gradient(net):
w1, b1, w2, b2 = net
g_w1 = [[0.0, 0.0] for _ in range(WIDTH)]
g_b1 = [0.0] * WIDTH
g_w2 = [0.0] * WIDTH
g_b2 = 0.0
n = float(len(ROWS))
for x, y in ROWS:
h, a = forward(net, x)
d_out = 2.0 * (a - y) * a * (1.0 - a) / n
g_b2 += d_out
for j in range(WIDTH):
g_w2[j] += d_out * h[j]
d_hidden = d_out * w2[j] * (1.0 - h[j] ** 2)
g_b1[j] += d_hidden
g_w1[j][0] += d_hidden * x[0]
g_w1[j][1] += d_hidden * x[1]
return g_w1, g_b1, g_w2, g_b2
def fresh(seed=42):
"""The same starting point for every rate, so only the rate differs."""
rng = random.Random(seed)
return ([[rng.uniform(-1.0, 1.0) for _ in range(2)] for _ in range(WIDTH)],
[rng.uniform(-1.0, 1.0) for _ in range(WIDTH)],
[rng.uniform(-1.0, 1.0) for _ in range(WIDTH)],
rng.uniform(-1.0, 1.0))
def size(g):
"""How much slope is left anywhere in the network."""
g_w1, g_b1, g_w2, g_b2 = g
flat = [v for row in g_w1 for v in row] + g_b1 + g_w2 + [g_b2]
return math.sqrt(sum(v * v for v in flat))
def run(lr, epochs=2000):
net = fresh()
for _ in range(epochs):
g_w1, g_b1, g_w2, g_b2 = gradient(net)
w1, b1, w2, b2 = net
for j in range(WIDTH):
w1[j][0] -= lr * g_w1[j][0]
w1[j][1] -= lr * g_w1[j][1]
b1[j] -= lr * g_b1[j]
w2[j] -= lr * g_w2[j]
net = (w1, b1, w2, b2 - lr * g_b2)
biggest = max(abs(v) for v in [x for row in net[0] for x in row] + net[1] + net[2] + [net[3]])
return loss(net), size(gradient(net)), biggest, net
RATES = (0.05, 0.5, 2.0, 10.0, 60.0, 300.0)
print("the same 2-4-1 network and the same seed, 2000 epochs, six learning rates")
print()
print(" rate final loss gradient size biggest weight solved XOR")
results = {}
for lr in RATES:
final, gsize, biggest, net = run(lr)
solved = [1 if forward(net, x)[1] > 0.5 else 0 for x, _ in ROWS] == [0, 1, 1, 0]
results[lr] = (final, gsize, biggest, solved)
print(" {:<7} {:11.8f} {:14.3e} {:14.2f} {}".format(
lr, final, gsize, biggest, "yes" if solved else "no"))
print()
print("Notice what going too fast does not do. There is no nan, no exception, no")
print("loss of a trillion. tanh and sigmoid both bound their output, so a huge step")
print("does not explode the numbers - it drives every unit to the flat end of its")
print("curve, where the derivative is almost zero. The gradient column shows it:")
print("the network is not stuck because it has arrived. It is stuck because there")
print("is no slope left to tell it which way to go.")
test("a very small rate is still on its way down and has not arrived",
[results[0.05][0] > 0.05, results[0.05][0] < 0.25], [True, True])
test("a sensible rate solves XOR", results[2.0][3], True)
test("the fastest rate does not solve it", results[300.0][3], False)
test("and it produced no error at all: the loss is a finite number under one",
results[300.0][0] < 1.0, True)
test("its weights ended up nine times larger than the working run's",
results[300.0][2] > 5.0 * results[2.0][2], True)
test("which leaves a gradient too small to recover with: the run is dead, not slow",
results[300.0][1] < 1e-6, True)What it printed, when the build ran it
the same 2-4-1 network and the same seed, 2000 epochs, six learning rates rate final loss gradient size biggest weight solved XOR 0.05 0.09048251 4.814e-02 2.11 yes 0.5 0.00088457 1.073e-03 4.09 yes 2.0 0.00017006 2.168e-04 4.80 yes 10.0 0.00002000 3.379e-05 4.73 yes 60.0 0.50000000 1.371e-08 9.90 no 300.0 0.49999999 3.522e-08 43.08 no Notice what going too fast does not do. There is no nan, no exception, no loss of a trillion. tanh and sigmoid both bound their output, so a huge step does not explode the numbers - it drives every unit to the flat end of its curve, where the derivative is almost zero. The gradient column shows it: the network is not stuck because it has arrived. It is stuck because there is no slope left to tell it which way to go. ok a very small rate is still on its way down and has not arrived ok a sensible rate solves XOR ok the fastest rate does not solve it ok and it produced no error at all: the loss is a finite number under one ok its weights ended up nine times larger than the working run's ok which leaves a gradient too small to recover with: the run is dead, not slow
This is the failure to recognise in a real run, because it is invisible in the loss curve
alone: the loss goes flat early and stays flat, and it looks like the model has converged.
The tell is the gradient. If a plateau has a tiny gradient and large weights, the
units are saturated and no amount of extra epochs will help — you restart with a lower rate,
not with more patience. The same picture is why relu took over from
tanh: it has no flat positive side to get stuck on. Its own version of this
failure is the dead unit, permanently negative, permanently outputting zero, gradient
exactly zero forever.
A task with data in it
Four hand-written rows do not prove much: a network with seventeen parameters could memorise them. So here is something slightly larger — 120 random points in a square, labelled by whether they fall inside the unit circle, with 40 of them held back and never trained on. The same network, updated one point at a time, against the same loop with no hidden layer at all.
# A task with data in it: is this point inside the circle? Train on 80, test on 40.
import math
import random
def sigmoid(z):
if z >= 0.0:
return 1.0 / (1.0 + math.exp(-z))
ez = math.exp(z)
return ez / (1.0 + ez)
def make_net(sizes, rng):
net = []
for n_in, n_out in zip(sizes, sizes[1:]):
net.append([[[rng.uniform(-1.0, 1.0) for _ in range(n_in)] for _ in range(n_out)],
[rng.uniform(-1.0, 1.0) for _ in range(n_out)]])
return net
def forward(net, x):
acts = [x]
for index, layer in enumerate(net):
z = [sum(w * v for w, v in zip(row, acts[-1])) + b for row, b in zip(layer[0], layer[1])]
acts.append([sigmoid(v) for v in z] if index == len(net) - 1
else [math.tanh(v) for v in z])
return acts
def learn(net, x, y, lr):
"""One stochastic step: forward, backward, update, exactly as lesson 14 did it."""
acts = forward(net, x)
out = acts[-1]
delta = [2.0 * (out[k] - y[k]) * out[k] * (1.0 - out[k]) for k in range(len(out))]
for index in range(len(net) - 1, -1, -1):
weights, biases = net[index]
prev = acts[index]
if index > 0:
back = [sum(weights[j][i] * delta[j] for j in range(len(delta)))
for i in range(len(prev))]
for j in range(len(delta)):
for i in range(len(prev)):
weights[j][i] -= lr * delta[j] * prev[i]
biases[j] -= lr * delta[j]
if index > 0:
delta = [back[i] * (1.0 - prev[i] ** 2) for i in range(len(prev))]
def accuracy(net, data):
right = sum(1 for x, y in data if (forward(net, x)[-1][0] > 0.5) == (y[0] > 0.5))
return right / float(len(data))
def mean_loss(net, data):
return sum((forward(net, x)[-1][0] - y[0]) ** 2 for x, y in data) / len(data)
# The data: 120 points in a square, labelled by whether they fall inside the unit circle.
rng = random.Random(42)
DATA = []
for _ in range(120):
x0 = rng.uniform(-1.5, 1.5)
x1 = rng.uniform(-1.5, 1.5)
DATA.append(([x0, x1], [1.0 if x0 * x0 + x1 * x1 < 1.0 else 0.0]))
TRAIN = DATA[:80]
TEST = DATA[80:]
inside = sum(1 for _, y in TRAIN if y[0] > 0.5)
print("80 training points, {} of them inside the circle, 40 held back for testing".format(inside))
print()
deep = make_net([2, 8, 1], random.Random(42))
flat = make_net([2, 1], random.Random(42)) # no hidden layer: one straight line
order = list(range(len(TRAIN)))
shuffler = random.Random(7)
print(" pass 2-8-1 train loss train acc test acc 2-1 test acc")
for epoch in range(301):
if epoch % 50 == 0:
print(" {:5} {:16.8f} {:9.3f} {:8.3f} {:12.3f}".format(
epoch, mean_loss(deep, TRAIN), accuracy(deep, TRAIN),
accuracy(deep, TEST), accuracy(flat, TEST)))
if epoch == 300:
break # so the last row printed is the final state
shuffler.shuffle(order)
for i in order:
x, y = TRAIN[i]
learn(deep, x, y, 0.5)
learn(flat, x, y, 0.5)
deep_train = accuracy(deep, TRAIN)
deep_test = accuracy(deep, TEST)
flat_test = accuracy(flat, TEST)
majority = max(inside, len(TRAIN) - inside) / float(len(TRAIN))
print()
print("final 2-8-1 train {:.3f} test {:.3f}".format(deep_train, deep_test))
print(" 2-1 test {:.3f} <- one straight line, and a circle is not one".format(flat_test))
print(" always saying 'outside' would score {:.3f} on the training set".format(majority))
print()
print("The boundary the hidden layer built, read along the line x1 = 0:")
for x0 in (-1.4, -1.0, -0.6, 0.0, 0.6, 1.0, 1.4):
p = forward(deep, [x0, 0.0])[-1][0]
print(" x = [{: .1f}, 0.0] p(inside) = {:.4f} {}".format(
x0, p, "inside" if p > 0.5 else "outside"))
test("the network gets more than nine in ten of the training points right",
deep_train > 0.9, True)
test("and more than eight in ten of the forty it never saw",
deep_test > 0.8, True)
test("that beats always guessing the commoner label", deep_test > majority, True)
test("the same loop with no hidden layer does much worse, because a circle is not a line",
flat_test < deep_test - 0.15, True)
test("it puts the middle of the circle inside and both ends of the row outside",
[forward(deep, [0.0, 0.0])[-1][0] > 0.5,
forward(deep, [-1.4, 0.0])[-1][0] < 0.5,
forward(deep, [1.4, 0.0])[-1][0] < 0.5], [True, True, True])
test("nothing was memorised: train and test agree to within a tenth",
abs(deep_train - deep_test) < 0.1, True)What it printed, when the build ran it
80 training points, 25 of them inside the circle, 40 held back for testing
pass 2-8-1 train loss train acc test acc 2-1 test acc
0 0.30578154 0.475 0.600 0.450
50 0.05837786 0.900 0.875 0.675
100 0.03536857 0.950 0.850 0.675
150 0.03154003 0.963 0.925 0.675
200 0.02575859 0.963 0.900 0.675
250 0.01506238 0.988 0.950 0.675
300 0.01132182 0.988 0.950 0.675
final 2-8-1 train 0.988 test 0.950
2-1 test 0.675 <- one straight line, and a circle is not one
always saying 'outside' would score 0.688 on the training set
The boundary the hidden layer built, read along the line x1 = 0:
x = [-1.4, 0.0] p(inside) = 0.0139 outside
x = [-1.0, 0.0] p(inside) = 0.1405 outside
x = [-0.6, 0.0] p(inside) = 0.9970 inside
x = [ 0.0, 0.0] p(inside) = 1.0000 inside
x = [ 0.6, 0.0] p(inside) = 1.0000 inside
x = [ 1.0, 0.0] p(inside) = 0.9985 inside
x = [ 1.4, 0.0] p(inside) = 0.0000 outside
ok the network gets more than nine in ten of the training points right
ok and more than eight in ten of the forty it never saw
ok that beats always guessing the commoner label
ok the same loop with no hidden layer does much worse, because a circle is not a line
ok it puts the middle of the circle inside and both ends of the row outside
ok nothing was memorised: train and test agree to within a tenth
Three details in that panel are the difference between a demo and a training run you would trust. The test set is split before training and never touched, so the second column is an estimate of performance on data the model has not seen. The updates are one point at a time in a shuffled order, which is stochastic gradient descent — noisier per step than the full-batch loop above, and in practice faster to a good answer. And the 2-1 network is run on identical data with identical code, so the gap between the columns is attributable to the hidden layer and to nothing else.
The same network, in a framework
Everything above collapses into about ten lines, and the initialisation and the backward pass are the two parts that disappear. Worth reading with the previous panels in mind: the library is making the initialisation choice for you, and it is not choosing zeros.
# The same 2-8-1 network in torch. Ten lines, and nothing new in them.
# NOT RUN HERE - torch is not installed in this environment.
import torch
import torch.nn as nn
torch.manual_seed(42) # the same reason random.Random(42) is used above
net = nn.Sequential(
nn.Linear(2, 8), # make_net([2, 8, 1]) - and note what it does
nn.Tanh(), # NOT initialise to zeros. nn.Linear draws from
nn.Linear(8, 1), # a uniform range set by the input width, exactly
nn.Sigmoid(), # to avoid the symmetry the second panel showed.
)
loss_fn = nn.MSELoss()
optimiser = torch.optim.SGD(net.parameters(), lr=0.5)
for epoch in range(300):
for x, y in loader: # the shuffled one-at-a-time loop
optimiser.zero_grad() # or gradients accumulate across steps
loss = loss_fn(net(x), y)
loss.backward() # lesson 14's backward pass
optimiser.step() # w -= lr * w.grad, for every parameter
with torch.no_grad(): # no graph, no stored activations
accuracy = ((net(x_test) > 0.5) == (y_test > 0.5)).float().mean()
# Two things worth knowing, both visible in the panels above:
# nn.init.zeros_ on a weight matrix reproduces the symmetry failure exactly.
# A learning rate an order of magnitude too high gives no error, just a flat loss
# and saturated units - so print the gradient norm, not only the loss.torch is not installed in this environment, so this panel was never executed and there is no loader or x_test defined in it. Every line has a plain-Python counterpart above that did run: nn.Sequential is make_net, loss.backward() is the backward pass, and the initialisation comment is the failure the symmetry panel proved.
What to carry forward. A hidden layer does not add decision boundaries, it changes the coordinates the final boundary is drawn in, which is why XOR and a circle both become easy. Initialisation must break symmetry or the width of your layers is decorative — zero weights are the one setting that cannot learn, and zero biases are fine. A learning rate that is too high, with squashing activations, does not announce itself: it flattens the loss and empties the gradient, and looks exactly like convergence. Watch the gradient as well as the loss. The next lesson keeps the network and changes what goes into it, from numbers you chose to vectors the model learns for itself.
16 Embeddings: meaning as coordinates
An embedding is a short list of numbers standing in for a word, arranged so that words used in similar ways end up in similar places. This lesson builds one from a corpus you can read in full, measures it with lesson 5's cosine similarity, and then shows exactly what the geometry does and does not know — which is the difference between using retrieval well and being surprised by it in production.
One-hot, and the one thing it cannot express
The obvious way to turn a word into numbers is to give every word in the vocabulary its own slot and put a 1 in it. It is unambiguous, reversible and completely useless for similarity, and the reason is arithmetic rather than opinion.
# One-hot vectors: correct, honest, and unable to say that two words are alike.
import math
VOCAB = ["cat", "dog", "kitten", "code", "python", "the"]
def one_hot(word):
return [1.0 if other == word else 0.0 for other in VOCAB]
def dot(a, b):
return sum(x * y for x, y in zip(a, b))
def norm(v):
return math.sqrt(sum(x * x for x in v))
def cosine(a, b):
"""Lesson 5's cosine similarity, unchanged."""
return dot(a, b) / (norm(a) * norm(b))
print("the vocabulary:", VOCAB)
print()
for word in VOCAB:
print(" {:8} {}".format(word, one_hot(word)))
PAIRS = [("cat", "dog"), ("cat", "kitten"), ("cat", "code"), ("cat", "the"), ("cat", "cat")]
print()
print(" pair cosine similarity")
for a, b in PAIRS:
print(" {:8} {:8} {:.4f}".format(a, b, cosine(one_hot(a), one_hot(b))))
print()
print("Every distinct pair scores zero. Not approximately - exactly, because two")
print("one-hot vectors never have a 1 in the same place. 'cat' is as far from")
print("'kitten' as it is from 'python'.")
# An embedding table is a matrix with one row per word. Looking a word up is the
# same arithmetic as multiplying its one-hot vector by that matrix.
D = 4
TABLE = [[0.1 * (row + 1) + 0.01 * col for col in range(D)] for row in range(len(VOCAB))]
def by_matmul(word):
v = one_hot(word)
return [sum(v[row] * TABLE[row][col] for row in range(len(VOCAB))) for col in range(D)]
def by_lookup(word):
return TABLE[VOCAB.index(word)]
print()
print("one_hot('python') times the table :", ["{:.3f}".format(v) for v in by_matmul("python")])
print("table row for 'python' :", ["{:.3f}".format(v) for v in by_lookup("python")])
print()
print("So nn.Embedding is not a new kind of layer. It is a Linear layer fed one-hot")
print("input, with the multiplication by zero skipped because the answer is known.")
# What the two representations cost at a realistic vocabulary size.
V = 50257
print()
print(" vocabulary {:,} tokens".format(V))
print(" one-hot, one dimension per token : {:,} numbers per token".format(V))
print(" an embedding table at d = 300 : {:,} numbers in total".format(V * 300))
print(" a one-hot to one-hot map would be: {:,}".format(V * V))
test("a one-hot vector has exactly one 1 and the rest zeros",
[sum(one_hot("dog")), one_hot("dog").count(1.0)], [1.0, 1])
test("two different words score exactly zero, whichever two you choose",
all(cosine(one_hot(a), one_hot(b)) == 0.0 for a, b in PAIRS[:-1]), True)
test("so cat and kitten are no closer than cat and python: the encoding cannot say",
close(cosine(one_hot("cat"), one_hot("kitten")),
cosine(one_hot("cat"), one_hot("python"))), True)
test("a word is still identical to itself, which is all one-hot can express",
close(cosine(one_hot("cat"), one_hot("cat")), 1.0), True)
test("a one-hot times the table is exactly the table row, so a lookup is a matmul",
all(close(a, b) for a, b in zip(by_matmul("python"), by_lookup("python"))), True)
test("one-hot needs one dimension per token, a table needs d of them",
[len(one_hot("cat")), len(by_lookup("cat"))], [6, 4])
test("at 50257 tokens that is the difference between 15 million and 2.5 billion",
[V * 300 < 16000000, V * V > 2000000000], [True, True])What it printed, when the build ran it
the vocabulary: ['cat', 'dog', 'kitten', 'code', 'python', 'the']
cat [1.0, 0.0, 0.0, 0.0, 0.0, 0.0]
dog [0.0, 1.0, 0.0, 0.0, 0.0, 0.0]
kitten [0.0, 0.0, 1.0, 0.0, 0.0, 0.0]
code [0.0, 0.0, 0.0, 1.0, 0.0, 0.0]
python [0.0, 0.0, 0.0, 0.0, 1.0, 0.0]
the [0.0, 0.0, 0.0, 0.0, 0.0, 1.0]
pair cosine similarity
cat dog 0.0000
cat kitten 0.0000
cat code 0.0000
cat the 0.0000
cat cat 1.0000
Every distinct pair scores zero. Not approximately - exactly, because two
one-hot vectors never have a 1 in the same place. 'cat' is as far from
'kitten' as it is from 'python'.
one_hot('python') times the table : ['0.500', '0.510', '0.520', '0.530']
table row for 'python' : ['0.500', '0.510', '0.520', '0.530']
So nn.Embedding is not a new kind of layer. It is a Linear layer fed one-hot
input, with the multiplication by zero skipped because the answer is known.
vocabulary 50,257 tokens
one-hot, one dimension per token : 50,257 numbers per token
an embedding table at d = 300 : 15,077,100 numbers in total
a one-hot to one-hot map would be: 2,525,766,049
ok a one-hot vector has exactly one 1 and the rest zeros
ok two different words score exactly zero, whichever two you choose
ok so cat and kitten are no closer than cat and python: the encoding cannot say
ok a word is still identical to itself, which is all one-hot can express
ok a one-hot times the table is exactly the table row, so a lookup is a matmul
ok one-hot needs one dimension per token, a table needs d of them
ok at 50257 tokens that is the difference between 15 million and 2.5 billion
Three reasons embeddings win, in order of how often they matter:
- similarity exists at all. One-hot gives every distinct pair a score of zero, so nothing downstream can generalise from one word to a related one. A dense vector gives a score you can rank on, which is the entire basis of retrieval.
- size. One dimension per token means a 50,000-long vector per word, almost all zeros. Three hundred dimensions is 300 numbers, and the whole table fits in fifteen million.
- the parameters are shared. A model that learns something about "cat" moves a vector that "kitten" is already near, so the lesson partly transfers. With one-hot every word has its own private parameters and learns from scratch.
Embeddings from counting, on a corpus you can read
The oldest way to get vectors that know something is to count: for each word, how often does every other word turn up near it. That row of counts is an embedding. Ten sentences and fifteen words below, so the whole matrix fits on the page.
# Embeddings from counting. Which words turn up near which other words.
import math
CORPUS = [
"cat drank milk",
"dog drank water",
"cat sat rug",
"dog sat rug",
"cat chased ball",
"dog chased ball",
"engineer wrote code",
"engineer wrote bug",
"engineer fixed bug",
"engineer shipped code",
]
WINDOW = 2 # how far either side of a word counts as "near"
VOCAB = sorted(set(word for line in CORPUS for word in line.split()))
INDEX = dict((word, i) for i, word in enumerate(VOCAB))
counts = [[0 for _ in VOCAB] for _ in VOCAB]
for line in CORPUS:
words = line.split()
for position, word in enumerate(words):
low = max(0, position - WINDOW)
high = min(len(words), position + WINDOW + 1)
for other in range(low, high):
if other != position:
counts[INDEX[word]][INDEX[words[other]]] += 1
print("{} sentences, {} words in the vocabulary, window of {} either side".format(
len(CORPUS), len(VOCAB), WINDOW))
print()
header = " " + "".join("{:>4}".format(w[:3]) for w in VOCAB)
print(header)
for word in VOCAB:
row = counts[INDEX[word]]
print(" {:10} ".format(word) + "".join("{:4}".format(v) for v in row))
print()
print("Each row is that word's first embedding: one number per context word, saying")
print("how often the two turned up together. No model, no training, just counting.")
def dot(a, b):
return sum(x * y for x, y in zip(a, b))
def norm(v):
return math.sqrt(sum(x * x for x in v))
def cosine(a, b):
return dot(a, b) / (norm(a) * norm(b))
def vector(word):
return [float(v) for v in counts[INDEX[word]]]
def similarity(a, b):
return cosine(vector(a), vector(b))
PAIRS = [("cat", "dog"), ("code", "bug"), ("cat", "engineer"),
("cat", "code"), ("cat", "sat"), ("milk", "water")]
print()
print(" pair cosine of the two count rows")
for a, b in PAIRS:
print(" {:10} {:10} {: .4f}".format(a, b, similarity(a, b)))
print()
print("cat and dog never appear in the same sentence and never once next to each")
print("other. What makes their rows similar is that they keep the same company:")
print("both drink, both sit on the rug, both chase the ball.")
print()
def nearest(word):
others = [(similarity(word, other), other) for other in VOCAB if other != word]
others.sort(reverse=True)
return others[:3]
for word in ("cat", "engineer", "code"):
print(" nearest to {:10}".format(word),
", ".join("{} {:.3f}".format(name, score) for score, name in nearest(word)))
test("counting is symmetric: near you means you are near it",
all(counts[i][j] == counts[j][i] for i in range(len(VOCAB)) for j in range(len(VOCAB))), True)
test("a word never counts as its own neighbour",
all(counts[i][i] == 0 for i in range(len(VOCAB))), True)
test("cat and dog score high, despite never appearing in the same sentence",
similarity("cat", "dog") > 0.8, True)
test("cat and engineer share no company at all, so they score zero",
close(similarity("cat", "engineer"), 0.0), True)
test("the nearest word to cat is dog, and to engineer it is not",
[nearest("cat")[0][1], nearest("engineer")[0][1] == "cat"], ["dog", False])
test("appearing next to a word is not what makes vectors similar: cat and sat prove it",
similarity("cat", "sat") < similarity("cat", "dog"), True)What it printed, when the build ran it
10 sentences, 15 words in the vocabulary, window of 2 either side
bal bug cat cha cod dog dra eng fix mil rug sat shi wat wro
ball 0 0 1 2 0 1 0 0 0 0 0 0 0 0 0
bug 0 0 0 0 0 0 0 2 1 0 0 0 0 0 1
cat 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0
chased 2 0 1 0 0 1 0 0 0 0 0 0 0 0 0
code 0 0 0 0 0 0 0 2 0 0 0 0 1 0 1
dog 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0
drank 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0
engineer 0 2 0 0 2 0 0 0 1 0 0 0 1 0 2
fixed 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0
milk 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
rug 0 0 1 0 0 1 0 0 0 0 0 2 0 0 0
sat 0 0 1 0 0 1 0 0 0 0 2 0 0 0 0
shipped 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
water 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
wrote 0 1 0 0 1 0 0 2 0 0 0 0 0 0 0
Each row is that word's first embedding: one number per context word, saying
how often the two turned up together. No model, no training, just counting.
pair cosine of the two count rows
cat dog 0.8333
code bug 0.8333
cat engineer 0.0000
cat code 0.0000
cat sat 0.3333
milk water 0.5000
cat and dog never appear in the same sentence and never once next to each
other. What makes their rows similar is that they keep the same company:
both drink, both sit on the rug, both chase the ball.
nearest to cat dog 0.833, sat 0.333, rug 0.333
nearest to engineer wrote 0.436, shipped 0.378, fixed 0.378
nearest to code bug 0.833, wrote 0.667, shipped 0.577
ok counting is symmetric: near you means you are near it
ok a word never counts as its own neighbour
ok cat and dog score high, despite never appearing in the same sentence
ok cat and engineer share no company at all, so they score zero
ok the nearest word to cat is dog, and to engineer it is not
ok appearing next to a word is not what makes vectors similar: cat and sat prove it
The reason this works is worth stating carefully, because it is the assumption under every embedding model ever shipped: a word is characterised by the company it keeps. Note the second-order nature of it. "cat" and "sat" appear next to each other constantly and score 0.33; "cat" and "dog" never appear together at all and score 0.83. Similarity is not about co-occurring with each other, it is about co-occurring with the same third words. That distinction is why a count matrix can group synonyms it has never seen in the same sentence.
What dimensionality means
Those count rows are as long as the vocabulary, which is the one-hot problem again in disguise — 50,000 words means a 50,000-long row per word, almost all zeros. So compress: find four numbers per word whose dot products reproduce the counts. That is a training problem, and lesson 7's loop solves it.
# From 15 numbers per word down to 4, by gradient descent. GloVe, in miniature.
import math
import random
CORPUS = [
"cat drank milk", "dog drank water", "cat sat rug", "dog sat rug",
"cat chased ball", "dog chased ball", "engineer wrote code",
"engineer wrote bug", "engineer fixed bug", "engineer shipped code",
]
WINDOW = 2
VOCAB = sorted(set(w for line in CORPUS for w in line.split()))
INDEX = dict((w, i) for i, w in enumerate(VOCAB))
V = len(VOCAB)
counts = [[0] * V for _ in range(V)]
for line in CORPUS:
words = line.split()
for position, word in enumerate(words):
for other in range(max(0, position - WINDOW), min(len(words), position + WINDOW + 1)):
if other != position:
counts[INDEX[word]][INDEX[words[other]]] += 1
# The target. log(1 + count) rather than the raw count, because counts are wildly
# skewed and a pair seen twice is not twice as informative as a pair seen once.
TARGET = [[math.log(1.0 + counts[i][j]) for j in range(V)] for i in range(V)]
def fit(d, steps, lr=1.0, seed=42):
"""Find U and W so that U[i] . W[j] + biases reproduces TARGET[i][j]."""
rng = random.Random(seed)
U = [[rng.uniform(-0.5, 0.5) for _ in range(d)] for _ in range(V)]
W = [[rng.uniform(-0.5, 0.5) for _ in range(d)] for _ in range(V)]
BU = [0.0] * V # one bias per word, which soaks up "this word is common"
BW = [0.0] * V
scale = 2.0 / (V * V)
def predict(i, j):
return sum(U[i][k] * W[j][k] for k in range(d)) + BU[i] + BW[j]
def total():
return sum((predict(i, j) - TARGET[i][j]) ** 2
for i in range(V) for j in range(V)) / (V * V)
history = [total()]
for _ in range(steps):
gU = [[0.0] * d for _ in range(V)]
gW = [[0.0] * d for _ in range(V)]
gBU = [0.0] * V
gBW = [0.0] * V
for i in range(V):
for j in range(V):
e = (predict(i, j) - TARGET[i][j]) * scale
gBU[i] += e
gBW[j] += e
for k in range(d):
gU[i][k] += e * W[j][k]
gW[j][k] += e * U[i][k]
for i in range(V):
BU[i] -= lr * gBU[i]
BW[i] -= lr * gBW[i]
for k in range(d):
U[i][k] -= lr * gU[i][k]
W[i][k] -= lr * gW[i][k]
history.append(total())
return U, history, predict
D = 4
STEPS = 1200
U, history, predict = fit(D, STEPS)
print("{} words, {} co-occurrence cells to explain, {} numbers per word".format(V, V * V, D))
print()
for step in (0, 50, 200, 600, STEPS):
print(" step {:5} loss {:.8f}".format(step, history[step]))
print()
print("the learned vectors, four numbers each")
for word in VOCAB:
print(" {:10} [{: .4f}, {: .4f}, {: .4f}, {: .4f}]".format(word, *U[INDEX[word]]))
def cosine(a, b):
denominator = math.sqrt(sum(x * x for x in a)) * math.sqrt(sum(y * y for y in b))
return sum(x * y for x, y in zip(a, b)) / denominator
def similarity(a, b, table=None):
table = U if table is None else table
return cosine(table[INDEX[a]], table[INDEX[b]])
def nearest(word, n=3):
others = [(similarity(word, other), other) for other in VOCAB if other != word]
others.sort(reverse=True)
return others[:n]
print()
print(" pair cosine in {} dimensions".format(D))
for a, b in (("cat", "dog"), ("code", "bug"), ("cat", "engineer"), ("cat", "code")):
print(" {:10} {:10} {: .4f}".format(a, b, similarity(a, b)))
print()
for word in ("cat", "dog", "engineer", "code"):
print(" nearest to {:10}".format(word),
", ".join("{} {:.3f}".format(name, score) for score, name in nearest(word)))
print()
print(" cell log(1 + count) reconstruction")
for a, b in (("cat", "drank"), ("cat", "engineer"), ("engineer", "code")):
i, j = INDEX[a], INDEX[b]
print(" {:9} {:9} {:12.4f} {: 14.4f}".format(a, b, TARGET[i][j], predict(i, j)))
# What the number of dimensions actually buys. Same corpus, same seed, same steps.
print()
print(" dimensions numbers stored loss after 400 steps")
sweep = {}
for d in (1, 2, 4, 8):
table, hist, _ = fit(d, 400)
sweep[d] = (hist[-1], table)
print(" {:10} {:14} {:.8f}".format(d, V * d, hist[-1]))
one_d = sweep[1][1]
one_d_scores = [round(similarity(a, b, one_d), 6)
for a in VOCAB for b in VOCAB if a != b]
print()
print("In one dimension every word is a single number, so every pair of words points")
print("either exactly the same way or exactly the opposite way. Cosine can only")
print("return +1 or -1, and 'similar' has stopped meaning anything. That is what a")
print("dimension is for: room to be near one word without being near its neighbours.")
test("the loss fell to a fifth of where it started",
history[-1] < history[0] / 5.0, True)
test("four numbers per word replaced fifteen, so 60 in place of 225",
[V * D, V * V], [60, 225])
test("cat and dog are still close after the squeeze", similarity("cat", "dog") > 0.8, True)
test("cat and engineer are not: the two topics separated on their own",
similarity("cat", "engineer") < 0.0, True)
test("the nearest word to cat is dog, in four dimensions as in fifteen",
nearest("cat")[0][1], "dog")
test("every extra dimension reconstructs the counts a little better",
[sweep[2][0] < sweep[1][0], sweep[4][0] < sweep[2][0], sweep[8][0] < sweep[4][0]],
[True, True, True])
test("in one dimension every cosine is plus or minus one, so similarity says nothing",
sorted(set(one_d_scores)), [-1.0, 1.0])What it printed, when the build ran it
15 words, 225 co-occurrence cells to explain, 4 numbers per word
step 0 loss 0.17426983
step 50 loss 0.06902652
step 200 loss 0.04298964
step 600 loss 0.03419662
step 1200 loss 0.03368938
the learned vectors, four numbers each
ball [ 0.3653, -0.8892, -0.3984, -0.4646]
bug [-0.3130, 0.0381, -0.0703, -0.7497]
cat [ 0.1199, -0.3445, 0.6992, 0.0339]
chased [-0.0826, -0.0692, -0.2795, 0.3873]
code [-0.3145, 0.0409, -0.0699, -0.7468]
dog [ 0.1184, -0.3415, 0.6997, 0.0369]
drank [-0.0635, -0.2389, -0.4754, 0.1818]
engineer [ 0.9145, 0.8160, -0.1250, -0.3421]
fixed [-0.1796, 0.2825, 0.0260, -0.2443]
milk [ 0.0773, -0.0634, -0.0370, 0.0922]
rug [ 0.1545, -0.5140, -0.3463, -0.0741]
sat [-0.0762, -0.1040, -0.2867, 0.3523]
shipped [-0.1719, 0.2664, 0.0233, -0.2604]
water [ 0.0742, -0.0569, -0.0360, 0.0986]
wrote [-0.3021, 0.5473, 0.0186, -0.2892]
pair cosine in 4 dimensions
cat dog 1.0000
code bug 1.0000
cat engineer -0.2681
cat code -0.1959
nearest to cat dog 1.000, milk 0.075, ball 0.062
nearest to dog cat 1.000, milk 0.075, water 0.060
nearest to engineer wrote 0.303, shipped 0.279, fixed 0.276
nearest to code bug 1.000, shipped 0.770, fixed 0.735
cell log(1 + count) reconstruction
cat drank 0.6931 0.8044
cat engineer 0.0000 0.0213
engineer code 1.0986 1.1679
dimensions numbers stored loss after 400 steps
1 15 0.06440298
2 30 0.05302081
4 60 0.03608876
8 120 0.01640182
In one dimension every word is a single number, so every pair of words points
either exactly the same way or exactly the opposite way. Cosine can only
return +1 or -1, and 'similar' has stopped meaning anything. That is what a
dimension is for: room to be near one word without being near its neighbours.
ok the loss fell to a fifth of where it started
ok four numbers per word replaced fifteen, so 60 in place of 225
ok cat and dog are still close after the squeeze
ok cat and engineer are not: the two topics separated on their own
ok the nearest word to cat is dog, in four dimensions as in fifteen
ok every extra dimension reconstructs the counts a little better
ok in one dimension every cosine is plus or minus one, so similarity says nothing
So dimensionality is a budget. Each dimension is one more direction in which two words can
differ, and the table above shows the reconstruction improving every time one is added. The
cost is parameters — vocabulary x d of them, which for a real model is most of
its embedding layer — and the risk at the other end is that a very wide table has enough room
to memorise noise. The numbers you will meet in practice are roughly 100 to 300 for
word-level models like word2vec and GloVe, and 768 or more for a transformer, where the same
vector has to carry syntax and context as well as topic. Note also what happened to
cat and dog: at four dimensions their cosine rounds to 1.0000. Too
few dimensions and near-neighbours do not merely sit close, they become the same point.
What the geometry does not know
Now the part that matters when a retrieval system misbehaves. Everything above measures shared company. Shared company usually tracks meaning, and then sometimes does the exact opposite, in a way that is completely predictable once you have seen it.
# The honest part. Nearby means "used in the same company", which is not meaning.
import math
CORPUS = [
"coffee tastes hot", "coffee tastes cold",
"hot water tap", "cold water tap",
"hot summer day", "cold winter day",
"tea served hot", "tea served cold",
]
WINDOW = 2
def cooccurrence(corpus, window):
vocab = sorted(set(w for line in corpus for w in line.split()))
index = dict((w, i) for i, w in enumerate(vocab))
counts = [[0] * len(vocab) for _ in vocab]
for line in corpus:
words = line.split()
for position, word in enumerate(words):
low = max(0, position - window)
high = min(len(words), position + window + 1)
for other in range(low, high):
if other != position:
counts[index[word]][index[words[other]]] += 1
return vocab, index, counts
VOCAB, INDEX, COUNTS = cooccurrence(CORPUS, WINDOW)
def cosine(a, b):
denominator = math.sqrt(sum(x * x for x in a)) * math.sqrt(sum(y * y for y in b))
return sum(x * y for x, y in zip(a, b)) / denominator
def similarity(a, b):
return cosine([float(v) for v in COUNTS[INDEX[a]]], [float(v) for v in COUNTS[INDEX[b]]])
print("the corpus:")
for line in CORPUS:
print(" ", line)
print()
print("the two rows for hot and cold, side by side")
print(" {:10}".format("") + "".join("{:>9}".format(w[:8]) for w in VOCAB))
for word in ("hot", "cold"):
print(" {:10}".format(word) + "".join("{:9}".format(v) for v in COUNTS[INDEX[word]]))
print()
print("They differ in exactly one column each: summer against winter. Every other")
print("context word they share.")
others = sorted(((similarity("hot", w), w) for w in VOCAB if w != "hot"), reverse=True)
print()
print(" everything ranked by similarity to 'hot'")
for score, word in others:
print(" {:10} {: .4f}".format(word, score))
print()
print("The nearest neighbour of 'hot' is 'cold'. Not a near-synonym, not a related")
print("thing - its opposite. Nothing has gone wrong: the vectors record which words")
print("keep the same company, and opposites keep almost identical company, because")
print("they are the two answers to the same question.")
# A second thing counting cannot see, for the same reason: which order words came in.
REVERSED = [" ".join(reversed(line.split())) for line in CORPUS]
_, _, REVERSED_COUNTS = cooccurrence(REVERSED, WINDOW)
identical = all(COUNTS[i][j] == REVERSED_COUNTS[i][j]
for i in range(len(VOCAB)) for j in range(len(VOCAB)))
_, _, BITES_A = cooccurrence(["dog bites man"], WINDOW)
_, _, BITES_B = cooccurrence(["man bites dog"], WINDOW)
print()
print("original :", CORPUS[2])
print("reversed :", REVERSED[2])
print("the two co-occurrence matrices are identical:", identical)
print()
print("counts for 'dog bites man' :", BITES_A)
print("counts for 'man bites dog' :", BITES_B)
print("the same, so who did what to whom is not in here at all.")
test("the nearest word to hot is cold, which is its opposite", others[0][1], "cold")
test("and they score high enough that any threshold would call them the same thing",
similarity("hot", "cold") > 0.8, True)
test("a word genuinely associated with hot scores far lower",
similarity("hot", "summer") < similarity("hot", "cold") / 2.0, True)
test("because the two rows differ in exactly one column each",
sum(1 for j in range(len(VOCAB))
if COUNTS[INDEX["hot"]][j] != COUNTS[INDEX["cold"]][j]), 2)
test("reversing every sentence leaves the counts untouched, so order is invisible too",
identical, True)
test("so 'dog bites man' and 'man bites dog' produce the same counts exactly",
BITES_A, BITES_B)What it printed, when the build ran it
the corpus:
coffee tastes hot
coffee tastes cold
hot water tap
cold water tap
hot summer day
cold winter day
tea served hot
tea served cold
the two rows for hot and cold, side by side
coffee cold day hot served summer tap tastes tea water winter
hot 1 0 1 0 1 1 1 1 1 1 0
cold 1 0 1 0 1 0 1 1 1 1 1
They differ in exactly one column each: summer against winter. Every other
context word they share.
everything ranked by similarity to 'hot'
cold 0.8750
water 0.2887
tea 0.2887
tastes 0.2887
tap 0.2887
served 0.2887
coffee 0.2887
winter 0.2500
summer 0.2500
day 0.1768
The nearest neighbour of 'hot' is 'cold'. Not a near-synonym, not a related
thing - its opposite. Nothing has gone wrong: the vectors record which words
keep the same company, and opposites keep almost identical company, because
they are the two answers to the same question.
original : hot water tap
reversed : tap water hot
the two co-occurrence matrices are identical: True
counts for 'dog bites man' : [[0, 1, 1], [1, 0, 1], [1, 1, 0]]
counts for 'man bites dog' : [[0, 1, 1], [1, 0, 1], [1, 1, 0]]
the same, so who did what to whom is not in here at all.
ok the nearest word to hot is cold, which is its opposite
ok and they score high enough that any threshold would call them the same thing
ok a word genuinely associated with hot scores far lower
ok because the two rows differ in exactly one column each
ok reversing every sentence leaves the counts untouched, so order is invisible too
ok so 'dog bites man' and 'man bites dog' produce the same counts exactly
This is not a toy artefact, and it will reach your users. Ask a retrieval system for "flights that allow pets" and it will happily return "pets are not permitted on this route", because those two sentences are made of nearly the same words in nearly the same arrangement. Every embedding model has this shape of failure: negation, antonyms, dates, numbers, and identifiers are all things the geometry handles badly, because none of them change the company a word keeps very much. When a similarity score of 0.91 turns out to be the opposite of what was asked for, this is why — and the fix is not a better threshold, it is a reranking step that reads the candidates rather than measuring them.
Two limitations of the count-based method specifically, both fixed later rather than here. One vector per word means no context: "bank" gets a single point that averages the river and the money, and no amount of extra dimensions separates them, because the input is a word rather than a word in a sentence. And word order is invisible — the reversal test above proves it exactly. Both are solved by the same mechanism: build the vector for a token from the tokens around it, on the fly, which is attention, and give the model a way to know which position each token came from, which is positional encoding. Those are the next two lessons in this part of the course.
How this is done in practice
Nobody counts by hand any more, but nothing conceptual changes. In a modern model the embedding table is not built separately at all — it is the first layer, and it is trained by the same backward pass as every other layer.
# Embeddings as a real project gets them.
# NOT RUN HERE - torch and gensim are not installed in this environment.
import torch
import torch.nn as nn
# The whole of panel one and panel three, as one layer. 15 words, 4 numbers each.
table = nn.Embedding(num_embeddings=15, embedding_dim=4)
ids = torch.tensor([2, 5, 7]) # cat, dog, engineer as integer ids
vectors = table(ids) # shape (3, 4) - three rows looked up
print(vectors.shape)
# It is the one-hot matmul from the first panel, with the zeros skipped:
one_hot = torch.eye(15)[ids]
assert torch.allclose(one_hot @ table.weight, vectors)
# In a language model the table is nn.Parameter, so it is trained by the same
# loss.backward() as lesson 14. Nothing is "built" first - the vectors are whatever
# minimises next-token prediction.
similarity = nn.functional.cosine_similarity(vectors[0], vectors[1], dim=0)
# Off the shelf, when you do not want to train your own:
# gensim.downloader.load("glove-wiki-gigaword-100") the count factorisation above
# sentence-transformers/all-MiniLM-L6-v2 a whole sentence to 384 numbers
#
# And the trap the last panel proved, restated for the API:
# model.most_similar("hot") returns "cold" near the top. It is not broken.torch and gensim are not installed in this environment, so this panel was never executed and the assert in it was never run. The identity it claims - that a one-hot times the table equals the table row - was written out and asserted in plain Python in the first panel, and the antonym behaviour in the closing comment is what the fourth panel measured.
Where this leaves you. An embedding is a table with one row of numbers per token, and a lookup is a one-hot multiplication with the zeros skipped. Similar vectors come from shared company, which is why counting works at all, and the dimension count is a budget for how many ways two words are allowed to differ. What the geometry knows is usage; what it does not know is meaning, order, or negation, so antonyms sit close together and "dog bites man" is indistinguishable from "man bites dog". Hold on to that last failure, because the rest of this course is largely about fixing it.