CSE802 Pattern Recognition, Spring 2009, MSU

Michigan State University
Spring 2009
CSE 802 - Pattern Recognition and Analysis, 4 credits

Tu, Th: 10:20 am - 12:10 pm, 3400 Engineering Building

Instructor Information

Instructor: Dr. Anil K. Jain

Office: 3143 EB

Office Hours: M, W: 1 pm - 2 pm or by appointment

Phone: 355-9282

Email: jain@cse.msu.edu

Teaching Assistant Information

Pavan Mallapragada (pavanm@cse.msu.edu)
Office: E.B. 3208.
Office hours: Tue-Thu: 1:30 pm-3 pm

Abhishek Nagar (nagarabh@cse.msu.edu)
Office: E.B. 3208.
Office hours: Tue-Thu: 3 pm-4:30 pm

Course Information

Introduction
Prerequisites
Text Book
Assigned Reading
Course Schedule
Grading
Project
Homework Assignments
Exam Resources
Miscellaneous: Software packages for pattern recognition; Introduction to MATLAB; A Simple Introduction to Support Vector Machines

Introduction

Pattern recognition techniques are used to automatically classify physical objects (2D or 3D) or abstract multidimensional patterns (n points in d dimensions) into known or possibly unknown categories. A number of commercial pattern recognition systems exist for character recognition, handwriting recognition, document classification, fingerprint classification, speech and speaker recognition, white blood cell (leukocyte) classification, military target recognition among others. Most machine vision systems employ pattern recognition techniques to identify objects for sorting, inspection, and assembly. The design of a pattern recognition system requires the following modules: (i) sensing, (ii) feature extraction and selection, (iii) decision making, and (iv) system performance evaluation. The availability of low cost and high resolution sensors (e.g., CCD cameras, microphones and scanners) and data sharing over the Internet have resulted in huge repositories of digitized documents (text, speech, image and video). Need for efficient archiving and retreival of this data has fostered the development of pattern recognition algorithms in new application domains (e.g., text, image and video retrieval, bioinformatics, and face recognition).

Pattern recognition systems can be designed using the following main approaches: (i) template matching, (ii) statistical methods, (iii) syntactic methods and (iv) neural networks. This course will introduce the fundamentals of statistical pattern recognition with examples from several application areas. Techniques for analyzing multidimensional data of various types and scales along with algorithms for projection, dimensionality reduction, clustering and classification of data will be explained. The course will present competing approaches to exploratory data analysis and classifier design so students can make judicious choices when confronted with real pattern recognition problems. Students will use the MATLAB software and implement some algorithms using their choice of a programming language.

Prerequisites

CSE 232, MTH 314, and STT 441, or equivalent courses.

Text Book

Duda, Hart and Stork, Pattern Classification, Second Edition, Wiley, 2001.

The text book has a web site. In particular, you may find the errata list useful.

A number of books on pattern recognition have been put on the Assigned Reading in the Engineering Library. In addition, a number of journals, including Pattern Recognition, Pattern Recognition Letters, IEEE Trans. Pattern Analysis & Machine Intelligence (PAMI), IEEE Trans. Geoscience & Remote Sensing, IEEE Trans. Image Processing, and IEEE Trans. Speech and Audio Processing routinely publish papers on pattern recognition theory and applications.

Assigned Reading

Following books are on hold in the Engineering library for assigned reading for CSE 802.

Theodoridis and Koutroumbas	Pattern Recognition
Christopher Bishop	Pattern Recognition and Machine Learning
Fukunaga	Introduction to Statistical Pattern Recognition
Devijver and Kittler	Pattern Recognition: A Statistical Approach
Tou and Gonzalez	Pattern Recognition Principles
Young and Calvert	Classification, Estimation and Pattern Recognition
Pavlidis	Structural Pattern Recognition
Gonzalez and Wintz	Syntactic Pattern Recognition
Oja	Subspace Methods of Pattern Recognition
Watanabe	Pattern Recognition: Human and Mechanical
Jain and Dubes	Algorithms for Clustering Data (Download the book)
Schalkoff	Pattern Recognition: Statistic, Structural and Neural Approaches

Course Schedule

