Personnel

Instructor:	Selim Aksoy
Office:	EA 423
Email:
Office Hours:	Thu 11:40-12:30

Course Information

Schedule:	Tue 8:40-10:30, Thu 10:40-11:30 (EB 204)
Mailing List:	http://retina.cs.bilkent.edu.tr/mailman/listinfo/cs551-spring2005
Prerequisites:	Probability theory, statistics, linear algebra
Texts:	R. O. Duda, P. E. Hart, D. G. Stork, Pattern Classification, 2nd edition, John Wiley & Sons, Inc., 2000. (required) C. M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, 1995. 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. Webb, Statistical Pattern Recognition, Arnold Publishers, 1999. A. K. Jain, R. C. Dubes, Algorithms for Clustering Data, Prentice Hall, 1988.

Lecture Schedule

Chapters	Contents
Introduction to Pattern Recognition [ Slides ] (Feb 3)	Topics: Pattern recognition systems The design cycle An example Readings: DHS Ch 1, Appendix A.1-A.2, A.4-A.5 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.
Bayesian Decision Theory [ Slides ] (Feb 8, 10, 15, 17)	Topics: Modeling using continuous and discrete features Discriminant functions The Gaussian density Error estimation Readings: DHS Ch 2.1-2.9
Parametric Models [ Slides: Part 1 \| Part 2 \| Part 3 \| Part 4 ] (Feb 22, 24, Mar 1, 3, 8, 10)	Topics: Maximum-likelihood estimation Bayesian estimation Expectation-Maximization and mixture density estimation Hidden Markov Models Bayesian Belief Networks Readings: DHS Ch 3.1-3.5, 3.9, 10.2-10.4, 3.10, 2.11 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. 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.
Non-parametric Methods [ Slides ] (Mar 15, 17)	Topics: Density estimation Parzen windows estimation Nearest neighbor estimation Readings: DHS Ch 4.1-4.4
Feature Reduction and Selection [ Slides ] (Mar 22, 24)	Topics: Problems of dimensionality Component analysis Principal components analysis (PCA) Linear discriminant analysis (LDA) Feature selection Readings: DHS Ch 3.7-3.8, 10.13-10.14 References: 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.
Non-Bayesian Classifiers [ Slides: Part 1 \| Part 2 \| Part 3 ] (Mar 29, 31, Apr 5, 7)	Topics: k-nearest neighbor classifier Linear discriminant functions Support vector machines Neural networks Decision trees Readings: DHS Ch 4.5-4.6, 5.1-5.3, 5.11, 6.1-6.3, 8.1-8.3 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. A. K. Jain, J. Mao, K. M. Mohiuddin, "Artificial neural networks: a tutorial" (local copy), IEEE Computer, 29(3):31-44, March 1996. P. F. Baldi, K. Hornik, "Learning in linear neural networks: a survey" (local copy), IEEE Transactions on Neural Networks, 6(4):837-858, July 1995. G. P. Zhang, "Neural networks for classification: a survey" (local copy), IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, 30(4):451-462, November 2000. T. M. Therneau, E. J. Atkinson, "An Introduction to Recursive Partitioning Using the RPART Routines" (local copy), Technical Report 61, Department of Health Science Research, Mayo Clinic, Rochester, Minnesota, September 1997.
Spring Break (Apr 11-15)	No class
Unsupervised Learning and Clustering [ Slides ] (Apr 19, 21, 26)	Topics: Criterion functions for clustering k-means clustering Hierarchical clustering Graph-theoretic clustering Cluster validity Readings: DHS Ch 10.1, 10.6-10.7, 10.9-10.10, 10.12 References: A. K. Jain, R. C. Dubes, "Algorithms for Clustering Data" (local copy), Prentice Hall, 1988 (334 pages, 40Mb!). A. K. Jain, M. N. Murty, P. J. Flynn, "Data Clustering: A Review" (local copy), ACM Computing Surveys, 31(3):264-323, September 1999. P. Berkhin, "Survey of Clustering Data Mining Techniques" (local copy), Technical Report, Accrue Software, San Jose, CA, 2002. S. Aksoy, R. M. Haralick, "Graph-Theoretic Clustering for Image Grouping and Retrieval" (also as technical report), in IEEE International Conference on Computer Vision and Pattern Recognition, 1:63-68, Fort Collins, CO, June 1999.
Algorithm-Independent Learning Issues [ Slides ] (Apr 28, May 3, 5, 10)	Topics: No Free Lunch Theorem Resampling for classifier design Comparing classifiers Combining classifiers Readings: DHS Ch 9.1-9.2, 9.5-9.7 References: J. Rissanen, "Modeling by Shortest Data Description," Automatica, 14:465-471, 1978. J. Rissanen, "A universal prior for integers and estimation by minimum description length," The Annals of Statistics, 11(2):416-431, 1983. J. Kittler, M. Hatef, R. P. W. Duin, J. Matas, "On Combining Classifiers" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 20(3):226-239, March 1998. R. P. W. Duin, D. M. J. Tax, "Experiments with Classifier Combining Rules" (local copy), in First International Workshop on Multiple Classifier Systems, Lecture Notes in Computer Science, 1857:16-29, Springer, 2000. L. Breiman, "Bagging Predictors" (local copy), Machine Learning, 24(2):123-140, August 1996. R. E. Schapire, "The Boosting Approach to Machine Learning: An Overview" (local copy), in Proceedings of MSRI Workshop on Nonlinear Estimation and Classification, 2002.
Structural and Syntactic Pattern Recognition [ Slides ] (May 12, 17)	Topics: Recognition with strings Grammatical methods Graph-theoretic methods Readings: DHS Ch 8.5-8.6 References: 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. 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.

