Personnel

Instructor:	Selim Aksoy
Office:	EA 422
Email:

Course Information

Schedule:	Tue 10:40-12:30, Fri 8:40-10:30 (EB 102)
Office hours:	TBD (EA 422)
Prerequisites:	Probability theory, statistics, linear algebra

Texts

K. P. Murphy, Machine Learning: A Probabilistic Perspective, MIT Press, 2012.
C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.
R. O. Duda, P. E. Hart, D. G. Stork, Pattern Classification, 2nd edition, John Wiley & Sons, Inc., 2000.
S. Theodoridis, K. Koutroumbas, Pattern Recognition, 3rd edition, Academic Press, 2006.
D. Koller, N. Friedman, Probabilistic Graphical Models: Principals and Techniques, MIT Press, 2009.
A. Webb, Statistical Pattern Recognition, 2nd edition, John Wiley & Sons, Inc., 2002.
T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer, 2003.
K. Fukunaga, Introduction to Statistical Pattern Recognition, Academic Press, 1990.
R. Schalkoff, Pattern Recognition: Statistical, Structural and Neural Approaches, John Wiley & Sons, Inc., 1992.
A. K. Jain, R. C. Dubes, Algorithms for Clustering Data, Prentice Hall, 1988.

Lecture Schedule

Chapters	Contents
Introduction to Pattern Recognition [ Slides ]	Topics: Pattern recognition systems The design cycle An example References: A. K. Jain, R. P. W. Duin, J. Mao, "Statistical Pattern Recognition: A Review" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(1):4-37, January 2000. C. M. Grinstead, J. L. Snell, Introduction to Probability (local copy), American Mathematical Society, 1997. R. C. Gonzales, R. E. Woods, "Brief Review of Matrices, Vectors, Probability and Random Variables" (local copy), 2002.
Bayesian Decision Theory [ Slides ]	Topics: Modeling using continuous and discrete features Discriminant functions The Gaussian density Error estimation References: Receiver Operating Characteristic Curves: An Introduction An ROC applet Another ROC applet T. Fawcett, "An Introduction to ROC Analysis" (local copy), Pattern Recognition Letters, 27(8):861-874, June 2006.
Parametric Models [ Slides: Part 1 \| Part 2 \| Part 3 ]	Topics: Maximum-likelihood estimation Bayesian estimation Expectation-Maximization and mixture density estimation Hidden Markov Models References: J. A. Bilmes, "A Gentle Tutorial on the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models" (local copy), Technical Report TR-97-021, International Computer Science Institute, University of California, Berkeley, April 1998. G. J. McLachlan, T. Krishnan, The EM Algorithm and Extensions, John Wiley & Sons, Inc., 1997. L. R. Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition" (local copy), Proceedings of the IEEE, 77(2):257-286, February 1989.
Non-parametric Methods [ Slides ]	Topics: Density estimation Histogram-based estimation Parzen windows estimation Nearest neighbor estimation
Probabilistic Graphical Models [ Slides: Part 1 \| Part 2 \| Part 3 ]	Topics: Directed graphical models - Bayesian networks Undirected graphical models Inference using graphical models Learning graphical models References: K. P. Murphy, "A Brief Introduction to Graphical Models and Bayesian Networks" (local copy), May 2001. E. Charniak, "Bayesian Networks Without Tears" (local copy), AI Magazine, 12(4):50-63, 1991. D. Heckerman, "A Tutorial on Learning With Bayesian Networks" (local copy), Technical Report MSR-TR-95-06, Microsoft Research, March 1995. W. L. Buntine, "Operations for Learning with Graphical Models" (local copy), Journal of Artificial Intelligence Research, 2:159-225, 1994.
Feature Reduction and Selection [ Slides ]	Topics: Problems of dimensionality Component analysis Principal components analysis (PCA) Linear discriminant analysis (LDA) Manifold learning Feature selection References: J. B. Tenenbaum, V. de Silva, J. C. Langford, "A Global Geometric Framework for Nonlinear Dimensionality Reduction" (local copy), Science, 290:2319-2323, 2000. S. T. Roweis, L. K. Saul, "Nonlinear Dimensionality Reduction by Locally Linear Embedding" (local copy), Science, 290:2323-2326, 2000. L. K. Saul, S. T. Roweis, "Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifolds" (local copy), Journal of Machine Learning Research, 4:119-155, 2003. L. Cayton, "Algorithms for Manifold Learning" (local copy), Technical Report CS2008-0923, University of California, San Diego, 2005. L. J. P. van der Maaten, E. O. Postma, H. J. van den Herik, "Dimensionality Reduction: A Comparative Review" (local copy), Technical Report TiCC-TR 2009-005, Tilburg University, 2009. Resources on manifold learning A. Hyvarinen, "Survey on Independent Component Analysis" (local copy), Neural Computing Surveys, 2:94-128, 1999. A. Hyvarinen, E. Oja, "Independent Component Analysis: Algorithms and Applications" (local copy), Neural Networks, 13(4-5):411-430, 2000. A. K. Jain, D. Zongker, "Feature Selection: Evaluation, Application, and Small Sample Performance" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(2):153-158, February 1997. Feature selection demonstrations
Non-Bayesian Classifiers [ Slides: Part 1 \| Part 2 ]	Topics: k-nearest neighbor classifier Linear discriminant functions Support vector machines References: M. A. Hearst, "Support Vector Machines" (local copy), IEEE Intelligent Systems, 13(4):18-28, July 1998. B. Scholkopf, C. Burges, A. J. Smola, "Introduction to Support Vector Learning" (local copy), in Advances in Kernel Methods - Support Vector Learning, MIT Press, 1999. C. J. C. Burges, "A Tutorial on Support Vector Machines for Pattern Recognition" (local copy), Data Mining and Knowledge Discovery, 2(2):121-167, June 1998.
Structural and Syntactic Pattern Recognition [ Slides ]	Topics: Graph-theoretic methods Recognition with strings Grammatical methods Readings: DHS Ch 8.5-8.6 References: B. T. Messmer, H. Bunke, "Efficient Subgraph Isomorphism Detection: A Decomposition Approach" (local copy), IEEE Trans. on Knowledge and Data Engineering, 12(2):307-323, March/April 2000. W. J. Christmas, J. Kittler, M. Petrou, "Structural Matching in Computer Vision Using Probabilistic Relaxation" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 17(8):749-764, August 1995. R. Myers, R. C. Wilson, E. R. Hancock, "Bayesian Graph Edit Distance" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(6):628-635, June 2000. D. Conte, P. Foggia, C. Sansone, M. Vento, "Thirty years of graph matching in pattern recognition" (local copy), International Journal of Pattern Recognition and Artificial Intelligence, 18(3):265-298, May 2004. R. P. W. Duin, "Structural Inference of Sensor-Based Measurements" (local copy), Pierre Devijver Award Lecture at S+SSPR 2006. R. P. W. Duin, "Representation Related Problems in Pattern Recognition" (local copy), Invited talk at Joint Meeting of the British Statistical Society and the Royal Classification Society, 2006. H. Bunke, "Graph Classification Based on Dissimilarity Space Embedding" (local copy), Invited talk at S+SSPR 2008. K.-S. Fu, T. L. Booth, "Grammatical Inference: Introduction and Survey - Part I," IEEE Trans. on Pattern Analysis and Machine Intelligence, 8(3):343-359, 1986. K.-S. Fu, T. L. Booth, "Grammatical Inference: Introduction and Survey - Part II," IEEE Trans. on Pattern Analysis and Machine Intelligence, 8(3):360-375, 1986. L. G. Shapiro, R. M. Haralick, "A Metric for Comparing Relational Descriptions," IEEE Trans. on Pattern Analysis and Machine Intelligence, 7:90-94, 1985. S. Dance, T. Caelli, Z.-Q. Liu, Picture Interpretation: A Symbolic Approach, World Scientific, 1995.

