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
| 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 |
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
- Open a file containing training or test data.
- Browse examples contained in an open file.
- Select an example and visualize it using your user control.
- View the perceptron's prediction for a user selected example.
- Set the perceptron's learning rate.
- Train (and retrain starting with the current weight vector) the perceptron using the current training data.
- Calculate the perceptron's test and training error.
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.