Chapters

Introduction to Pattern Recognition

[ Slides ]

(Feb 3)

Topics:

Pattern recognition systems
The design cycle
An example

Readings:

DHS Ch 1, Appendix A.1-A.2, A.4-A.5

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.

Bayesian Decision Theory

[ Slides ]

(Feb 8, 10, 15, 17)

Topics:

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

Readings:

DHS Ch 2.1-2.9

Parametric Models

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

(Feb 22, 24, Mar 1, 3, 8, 10)

Topics:

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

Readings:

DHS Ch 3.1-3.5, 3.9, 10.2-10.4, 3.10, 2.11

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.
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.

Non-parametric Methods

[ Slides ]

(Mar 15, 17)

Topics:

Density estimation
Parzen windows estimation
Nearest neighbor estimation

Readings:

DHS Ch 4.1-4.4

Feature Reduction and Selection

[ Slides ]

(Mar 22, 24)

Topics:

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

Readings:

DHS Ch 3.7-3.8, 10.13-10.14

References:

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.

Non-Bayesian Classifiers

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

(Mar 29, 31, Apr 5, 7)

Topics:

k-nearest neighbor classifier
Linear discriminant functions
Support vector machines
Neural networks
Decision trees

Readings:

DHS Ch 4.5-4.6, 5.1-5.3, 5.11, 6.1-6.3, 8.1-8.3

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.
A. K. Jain, J. Mao, K. M. Mohiuddin, "Artificial neural networks: a tutorial" (local copy), IEEE Computer, 29(3):31-44, March 1996.
P. F. Baldi, K. Hornik, "Learning in linear neural networks: a survey" (local copy), IEEE Transactions on Neural Networks, 6(4):837-858, July 1995.
G. P. Zhang, "Neural networks for classification: a survey" (local copy), IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, 30(4):451-462, November 2000.
T. M. Therneau, E. J. Atkinson, "An Introduction to Recursive Partitioning Using the RPART Routines" (local copy), Technical Report 61, Department of Health Science Research, Mayo Clinic, Rochester, Minnesota, September 1997.

Spring Break

(Apr 11-15)

No class

Unsupervised Learning and Clustering

[ Slides ]

(Apr 19, 21, 26)

Topics:

Criterion functions for clustering
k-means clustering
Hierarchical clustering
Graph-theoretic clustering
Cluster validity

Readings:

DHS Ch 10.1, 10.6-10.7, 10.9-10.10, 10.12

References:

A. K. Jain, R. C. Dubes, "Algorithms for Clustering Data" (local copy), Prentice Hall, 1988 (334 pages, 40Mb!).
A. K. Jain, M. N. Murty, P. J. Flynn, "Data Clustering: A Review" (local copy), ACM Computing Surveys, 31(3):264-323, September 1999.
P. Berkhin, "Survey of Clustering Data Mining Techniques" (local copy), Technical Report, Accrue Software, San Jose, CA, 2002.
S. Aksoy, R. M. Haralick, "Graph-Theoretic Clustering for Image Grouping and Retrieval" (also as technical report), in IEEE International Conference on Computer Vision and Pattern Recognition, 1:63-68, Fort Collins, CO, June 1999.

Algorithm-Independent Learning Issues

[ Slides ]

(Apr 28, May 3, 5, 10)

Topics:

No Free Lunch Theorem
Resampling for classifier design
Comparing classifiers
Combining classifiers

Readings:

DHS Ch 9.1-9.2, 9.5-9.7

References:

