Digit recognition with a neural network in Python

Problem

The total from a photo

To return an item, the customer sends a photo of the till receipt, and the system has to read the total. The till prints the digits in one font, so it looks easy: compare the pixels with the font and you are done.

But paper creases, ink fades and the photo has smudges. Here is the 7 from the font and three 7s from real receipts:

print_side([show(pixels(DIGITS[7])), show(train_x[7]), show(train_x[17]), show(train_x[27])])

#####   #####   #####   #####
....#   ....#   ....#   ....#
...#.   ...##   .....   ...#.
..#..   ..#..   #.#..   ..##.
..#..   ..#..   ..#..   #.##.

The third 7 is missing a pixel in the middle row, the fourth has extra ink at the bottom. A rule “it is a 7 if these 9 pixels are ink” breaks at the first smudge. And you cannot write a rule for every possible smudge.

The idea

The pixels are features

A 5 × 5 picture is 25 pixels. Line them up row by row and you have 25 numbers: 1 for ink, 0 for blank. These are features, just like the distance and the weight of an order. Recognising a picture is classification with 25 features and 10 classes, the digits 0 to 9. This is image classification.

The network is one layer of 10 neurons, one per digit. Every neuron has one weight for every pixel: its sum is large when the ink is where its digit has ink.

The ten sums become probabilities with softmax: every sum becomes eˢ, then every number is divided by the total of all of them. The numbers are positive and add up to 1. The largest one is the answer, and its size is how sure the network is.

Training is the loop from the previous lesson: epochs, shuffling, batches, a step. The error for one picture is −ln(p) of the right digit: 0 if the network gives the right answer 100%, and large if it gives it little.

The data: 60 digits for training (6 of each) and 30 for the test (3 of each), all from the font with smudges. Every pixel flips with probability 8%, two pixels per digit on average.

See it

The data and the network

The font is written in the code as text, # is ink:

# the digits of the till font: 5 × 5 pixels, # is ink
DIGITS = [
    [".###.", "#...#", "#...#", "#...#", ".###."],
    ["..#..", ".##..", "..#..", "..#..", ".###."],
    [".###.", "#...#", "..##.", ".#...", "#####"],
    ["####.", "....#", ".###.", "....#", "####."],
    ["#..#.", "#..#.", "#####", "...#.", "...#."],
    ["#####", "#....", "####.", "....#", "####."],
    [".###.", "#....", "####.", "#...#", ".###."],
    ["#####", "....#", "...#.", "..#..", "..#.."],
    [".###.", "#...#", ".###.", "#...#", ".###."],
    [".###.", "#...#", ".####", "....#", ".###."],
]

A picture becomes features, the smudges come from the generator, and the features turn back into a picture so we can print them:

# the picture as 25 features: row by row, 1 for ink, 0 for blank
def pixels(rows):
    return [1.0 if rows[r][c] == "#" else 0.0 for r in range(5) for c in range(5)]


# a smudge or faded ink: every pixel flips with probability 8%
def smudge(x, rng):
    return [1 - v if rng.next() < 0.08 else v for v in x]


# the features back as a picture
def show(x):
    return ["".join("#" if v > 0.5 else "." for v in x[r * 5:r * 5 + 5]) for r in range(5)]


# several pictures side by side
def print_side(pics):
    for r in range(5):
        print("   ".join(pic[r] for pic in pics))

The generator is the one from the previous lesson, with seed 7. First come the 60 training digits, then the 30 test digits:

class Rng:
    def __init__(self, seed):
        self.state = seed

    # the next number between 0 and 1; one seed gives the same numbers
    def next(self):
        self.state = self.state * 48271 % 2147483647
        return self.state / 2147483647

rng = Rng(7)
train_y = [n % 10 for n in range(60)]
train_x = [smudge(pixels(DIGITS[d]), rng) for d in train_y]
test_y = [n % 10 for n in range(30)]
test_x = [smudge(pixels(DIGITS[d]), rng) for d in test_y]

The network: 10 × 25 weights and 10 biases. predict computes the ten sums and turns them into probabilities. Before exp, the largest sum is subtracted from every sum: the result is the same, but exp does not overflow on large sums. In step the slope of neuron k by its sum is p[k] − 1 for the right digit and p[k] for the others: the right neuron is pushed up and the others down, by as much as they were wrong.