Feb 26	Mid Term Exam [Mid Term Solutions]
Jan 13	Introduction to Pattern Recognition (Ch 1) Statistical Pattern Recognition: A Review Slides of Dr. Jain's lecture: Pattern Recognition. HW1 assigned
Jan 15, 20, 22, 27	Statistical Decision Theory (Ch 2) Jan 20: HW2 assigned; HW1 due An Introduction to Matlab.
Jan 29	Statistical Decision Theory (Ch 2) Notes on Neyman-Pearson decision rule Notes on error rate of a linear discriminant function
Feb 3, 5	Parameter Estimation (Ch 3) Bayes Estimator for multivariate Gaussian density with unknown covariance matrices Bayes Estimator under quadratic loss Feb 3: HW3 assigned; HW2 due
Feb 10, 12	Parameter Estimation (Ch 3) An Introduction to Expectation Maximization (EM) Algorithm EM Lecture Slides from the class. Coin Tossing Example
Feb 17	Curse of Dimensionality (Ch 3) A Problem of Dimensionality: A Simple Example Feb 17: HW4 assigned; HW3 due
Feb 19	Component analysis and Discriminants (Ch 3) Principle Component Analysis (PCA) Principal component analysis for face Recognition.
Feb 24	Nonparametric Techniques (Ch 4)
Mar 3, 5	Non-parametric Techniques (Ch 4) A Branch and Bound Algorithm for Computing k-Nearest Neighbors Mar 3: HW5 assigned; HW4 due Mar 5: Project Proposal Due (2 pages)
Mar 10, 12	SPRING BREAK
Mar 17, 19	Linear Discriminant functions (Ch 5) Signature Verification Support Vector Machines Mar 17: HW6 assigned; HW5 due
Mar 24	Decision Trees (Ch 8) Hierarchical Classifier Design Using Mutual Information Sethi and Sarvarayudu
Mar 26, 31	Neural Networks (Ch 6) A note on comparing classifiers A Tutorial on Artificial Neural Networks Performance evaluation of pattern classifiers for handwritten character recognition Mar 31: HW7 assigned; HW6 due
Apr 2, Apr 7	Error Rate Estimation, Bagging, Boosting (Ch 9)
Apr 9	Classifier Combination (Ch 9) Combination of Multiple Classifiers Using Local Accuracy Estimates by Woods, Kegelmeyer and Bowyer Handwriting digits recognition by combining classifiers by van Breukelen, Duin, Tax and den Hartog
Apr 14	Feature Selection Branch and Bound Algorithm for Feature Subset Selection by Narendra and Fukunaga Feature Selection : Evaluation, Application, and Small Sample Performance by Jain and Zongker
Apr 16, 21, 23	Unsupervised Learning, Clustering, and Multidimensional Scaling (Ch 10) Apr 14: HW7 due Introduction to clustering Data Clustering : 50 Years Beyond K-means (Download Presentation Slides here) *New* Graph Theoretical Methods for Detecting and Describing Gestalt Clusters by C. Zahn A Nonlinear Mapping for Data Structure Analysis by J. Sammon Representation and Recognition of Handwritten Digits Using Deformable Templates by Jain and Zongker
Apr 28	Semi-supervised learning by Xiaojin Zhu BoostCluster by Liu, Jin and Jain Constrained K-means Clustering with Background Knowledge by Wagstaff et al. Semi-supervised clustering by seeding by Basu et al.
Apr 30	Review Final Project Presentation
May 1	Final Project Report Due
May 5	FINAL EXAM, 10 am - 12 noon, 3400 EB

Grading

Course grade will be assigned based on scores on seven homework assignments, two exams and one project. Weights for these three components are as follows: HW (25%), MID TERM EXAM (25%), FINAL EXAM (25%), PROJECT (25%). The cumulative score will be mapped to the letter grade as follows: 90% or higher: 4.0; 85% to 90%: 3.5; 80% to 85%: 3.0 and so on.

Both the exams will be closed book. Makeup exams will be given ONLY if properly justified. Homeworks must be turned in the class on the date they are due. Late homeworks will not be accepted.

Please refer to MSU's policy on the Integrity of Scholarship. All homework solutions must reflect your own work. Failure to do so will result in a grade of 0 in the course.

