Practical 4: The Feed Forward Backpropagation Neural Network

Work down that output with a calculator once and backpropagation is no longer mysterious. Four things in it are worth saying in the journal.

The error before training is 0.1159 and the output is 0.5185 when the target is 1. The untrained network is guessing, which is what random weights do.

The delta at the output is (a - t) a (1 - a). The first factor is how wrong the answer is; the second and third are the slope of the sigmoid there. Multiplying by the slope is what makes this gradient descent rather than a guess: a neuron that is already saturated, output near 0 or near 1, has almost no slope and so moves almost not at all.

The delta at a hidden neuron is the output's delta, carried back through the weight that joined them, times that neuron's own slope. Hidden 1 gets a negative delta and hidden 2 a positive one, because their weights to the output have opposite signs. That single line is the whole of "backpropagation".

The two weights from input 2 did not move at all. Look at the last two lines: w1[1][0] and w1[1][1] come out exactly as they went in, because input 2 was 0 and every update is multiplied by the input. A weight from an input that is zero carries no blame, and it learns nothing from that example.

Step 2: the network, and a task it can only do with a hidden layer

XOR: output 1 when exactly one input is 1. It is the standard first task for a network because no straight line separates its two classes, so it cannot be done without a hidden layer, and demonstrating that is half the practical.

"""Practical 4: a feed forward network trained by backpropagation, on XOR."""
import math
import random

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

class Network:
    """One hidden layer. Weights are lists of lists; no library is used."""

    def __init__(self, n_in, n_hidden, n_out, seed=1):
        rng = random.Random(seed)
        span = 1.0
        self.w1 = [[rng.uniform(-span, span) for _ in range(n_hidden)] for _ in range(n_in)]
        self.b1 = [rng.uniform(-span, span) for _ in range(n_hidden)]
        self.w2 = [[rng.uniform(-span, span) for _ in range(n_out)] for _ in range(n_hidden)]
        self.b2 = [rng.uniform(-span, span) for _ in range(n_out)]

    def forward(self, x):
        self.a1 = [sigmoid(self.b1[j] + sum(x[i] * self.w1[i][j] for i in range(len(x))))
                   for j in range(len(self.b1))]
        self.a2 = [sigmoid(self.b2[k] + sum(self.a1[j] * self.w2[j][k] for j in range(len(self.a1))))
                   for k in range(len(self.b2))]
        return self.a2

    def backward(self, x, target, rate):
        out = self.a2
        d_out = [(out[k] - target[k]) * out[k] * (1 - out[k]) for k in range(len(out))]
        d_hid = [sum(d_out[k] * self.w2[j][k] for k in range(len(out)))
                 * self.a1[j] * (1 - self.a1[j]) for j in range(len(self.a1))]
        for j in range(len(self.a1)):
            for k in range(len(out)):
                self.w2[j][k] -= rate * d_out[k] * self.a1[j]
        for k in range(len(out)):
            self.b2[k] -= rate * d_out[k]
        for i in range(len(x)):
            for j in range(len(self.a1)):
                self.w1[i][j] -= rate * d_hid[j] * x[i]
        for j in range(len(self.a1)):
            self.b1[j] -= rate * d_hid[j]

    def train(self, data, epochs, rate, report_every=0):
        curve = []
        for epoch in range(1, epochs + 1):
            total = 0.0
            for x, t in data:
                out = self.forward(x)
                total += sum(0.5 * (t[k] - out[k]) ** 2 for k in range(len(t)))
                self.backward(x, t, rate)
            curve.append(total)
            if report_every and (epoch == 1 or epoch % report_every == 0):
                print("  epoch %6d   total error %.6f" % (epoch, total))
        return curve

XOR = [([0.0, 0.0], [0.0]),
       ([0.0, 1.0], [1.0]),
       ([1.0, 0.0], [1.0]),
       ([1.0, 1.0], [0.0])]

