Skip to content
wannacode

Backpropagation

In short: Backpropagation computes the slope of the error for every weight at once with the chain rule, going from the output back towards the input.

Problem

Nine numbers. Which one do you move?

The network from the lesson on layers solved the rule of the differing countries because its weights were chosen by hand. A real network starts with weights that mean nothing, and has to find them itself.

Here is the same network with starting weights. A customer abroad pays with a foreign card from a foreign IP, case (1, 1). That is fine, the label is 0. The network says 0.4489.

The network has nine numbers: four weights and two biases in the hidden layer, two weights and a bias at the output. Which one do you move, which way and how far? If you try blindly, every attempt is a forward pass. With a network of a million weights (an example of scale) that is millions of attempts for one step.

The idea

Nudge the weight and watch the error

The error for one payment is (p − y)², the square of the difference. Take one weight, v[0], and move it a little up and a little down, by 0.0001. Each time you compute the error again.

The network as a class with the nine numbers, the functions from the previous lesson, and the error:

class Net {
    double[][] w; // the hidden layer: weights and biases
    double[] b;
    double[] v; // the output: weights and bias
    double c;


    Net(double[][] w, double[] b, double[] v, double c) {
        this.w = w;
        this.b = b;
        this.v = v;
        this.c = c;
    }


    static Net zeros() {
        return new Net(new double[2][2], new double[2], new double[2], 0);
    }
}
static double[] hidden(Net net, double[] x) {
    return new double[] {neuron(x, net.w[0], net.b[0]), neuron(x, net.w[1], net.b[1])};
}


static double forward(Net net, double[] x) {
    return neuron(hidden(net, x), net.v, net.c);
}


static double loss(Net net, double[] x, double y) {
    double d = forward(net, x) - y;
    return d * d;
}

The starting weights and the payment:

// the starting weights: the network has not learned yet
Net net = new Net(new double[][] {{1.5, 1.0}, {2.5, 2.0}},
        new double[] {-0.5, -3.0}, new double[] {1.5, -1.5}, -0.3);
double[] x = {1, 1}; // a foreign card from a foreign IP: a customer abroad
double y = 0;
System.out.printf("p = %.4f, error = %.6f%n", forward(net, x), loss(net, x, y));
double old = net.v[0];
net.v[0] = old + 0.0001;
double up = loss(net, x, y);
net.v[0] = old - 0.0001;
double down = loss(net, x, y);
net.v[0] = old;
System.out.printf("v[0] + 0.0001: error = %.6f%n", up);
System.out.printf("v[0] - 0.0001: error = %.6f%n", down);
System.out.printf("slope = %.4f%n", (up - down) / 0.0002);
Output
p = 0.4489, error = 0.201500
v[0] + 0.0001: error = 0.201520
v[0] - 0.0001: error = 0.201481
slope = 0.1956

Up, the error grows; down, it falls. The difference divided by the distance between the two points (0.0002) is the slope: 0.1956. Positive means "a bigger v[0] gives a bigger error". So v[0] has to go down. This is the slope from gradient descent, only for one of the nine weights.

It works, but it needs two forward passes for every weight. We need a way to get the slope without touching the weight.

The idea

The chain rule with numbers

v[0] does not touch the error directly. It touches the sum z at the output, z touches p, and p touches the error. A chain of three links. If you know how much each link moves when you move the one before, the slope is their product:

  1. The error (p − y)² moves by 2·(p − y) when you move p.
  2. p = σ(z) moves by p·(1 − p) when you move z. That is the slope of the sigmoid.
  3. z = v[0]·h[0] + v[1]·h[1] + c moves by h[0] when you move v[0].
double[] h = hidden(net, x);
double p = neuron(h, net.v, net.c);
double a = 2 * (p - y); // how the error moves with p
double s = p * (1 - p); // how p moves with its sum z
double dz = h[0];       // how z moves with v[0]
System.out.printf("2(p - y) = %.4f%n", a);
System.out.printf("p(1 - p) = %.4f%n", s);
System.out.printf("h[0] = %.4f%n", dz);
System.out.printf("slope for v[0] = %.4f%n", a * s * dz);
Output
2(p - y) = 0.8978
p(1 - p) = 0.2474
h[0] = 0.8808
slope for v[0] = 0.1956