class Net:
    # small random weights; biases stay 0
    def __init__(self, rng):
        self.w = [[(rng.next() * 2 - 1) * 0.1 for _ in range(25)] for _ in range(10)]  # a weight for every pixel for each of the 10 neurons
        self.b = [0.0] * 10

    # the ten probabilities (softmax): they add up to 1
    def predict(self, x):
        p = []
        for k in range(10):
            s = self.b[k]
            for i in range(25):
                s += self.w[k][i] * x[i]
            p.append(s)
        top = max(p)
        total = 0.0
        for k in range(10):
            p[k] = math.exp(p[k] - top)
            total += p[k]
        for k in range(10):
            p[k] /= total
        return p

    # the error: the average −ln(p) of the right answer
    def loss(self, xs, ys):
        total = 0.0
        for x, y in zip(xs, ys):
            total -= math.log(self.predict(x)[y])
        return total / len(xs)

    # a step per batch: the slope of neuron k is p[k] − 1 for the right digit, p[k] for the others
    def step(self, xs, ys, batch, rate):
        gw = [[0.0] * 25 for _ in range(10)]
        gb = [0.0] * 10
        for n in batch:
            p = self.predict(xs[n])
            for k in range(10):
                d = p[k] - (1 if k == ys[n] else 0)
                gb[k] += d
                for i in range(25):
                    gw[k][i] += d * xs[n][i]
        for k in range(10):
            self.b[k] -= rate * gb[k] / len(batch)
            for i in range(25):
                self.w[k][i] -= rate * gw[k][i] / len(batch)

Try it

Predict the output

What does the program print? x[r * 5 + 2] is the pixel in row r and column 2 (counting from 0).

x = pixels(DIGITS[7])
print(" ".join(str(int(x[r * 5 + 2])) for r in range(5)))

Answer

1 1 1 0 0

0 0 0 1 0

1 0 0 1 1

See it

Training, and one digit up close

60 epochs, batches of 10, rate 0.5. Every 10 epochs the program prints the error and how many digits are right on the training and the test set:

net = Net(rng)
order = list(range(len(train_x)))
print("epoch  error  training  test")
for epoch in range(1, 61):
    shuffle(order, rng)
    for start in range(0, len(order), 10):
        net.step(train_x, train_y, order[start:start + 10], 0.5)
    if epoch % 10 == 0:
        right = f"{correct(net, train_x, train_y)}/{len(train_x)}"
        test = f"{correct(net, test_x, test_y)}/{len(test_x)}"
        print(f"{epoch:5d}{net.loss(train_x, train_y):7.3f}{right:>10}{test:>6}")

epoch  error  training  test
   10  0.268     59/60 28/30
   20  0.128     60/60 29/30
   30  0.084     60/60 29/30
   40  0.063     60/60 29/30
   50  0.050     60/60 29/30
   60  0.042     60/60 29/30

After 20 epochs the network gets all 60 training digits and 29 of 30 on the test set. The error keeps falling because the network gets more sure, but the test digit it misses stays the same.

Here is what happens to one digit. The pixels go in, every neuron adds up its weights over them, and softmax turns the sums into probabilities:

# the ten probabilities (softmax): they add up to 1
def predict(self, x):
    p = []
    for k in range(10):
        s = self.b[k]
        for i in range(25):
            s += self.w[k][i] * x[i]
        p.append(s)
    top = max(p)
    total = 0.0
    for k in range(10):
        p[k] = math.exp(p[k] - top)
        total += p[k]
    for k in range(10):
        p[k] /= total
    return p

net = train(train_x, train_y, rng)
shifted = pixels(shift(DIGITS[1]))
for x in [test_x[17], shifted]:
    print_side([show(x)])
    p = net.predict(x)
    for k in range(10):
        bar = "█" * round(p[k] * 20)
        print(f"{k} {bar:<20} {p[k] * 100:5.1f}%")
    print(f"→ {best(p)}")

Step by step, in words

A 7 from the test set, with a smudge at the bottom left. For the network it is 25 numbers: 1 for ink, 0 for blank.
Each of the 10 neurons adds up its weights over the ink pixels. The neuron for 7 gets the largest sum: 6.68.
Softmax: e to the power of every sum, divided by the total. The ten bars add up to 100%.
The largest bar is the answer: 7 with 98.4%. The smudge did not get in the way.
The 1 from the font, without a smudge, printed one pixel to the right. Its ink is in the fourth column.
The network says 4 with 57.1%, and 1 gets only 4.4%. The weights of 4 wait for ink in that column.
Every weight is tied to one pixel. Smudges it has learned to ignore; a shift of one pixel it has never seen.