net = Network(2, 4, 1, seed=1)
print("training on XOR, 2 inputs, 4 hidden, 1 output, learning rate 0.5")
net.train(XOR, 20000, 0.5, report_every=4000)
print()
print("%-8s %10s %10s %8s" % ("input", "target", "output", "rounded"))
right = 0
for x, t in XOR:
    out = net.forward(x)[0]
    got = 1 if out >= 0.5 else 0
    right += (got == int(t[0]))
    print("%-8s %10.0f %10.6f %8d" % ("%d %d" % (x[0], x[1]), t[0], out, got))
print()
print("correct: %d of %d" % (right, len(XOR)))

training on XOR, 2 inputs, 4 hidden, 1 output, learning rate 0.5
  epoch      1   total error 0.570178
  epoch   4000   total error 0.001644
  epoch   8000   total error 0.000655
  epoch  12000   total error 0.000401
  epoch  16000   total error 0.000287
  epoch  20000   total error 0.000223

input        target     output  rounded
0 0               0   0.010836        0
0 1               1   0.989533        1
1 0               1   0.989801        1
1 1               0   0.010678        0

correct: 4 of 4

The error falls from 0.570 to 0.000223 and all four cases come out right. Note that the outputs are 0.0108 and 0.9895, not 0 and 1: a sigmoid never quite reaches either end, so the answer is rounded at 0.5. Print the raw output as well as the rounded one, because the raw number is the network's confidence and an examiner may ask for it.

Note also where the error falls. Between epoch 1 and epoch 4,000 it drops from 0.570 to 0.0016; over the next 16,000 epochs it only reaches 0.00022. Almost all the learning happens early, and training ten times longer buys very little. That is the shape of every learning curve you will draw in this subject.

Step 3: three things that decide whether it learns at all

"""Three things that decide whether a network learns anything at all."""
import math, random
def sigmoid(z): return 1 / (1 + math.exp(-z))

class Network:
    def __init__(self, n_in, n_hidden, n_out, seed=1):
        rng = random.Random(seed)
        self.w1 = [[rng.uniform(-1, 1) for _ in range(n_hidden)] for _ in range(n_in)]
        self.b1 = [rng.uniform(-1, 1) for _ in range(n_hidden)]
        self.w2 = [[rng.uniform(-1, 1) for _ in range(n_out)] for _ in range(n_hidden)]
        self.b2 = [rng.uniform(-1, 1) for _ in range(n_out)]
    def forward(self, x):
        self.a1 = [sigmoid(self.b1[j] + sum(x[i]*self.w1[i][j] for i in range(len(x))))
                   for j in range(len(self.b1))]
        self.a2 = [sigmoid(self.b2[k] + sum(self.a1[j]*self.w2[j][k] for j in range(len(self.a1))))
                   for k in range(len(self.b2))]
        return self.a2
    def backward(self, x, t, rate):
        out = self.a2
        d_out = [(out[k]-t[k])*out[k]*(1-out[k]) for k in range(len(out))]
        d_hid = [sum(d_out[k]*self.w2[j][k] for k in range(len(out)))*self.a1[j]*(1-self.a1[j])
                 for j in range(len(self.a1))]
        for j in range(len(self.a1)):
            for k in range(len(out)): self.w2[j][k] -= rate*d_out[k]*self.a1[j]
        for k in range(len(out)): self.b2[k] -= rate*d_out[k]
        for i in range(len(x)):
            for j in range(len(self.a1)): self.w1[i][j] -= rate*d_hid[j]*x[i]
        for j in range(len(self.a1)): self.b1[j] -= rate*d_hid[j]
    def train(self, data, epochs, rate):
        for _ in range(epochs):
            total = 0.0
            for x, t in data:
                o = self.forward(x)
                total += sum(0.5*(t[k]-o[k])**2 for k in range(len(t)))
                self.backward(x, t, rate)
        return total

XOR = [([0.,0.],[0.]), ([0.,1.],[1.]), ([1.,0.],[1.]), ([1.,1.],[0.])]

def score(net):
    return sum(1 for x, t in XOR if (1 if net.forward(x)[0] >= 0.5 else 0) == int(t[0]))