0.8978 × 0.2474 × 0.8808 = 0.1956. The same number as with nudging, but without a single new computation of the network. This is the chain rule: the slope along a chain is the product of the slopes of its links.

The idea

The error travels back

The first two links are shared by everything before the output. Their product is the share of the output, dOut = 2·(p − y)·p·(1 − p) = 0.2221. From there:

  • The output weights: the slope for v[j] is dOut × h[j].
  • The output bias: the slope for c is dOut itself, because z moves by 1 when you move c.
  • The hidden neurons: h[j] enters z with weight v[j]. Its share is dH = dOut × v[j] × h[j]·(1 − h[j]): the blame of the output, times the strength of the edge, times the slope of its own sigmoid.
  • The hidden weights: the slope for w[j][i] is dH × x[i], and for b[j] it is dH.

The blame travels back along the same edges the signal took forward, and each weight gets its share. This is backpropagation of the error (backprop for short): one forward pass, to know h and p, and one backwards, for all the slopes at once.

static Net backward(Net net, double[] x, double y) {
    double[] h = hidden(net, x);
    double out = neuron(h, net.v, net.c);
    Net g = Net.zeros();
    // the share of the output
    double dOut = 2 * (out - y) * out * (1 - out);
    g.c = dOut;
    for (int j = 0; j < 2; j++) {
        g.v[j] = dOut * h[j];
        // the share of hidden neuron j
        double dH = dOut * net.v[j] * h[j] * (1 - h[j]);
        g.b[j] = dH;
        for (int i = 0; i < 2; i++) {
            g.w[j][i] = dH * x[i];
        }
    }
    return g;
}
Net.zeros() is a network of zeros with the same shape: there is one slope for every weight, so the slopes are kept in the same class.

See it

Nudging against backprop, for all nine weights

To walk the nine numbers with one loop, get and set number them from 0 to 8. nudge is the nudging from above, for weight number k:

static final String[] NAMES =
        {"w[0][0]", "w[0][1]", "w[1][0]", "w[1][1]", "b[0]", "b[1]", "v[0]", "v[1]", "c"};


// k: w[0][0], w[0][1], w[1][0], w[1][1], b[0], b[1], v[0], v[1], c
static double get(Net n, int k) {
    if (k < 4) return n.w[k / 2][k % 2];
    if (k < 6) return n.b[k - 4];
    if (k < 8) return n.v[k - 6];
    return n.c;
}


static void set(Net n, int k, double value) {
    if (k < 4) n.w[k / 2][k % 2] = value;
    else if (k < 6) n.b[k - 4] = value;
    else if (k < 8) n.v[k - 6] = value;
    else n.c = value;
}
static double nudge(Net net, int k, double[] x, double y) {
    double old = get(net, k);
    set(net, k, old + 0.0001);
    double up = loss(net, x, y);
    set(net, k, old - 0.0001);
    double down = loss(net, x, y);
    set(net, k, old);
    return (up - down) / 0.0002;
}
Net g = backward(net, x, y);
System.out.println("             nudge  backprop");
for (int k = 0; k < 9; k++) {
    System.out.printf("%-8s%10.4f%10.4f%n", NAMES[k], nudge(net, k, x, y), get(g, k));
}
Output
             nudge  backprop
w[0][0]     0.0350    0.0350
w[0][1]     0.0350    0.0350
w[1][0]    -0.0497   -0.0497
w[1][1]    -0.0497   -0.0497
b[0]        0.0350    0.0350
b[1]       -0.0497   -0.0497
v[0]        0.1956    0.1956
v[1]        0.1816    0.1816
c           0.2221    0.2221

All nine match to the fourth decimal. The inputs are (1, 1), so the two weights and the bias of one hidden neuron have the same slope: each of them moves that neuron's z by 1. And the two hidden neurons have opposite signs, because v[0] = 1.5 and v[1] = −1.5 enter the output in opposite directions.

