Pattern Recognition, Winter 2002-3

Discussion of the course outline.

We will concentrate on the classification of hand-printed digits.

Applications for this work includes ZIP code mail sorting, census and tax form processing.

Pattern recognition consists of two principal aspects, extraction of d numerical features from the unknown objects and then performing decision making in the d-dimensional space.

If the situation is nice (it is not always nice), the feature vectors for the various categories are easy to separate using some simple computational rule, such as a linear (matrix) operation.

Programming assignments will make up a large part of the Pattern Recognition course. You can do the work in the language of your choice I recommend J, MatLab, and IDL for the expressivity for these applications. MatLab is particularly easy to learn.

There will be four laboratory programming assignments which will be due the first day of Quarter weeks 3, 5, 7, and 9. A large exercise (you will participate in selecting) is due the last day of the Quarter's finals' week. More details about the large project will be available later, but you should begin thinking about what you would like to do in depth as soon as possible.

You could consider the large project as part of a pre-proposal for a dissertation.

The most important part of your submission is the discussion, the plan of the exercise, the analysis of the outcome. Submit the report along with the program listing and the outputs (summarize voluminous output with graphs).

This is an advanced, graduate course, so the specific details of each programming assignment will often be up to interpretation. That interpretation (determination of the detailed functional requirements) is up to you. We can discuss these issues as they come up. We will use email, phone calls, and office hours.

I prefer written material delivered in hard copy, prepared using LaTeX. Other methods, in decreasing order of preference, are html and Word. You can send me email attachments or a URL.

There will be four written assignments, generally taken from the exercises of the text book.

The due dates for these is the same as the programming exercises.

Resources

• Bell Labs's digits
• 4179 digits
• 15,000 digits. This file has:
  1413 0's
  1229 1's
  1176 2's
  1751 3's
  1563 4's
  716 5's
  1799 6's
  1859 7's
  1680 8's
  1814 9's
  
• 100,000 digits. There are more digits here in individual files in subdirectories, as follows:
  Census_digits/0: 9851
  Census_digits/1: 8670
  Census_digits/2: 10617
  Census_digits/3: 11079
  Census_digits/4: 11273
  Census_digits/5: 10171
  Census_digits/6: 10127
  Census_digits/7: 10879
  Census_digits/8: 9631
  Census_digits/9: 8117
  They are all packaged in a single file: Census_digits/100K-census-normalized.zip
  Before a kind student normalized them, they are in: Census_digits/census_digits.tar
  An abbreviated version is in: Census_digits/abbreviated.tar
• A subset of 1600+ of the 100,000 digits is in the directory: Abbreviated_census.

Assignments

• Programming Assignment #1.

  Demonstrate that you can create some graphs and access and process the digit image files.

  The digit images are available is: http://www.cs.rit.edu/usr/local/pub/pga/Images/Digits/

  There is a "read-me" file in that directory.

  • Create and plot some pseudo-random 1- and 2-dimensional scatter data. Experiment with normal distributions. Plot scatter diagrams and histograms.
  • Extract some numerical feature data from the digit image files. Plot the scatter plots for some pairs of features and some histograms for single numeric features.

  Some recommendations for numerical features are:

  • x and y coordinate of the center of mass (this is the "first moment" -- black pixels are considered to have mass=1).
  • Higher moments, as in Physics-I.
  • Black pixel count in sub-windows, e.g., in each quadrant.

  • The easiest set of files to do this work with is the Bell Labs's digits ("DigitsBTL"). You can look at them individually using a web browser or download the entire set in the tar file. the Census Digits are richer: they are not 100% properly classified, they are not normalized to a fixed image size, and there are about 100,000 of them.

• Programming Assignment #2.

  For detailed specs (with LaTeX math), please see either postscript or pdf

  By now, you should be comfortable with data files in general, and with plotting. You are, here, asked to generate some artificial data according to some parameters, then see whether you can extract those parameters back from the data. Also, you will construct some simple, two-category classifiers.

• Programming Assignment #3.

  In the previous exercises, you worked with data clouds in d-space: artificial clouds in 2-space and clouds corresponding to d numeric features for hand-printed digits.

  Now, use both of those data clouds for other methods, as described below. for the artificial 2-dimensional cases, plot the information (e.g., decision surfaces) you obtain.

  • Apply principal component analysis to the data clouds.
  • Construct nearest neighbor classifiers using the single nearest neighbor and the three nearest neighbors (3-NN) to classify the points according to two categories.

    Divide the data clouds (randomly) into two halves each, for training and testing.

    Report the outcomes of these experiments by constructing confusion matrices for nearest neighbor classification and for the previous methods (section 2.6, Mahalanobis distance).

  • Estimate analytically and by experimental timings the computational complexity of the nearest neighbor methods.
  • Replace the training sets for the nearest neighbor methods with significantly smaller sets, re-perform the experiments, determine the time speed-up, and the classification accuracy loss.

    Write a one-page (250--300 word) analysis of this experiment. Include suggestions for future experiments.

• Programming Assignment #4.

  For detailed specs (with LaTeX math), please see either postscript or pdf

Weekly Plan

• [December 2, 4] Week 0 Introduction
  [1] (reading assignment are in brackets)
  Identification of the character image data sets
  Software to manipulate the images
  
  
• [December 9, 11] Week 1 Bayesian decision making
  [2.1-5]
  discrimination functions
  risk
  confidence
  
  
• [December 16, 18] Week 2 Normal Distribution
  [2.5-6, 3.1-5]
  creation of normal distributions
  determination of parameters from data
  determination of decision functions from normal parameters
  Mahalanobis distance
  
  
  
• [January 6, 8] Week 3 Dimensionality identification and reduction
  [3.7-8]
  over-fitting
  computational complexity
  principal component analysis
  Fisher's linear discriminant
  
  
  
• [January 13, 15] Week 4 Non-parametric density estimation
  [4.1-5]
  Parzen windows
  Nearest neighbor
  K nearest neighbor
  
  
• [January 20, 22] Week 5 Linear discrimination and perceptrons
  [5.1-8]
  supervised training
  perceptron training
  delta rule
  Pseudo inverse, linear regression
  
  
• [January 27, 29] Week 6 Character recognition algorithms
  [References to be supplied]
  Polynet
  
  
• [February 3, 5] Week 7 Multilayer NN training
  [6.1-8]
  backprop
  
  
• [February 10, 12] Week 8 Heuristic search techniques
  [7]
  Feature set selection
  Nearest neighbor pruning
  Genetic programming
  
  
• [February 17, 19] Week 9 Cluster analysis
  [10]
  Leader algorithm, adaptive resonance
  K-means
  Kohonen network