print("A. how many hidden neurons XOR needs")
print("%-10s %14s %10s" % ("hidden", "final error", "correct"))
for n in (0, 1, 2, 3, 4):
    if n == 0:
        # no hidden layer at all: a single sigmoid unit on the two inputs
        rng = random.Random(1)
        w = [rng.uniform(-1, 1) for _ in range(2)]; b = rng.uniform(-1, 1)
        for _ in range(20000):
            total = 0.0
            for x, t in XOR:
                o = sigmoid(b + w[0]*x[0] + w[1]*x[1])
                total += 0.5*(t[0]-o)**2
                d = (o-t[0])*o*(1-o)
                w[0] -= 0.5*d*x[0]; w[1] -= 0.5*d*x[1]; b -= 0.5*d
        got = sum(1 for x, t in XOR
                  if (1 if sigmoid(b+w[0]*x[0]+w[1]*x[1]) >= 0.5 else 0) == int(t[0]))
        print("%-10s %14.6f %10d" % ("none", total, got))
        continue
    net = Network(2, n, 1, seed=1)
    err = net.train(XOR, 20000, 0.5)
    print("%-10d %14.6f %10d" % (n, err, score(net)))

print()
print("B. the learning rate, 4 hidden neurons, 20000 epochs")
print("%-14s %14s %10s" % ("learning rate", "final error", "correct"))
for rate in (0.01, 0.1, 0.5, 2.0, 10.0, 50.0, 200.0):
    net = Network(2, 4, 1, seed=1)
    err = net.train(XOR, 20000, rate)
    print("%-14.2f %14.6f %10d" % (rate, err, score(net)))

print()
print("C. the starting weights, 4 hidden neurons, rate 0.5")
print("%-10s %14s %10s" % ("seed", "final error", "correct"))
for seed in (1, 2, 3, 4, 5):
    net = Network(2, 4, 1, seed=seed)
    err = net.train(XOR, 20000, 0.5)
    print("%-10d %14.6f %10d" % (seed, err, score(net)))
net = Network(2, 4, 1, seed=1)
net.w1 = [[0.0]*4 for _ in range(2)]; net.b1 = [0.0]*4
net.w2 = [[0.0] for _ in range(4)]; net.b2 = [0.0]
err = net.train(XOR, 20000, 0.5)
print("%-10s %14.6f %10d" % ("all zero", err, score(net)))

Three separate lessons, each measured rather than asserted.

A. XOR needs a hidden layer, and needs at least two neurons in it. With no hidden layer the single unit trained for 20,000 epochs and got 2 of 4, which is what guessing gets. With one hidden neuron, 3 of 4. With two or more, 4 of 4. That is the oldest result in the subject: a single layer of weights can only carve the input space with one straight line, and no straight line separates XOR.

B. The learning rate has a floor and a ceiling. At 0.01 the network was still at error 0.48 after 20,000 epochs: it was learning, just far too slowly. From 0.1 to 10 it worked, and on this very small problem the larger rates reached a lower error. At 50 it broke, and at 200 the error sat at exactly 1.000, which is the worst it can be: the steps are so large that each one overshoots and the weights are thrown further out than they started. Too small and it never arrives; too large and it never settles. On real data the useful range is much narrower than it is here, and 0.01 to 0.5 is where to start.

C. The starting weights must be random and different. Five different seeds all reached 4 of 4. Setting every weight to zero gave 3 of 4 and an error of 0.343. The reason is worth a sentence in the journal: if all the hidden neurons start identical, they receive identical deltas, so they stay identical for ever, and a layer of four identical neurons can do exactly what one can. Random starting weights are what break that symmetry.

Step 4: a real dataset, and the mistake that ruins it

MU says "use a given dataset to train the neural network for a specific task". The task: predict Pass or Fail from attendance and practice hours, on the thirty students of chapter 3.

There is one thing to get right first. Attendance runs from 35 to 98 and practice from 2 to 45. Feed those numbers straight into a sigmoid and the sum z is in the hundreds before training starts, the sigmoid is flat out at 1.000, a * (1 - a) is almost zero, and every delta is almost zero, so nothing learns. That is called saturation, and the cure is to squeeze every feature into the same small range first.