Chapters

Introduction to Pattern Recognition

[ Slides ]

Topics:

Pattern recognition systems
The design cycle
An example

References:

A. K. Jain, R. P. W. Duin, J. Mao, "Statistical Pattern Recognition: A Review" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(1):4-37, January 2000.
C. M. Grinstead, J. L. Snell, Introduction to Probability (local copy), American Mathematical Society, 1997.
R. C. Gonzales, R. E. Woods, "Brief Review of Matrices, Vectors, Probability and Random Variables" (local copy), 2002.

Bayesian Decision Theory

[ Slides ]

Topics:

Modeling using continuous and discrete features
Discriminant functions
The Gaussian density
Error estimation

References:

Receiver Operating Characteristic Curves: An Introduction
An ROC applet
Another ROC applet
T. Fawcett, "An Introduction to ROC Analysis" (local copy), Pattern Recognition Letters, 27(8):861-874, June 2006.

Parametric Models

[ Slides: Part 1 | Part 2 | Part 3 ]

Topics:

Maximum-likelihood estimation
Bayesian estimation
Expectation-Maximization and mixture density estimation
Hidden Markov Models

References:

J. A. Bilmes, "A Gentle Tutorial on the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models" (local copy), Technical Report TR-97-021, International Computer Science Institute, University of California, Berkeley, April 1998.
G. J. McLachlan, T. Krishnan, The EM Algorithm and Extensions, John Wiley & Sons, Inc., 1997.
L. R. Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition" (local copy), Proceedings of the IEEE, 77(2):257-286, February 1989.

