Homework 1 -- Due Monday September 14, 5:00PM


Homework policy: no late homeworks will be accepted without prior permission from the instructor.

Homeworks are to be turned into Ferris Hall 355.

Getting Familiar with the MNIST Database

This assignment concerns perceptron learning. You are to train a single perceptron to recognize some digits from the MNIST Database. See the MNIST Database of Handwritten Digits homepage for more on these databases. I've made the available available locally as the following four files. If you are using Netscape you might hold the shift key down before clicking on these images to avoid using Netscape's decompression. You can then decompress them after downloading.
  1. Test images: t10k-images.idx3-ubyte gzipped(t10k-images.idx3-ubyte.gz) or zipped (t10k-images.idx3-ubyte.zip)
  2. Test labels: t10k-labels.idx3-ubyte gzipped (t10k-labels.idx1-ubyte.gz) or zipped (t10k-labels.idx1-ubyte.zip)
  3. Training images: train-images.idx3-ubyte gzipped (train-images.idx3-ubyte.gz) or zipped (train-images.idx3-ubyte.zip)
  4. Training labels: train-labels.idx1-ubyte gzipped (train-labels.idx1-ubyte.gz) or zipped (train-labels.idx1-ubyte.zip) Note that to write a successful program you must make some sense of the file formats of these databases. To help some, a small java application is provided which extracts an arbitrary characters as a .ppm file. (More on the ppm format later.) Also included are some unix shell scripts which call the java program appropriately. For example, one of them pipes the output directly into the graphical viewing program xv. Even if you are not a java programmer, you might get some insights on how to read from the MNIST database. Here are the files: Want to download MNISTTools these tools? Great. Here they are tarred and gzipped (MNISTTools.tgz) or zipped (MNISTTools.zip) To run this code, you must have the java environment installed on your machine. But the best way to use this code is to simply print it out and look at it. Hopefully it will help you write your own drivers to read from the MNIST database and print the characters. Note: You are not required to use this code. This is only to point you in the right direction.

    Part I -- A Perceptron Learning Program (75%)

    Choose two numbers between 0 and 9 (at random if you feel up to it...) Train a single perceptron to learn to signal +1 when it encounters either of those two numbers and -1 when it encounters any other number.

    You should follow these guidelines for Part I:

    You should turn in the following for Part I:
    1. All source code
    2. A brief overview of how you implemented your project, including what two numbers you chose to learn and the parameters which worked the best.
    3. A graph of error over time (%-failed on y axis, time on x axis). How many data points? Well, you should test for error using the testing set "as often as is necessary" to get a good picture of learning.
    4. An animation of the weightspace as it changes over time. This will allow you to watch learning progress. We suggest writing the weights matrix fairly often to a commin graphical file format called portable pixmap (.ppm). From there you can translate into .gif and finally to animated gif. Here is more information on creating a good animation. (Note: if you can't get this to work, print out graphs of the weight matrix as it changes for a minor loss of credit.)
    5. Except for the animation, all material should be printed out. The animated gif can be emailed to Doug (email at bottom of this page).

    Part II -- Two Questions to Hand In (12.5% Each)

    You should turn in for Part II brief answers to these questions:
    1. (a) The perceptron may be used to perform numerous logic functions. Demonstrate the implementation of the basic binary logic functions AND, OR, and COMPLEMENT. (b) A basic limitation of the perceptron is that it cannont implement the EXCLUSIVE OR function. Explain the reason for this limitation.
    2. Learning is like politeness: too much of it reverses the intended effect. (a) Explain why over-learning can hamper the performance of a network. (b) Suggest a method for guarding against such failure.

    Part III -- Required Extra Work for Pairs (part of Part II)

    Hint: it's not that much extra work. And your instructors strongly suggest that you work in pairs.

    Train the network to discern between a single number between 0 and 9 and the rest of the numbers in the training set.

    1. Turn in the same graphs you turned in for Part I.
    2. Explain the differences in performance between this single number case and the two-number case from Part I.
    3. Briefly describe how you divided the work.

    Last modified: Mon Aug 31 16:57:32 MDT 1998