J. Rissanen, "Modeling by Shortest Data Description," Automatica, 14:465-471, 1978.
J. Rissanen, "A universal prior for integers and estimation by minimum description length," The Annals of Statistics, 11(2):416-431, 1983.
J. Kittler, M. Hatef, R. P. W. Duin, J. Matas, "On Combining Classifiers" (local copy), IEEE Trans. on Pattern Analysis and Machine Intelligence, 20(3):226-239, March 1998.
R. P. W. Duin, D. M. J. Tax, "Experiments with Classifier Combining Rules" (local copy), in First International Workshop on Multiple Classifier Systems, Lecture Notes in Computer Science, 1857:16-29, Springer, 2000.
L. Breiman, "Bagging Predictors" (local copy), Machine Learning, 24(2):123-140, August 1996.
R. E. Schapire, "The Boosting Approach to Machine Learning: An Overview" (local copy), in Proceedings of MSRI Workshop on Nonlinear Estimation and Classification, 2002.

Structural and Syntactic Pattern Recognition

[ Slides ]

(May 12, 17)

Topics:

Recognition with strings
Grammatical methods
Graph-theoretic methods

Readings:

DHS Ch 8.5-8.6

References:

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.
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.

Assignments

Homework assignment 1 (Due: March 3 as hardcopy in the class)
Homework assignment 2 (Due: March 28 as online submission)
Homework assignment 3 (Due: April 18 as online submission)
Homework assignment 4 (Due: May 13 as online submission)

Late submission policy: Unless you make prior arrangements with me (before the due date), your grade will be multiplied by "1 - 0.33(t-due)" where due is the assignment due date and t is the date you submit it (t=due, due+1, due+2).

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 as high an accuracy as possible on the selected datasets.

You can use your own data from your thesis research, select datasets from the list of data resources below, or contact the instructor for data from ongoing research on multimedia analysis (including video, audio and text data) or image classification. 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 know the details of the algorithms that the code implements.

You are required to work in groups of three, and submit a project proposal, an interim progress report, a final report written in a conference paper format, and make a poster presentation during the finals week. Tentative schedule of the project is as follows:

Project proposal (due April 8): 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 May 4): Submit a report that describes your progress with the project and your plans for the rest of the semester.
Final report (due May 24): 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. Also submit well-documented software with your report.
Poster presentation (due May 25): Present your work as a poster that fits to a board of approximately 1m-by-1m. 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:

Follow IEEE two-column format as shown in the example and the format definition table and glossary.
The page limit is 6 pages.
The report should not have any page numbers, headers or footers.
You can use IEEE's LaTeX template or Word template. (LaTeX users: Be sure to use the template's conference mode.)
PDF submission is recommended.

All projects' final reports are available as a pdf file (Bilkent only access).

#	Projects	Members
1	Multi-scale region-based remote sensing image classification using a Hidden Markov Model	Gokhan Akcay, Bayram Boyraz, Derya Ozkan
2	Segmentation algorithm for news videos based on speech / speech+music classification	Caglar Ari, Osman Tapkan
3	A probabilistic content model learning application	Ibrahim Demir, Gonenc Ercan, E. Kartal Tabak
4	Region based object recognition using boosting algorithm	Demir Gokalp
5	Offline handwritten word recognition	Ayca Ozcelikkale, Deniz Ustebay, Funda Durupinar
6	Comparison of unsupervised learning algorithms	Hande Dogan, Sami Ezercan
7	Comparison of feature sets for text categorization	Yigithan Dedeoglu, I. Emre Sahin, H. Ozgur Tan, Yasin Uzun
8	Frontal face detection and recognition	A. Polat Ay, Kivanc Kose, Ayse Kucukyilmaz, Onur Onder
9	Comparison of classification algorithms using semi-supervised learning on middle-scale datasets	M. Erol Aran, Faysal Basci, H. Dogu Taskiran
10	A performance analysis of various pattern recognition algorithms on hazelnut impact sounds	Berkan Dulek, Ibrahim Onaran, Mehmet Turkan
11	Discrimination between upstream and downstream genes	Ozgun Babur
12	A comparative study of different techniques to target differentiation and localization with infrared sensors	Cagri Yuzbasioglu, Ilker Bayram, Serkan Onart, Tayfun Aytac

Grading Policy

Homework and quiz:	55%
Term project:	40%
Class participation:	5%

Grades (Bilkent only access) for all quizzes, homework assignments and project are available (also available on SAPS).

Announcements

Personnel

Course Information

Lecture Schedule

Chapters

Contents

Introduction to Pattern Recognition

Bayesian Decision Theory

Parametric Models

Non-parametric Methods

Feature Reduction and Selection

Non-Bayesian Classifiers

Spring Break

Unsupervised Learning and Clustering

Algorithm-Independent Learning Issues

Structural and Syntactic Pattern Recognition

Assignments

Project

Final report guidelines:

Grading Policy

Related Links