Tuesday, August 24th, 2010...7:51 pm
Digit recognition with Pythagoras
Classifying handwritten digits is an issue, for instance, for the postal service. Automating the process of reading zip codes, for instance, can increase efficiency of mail sorting.
To explore this idea, we will use the MNIST database of handwritten digits, which contains a training set of 60,000 digits and a test set of 10,000 numbers. Each digit in the database was placed in a 28 x 28 grayscale image such that the center of mass of its pixels is at the center of the picture. For instance, below we see four different examples of the number 3 from the dataset. Can we create an algorithm to automatically recognize that each of these is the digit 3?
There are a variety of interesting and even complex algorithms for digit recognition. Let’s develop a simple method that uses only finding the average of an array of numbers and the Pythagorean theorem.
A mean digit
Let’s call a digit we want to classify a test digit. We’ll store each digit as a vector where each entry in the vector is the grayscale value of one of the pixels in the corresponding 28 x 28 image. So, the information for this test digit is stored in a 784 x 1 vector that will be called the test vector. While we could test this test vector against each training vector and see which is closest to it, let’s try something a bit different.
There are 5,923 images of the number 0 in the training set. Rather than compare our test digit to each of these images, we will create an average handwritten 0 from this training set. Let the ijth pixel of this average zero equal the average of the ijth pixel in all the images of a zero in the training set. Let 
The notation could make this look trickier than it is. Keep in mind this is only averaging the pixels, for instance, in the upper left hand corner of all the images of our training digits for the number 0 to find the pixel value in the upper left hand corner of our “average 0” image.
Our algorithm is then simple. Suppose we find the norm between the vectors for the test digit and each average digit computed above. Whichever average digit produces the smallest norm with the test digit indicates how we will classify the test digit. For instance, if the smallest norm comes from the vectors for the average 4 and the test digit, then we classify the test digit as a 4.
How do we do? What do the digits look like? If we compute an average digit for all the numbers from 0 to 9, we get the images below:
Let’s concentrate again on the number 3. This method recognizes that all threes below (which are the same four seen above) are indeed the number 3.
But, those complicated algorithms for digit recognition exist as it can be difficult to fully recognize handwritten digits. Sometimes, we write fast and some of us, frankly, have hard to read handwriting! The digit we see below is a 3 but is classified as a 5. See why? Not too hard to see the elements of the digit 5 that are within it.
Nonetheless, this is a simple and accessible way of classifying digits thanks to Pythagoras and a 784 dimensional version of his theorem!
