Reading like a robot

Overview

The question. A computer only stores 0s and 1s. So how does it recognise a letter we write by hand on a screen or on an envelope? The activity answers with a real method, simplified enough to fit on an A6 card: the picture becomes a grid of 35 bits, the grid becomes a vector, and the vector is compared with the vectors of the letters the robot already knows. The most similar one is the answer.

What the pupils learn. By the end of the lesson, the pupils should be able to:

• turn a simple picture into a grid of 0s and 1s (binarise it) and explain what is lost;
• write that grid as a single row of bits (a vector) and say what it is for;
• compare two vectors position by position and decide which is more similar, using a simple measure;
• explain why counting only the matches fools the robot, and why counting the differences (the Hamming distance) solves the problem;
• point out two or three ways in which real recognisers go further.

What the pupils do. Five levels of A6 cards, each with one new step: writing bits (level 1), deciding and writing the vector (level 2), recognising a letter by comparing it with the memory (level 3), finding the flaw in the measure and replacing it (level 4) and challenges in pairs (level 5). Each pupil gets a different letter in levels 1 and 2, which gives them something to compare with the classmate next to them.

Links to other lessons. In Faíscas, this lesson comes after «Portas lógicas» (Logic gates), where the pupils have already seen that a computer works with 0s and 1s, and before «Comandar um robô» (Commanding a robot). If the class has not done the previous lesson, the section «Background for the teacher» has what you need.

Before the lesson

Prior knowledge

• Counting up to 35 and adding up seven small numbers.
• Reading a grid by rows and columns (like a table).
• Knowing what a bit is helps, but is not necessary: the activity defines it on slide 5 (“a coloured circle is 1, an empty one is 0”).

What to prepare

• Open Slides (PDF) in full screen and check that the handwritten letter on slides 3 and 5 can be seen clearly from the back of the room.
• Print and cut out the cards (see the table). Cut each sheet in half vertically and horizontally along the marks; the marks are in the margins and in the centre of each sheet.
• Sort the cards by level into five piles. Shuffle each pile: pupils sitting next to each other should get different letters.
• A pencil and a rubber for each pupil. A ruler helps to follow the rows of the grid in levels 3 and 4, but is not necessary.

What to print

The cards are in A6 sheets (PDF), in black and white, four A6 cards per A4 sheet, each sheet with cards from one level only. We recommend printing single-sided, because the cards are cut out and handed out one by one.

General rule for a class of $𝑛$ pupils: levels 1, 2 and 3, $\frac{𝑛}{8}$ copies of their two pages (rounded up); level 4, $\frac{𝑛}{2}$ copies of page 7; level 5, $\frac{𝑛}{8}$ copies of page 8. In the 60-minute lesson, 24 pupils need 33 A4 sheets and 28 pupils need 42. In the 45-minute version, without level 5, 24 pupils need 30 A4 sheets and 28 pupils need 38. The class pack, on the lesson page, does these sums for any class and puts the pages in the right order.

A4 sheets (PDF) has the same 32 cards, one per page, enlarged to twice the size. It is for pupils who need larger print and cells, for projecting a card, and for anyone who prefers each exercise on its own page.

Timings

45-minute version. Opening 4, level 1 8, level 2 8, level 3 12, level 4 8 (one card of 4.1/4.2 and one of 4.3/4.4, as in the 60-minute lesson), closing 5. Level 5 is left for those who finish early or for a second lesson.

Lesson plan

Background for the teacher

Binarising: from the picture to the bits

A camera captures millions of pixels, each with a colour. Here we reduce the picture to 35 cells (5 columns × 7 rows) and to two values: 1 if the letter goes through the cell, 0 if it does not. Information is lost, on purpose: that is the price of having something small that can be compared quickly. The 5×7 grid is the one used by many old text displays, where each character was drawn with 5×7 dots. Slide 6 deals with the decision for the cells on the boundary; in real systems the same difficulty leads to using shades of grey (how much of the pixel is covered) instead of just 0 and 1.

Everyone’s handwriting

The letter that goes into the robot is always a letter written by someone, and no two people ever write the same letter in the same way: the slant, the width, a shaky hand and the pen all change the stroke, and the stroke changes the grid. The same A written by three people:

00100001000101001010011101000110001

blue pen, upright · 13 bits set to 1 · 0 differences from the model

00100001000100001010011100100110001

pencil, slanted · 12 bits set to 1 · 3 differences from the model

00100001000101001010011101001010001

fine pencil, shaky · 13 bits set to 1 · 2 differences from the model

Between these three As there are 3, 2 and 5 different cells; the model A in the memory is 0, 3 and 2 differences away from each of them. That is why the activity always starts from handwriting (the cards have letters by four different hands, and on cards 2.7, 2.8 and 5.4 the hand is the pupil’s own) and why a robot with only one model per letter ends up failing: the next section and level 5 show where.

Matrix and vector

The grid is a matrix of 7 rows and 5 columns. To store and compare it, it is flattened into a row of 35 bits, the vector: row 1, row 2, up to row 7. This is called flattening, and it is literally what happens in a computer’s memory, where everything is a sequence. Two letters on the same grid give vectors of the same length, which makes it possible to compare position 1 with position 1, 2 with 2, up to 35. On the cards, the comparison is done row by row on the grids, which is the same thing without the row of 35 digits, which is harder to follow by eye.

