Assignments

Submission Instructions: Please submit your programs and write-ups for each programming assignment through the MyCourses dropbox for the assignment (link above). All programming projects are to be completed individually.

Information on obtaining and using the MNIST handwritten digit dataset is provided below.

Assignment 2 (Due Friday, Nov. 19th, 9am)

Note:Projects submitted later than the deadline will receive a 0.

Using the designated drop box in MyCourses, please submit a single .zip file containing 1) your assignment write-up as a .pdf file, 2) a README summarizing how to run your programs, and 3) your MATLAB code for the assignment.

You will be using the MNIST data for each of the questions below. All programs should be implemented in MATLAB, using the PRTools library for visualization and error reporting.

1. Write functions to convert the MNIST data matrices (784 element pixel intensity vector) to each of the following feature representations:
   1. Simple projection profiles of the image: this is the sum of image intensity values lying within fixed ranges in the horizontal and vertical directions. To reduce the dimensionality, use bins of width 7 (producing 4 bins in the each direction). The combined feature vector should contain 8 elements.
   2. The first 7 Hu moments.
   You may use methods built-in to PRTools for this portion of the assignment. You may scale and/or normalize the features if you wish.
2. Implement two of the following algorithms. Note that the code should be your own, and not make use of the implementations provided by PRTools.
   1. A decision tree construction algorithm using entropy as the impurity measure, using critical-value pruning with the Chi-squared test after building the complete tree, allowing the pruning value to be provided as an argument.
   2. A multi-layer perceptron construction and learning algorithm, where the sigmoid function is used as the activation function, with the number of layers and nodes in each layer provided as an argument.
   3. A function that constructs one 1-versus-all support vector machine for each class, and combines them to produce a final result. You may use the MATLAB quadratic programming solvers (e.g. quadprog) to determine the support vector weights.
   Implement the functions so that the result is a PRTools `mapping' (classifier); this will allow you to use your classifiers with the existing PRTools utilities (see the PRTools manual for details on how to implement mappings).

   In the write-up, describe your implementation of the two classification algorithms that you selected, along with any design decisions that you made.

3. Select 100 instances from each class (1000 instances total) to be used as your training set. Then report the error rates and confusion matrices for each of your classifiers on the complete MNIST test set. For each classifier, train and test using each feature representation (4 runs in total).

   In the write-up, provide tables summarizing the classifier error rates and provide the confusion matrices. Discuss the results in terms of properties of the algorithms that you implemented, including anything arising from design decisions made for your implementations.

4. Using your available features and classification functions, produce an ensemble of classifiers that out-performs your set of base classifiers. You are welcome to use the PRTools combiners, adapt them, or implement a combination of your own. Present the error rate and confusion matrix for the best combination that you produce, and compare this with the results from the previous question (using the same training and test sets).

   In the write-up, again present the error rates and confusion matrices, compare the performance of the base classifiers and your classifier ensemble, and then discuss the observed result for the combination.

• prwaitbar('off') can be used to get rid of the PRTools progress bar.
• You are welcome to compare your algorithm implementation results with those produced by the PRTools implementations (e.g. to assist with debugging).

Assignment 1 (Due Thurs, Sept. 23)

Submit a .pdf document providing your figures and comments for each question, all MATLAB programs needed to run your experiments, and a textfile named 'README' briefly explaining how to run your code using MATLAB/PRTools, and identifying which program corresponds to which question.

1. Use the raw MNIST image vectors for classification, using the entire training and testings data sets. Report the differences in the performance between linear and quadratic 'Bayesian' classifiers, as well as 1-NN and 3-NN classifiers, for the case when errors have uniform cost and all class priors are equivalent. Then briefly discuss the results, in terms of differences between the classification techniques.
2. Repeat the experiment in part 1, using all 10000 test samples, but only 1000 training samples (100 per class). Again, comment on the results.
3. Using the data from Question 2, Define two real-valued features to represent the appearance of the digits, and create a new data set (again, with 100 symbols per class). Create a figure showing the distribution of the training data in feature space, and the decision boundaries produced by each of the four classifiers. Then report the accuracy of the classifiers on the full MNIST Test data, and comment on the result.
4. For this question, produce a binary classifier for discriminating 0-1 using 100 of the available 0's and 1's from the MNIST training set.
   1. Create a figure showing the distribution of the training data in feature space, and draw the decision boundaries for each of the four classifier types (linear, quadratic, 1-NN, 3-NN).
   2. Report the observed recognition rate for the classifiers when testing only on 0's and 1's from the complete MNIST test set.
   3. Introduce a 'rejection' option into your binary classifier, and create a figure to illustrate the training data and resulting decision boundaries. Briefly describe the design of your reject option, and report results for testing using all test digits for classes 0, 1, 7, and 9 (7 and 9 should ideally be rejected).

PRTools Data and Utility Functions for MNIST

Make sure to first check that you have properly installed PRTools, and put the directory containing the prtools files in the MATLAB search path. To obtain the MNIST data set, download the files stored here, and place them in a directory within your MATLAB search path. The training and testing sets are raw image data: each feature vector is a 28 x 28 image, stored as a single vector with 784 elements.

• Loading: You can load the 60,000 training images using the command load mnist_train, and the 10,000 testing images using the command load mnist_test. These will define PRTools datasets in your workspace named Train and Test. To see a description of their contents, use struct, e.g. struct(Train).
• Viewing Images: use the PRTools 'show' command to view images (issue 'help dataset/show' in MATLAB for details). Once you have loaded the training set, you can issue the command: show( selx( Train, 1, 200 ) ) to view the first 200 images.
• Selecting Instances (Inputs): I have defined two functions to make it easy to select images/instances from a PRTools dataset. selx( Data, start, finish ) returns a new PRTools data set containing elements [start: finish] in Data.

  selx makes use of a more general selection function called selectx. To select all the testing data images containing the digit '3', and then print the first 200 of them, issue the following:

  Threes = selectx( Test, findlabels(Test, [3]) );
  show( selx(Threes, 1, 200) );

  The semi-colon (;) prevents MATLAB from printing out the results of an operation (this can have a significant impact on the speed of a MATLAB program). Here findlabels is a PRTools method used to obtain a vector of index values for instances in a dataset with given label(s) (here just threes: [3]).

Once you have downloaded the data, you can use the built-in PRTools functions to generate simple classifiers (e.g. linear discriminant classifiers using ldc), apply feature transformations, etc. (see the PRTools documentation).