net = train(train_x, train_y, rng)
shifted = pixels(shift(DIGITS[1]))
for x in [test_x[17], shifted]:
    print_side([show(x)])
    p = net.predict(x)
    for k in range(10):
        bar = "█" * round(p[k] * 20)
        print(f"{k} {bar:<20} {p[k] * 100:5.1f}%")
    print(f"→ {best(p)}")

#####
....#
...#.
..#..
#.#..
0                        0.1%
1                        0.0%
2                        0.2%
3                        0.4%
4                        0.0%
5                        0.7%
6                        0.0%
7 ████████████████████  98.4%
8                        0.1%
9                        0.1%
→ 7
...#.
..##.
...#.
...#.
..###
0                        0.2%
1 █                      4.4%
2 ███                   15.4%
3                        2.3%
4 ███████████           57.1%
5                        0.6%
6 █                      5.0%
7 █                      7.1%
8 █                      2.9%
9 █                      5.0%
→ 4

The 7 from the test set has a smudge at the bottom left, and the network still says 7 with 98.4%. The second picture is the 1 from the font, printed one pixel to the right. Not a single smudge, and the network says 4 with 57.1%. We will come back to it.

The idea

What every neuron looks at

Every neuron has 25 weights, one per pixel, so its weights are a 5 × 5 picture too. A large positive weight means “ink here is for me”, a large negative one means “ink here is against me”:

# # strong “yes”, + “yes”, . no matter, - “no”, = strong “no”
def symbol(v):
    if v > 0.8:
        return "#"
    if v > 0.25:
        return "+"
    if v < -0.8:
        return "="
    if v < -0.25:
        return "-"
    return "."


def weight_map(weights):
    return ["".join(symbol(v) for v in weights[r * 5:r * 5 + 5]) for r in range(5)]

net = train(train_x, train_y, rng)
print("  0       1       7  ")
print_side([weight_map(net.w[d]) for d in (0, 1, 7)])

  0       1       7
.+.--   .-+=.   #+++#
+.-.#   -##.-   -.--+
#===#   --+=-   -==+.
#--.+   -+#.-   ..#.-
.+.--   -+.+-   -=+-.

