Problem Set 3: Handwritten digit classification
[Due 2/24 at 11:59pm]

In this this assignment you will implement a perceptron that learns to classify images of handwritten digits as 3s or 5s. You program will also provide a gui to visual data and control the perceptron.

Work on this project with a partner. Email Jeff if you will be working with someone different than in problem set 2.

All code you write must be documented.

Turn in your solution by email. Please email Peter-Michael all source, project and solution files needed to compile your project. Additionally, include a plain text or pdf file with your answers to part 6 and, if you so choose, the optional challenge problem.

Overview

In this problem set, you will use a perceptrons to classify handwritten digits as 3s or 5s. As discussed in lecture, a perceptron is a system for classifying data. A perceptron takes an example (expressed as a feature vector) and predicts how that example should be labeled. The February 11th lecture notes describe the main perceptron operations: prediction and update.

Data and Labels

In this problem set, examples are low resolution pictures of handwritten digits: either 3s or 5s. These images are stored in two input files: 35 TrainingData.txt and 35 TestData.txt. The first contains 1400 labeled images for training your perceptron, and the second contains 1400 labeled images for testing it. Images are 8 by 8 pixels in size, and each pixel is either black or white. Input files are made of lines of the form label: x1 x2 . . . x64 where label is one of three or five and each xi is either 1 or -1. This encodes an image when we line up the xs as,

x1 x2 x3 x4 x5 x6 x7 x8
x9 x10 x11 x12 x13 x14 x15 x16
. .
. .
. .
x57 x58 x59 x60 x61 x62 x63 x64

and interpret values of -1 as white and 1 as black.

For example, consider the input line

three: 1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 1 1 1 -1 -1 .

This should be arranged into the grid
1111 1-1-1-1
1-1-1-1 11-1-1
-1-1-1-1 111-1
-1-1-1-1 -1111
-1-1-1-1 -1-111
-1-1-1-1 -1-111
-11-1-1 1111
1111 11-1-1

Drawing each -1 or 1 as white or black yields the following image.

                                       
         
         
         
         
         
         
         

For simplicity we will use an each of an image's pixels as a feature. That is, the data instance x1 x2 . . . x64 simply maps to the feature vector <x1, x2, . . . x64>.

Training and Testing the Perceptron

As noted above there are two data sets: one for training and one for testing. Training data is used initially to train the perceptron with the update rule. Both training and test data can be used to evaluate its prediction accuracy.

Initially your perceptron will start with no “knowledge.” By iterating through the training data, and applying the update rule at each step, the perceptron will refine its prediction capability. Taking multiple passes through the training data may lead to further improvements, but eventually the perceptron's behavior should stabilize.

After training, we can quantify the perceptron's abilities by calculating error rates. There are two interesting rates. Training error is calculated by running the trained perceptron without the update rule (i.e. only making predictions) on all examples in the training data set. The training error is the percent of examples on which the the perceptron produce an incorrect prediction. In contrast, test error is calculated by running the same experiment on the test data set. The test error represents the perceptron's ability to classify examples that it has not yet seen.

Part 1: The Pair Utility Class

Write a generic class, Pair, that implements the IPair interface located in IPair.cs. A Pair<S, T> object represents an structure containing an S and a T. As described in IPair.cs, Pair objects should be immutable: Once an object outside of the Pair class has seen a particular a Pair object, that Pair object should never change. In addition to the implementing IPair, give Pair a two argument constructor, public Pair(S s, T t).

Part 2: The Vector Class

Write a class, Vector, to represent linear algebra style vectors. Your Vector implementation must be sufficient to solve Part 3, but is otherwise unconstrained.

Part 3: The Perceptron

Implement the IPerceptron interface (from IPerceptron.cs) with a class that carries out the perceptron learning and prediction as discussed during the February 11th lecture.

Part 4: Build a Data Visualizer

Implement a user control to display a handwriting example as a black and white image.

Part 5: Design a “Perceptron Workbench”

Build a gui that can drive your project. From the gui the user must be able to

Part 6: Learning Rate

Explore how adjusting the learning rate effects the perceptron's behavior. Write a concise summary explaining what you found. In this setting does learning rate have a large or a small effect on error rates?

Challenge Problem: Feature Selection

Add additional features to the feature vectors. Write a short summary explaining what you did and how it effected the perceptron's behavior.