Measuring similarity: matches or differences

With two vectors $𝑥$ and $𝑦$ of 35 bits, the measure in levels 3 and 4 (first part) counts the positions where both have a 1:

This is the dot product of the two vectors. The bigger it is, the more alike. The flaw: it only sees what matches. A letter in the memory that contains the letter read (E contains L) ties with the right answer, and a vector that is all 1s (the “blot”) matches everything, so it always ties or wins. In other words, the measure favours whoever has more 1s.

The measure in level 4 (second part) counts the positions where the two vectors differ:

This is the Hamming distance. The smaller it is, the more alike; the letter itself gives 0; the blot gives 35 minus the number of 1s in the letter read, because each 0 in the letter is a difference. That is why the blot no longer beats the right letter, although it may end up closer than another letter in the memory (on card 4.2, the O read is closer to the blot than to A). The worst possible result, 35, is that of the opposite vector, with a 1 wherever the letter has a 0 and a 0 wherever it has a 1. The Hamming distance counts what is missing and what is extra, and so it does not have the earlier flaw. For vectors of 0s and 1s it is also the square of the Euclidean distance, the “straight-line distance” between two points, which links this activity to the geometry the pupils know.

Ties

With either measure there can be a tie (card 5.1: the shifted I is the same distance from I and from T). A real system can choose at random, ask for more information (which letter comes before and after it in the word), or declare that it is not sure. A good question for the class: “If you were the robot, what would you do?”

What real recognisers do differently

The activity’s method is the nearest neighbour: examples are stored and the most similar one is chosen. It is a real method and, with a bigger grid and many examples per letter, it works well for handwritten digits. Real systems differ in five ways that are worth telling the pupils, without exaggerating any of them:

1. Bigger grids and shades of grey. A classic reference, the MNIST set of handwritten digits, uses 28 × 28 = 784 pixels, each with a shade of grey, instead of 35 bits.
2. Many examples per letter. Instead of one model for each letter, thousands of examples written by different people; the letter read is compared with all of them, and the decision can be made by a majority of the $𝑘$ nearest.
3. Normalisation. Before comparing, the letter is centred and resized, which solves the problem of card 5.1. Systems are also trained with shifted and rotated versions of the examples.
4. Learnt features. A neural network does not compare pixel by pixel; from the examples, it learns which combinations of pixels (a horizontal stroke in the middle, a closed curve) tell the letters apart.
5. Context. A word reader uses the letters before and after, and a dictionary; a number-plate reader knows the format of number plates.

The table of differences on card 5.2 shows what stays the same: even in real systems, confusions happen between the classes whose representations are closest.

Solutions

Each handwritten letter was drawn afresh for this edition, by four “writers” with different hands; the solution is the grid obtained with the rule on slide 6. In levels 1 and 3 the circles are already coloured in, so there is no leeway; in level 2, accept one or two different cells near the edge.

Level 1 — From the letter to the bits

Level 2 — From the grid to the vector

Levels 3 and 4 — comparisons

For each card: the grid of the letter read and, for each letter in the memory, the seven counts per row and the total. In level 3 and on cards 4.1 and 4.2, matches are counted (the biggest wins); on cards 4.3 and 4.4, differences are counted (the smallest wins).

Level 5 — Challenges

Common mistakes and how to respond

Inclusion

The activity is all on paper, with no long reading, and each level has only one step; even so, some adaptations make a big difference for some pupils.

Extensions

• A whole alphabet. Each pupil draws a different letter and writes its vector; the class puts the 26 together and, using the table of differences from card 5.2, looks for the pairs that are most alike.
• Shades of grey. Repeat level 1 with three values per cell (0, 1 and 2, depending on whether the letter covers little, some or a lot of the circle) and see whether the comparison becomes more reliable.
• Several samples per letter. Store three different As in the memory instead of one and decide by a majority among the closest; discuss why real systems store thousands.
• Words and context. Give the pupils a word in which one letter ties between two possibilities (for example, “QU_CK”) and see how the context solves what the distance cannot.
• Pictures instead of letters. The next activity, «Ver como um robô» (Seeing like a robot), describes pictures by their features and uses the same kind of comparison.

Checking what they have learnt

Five quick questions, out loud or on half a sheet of paper, at the end of the lesson.

1. How many bits does a grid of 5 columns and 7 rows have? 35.
2. What is the vector of a letter? The rows of the grid written one after another, in a single row of 35 bits.
3. Why does counting only the 1s that match fool the robot? Because it ignores what is extra: a letter that contains the letter read, or a blot that is all 1s, ties or wins.
4. How do you count the Hamming distance between two letters? Position by position, counting the positions where one has a 1 and the other has a 0; the smaller it is, the more alike they are.
5. Name one thing that real recognisers do and that we did not do. Bigger grids with greys; many examples per letter; centring the letter before comparing; learning the important strokes; using the context. Any one of these will do.

Sources and credits

Activity created for Primeiros Bits (Instituto Superior Técnico and TreeTree2) and also used in the Faíscas programme. This edition reorganises the levels, adds levels 4 and 5, replaces the handwritten letters with new drawings and brings together the background and the solutions. The letters, the grids and the solutions were generated by a program from the same skeleton for each letter, so the solutions can be checked. Contact: faiscas@treetree2.org · faiscas.pt