Course Project

The purpose of the project is to enable the students to get some hands-on experience in the design, implementation and evaluation of pattern recognition algorithms. To facilitate the completion of the project in a semester, it is advised that students work in teams of two. Project will involve using several (at least 4) classifiers of your choice and evaluating their performance on a common pattern classification task. The objective is to use classifier combination, feature extraction/selection, bagging and boosting to get as high an accuracy as possible on the selected classification task.

The project will involve solving the following task:

Hand written digit classification using the MNIST data set. The MNIST data set consists of 60,000 images of the ten digits. The dataset has an independent set of 10,000 digits for evaluating the classifier performance.

The project report should clearly explain the objective of the study, some background work on this problem, difficulty of the classification task, choice of representation, choice of classifiers, combination strategies, error rate estimation, etc. For most of the classifiers, e.g., support vector machines and neural networks, software packages are available in the public domain. Feel free to use them. Emphasis of the project is to solve a practical and interesting pattern recognition problem using the tools that you have learnt in this course and evaluation of your performance compared to the state-of-the-art. Use the projection algorithms to display 2- and 3-dimensional representations of the multidimensional data.

Some tips for your project

If you want to apply multiple discriminant analysis to a high-dimensional data set, you need to first apply PCA to reduce the dimensionality, so that the within-class scatter matrix is not nearly singular.
If you encounter "out of memory" error when running some third-party software, you can create different classifiers for different random subset of the data, and combine the classifiers later.
If you encounter "out of memory" error when running some program you wrote yourself, talk to the TA. He/she probably knows some tricks to reduce the memory consumption.

Some guidelines for writing the report:

Practical applications of digit recognition and challenges in solving this problem.
A brief review of digit recognition approaches, along with references.
State-of-the-art performance, including those reported on MNIST dataset in the literature.
A brief explanation of feature extraction methods, classifiers and classifier combination methods that will be used in the project. Include a rationale for the choice.

Related Publications (MSU Access is provided for the non-public domain articles; click on the links to be routed through magic.msu.edu)

Y. LeCun, L. D. Jackel, L. Bottou, A. Brunot, C. Cortes, J. S. Denker, H. Drucker, I. Guyon, U. A. Muller, E. Sackinger, P. Simard and V. Vapnik, Comparison of learning algorithms for handwritten digit recognition , in Fogelman, F. and Gallinari, P. (Eds), International Conference on Artificial Neural Networks, 53-60, 1995.
Chris J. C. Burges, Bernhard Scholkopf Improving the accuracy and speed ofSupport Vector machines , NIPS 1997, 375-381.
Y. LeCun, L. Bottou, Y. Bengio and P. Haffner, Gradient-Based Learning Applied to Document Recognition . Proceedings of the IEEE, 86(11):2278-2324, November 1998.
Cheng-Lin Liu, Hiroshi Sako and Hiromichi Fujisawa Performance evaluation of pattern classifiers for handwritten character recognition , IJDAR, 4(3), March 2002.
Serge Belongie, Jitendra Malik and Jan Puzicha Shape Matching and Object Recognition Using Shape Contexts. IEEE Trans. on Pattern Analysis and Machine Intelligence, 24(4), 509-522, April 2002.
Dennis Decoste and Bernhard Scholkopf. Training Invariant Support Vector Machines. Machine Learning, 2002.
Cheng-Lin Liu, K. Nakashima, Hiroshi Sako, Hiromichi Fujisawa Handwritten digit recognition: benchmarking of state-of-the-art techniques , Pattern Recognition, 2003.
Patrice Y. Simard, Dave Steinkraus and John C. Platt Best Practice for Convolutional Neural Networks Applied to Visual Document Analysis . Proc. ICDAR 2003.
X Wang, X Ding and C Liu. Gabor filters-based feature extraction for character recognition Pattern Recognition, 2005.
Keysers, D. and Gollan, C. Deformation Models for Image Recognition. IEEE Trans. PAMI. 29, 8, August 2007, 1422-1435.

Compliation of some of the existing results on MNIST database:

CSE 802 Home Page

Michigan State University Spring 2009 CSE 802 - Pattern Recognition and Analysis, 4 credits