Pattern Recognition
HT2011, 10 ECTS



Overview

Recognizing patterns in nature, numbers, geometry, and the world around us forms the basis of discovery in mathematics and the sciences. The human brain from the time of its inception is in ever continual learning, constantly striving to sort out and simplify complex input upon which it builds generalizations and innately attempts to find order. Understanding the nature of such a process and how it takes place in the realm of the mind is in itself an overpowering task. Humans are naturally adept at integrating and assimilating information and at recognizing patterns intuitively whether in human behavior, identifying familiar objects, or recognizing other people. However, the process through which we achieve such recognition is almost entirely hidden from us, and there is only very little we know today of how our own brain functions and how it is built for pattern recognition tasks. Despite this reality, great applications still arise from our current knowledge and from extending our ability in pattern recognition to machines enabling them to mimic in a primitive way how humans perform such tasks. On the other hand, though lacking in cognition computers provide us with a greater ability than our own in deriving secondary features from objects that may otherwise not be apparent to a human observer, a fact that may prove vital in achieving correct classification. The understanding of how we may program machines to carry out pattern recognition tasks on their own and assist humans in decision making processes constitutes the basis of this course.


Course Description

The course is intended to provide the student with an extensive and thorough insight into pattern recognition.
The main topics covered are supervised and unsupervised classification methods, regression, density estimation, and dimensionality reduction.
The course includes a treatment of the following subjects:
  • Multivariate data visualization
  • Bayesian approach to pattern recognition
  • Parametric/Non-parametric density estimation
  • Evaluation, overtraining, and cross-validation
  • Dimensionality reduction and feature set representation
  • Feature selection, linear/nonlinear feature extraction
  • Clustering techniques and validation methods
  • Expectation-Maximization algorithm
  • Classifiers: Parzen, k-nn, proportional classifier, logistic classifier, normal based discriminants (quadratic/linear/nearest mean),
    Fisher classifier, support vector machines, neural networks, concept learning.
  • Complexity and regularization
  • Ensemble classification and boosting methods
  • Linear/nonlinear and multidimensional regression
Emphasis will be given to certain concepts such as the bias-variance dilemma, classifier complexity, and the curse of dimensionality.
The subjects will be presented theoretically through lectures and discussions and practically through lab sessions and project work.


Learning Outcomes

In completing the course, the student shall be able to:
  • formulate and describe various applications in pattern recognition
  • understand the Bayesian approach to pattern recognition
  • be able to mathematically derive, construct, and utilize Bayesian-based classifiers, and non-Bayesian based classifiers both theoretically and practically.
  • be able to identify the strengths and weaknesses of different types of classifiers
  • understand basic concepts such as the central limit theorem, the curse of dimensionality, the bias-variance dilemma, and cross-validation
  • validate and assess different clustering techniques
  • apply various dimensionality reduction methods whether through feature selection or feature extraction
  • assess classifier complexity and regularization parameters
  • be able to combine various classifiers using fixed rules or trained combiners and boost their performance
  • understand the possibilities and limitations of pattern recognition


Course Literature
  • A. Webb, “Statistical Pattern Recognition”, second edition, Wiley
  • Duda, Hart, & Stork,“Pattern Classification”, second edition, Wiley

Prerequisites/Co-requisites
  • Probability Theory
  • Linear Algebra
  • Multivariate Statistics

Lab Work

The course will include six lab sessions requiring programming in Matlab. Each lab session is generally assigned a two week deadline. Note that the labs are a compulsory part of the course. You are encouraged to work in groups of two during the labs, however you may also choose to work individually. You will be provided assistance throughout the lab periods and discussions among the students and groups is highly recommended.


Project

For the project assignment you are encouraged to work in groups of two or three. You have to choose your own project in either one of the following main topics: unsupervised classification, supervised classification, or regression.
You will have to adapt the lab work in order to solve more challenging problems. There will be some project suggestions, however in any case the datasets you choose for the project have to be approved a priori.


Assessment
  • Labs-P/F
  • Compulsory Project-30% of grade
  • Written Examination-70% of grade. PhD students may choose between written or oral examination.


Schedule