The neuron for 0 wants ink in the two outer columns and is strongly against ink in the middle of the third row: there the 0 is blank, while 8, 3 and 2 have ink. The neuron for 7 wants the whole top row and the third column at the bottom. The neuron for 1 wants the two pixels at the top middle (.##.) and is against the bottom left corner, where 2 and 5 have ink.

Nobody told the network where the stroke of the 7 is. The weights were found from the examples alone. They are not a copy of the digit: a neuron also looks at where its digit differs from the others.

Try it

Fill in

The last lines of softmax. What is every number divided by, so that the ten add up to 1?

for k in range(10):
    p[k] /=

The idea

One pixel to the side

The till sometimes prints a digit a little to the side, and the photo is taken at an angle. Here are three digits from the font, without smudges, moved one pixel to the right:

# the same digit, printed one pixel to the right
def shift(rows):
    return ["." + row[:4] for row in rows]

net = train(train_x, train_y, rng)
digits = [1, 3, 7]
print_side([shift(DIGITS[d]) for d in digits])
for d in digits:
    p = net.predict(pixels(shift(DIGITS[d])))
    print(f"{d} → {best(p)} ({p[best(p)] * 100:.1f}%)")

...#.   .####   .####
..##.   .....   .....
...#.   ..###   ....#
...#.   .....   ...#.
..###   .####   ...#.
1 → 4 (57.1%)
3 → 9 (77.7%)
7 → 9 (39.0%)

The network that gets 29 of 30 smudged digits gets all three wrong. Of all ten moved digits only the 9 comes out right, and with 53.8%.

The reason is in the weights. Every weight is tied to one pixel in one place. The neuron for 1 expects ink in the middle column. The moved 1 is in the fourth column, and ink there is what the neuron for 4 expects. For the network the same shape in another place is another picture: it does not know it has seen “a stroke”, it only knows which pixels are ink.

That is why the training data has to look like the real data. If digits move around on the photos, the training examples have to move too. Or the network has to be of another kind, one that looks for the shape everywhere (see “More”).

Try it

Find the bug

A colleague writes a report on the accuracy of the network and says “100%”. On customers' receipts the network makes mistakes. Which line has the bug?

Pick the line with the bug.

The idea

When it hurts

Confidently wrong. The only mistake on the test set is a 3 with a smudge in the middle that the network reads as a 9 with 91.2%. The probability is how sure the network is, not how right it is. When a mistake costs money, the threshold for “sure” is checked on a test set, and a person looks at the doubtful digits.
Anything it has not seen. A shift, another font, a tilted photo, a handwritten digit: the network has only seen the font with smudges and knows nothing else. To it every picture is one of the ten digits, even an empty square or a letter.
Little data. 60 pictures are enough because there is one font and the digits are 5 × 5. A photo of a real receipt needs thousands of examples and a bigger network.
No network needed. If the till also sends the total as text, or prints a QR code on the receipt, read that. Recognition is for the cases where there is no other way.

More precisely, if you are curious

Softmax as a formula. The sums of the ten neurons are s₀ … s₉. The probability of digit k is:

p[k] = e^(s[k]) / (e^(s₀) + e^(s₁) + … + e^(s₉))

In words: make every sum positive with e to the power of the sum, then divide by the total. With two digits this is the sigmoid from logistic regression: softmax is its extension to more classes. Subtracting the largest sum does not change the result, because e^(s − m) = e^s / e^m, and e^m cancels out.

Why the slope is p[k] − 1. The error for one picture is L = −ln(p[y]), where y is the right digit (cross-entropy). Its slope by the sum of neuron k comes out very simple: p[k] − 1 for k = y and p[k] for the others. If the network gives the right answer 98%, the push is only −0.02. If it gives it 10%, it is −0.9. From there backprop goes on to the weights as in the earlier lessons: the slope by weight i is the slope by the sum times pixel i.

Why there is no hidden layer. With 10 neurons straight from the pixels, every weight is for one pixel and one digit, so the weight map can be read. With a hidden layer the network gets more right, but the maps of the hidden neurons are a mix of parts of several digits and hard to read. Try it in the exercises.

Networks for pictures. Real networks for pictures are convolutional (CNN): a small window of weights, say 3 × 3, slides over the whole picture and looks for the same shape everywhere. A stroke is a stroke on the left and on the right, so a shift hardly bothers them. The classic example is MNIST: 70,000 handwritten digits, 28 × 28 pixels. In PyTorch the window is nn.Conv2d.

The same numbers in four languages. The programs print the probabilities with one decimal, and the bars are rounded to 20 parts. The lesson checks that no bar and no weight sits exactly on a rounding boundary, so the output is the same in Java, C#, Python and JavaScript.

Exercise

The total on the receipt

Solve it in your editor.

The total on the receipt is €12.90: the digits 1, 2, 9 and 0. The till printed the last digit one pixel to the right, and the photo has smudges. Make the four pictures (the last one moved, all of them smudged with the same generator, after training), recognise each one and print the digit and its probability. If the probability is below 90%, mark the digit to be checked by hand and put a ? in its place in the total.

digit 1: 1 (97.0%)
digit 2: 2 (94.4%)
digit 3: 9 (90.5%)
digit 4: 7 (37.4%) → check by hand
total: €12.9? → check by hand

The moved 0 becomes a 7, but only with 37.4%, and the threshold catches it. The 9 passes with 90.5%, a hair above the threshold. The threshold does not make the network smarter, it tells you when not to trust it. A receipt with a ? goes to a person, not to accounting.

More exercises

Moved examples. Add to the training data every digit of the font moved one pixel to the left and to the right, and train again. How many of the ten moved digits does it get now? And how many on the test set?
A hidden layer. Put a hidden layer of 16 neurons with a sigmoid between the pixels and softmax. Print the weights of two hidden neurons as a picture. Does any of them look like a digit?

Test

Check yourself

1. How does the network see a 5 × 5 picture?As 25 numbers: one for every pixel, row by rowAs 5 numbers: one for every rowAs edges and lines it finds on its own

2. The network gives 98.4% for 7 and small numbers for the other digits. What do the ten probabilities add up to?The sum of the weightsIt depends on the pictureExactly 1 (100%)

3. The 1 is printed one pixel to the right, and the network says 4 with 57.1%. Why?There are too many smudges in the training dataThe network is undertrained: more epochs will fix itEvery weight is tied to one pixel: the moved digit lands on the weights of another digit

4. A colleague reports 100% accuracy, measured on the 60 digits the network learned from. What does that say about new receipts?That smudges do not matterThat the network will read every digitAlmost nothing: the measure for new receipts is the test set the network has not seen

5. The network reads a 3 from the test set as a 9 with 91.2%. What follows?The network is broken and has to be trained againProbabilities above 90% are always rightA high probability does not mean a right answer

The digits on the receipt

Cookies