See it

The signal forward, the error back

static Net backward(Net net, double[] x, double y) {
    double[] h = hidden(net, x);
    double out = neuron(h, net.v, net.c);
    Net g = Net.zeros();
    // the share of the output
    double dOut = 2 * (out - y) * out * (1 - out);
    g.c = dOut;
    for (int j = 0; j < 2; j++) {
        g.v[j] = dOut * h[j];
        // the share of hidden neuron j
        double dH = dOut * net.v[j] * h[j] * (1 - h[j]);
        g.b[j] = dH;
        for (int i = 0; i < 2; i++) {
            g.w[j][i] = dH * x[i];
        }
    }
    return g;
}
Step by step, in words
  1. The starting weights and the case x = (1, 1): both from abroad, so it is fine, y = 0.
  2. Forward first: h1 = 0.8808, h2 = 0.8176, p = 0.4489.
  3. The error: (0.4489 − 0)² = 0.2015. The network should say less.
  4. Back from the output: the share is 2(p − y) · p(1 − p) = 0.8978 × 0.2474 = 0.2221, also the slope for c.
  5. The slope for v[j] is the share times h[j]: 0.2221 × 0.8808 = 0.1956 and 0.2221 × 0.8176 = 0.1816.
  6. Back along v and through σ: h1 gets 0.2221 × 1.5 × 0.1050 = 0.0350, h2 gets −0.0497. Also the slopes for b.
  7. The slope for w[j][i] is the share of h[j] times x[i]. Both inputs are 1: 0.0350 and −0.0497.
  8. Nine slopes from one pass back, the same as with nudging. A weight with a positive slope goes down.

Values travel forward, slopes travel back. The slope of every edge is the share of the neuron the edge leads to, times the value that went along it.

Try it

Predict the output

The share of the output is 0.4, the weight to the output is 1.5, and the hidden neuron gave 0.5. What will it print: the slope for that weight and the share of the hidden neuron?

double dOut = 0.4; // the share of the output
double v = 1.5;
double h = 0.5;
double dH = dOut * v * h * (1 - h);
System.out.printf("%.2f %.2f%n", dOut * h, dH);
Answer

Try it

Find the bug

A colleague writes backward themselves. The network learns, but slowly and oddly. The check with nudging shows that the output slopes match, while the hidden ones are 7 to 10 times too big. Which line has the bug?

Pick the line with the bug.

See it

One learning step

The slopes give the direction. The step is the one from gradient descent: each number moves against its slope, times the learning rate. The slope is the mean over the four payments, because the network has to be right for all of them:

static double meanLoss(Net net, double[][] cases, double[] labels) {
    double s = 0;
    for (int n = 0; n < cases.length; n++) {
        s += loss(net, cases[n], labels[n]);
    }
    return s / cases.length;
}
double[][] cases = {{0, 0}, {1, 0}, {0, 1}, {1, 1}};
double[] labels = {0, 1, 1, 0};
// the mean slope over the four payments
Net mean = Net.zeros();
for (int n = 0; n < 4; n++) {
    Net g = backward(net, cases[n], labels[n]);
    for (int k = 0; k < 9; k++) {
        set(mean, k, get(mean, k) + get(g, k) / 4);
    }
}
double rate = 2.0; // the learning rate
double before = meanLoss(net, cases, labels);
for (int k = 0; k < 9; k++) {
    double next = get(net, k) - rate * get(mean, k);
    System.out.printf("%-8s%8.4f → %.4f%n", NAMES[k], get(net, k), next);
    set(net, k, next);
}
double after = meanLoss(net, cases, labels);
System.out.printf("mean error: %.4f → %.4f%n", before, after);
Output
w[0][0]   1.5000 → 1.5147
w[0][1]   1.0000 → 1.0210
w[1][0]   2.5000 → 2.4863
w[1][1]   2.0000 → 1.9926
b[0]     -0.5000 → -0.4947
b[1]     -3.0000 → -3.0367
v[0]      1.5000 → 1.4987
v[1]     -1.5000 → -1.5266
c        -0.3000 → -0.3285
mean error: 0.2236 → 0.2218