attendance ranges 35 to 98, practice 2 to 45
first row raw   : [50.0, 22.0]
first row scaled: [0.2381, 0.4651]

features                train acc  test acc
raw, 35 to 98               0.571     0.444
scaled to 0 and 1           0.952     0.778

0.444 on the test set with raw features, 0.778 with scaled ones. The raw run did not merely do worse, it did worse than the baseline of chapter 3. Scaling is not a refinement here; without it the network learned almost nothing.

Note one honest point about the test figure: nine test rows, so 0.778 is 7 of 9 and one row is worth 0.111. The training figure, 0.952, is 20 of 21.

Step 5: the same network from scikit-learn

"""The same job from scikit-learn: MLPClassifier, and scaling again."""
import csv
from sklearn.neural_network import MLPClassifier
from sklearn.preprocessing import MinMaxScaler
from sklearn.model_selection import train_test_split

with open("students.csv", newline="") as fh:
    rows = list(csv.DictReader(fh))
X = [[float(r["attendance"]), float(r["practice"])] for r in rows]
y = [r["result"] for r in rows]
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=1, stratify=y)

def run(name, Atr, Ate):
    net = MLPClassifier(hidden_layer_sizes=(4,), activation="logistic",
                        solver="lbfgs", max_iter=4000, random_state=1)
    net.fit(Atr, ytr)
    print("%-22s %10.3f %9.3f" % (name, net.score(Atr, ytr), net.score(Ate, yte)))

print("%-22s %10s %9s" % ("features", "train acc", "test acc"))
run("raw", Xtr, Xte)
scaler = MinMaxScaler().fit(Xtr)
run("scaled to 0 and 1", scaler.transform(Xtr), scaler.transform(Xte))

features                train acc  test acc
raw                         0.857     0.778
scaled to 0 and 1           0.952     0.778

MLPClassifier with hidden_layer_sizes=(4,) and activation="logistic" is the same network: one hidden layer of four sigmoid neurons. Its scaled result, 0.952 training and 0.778 test, is exactly what our own program reached, and that agreement is the best evidence available that the implementation above is correct. Put both in the journal side by side and say so.

Two differences to be honest about. solver="lbfgs" is a cleverer optimiser than the plain gradient descent we wrote, which is why scikit-learn reaches the same answer in 4,000 iterations of a different kind. And its raw-feature run scored 0.857 rather than our 0.571, because lbfgs copes with badly scaled inputs better than plain gradient descent does; it still gained from scaling.

Procedure

1. Write sigmoid and confirm sigmoid(0) is 0.5.
2. Work one forward pass by hand on a 2-2-1 network with fixed weights, then one backward pass, and check every number against the program.
3. Write the Network class: random weights, forward, backward, train.
4. Train it on XOR and record the error at intervals and the four final outputs.
5. Repeat with 0, 1, 2, 3 and 4 hidden neurons and record how many of the four cases each gets right.
6. Repeat with learning rates from 0.01 to 200 and record the final error.
7. Repeat with five different random seeds, and once with every weight set to zero.
8. Scale the student dataset to the range 0 to 1, split it, train, and measure on the held-out rows. Then do it again without scaling and record both.
9. Run MLPClassifier on the same split and compare.

Observations

Result

A feed forward network trained by backpropagation was implemented from nothing and used on two tasks. One forward and one backward pass were worked with every intermediate value printed and checked. On XOR the network reached an error of 0.000223 and classified all four cases correctly, while the same network with no hidden layer managed 2 of 4 and with all weights initialised to zero managed 3 of 4. The learning rate worked between 0.1 and 10 and failed outside it in both directions. On the thirty-student dataset, scaling the features to the range 0 to 1 raised test accuracy from 0.444 to 0.778 and training accuracy from 0.571 to 0.952, and MLPClassifier on the same scaled split reached the same 0.952 and 0.778.

Where marks are lost

No hidden layer. XOR cannot be learned without one, and the program will happily train for 20,000 epochs and get half of them right.

