Unit 8: Backpropagation

One mistake, nine culprits

The network answered 0.8 when it should have said 0. The mistake is easy: out - y, so 0.8 too high.

The hard part is that nine numbers helped produce that 0.8. Which of them should move, and by how much? Gradient descent needs a slope for every single weight.

Blame goes where the push came from

Think about one weight in the output neuron. It multiplied the hidden value that arrived along it.

- If that hidden neuron sent a big number, this weight did a lot of the pushing — much of the blame is its.
- If the hidden neuron sent nearly 0, the weight changed nothing whatever it was — no blame.

Which is why the share of the blame is the mistake multiplied by the value that came in. You saw the same rule in unit 3, where each weight change was multiplied by its own input.

And the blame keeps travelling

The hidden neurons were not innocent either — they chose what to send. A hidden neuron's share of the blame is the output's blame, carried back along the weight that connects them: a fat weight passes back a lot, a weight near zero passes back almost none.

So the mistake starts at the answer and walks backwards through the network, splitting up as it goes. That walk is backpropagation.

One more thing is needed

The blame arrives at a neuron as "your total should have been lower". But the neuron does not hand out its total — it hands out the *squashed* total. So how much does moving the total actually move the answer?

That is the slope of the sigmoid at the point the neuron is sitting on, and it has a remarkably tidy shortcut:

slope = s * (1 - s)

where s is the value the sigmoid already gave.

Do not take our word for it

You already own a way to measure a slope: nudge the input and see how much the output moves. Here the shortcut and the nudge are put side by side.

Python

import math

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

h = 0.0001
for x in [-2, 0, 1]:
    nudged = (sigmoid(x + h) - sigmoid(x)) / h
    s = sigmoid(x)
    print(x, round(nudged, 4), round(s * (1 - s), 4))

It prints

-2 0.105 0.105
0 0.25 0.25
1 0.1966 0.1966

A confident neuron learns slowly

The slope is biggest in the middle — 0.25 at a sigmoid of 0.5 — and shrinks towards nothing at both ends. A neuron answering 0.99 has a slope of about 0.01, so all the blame arriving at it gets multiplied by almost zero and it barely moves.

That is a real problem with real networks, and it has a name: vanishing gradients. It is why very deep networks were hard to train for years.

Python

for s in [0.5, 0.75, 0.9, 0.99, 0.999]:
    print(s, round(s * (1 - s), 5))

It prints

0.5 0.25
0.75 0.1875
0.9 0.09
0.99 0.0099
0.999 0.001

Putting the three pieces together

For every example, run it forwards, then work out three blames and move nine numbers:

d_out = (out - y) * out * (1 - out) — the mistake, times the output neuron's slope.

d_h1 = d_out * w5 * h1 * (1 - h1) — the blame carried back along w5, times that neuron's own slope.

Then every weight moves by rate * blame * whatever came in along it, exactly as in unit 3.

Why the loss has a half in it

We score with (out - y) ** 2 / 2 rather than plain squaring. Halving cannot change which weights are best — it shrinks every score by the same amount — but it makes the slope come out as exactly out - y, with no stray 2 to carry around.

It is a tidiness trick, and everybody uses it.

Nine numbers, chosen badly on purpose

Training starts from small mixed-up numbers. They must not all be the same: identical neurons receive identical blame, change identically, and stay identical forever. A hidden layer of clones is one neuron wearing a hat.

Python

w1, w2, b1 = 0.5, -0.4, 0.1
w3, w4, b2 = -0.3, 0.6, -0.2
w5, w6, b3 = 0.7, -0.5, 0.3

print(w1, w2, b1)
print(w3, w4, b2)
print(w5, w6, b3)

It prints

0.5 -0.4 0.1
-0.3 0.6 -0.2
0.7 -0.5 0.3

Twenty thousand times round

Watch the loss. It sits almost still for a thousand passes — the network is drifting about learning nothing much — and then falls off a cliff. That plateau is normal, and it is why people leave training running.

Python

import math

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

data = [[0, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]]
w1, w2, b1 = 0.5, -0.4, 0.1
w3, w4, b2 = -0.3, 0.6, -0.2
w5, w6, b3 = 0.7, -0.5, 0.3
rate = 0.5

def forward(a, b):
    h1 = sigmoid(a * w1 + b * w2 + b1)
    h2 = sigmoid(a * w3 + b * w4 + b2)
    return h1, h2, sigmoid(h1 * w5 + h2 * w6 + b3)

def loss():
    total = 0
    for a, b, y in data:
        total = total + (forward(a, b)[2] - y) ** 2 / 2
    return total / len(data)