Non-parametric Methods

[ Slides ]

Topics:

Density estimation
Histogram-based estimation
Parzen windows estimation
Nearest neighbor estimation

Probabilistic Graphical Models

[ Slides: Part 1 | Part 2 | Part 3 ]

Topics:

Directed graphical models - Bayesian networks
Undirected graphical models
Inference using graphical models
Learning graphical models

References:

K. P. Murphy, "A Brief Introduction to Graphical Models and Bayesian Networks" (local copy), May 2001.
E. Charniak, "Bayesian Networks Without Tears" (local copy), AI Magazine, 12(4):50-63, 1991.
D. Heckerman, "A Tutorial on Learning With Bayesian Networks" (local copy), Technical Report MSR-TR-95-06, Microsoft Research, March 1995.
W. L. Buntine, "Operations for Learning with Graphical Models" (local copy), Journal of Artificial Intelligence Research, 2:159-225, 1994.

Feature Reduction and Selection

[ Slides ]

Topics:

Problems of dimensionality
Component analysis
- Principal components analysis (PCA)
- Linear discriminant analysis (LDA)
Manifold learning
Feature selection

References:

J. B. Tenenbaum, V. de Silva, J. C. Langford, "A Global Geometric Framework for Nonlinear Dimensionality Reduction" (local copy), Science, 290:2319-2323, 2000.
S. T. Roweis, L. K. Saul, "Nonlinear Dimensionality Reduction by Locally Linear Embedding" (local copy), Science, 290:2323-2326, 2000.
L. K. Saul, S. T. Roweis, "Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifolds" (local copy), Journal of Machine Learning Research, 4:119-155, 2003.
L. Cayton, "Algorithms for Manifold Learning" (local copy), Technical Report CS2008-0923, University of California, San Diego, 2005.
L. J. P. van der Maaten, E. O. Postma, H. J. van den Herik, "Dimensionality Reduction: A Comparative Review" (local copy), Technical Report TiCC-TR 2009-005, Tilburg University, 2009.
Resources on manifold learning
A. Hyvarinen, "Survey on Independent Component Analysis" (local copy), Neural Computing Surveys, 2:94-128, 1999.
A. Hyvarinen, E. Oja, "Independent Component Analysis: Algorithms and Applications" (local copy), Neural Networks, 13(4-5):411-430, 2000.
A. K. Jain, D. Zongker, "Feature Selection: Evaluation, Application, and Small Sample Performance" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(2):153-158, February 1997.
Feature selection demonstrations

Non-Bayesian Classifiers

[ Slides: Part 1 | Part 2 ]

Topics:

k-nearest neighbor classifier
Linear discriminant functions
Support vector machines

References:

M. A. Hearst, "Support Vector Machines" (local copy), IEEE Intelligent Systems, 13(4):18-28, July 1998.
B. Scholkopf, C. Burges, A. J. Smola, "Introduction to Support Vector Learning" (local copy), in Advances in Kernel Methods - Support Vector Learning, MIT Press, 1999.
C. J. C. Burges, "A Tutorial on Support Vector Machines for Pattern Recognition" (local copy), Data Mining and Knowledge Discovery, 2(2):121-167, June 1998.

Structural and Syntactic Pattern Recognition

[ Slides ]

Topics:

Graph-theoretic methods
Recognition with strings
Grammatical methods

Readings:

DHS Ch 8.5-8.6

References:

