Slides

Weeks 1/2

• Overview (updated)
  • Key problems, features, canonical model of a classifier, generalization, clustering
• Classifier Evaluation
  • Error rates, confusion matrices, training and testing procedures, guidelines for experiments
• Nuts, Bolts, Rings and Scrap example (PRTools example shown in-class, from van der Heijden's Text (Ch.2), code for example available here (unpack listings.zip, install PRTools, run 'Listing22'))
• Bayesian Decision Theory
  • The Gaussian distribution (starting slide 21, univariate and multivariate), Bayesian classification, 'Bayesian' classifiers that assume gaussian feature value distributions for classes (linear discriminant, quadratic discriminant) - see Kuncheva Ch. 2 (Equations 2.9-2.11) regarding estimating the mean and variance/covariance matrix from a sample.
  • Covered remaining material in Week 2: Bayesian classifiers, relationship with the canonical classifier, 'Bayesian' classifiers when we assume that feature distributions are normally distributed under different constraints on covariance matrices for the classes.

Week 2

• Density estimation and non-parametric classification
  • General notes on non-parametric density estimation
  • Multinomial/histogram density est./classification
  • Parzen window density estimates/classification
  • k-NN density estimation and classification rule

Week 3

• Decision Trees
  • Decision trees: CART, ID3, C4.5
  • Construction: impurity and splitting criteria
  • Stopping, Pruning
  • Missing attributes

Week 4

• Neural Networks: Overview
  • Expressivity of different 'neural' architectures
  • The node (including inputs and bias, input weights, net sum, activation function, and activation value)
  • Perceptrons
  • Multi-layer Perceptrons
  • Backpropagation (for MLPs)
• Pragmatic Issues for Backpropagation
  • Slides from presentation by Lei Hu, Paul Romanczyk and Erin Wirch
• Regularization, note handout
  • Slides and handout from presentation by Wenbo Wang, Justin Talbot, and James Loomis

Week 5

• Support Vector Machines
  • See Bishop Section 6.2 for details on kernel methods, and in particular the methods for constructing new valid kernels from existing ones.
  • See the Tax/Duin book (available under the 'Resources' link) for the nuts and bolts example comparing quadratic and gaussian (radial basis function) kernels, and a brief description of the 'C' parameter for their SVM implementation, which limits the maximum weight for an individual support vector (section 5.3.4, p. 168). Recall that this allows a SVM to be constructed in the case where data is not linearly separable.

Week 6

• Classifier Combination (overview)
  • Motivation
  • Ensembles/Fusion, Selection, Cascades
  • Combining output labels vs. ranked labels vs. discriminant values
• Majority Vote and Weighted Majority Vote (Erin Wirch and Justin Talbot)
  • Notes
• Classifier Selection (Lei Hu and James Loomis)
• Bagging and Boosting (Wenbo Wang and Paul Romanczyk)
  • PRTools boosting example (Matlab)

Week 7

• Receiver Operating Characteristic (ROC) Curves and Class Separability Measures
• Linear Disciminant Analysis (LDA) and Principal Components Analysis (PCA)
  • LDA: finding line in feature space that best separates classes (e.g. according to Fisher's Discriminant Ratio) when points are projected onto the line (along the direction perpendicular to the line).
  • PCA: redfining feature space representation as mean of the original space, plus new set of k, k less than n where n is the number of features, orthogonal basis vectors. New feature space represent the 'coordinates' of a feature vector along the new basis vectors, where the mean of the original feature space acts as the origin in the new feature space. In many applications a set of k eigenvectors where k is much smaller than n may be found to provide better separation of classes than in the original feature space.
  • Eigenface example: prex_eigenfaces under PRTools.

Week 8

• Clustering Overview
  • Similarity measures; feature scaling; use of scatter matrices in clustering criterions.
• Hierarchical Clustering (Paul Romanczyk and James Loomis)
  • MATLAB source code (including automatic generation of TeX figures)
• k-Means Clustering
• Cluster Validity (Erin Wirch and Wenbo Wang)

Week 9

• Hidden Markov Models
  • Example applet (using HMMs for context-based correction in OCR systems): http://www.cim.mcgill.ca/~latorres/Viterbi/va_main.html
• Syntactic Pattern Recognition (DHS 8.6)
• Grammars and formal languages; Chomsky hierarchy of grammar/language types
• Using grammars for generation (transforming start symbol to a sentence in the language), and parsing (reducing legal sentences to the start symbol).
• HMMs are stochastic regular languages, where each production has an associated probability.
• Regular languages can be used to model sequences; context-free languages may also be used to model nesting (e.g. 'bracketing').
• Cocke-Yonger-Kasami algorithm: a dynamic programming algorithm for determining all legal parses of an input sentence, by recursively considering larger string sub-sequences. Used with context-free grammars in Chomsky Normal Form. CYK may be adapted to record probabilities as well as productions within the dynamic programming table (data structure), for use with stochastic regular languages and stochastic context-free grammars.
• Example Applications: recognizing mathematical notation (P. Chou, 1989, "Recognition of Equations Using a Two-Dimensional Stochastic Context-Free Grammar". SPIE Vol. 1199 Visual Communicationa and Image Processing IV, pp. 852-863, 1989.), recovering form contents using graph grammars (Amano, A. and Asada, N. "Graph Grammar Based Analysis System of Complex Table Form Document," Proc. Int'l Conf. Document Analysis and Recognition, 2003).