for step in range(1, 20001):
    for a, b, y in data:
        h1, h2, out = forward(a, b)
        d_out = (out - y) * out * (1 - out)
        d_h1 = d_out * w5 * h1 * (1 - h1)
        d_h2 = d_out * w6 * h2 * (1 - h2)
        w5 = w5 - rate * d_out * h1
        w6 = w6 - rate * d_out * h2
        b3 = b3 - rate * d_out
        w1 = w1 - rate * d_h1 * a
        w2 = w2 - rate * d_h1 * b
        b1 = b1 - rate * d_h1
        w3 = w3 - rate * d_h2 * a
        w4 = w4 - rate * d_h2 * b
        b2 = b2 - rate * d_h2
    if step in [500, 1000, 2000, 5000, 20000]:
        print(step, round(loss(), 4))

for a, b, y in data:
    print(a, b, round(forward(a, b)[2], 2))

It prints

500 0.1247
1000 0.1023
2000 0.0026
5000 0.0004
20000 0.0001
0 0 0.01
0 1 0.99
1 0 0.99
1 1 0.01

Stop and look at what just happened

Unit 3 proved that one neuron can never learn XOR. This network started from nine nearly-useless numbers, was told only which answers were right, and found nine numbers that work — including hidden neurons that do the jobs Or and Nand do, which nobody asked it for.

That is a neural network training itself, and it is the same procedure, unchanged, that trains models with a billion weights.

The same code, stuck

Nothing changed here except the learning rate — 1.0 instead of 0.5. Two of the four answers are 0.48, which is the network shrugging, and no amount of extra training moves them.

It has rolled into a dip that is not the bottom of the valley. Every direction out of a dip is uphill, so gradient descent stays. This is called a local minimum.

Python

import math

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

data = [[0, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]]
w1, w2, b1 = 0.5, -0.4, 0.1
w3, w4, b2 = -0.3, 0.6, -0.2
w5, w6, b3 = 0.7, -0.5, 0.3
rate = 1.0

def forward(a, b):
    h1 = sigmoid(a * w1 + b * w2 + b1)
    h2 = sigmoid(a * w3 + b * w4 + b2)
    return h1, h2, sigmoid(h1 * w5 + h2 * w6 + b3)

for step in range(3000):
    for a, b, y in data:
        h1, h2, out = forward(a, b)
        d_out = (out - y) * out * (1 - out)
        d_h1 = d_out * w5 * h1 * (1 - h1)
        d_h2 = d_out * w6 * h2 * (1 - h2)
        w5 = w5 - rate * d_out * h1
        w6 = w6 - rate * d_out * h2
        b3 = b3 - rate * d_out
        w1 = w1 - rate * d_h1 * a
        w2 = w2 - rate * d_h1 * b
        b1 = b1 - rate * d_h1
        w3 = w3 - rate * d_h2 * a
        w4 = w4 - rate * d_h2 * b
        b2 = b2 - rate * d_h2

for a, b, y in data:
    print(a, b, round(forward(a, b)[2], 2))

It prints

0 0 0.03
0 1 0.48
1 0 0.98
1 1 0.48

What people actually do about it

They start again from different numbers, or change the learning rate, or add more hidden neurons so there are more ways down.

There is no guarantee anywhere in this. Training a network is not a calculation with a right answer at the end — it is an attempt, and part of the job is noticing when it has failed.

The other way to fail: learn the wrong thing perfectly

Now hide one row. The network trains on three of XOR's four cases and never sees 1 1.

Python

import math

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

train = [[0, 0, 0], [0, 1, 1], [1, 0, 1]]
w1, w2, b1 = 0.5, -0.4, 0.1
w3, w4, b2 = -0.3, 0.6, -0.2
w5, w6, b3 = 0.7, -0.5, 0.3
rate = 0.5

def forward(a, b):
    h1 = sigmoid(a * w1 + b * w2 + b1)
    h2 = sigmoid(a * w3 + b * w4 + b2)
    return h1, h2, sigmoid(h1 * w5 + h2 * w6 + b3)

for step in range(5000):
    for a, b, y in train:
        h1, h2, out = forward(a, b)
        d_out = (out - y) * out * (1 - out)
        d_h1 = d_out * w5 * h1 * (1 - h1)
        d_h2 = d_out * w6 * h2 * (1 - h2)
        w5 = w5 - rate * d_out * h1
        w6 = w6 - rate * d_out * h2
        b3 = b3 - rate * d_out
        w1 = w1 - rate * d_h1 * a
        w2 = w2 - rate * d_h1 * b
        b1 = b1 - rate * d_h1
        w3 = w3 - rate * d_h2 * a
        w4 = w4 - rate * d_h2 * b
        b2 = b2 - rate * d_h2

for a, b, y in train:
    print("seen", a, b, round(forward(a, b)[2], 2))

print("never seen 1 1 ->", round(forward(1, 1)[2], 2))

It prints

seen 0 0 0.02
seen 0 1 0.99
seen 1 0 0.99
never seen 1 1 -> 1.0

It learned "or" and is certain about it

Perfect on all three examples it was given. Completely wrong on the one it was not — and not hesitantly wrong, 1.0 wrong.

This is overfitting: the model fitted what it was shown instead of the pattern behind it. Nothing in its training could possibly have told it otherwise, and nothing in its confidence tells you it happened. Only a test set does.