B. T. Messmer, H. Bunke, "Efficient Subgraph Isomorphism Detection: A Decomposition Approach" (local copy), IEEE Trans. on Knowledge and Data Engineering, 12(2):307-323, March/April 2000.
W. J. Christmas, J. Kittler, M. Petrou, "Structural Matching in Computer Vision Using Probabilistic Relaxation" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 17(8):749-764, August 1995.
R. Myers, R. C. Wilson, E. R. Hancock, "Bayesian Graph Edit Distance" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(6):628-635, June 2000.
D. Conte, P. Foggia, C. Sansone, M. Vento, "Thirty years of graph matching in pattern recognition" (local copy), International Journal of Pattern Recognition and Artificial Intelligence, 18(3):265-298, May 2004.
R. P. W. Duin, "Structural Inference of Sensor-Based Measurements" (local copy), Pierre Devijver Award Lecture at S+SSPR 2006.
R. P. W. Duin, "Representation Related Problems in Pattern Recognition" (local copy), Invited talk at Joint Meeting of the British Statistical Society and the Royal Classification Society, 2006.
H. Bunke, "Graph Classification Based on Dissimilarity Space Embedding" (local copy), Invited talk at S+SSPR 2008.
K.-S. Fu, T. L. Booth, "Grammatical Inference: Introduction and Survey - Part I," IEEE Trans. on Pattern Analysis and Machine Intelligence, 8(3):343-359, 1986.
K.-S. Fu, T. L. Booth, "Grammatical Inference: Introduction and Survey - Part II," IEEE Trans. on Pattern Analysis and Machine Intelligence, 8(3):360-375, 1986.
L. G. Shapiro, R. M. Haralick, "A Metric for Comparing Relational Descriptions," IEEE Trans. on Pattern Analysis and Machine Intelligence, 7:90-94, 1985.
S. Dance, T. Caelli, Z.-Q. Liu, Picture Interpretation: A Symbolic Approach, World Scientific, 1995.

Exam

Midterm exam will be held at EB 102 and 104 during 8:40-10:30 (class hours) on December 16, 2016. The exam will cover all topics from the beginning of the semester until the end of the non-Bayesian classifiers chapter. Exam locations are as follows:
- EB-102: AKBAS - INEL
- EB-104: KAHVECI - YUCEL

Assignments

Homework assignment 1: description (Due: November 7, 2016 as online submission)
Homework assignment 2: description | data (Due: November 28, 2016 as online submission)
Homework assignment 3: description | data (Due: December 21, 2016 as online submission)

Late submission policy: Unless you make prior arrangements with me (before the due date), no late homework will be accepted.

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 by applying them to real-world problems. The objective is to try multiple algorithms for different steps of the design cycle such as feature extraction and selection, model learning and estimation, classification and evaluation, to get an acceptable accuracy on the selected data sets. An acceptable accuracy will be problem dependent but needs to be measured using formal quantitative methods.

You can use your own data from your thesis research, select data sets from the list of data resources below, or contact the instructor. In any case, you should get prior approval before starting your project.

You are free to use any programming language but Matlab is strongly recommended because it is very convenient for prototyping and has many tools available for pattern recognition. You can write the codes yourself or use any code that is available in the public domain. In case you use somebody else's code, you are required to properly cite its source and know the details of the algorithms that the code implements.

You are required to work in groups of two, and submit a project proposal, an interim progress report, and a final report written in a conference paper format. Tentative schedule of the project is as follows:

Project proposal (due December 5, 2016): Submit a 1-2 page proposal that describes the problem you would like to tackle, objective of the study, proposed algorithms, hardware/software tools and data that you plan to utilize, and evaluation strategies that you plan to use. Also provide a short list of related references.
Interim progress report (due December 26, 2016): Submit a report that describes your progress with the project and your plans for the rest of the semester.
Final report (due January 9, 2016): Submit a readable and well-organized report that provides proper motivation for the task, proper citation and discussion of related literature, proper explanation of the details of the approach and implementation strategies, proper performance evaluation, and detailed discussion of the results. Highlight your contributions and conclusions as a team. Also submit well-documented software with your report. Each team member should also provide a written description of her/his own contributions to the project.

All reports and software can be submitted using the online form.

Final report guidelines:

The reports are expected to be 6 pages and must follow the IEEE Computer Society two-column format as described in their templates. Try to follow the format as closely as possible.
PDF submission is required.

Grading Policy

Midterm exam:	25%
Homework:	40%
Project:	30%
Class participation:	5%

Announcements

Personnel

Course Information

Texts

Lecture Schedule

Chapters

Contents

Introduction to Pattern Recognition

Bayesian Decision Theory

Parametric Models

Non-parametric Methods

Probabilistic Graphical Models

Feature Reduction and Selection

Non-Bayesian Classifiers

Structural and Syntactic Pattern Recognition

Exam

Assignments

Project

Final report guidelines:

Grading Policy

Related Links