All lectures will be held at the Centre for Image Analysis (CBA), Polacksbacken 2, Uppsala.
  • Introduction

    • Lecture 1 : Introduction to Pattern Recognition

    Thursday, 27 Oct, 10.15-12.00 room: 2115 lecturer: J,Azar
    Main idea, supervised classification, clustering, and regression. Feature space representation, terminology, decision functions & generalization. Multivariate data visualization. (Appendix D, 1.1-1.4).

    Lecture 2 : Mathematical Background

    Friday, 28 Oct, 10:15-12:00 room: 2115 lecturer: J,Azar
    Measurements and features in regard to image processing. Revision of basic probability & statistics: joint probabilities, central limit theorem, Bayes’ theorem, covariance, independence and correlation. Lagrange multipliers. (Appendix E)

    Lecture 3 : Fundamental Concepts

    Tuesday, 1 Nov, 10:15-12:00 room: 2115 lecturer: J,Azar
    Bayesian approach to pattern recognition. Density estimation: parametric methods, multivariate Gaussian, data whitening. Non-parametric methods (k-NN, Parzen), curse of dimensionality, maximum likelihood, cross-validation. (2.2, 3.1-3.3, 3.5)

    Lab-1

    Thursday, 3 Nov, 13:15-17:00 room: 2315D
    Data visualization, central limit theorem, multivariate normal distribution, data whitening, non-parametric density estimation: Parzen, nearest neighbor.


  • Dimensionality Reduction

    • Lecture 4 : Feature Selection

    Monday, 7 Nov, 10:15-12:00 room: 2115 lecturer: J,Azar
    Search algorithms, branch & bound, scatter matrices, criteria functions. Feature selection by global optimization: (meta)-heuristic methods: genetic algorithms, simulated annealing. (9.1-9.2)

    Lecture 5 : Feature Extraction

    Tuesday, 8 Nov, 13:15-15:00 room: 2115 lecturer: J,Azar
    Linear feature extraction: PCA, LDA-Fisher mapping. Nonlinear feature extraction: overview, multidimensional scaling, dissimilarity-based classifiers & embedding. (9.3-9.4, Appendix A)

    Lab-2

    Thursday, 10 Nov, 13:15-17:00 room: 2315D lecturer: J,Azar
    Forward selection, backward selection, take l-add-r selection, branch & bound, genetic algorithms. PCA, Fisher mapping, nonlinear feature extraction, multidimensional scaling, dissimilarity representation.


  • Unsupervised Classification

    • Lecture 6 : Clustering

    Monday, 14 Nov, 15:15-17:00 room: 2115 lecturer: J,Azar
    Unsupervised learning, hierarchical clustering, k-means, fuzzy c-means, mean shift algorithm. Gaussian mixture model, expectation-maximization algorithm, self-organizing maps. (10.1-10.5, 2.3)

    Lecture 7 : Cluster Validation

    Tuesday, 15 Nov, 13:15-15:00 room: 2115 lecturer: J,Azar
    Cluster validation, number of clusters, distortion measures, Davies-Bouldin index, other assessment criteria. Novelty detection, ROC curve. (10.6-10.10, 8.2.3)

    Lab-3

    Thursday, 17 Nov, 13:15-17:00 room: 2315D
    Hierarchical clustering, k-means, fuzzy c-means, Gaussian mixture model, expectation-maximization, Davies-Bouldin index, self-organizing maps.


  • Supervised Classification I

    • Lecture 8 : Bayesian Classifiers

    Monday, 21 Nov, 10:15-12:00 room: 2115 lecturer: J,Azar
    Bayes decision theory, Bayes classifier, Bayes error & risk, logistic classifier. Parzen classifier, k-NN classifier, proportional classifier. (3.3, 3.5, 4.2.1, 4.4)

    Lecture 9 : Bayesian Normal based Classifiers/Discriminant Analysis

    Tuesday, 22 Nov, 10:15-12:00 room: 2115 lecturer: J,Azar
    Quadratic discriminant classifier, linear discriminant classifier, nearest mean classifier. Fisher classifier, classification confidence & rejection. (2.2, 4.2.3, 4.3.9)

    Lab-4

    Friday, 25 Nov, 13:15-17:00 room: 2315D
    Implementation of Bayesian classifier, Parzen classifier, k-NN classifier, logistic classifier, quadratic/linear/nearest-mean classifiers, and Fisher classifier. Curse of dimensionality.


  • Regression

    • Lecture 10 : Linear Regression

    Monday, 28 Nov, 10:15-12:00 room: 2115 lecturer: J,Azar
    Bayesian regression. MMSE estimator, MAP estimator, ML estimator. Model evaluation, quality of regression.

    Lecture 11 : Nonlinear & Multidimensional Regression

    Monday, 28 Nov, 15:15-17:00 room: 2115 lecturer: J,Azar
    Nonlinear regression, kernel smoothing, local regression, backfitting algorithm.
    Multidimensional regression: confidence bounds, model regularization: ridge regression, Least-Absolute-Shrinkage-&-Selection-Operator.

    Lab-5

    Wednesday, 30 Nov, 13:15-17:00 room: 2315D
    Linear regression, MMSE, MAP, MLE, quality measures. Nonlinear regression: kernel smoothing/local weighted regression.


  • Supervised Classification II

    • Lecture 12 : Support Vector Machines

    Tuesday, 6 Dec, 13:15-15:00 room: 2115 lecturer: J,Azar
    Support vector classifier: (non)-separablity, slack variable, (non)-linearity, kernel trick, multiclass problems, control parameters. Classifier complexity/simplicity, VC-dimension. (4.2.5, 5.4, 4.3, 11.6)

    Lecture 13 : Artificial Neural Networks

    Thursday, 8 Dec, 10:15-12:00 room: 2115 lecturer: J,Azar
    Classification: perceptrons, multi-layer perceptrons, backpropagation training, decision functions. Autoregressive ANN, radial basis function ANN. Use in regression & feature extraction. (4.2.2, 6.2)

    Lecture 14 : Combining Classifiers

    Friday, 9 Dec, 10:15-12:00 room: 2115 lecturer: J,Azar
    Ensemble classification: fixed rules, trained combiners. Improving classifier performance: bagging, arcing, boosting, and cloning approach. (8.4)

    Lab-6

    Monday, 12 Dec, 13:15-17:00 room: 2315D
    SVM, ANN, ensemble classification, complexity: bias-variance trade-off, improving performance (implement either boosting or cloning).

    Lecture 15 : Review

    Thursday, 15 Dec, 10:15-12:00 room: 2115 lecturer: J,Azar
    Course review/philosophical approach to principles of pattern recognition.
    Information concerning the final exam.


    Examination

    Tuesday, 20 Dec, 13:15-17:00 room: 2115

    Project Presentation

    Thursday, 12 Jan, 13:15-17:00 room: 2115




    Responsible for the course and web page: Jimmy Azar, Centre for Image Analysis