The mean error falls from 0.2236 to 0.2218. A little, but in the right direction. Training is this same step repeated thousands of times: forward pass, backward pass, step. The whole loop and how the error falls is the next lesson.

Try it

Fill in

What is the step for each number of the network?

for (int k = 0; k < 9; k++) {
    set(net, k, get(net, k)  rate * get(g, k));
}

The idea

When backprop hurts

  • The slope vanishes. The slope of the sigmoid p·(1 − p) is at most 0.25. Through ten layers with a sigmoid the factors give at most 0.25¹⁰, about 0.000001. The first layers barely learn. That is why hidden layers today use ReLU: its slope is 1 for every positive z.
  • The slope explodes. If the weights are big, the products grow through the layers, and the step throws the weights far away. A smaller learning rate and normalisation help.
  • A bug in the slopes does not crash, it learns badly. The network still moves, only more slowly or towards something worse. That is why your own backprop is first compared with nudging, as in the program with the nine weights.
  • Nudging is only a check. It is accurate, but it needs two passes for every weight. For learning it is far too slow.
  • The slope only says "which way is down here". The step may be too big and overshoot, and a small one is slow. That is the learning rate from gradient descent.
More precisely, if you are curious

The formula. With L = (p − y)² and p = σ(z):

∂L/∂v₀ = ∂L/∂p · ∂p/∂z · ∂z/∂v₀ = 2(p − y) · p(1 − p) · h₀

∂ reads "partial derivative": how much the left side moves when you move only the right side and everything else stays put. For the hidden layer the chain is two links longer: ∂z/∂h₀ = v₀ and ∂h₀/∂z₀ = h₀(1 − h₀), then ∂z₀/∂w₀ᵢ = xᵢ.

Why the slope of the sigmoid is p(1 − p). If σ(z) = 1 / (1 + e^(−z)), its derivative is σ(z)·(1 − σ(z)). That is handy: the value p is already computed in the forward pass, and the slope comes without a new exp.

Nudging, more precisely. The program moves the weight both up and down (a central difference). The error of this estimate is of the order of h², with h = 0.0001 about 0.00000001. If you move only up, the error is of the order of h and the numbers match to fewer decimals.

In real libraries. Nobody writes backward by hand for every network. PyTorch and the like record every operation of the forward pass and then walk back along it themselves (automatic differentiation): in PyTorch that is loss.backward(). The rule inside is the same chain rule.

Training big networks (with graphics cards and many machines) and putting them into service is infrastructure. That is in the ZeroToOps course.

Exercise

Backprop for one neuron

Solve it in your editor.

The payment from the neuron lesson: €230, a new account, a foreign card, weights 0.9, 1.4 and 1.8 and a bias of −4. The payment turned out to be fraud: y = 1. The neuron said 0.7807. Compute the slope of the error (p − y)² for each weight and for the bias with the chain rule: dz = 2·(p − y)·p·(1 − p), the slope for w[i] is dz × x[i], and for b it is dz. Check the weights by nudging (± 0.0001).

Output
p = 0.7807, error = 0.0481
w[0]: backprop -0.1727, nudge -0.1727
w[1]: backprop -0.0751, nudge -0.0751
w[2]: backprop -0.0751, nudge -0.0751
b: backprop -0.0751

The slopes are negative: bigger weights give a bigger p, closer to 1, and the error falls. The weight of the amount gets the most blame, because the amount is the biggest input (2.3).

More tasks

  • A step. Take one step with a learning rate of 0.5 and print the new p. It should be closer to 1.
  • Another payment. Do the same for the €40 payment, which is fine (y = 0). Which slopes become zero, and why?

Test

Check yourself

1. What does the slope of the error tell you about one weight?
2. Why backprop and not nudging every weight?
3. The share of hidden neuron j is dOut × v[j] × h[j] × (1 − h[j]). Why is v[j] there?
4. The input x[i] is 0. What is the slope for the weight w[j][i]?
5. Backprop is written with a bug, and the network still learns a little. How do you catch it?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·