Unscaled inputs. The sigmoid saturates, the slope goes to zero, and the network learns nothing. This cost 0.33 of test accuracy above.

All weights initialised to zero. Every hidden neuron stays identical to every other one for ever.

Reporting the rounded output only. Print the raw sigmoid value too; it is the confidence.

Forgetting the bias. A neuron with no bias is a line through the origin, and there is no reason the answer should pass through the origin.

Using the same learning rate everywhere. It has a floor and a ceiling and both were found above. Report the one you used.

Not seeding. Random starting weights mean a different answer every run, and then the journal and the re-run disagree.

Measuring on the training rows. Chapter 3, and it applies here as much as anywhere.

Updating the weights while still computing the deltas. Compute all the deltas from the old weights, then update. Changing w2 before d_hid is computed uses the new weights to apportion the old blame, and the network trains slowly or not at all.

For the journal

Aim; the neuron equation and the sigmoid with its derivative; the network diagram; the hand-worked forward and backward pass with every number; the Network class; the XOR training run with the error at intervals and the four outputs; the three experiment tables for hidden size, learning rate and initialisation; the scaling formula; the student dataset run with and without scaling; the MLPClassifier comparison; all the observation tables; the result.

Quick revision

• A neuron computes z = bias + sum of weight times input, then a = sigmoid(z).
• sigmoid(z) = 1 / (1 + e to the minus z); its slope is a * (1 - a).
• Feed forward: inputs to hidden to output. Backpropagation: the error travels back through the same weights.
• Delta at the output = (output - target) output (1 - output).
• Delta at a hidden neuron = sum over outputs of (their delta times the joining weight), times its own a * (1 - a).
• Update: weight = weight - rate delta input, where the input is the one that weight carried.
• Compute every delta before updating any weight.
• XOR needs a hidden layer: without one, 2 of 4.
• Zero initial weights leave every hidden neuron identical for ever.
• Scale every input to a small range or the sigmoid saturates: 0.444 against 0.778 here.
• Almost all the learning happens in the first few thousand epochs.
• Round the output at 0.5, but report the raw value too.

Questions you must be able to answer

1. Why a sigmoid and not a step function? Because backpropagation needs a slope to work with, and a step has none anywhere except one point where it is undefined. The sigmoid has a smooth slope everywhere, and it can be written as a * (1 - a).

2. Why can a network with no hidden layer not learn XOR? Because one layer of weights draws one straight boundary, and the two classes of XOR cannot be separated by a straight line. Measured here: 2 of 4 after 20,000 epochs.

3. What is the delta at the output, and what are its parts? (output - target) output (1 - output). The first factor is how wrong the answer is and the rest is the slope of the sigmoid there, so a saturated neuron barely moves.

4. How is the error shared with the hidden layer? Each hidden neuron takes the output's delta multiplied by the weight joining them, and multiplies by its own slope. That is backpropagation in one sentence.

5. What happens if every weight starts at zero? Every hidden neuron computes the same thing, receives the same delta, and is updated identically, so they stay identical for ever. The four-neuron layer behaves like one neuron: 3 of 4 here.

6. Why must the features be scaled? Because a raw sum of large inputs drives the sigmoid to 0 or 1, where its slope is almost zero, so the deltas are almost zero and nothing learns. Scaling raised test accuracy from 0.444 to 0.778.

7. What does the learning rate do, and what are the symptoms of getting it wrong? It sets how far each weight moves per step. Too small and training is still far from the answer after any number of epochs; too large and it overshoots, and the error stops falling or rises. Both were produced above.

8. Your network outputs 0.9895 for a target of 1. Is it wrong? No. A sigmoid never reaches 1. Round at 0.5 to read the class, and quote the raw value as the confidence.

9. Why compute all the deltas before changing any weight? Because the hidden deltas are defined in terms of the weights that carried the values forward. Change those weights first and the blame is apportioned with the wrong numbers.

10. How do you know your own implementation is right? By making it agree with a known one on the same data. Ours and MLPClassifier both reached 0.952 training and 0.778 test on the same scaled split.