• Course Info
• Lectures
• Assignments
• Project
• Grading
• Links

Announcements

1. (Feb 10) Course page is online.
2. (Feb 10) Syllabus is available.
3. (Feb 10) Slides for Introduction to Pattern Recognition are available.
4. (Feb 13) Slides for Bayesian Decision Theory are available.
5. (Feb 22) Class hours were changed.
6. (Feb 23) First part of the slides for Parametric Models is available.
7. (Mar 4) Homework assignment 1 is available.
8. (Mar 5) Second part of the slides for Parametric Models is available.
9. (Mar 12) Third part of the slides for Parametric Models is available.
10. (Mar 23) Fourth part of the slides for Parametric Models is available.
11. (Mar 25) Slides for Non-parametric Methods are available.
12. (Mar 30) Homework assignment 2 is available.
13. (Apr 1) Slides for Feature Reduction and Selection are available.
14. (Apr 5) Homework assignment 2 due date is postponed to April 17, 2008.
15. (Apr 9) First part of the slides for Non-Bayesian Classifiers is available.
16. (Apr 9) Second part of the slides for Non-Bayesian Classifiers is available.
17. (Apr 23) Homework assignment 3 is available.
18. (Apr 27) Third part of the slides for Non-Bayesian Classifiers is available.
19. (Apr 27) Slides for Unsupervised Learning and Clustering are available.
20. (May 7) Slides for Algorithm-Independent Learning Issues are available.
21. (May 9) Project presentations will be made at EA 502 during 13:30-16:00 on May 29th.
22. (May 12) Homework assignment 3 due date is postponed to May 19, 2008.
23. (May 14) Slides for Structural and Syntactic Pattern Recognition are available.

Personnel

Instructor:	Selim Aksoy
Office:	EA 423
Email:

Course Information

Schedule:	Mon 9:40-10:30, Wed 9:40-11:30 (EA 502)
Office hours:	Wed 13:40-15:30
Mailing list:	http://retina.cs.bilkent.edu.tr/mailman/listinfo/cs551-spring2008
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)
• A. Webb, Statistical Pattern Recognition, 2nd edition, John Wiley & Sons, Inc., 2002.
• C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.
• S. Theodoridis, K. Koutroumbas, Pattern Recognition, 3rd edition, Academic Press, 2006.
• 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 ] (Feb 11, 13)	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. 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 ] (Feb 18, 20, 25)	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 27, Mar 3, 5, 10, 12, 17, 19, 24)	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 26, 31)	Topics: Density estimation Histogram-based estimation Parzen windows estimation Nearest neighbor estimation Readings: DHS Ch 4.1-4.4
Feature Reduction and Selection [ Slides ] (Apr 2)	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: 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. 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 ] (Apr 7, 9, 14, 16)	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.
Unsupervised Learning and Clustering [ Slides ] (Apr 28, 30, May 5)	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. A. K. Jain, A. Topchy, M. H. C. Law, J. M. Buhmann, "Landscape of Clustering Algorithms" (local copy), in IAPR International Conference on Pattern Recognition, 1:260-263, Cambridge, UK, August 2004.
Algorithm-Independent Learning Issues [ Slides ] (May 7, 12)	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 14, 20)	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. S. Dance, T. Caelli, Z.-Q. Liu, Picture Interpretation: A Symbolic Approach, World Scientific, 1995. 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.

Assignments

1. Homework assignment 1 (Due: March 19, 2008 as hardcopy in the class)
2. Homework assignment 2 (Due: April 17, 2008 as online submission)
3. Homework assignment 3 (Due: May 19, 2008 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 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 at the RETINA group (including image, video, audio and text data). 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 as a group, and submit a project proposal, an interim progress report, a final report written in a conference paper format, and make a presentation during the finals week. Tentative schedule of the project is as follows:

• Project proposal (due April 15, 2008): 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 12, 2008): Submit a report that describes your progress with the project and your plans for the rest of the semester.
• Final report (due May 27, 2008): 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.
• Presentation (due May 29, 2008): Make a ~10 minute presentation of your work to the class. 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 Computer Society two-column format as described in their examples and templates.
• The page limit is 6 pages.
• The report should not have any page numbers, headers or footers.
• PDF submission is recommended.

#	Projects	Members
1	Exploitation of feature selection methods in hierarchical image segmentation	Firat Kalaycilar, Asli Kale, Daniya Zamalieva
2	Classification of cardiac arrhythmia using nominal and continuous features	Burak Ozek
3	Using graph-based method for semantic scene classification	Dogan Altunbay, Onur Kucuktunc
4	Motion recognition with gyroscopes	Derya Gol, Erdem Sahin
5	Speaker detection	Hidayet Aksu, Ethem F. Can, Mahmut Yavuzer
6	Feature selection for scene classification	R. Gokberk Cinbis, A. Osman Ulusoy
7	Image clustering	Sare Gul Sevil, Can Sardan, Hilal Zitouni
8	Speech recognition for expression evaluation	Enver Kayaaslan, Sitar Kortik, Tugba Yildiz

Grading Policy

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

Related Links

• Previous semesters for CS 551
  • Spring 2007
  • Spring 2006
  • Spring 2005
• Duda, Hart, Stork book
  • Book's website
  • Make sure you check the errata for the particular printing you have.
• Webb book
  • Book's website
• Bishop book
  • Book's website
• Theodoridis and Koutroumbas book
  • Book's website
• Hastie, Tibshirani, Friedman book
  • Book's website
• Software resources
  • PRTools by the Delft Pattern Recognition Group (in Matlab) (local copy)
  • Netlab Neural Network Software (in Matlab) (local copy of software and its documentation)
  • Weka Data Mining Software (in Java)
  • Bayes Net Toolbox (in Matlab)
  • Hidden Markov Model Toolbox (in Matlab)
  • SVMlight - SVM training package (in C)
  • Sequential Minimal Optimization algorithm for SVM training
  • LIBSVM - A Library for SVM (in C++ and Java, with interfaces for additional languages)
  • Numerical Recipes (in C)
  • Software resources from Pattern Recognition Information web site
  • Software resources from Kevin Murphy's web site
  • Software resources from Kernel Machines web site
  • Software resources from Kernel Methods web site
  • Software resources from American Association for Artificial Intelligence web site
  • StatLib
  • Mathtools.net Technical Computing (in Matlab, C/C++, Java)
• Matlab tutorials
  • Matlab Primer v2
  • Matlab Tutorial by Indiana University
  • Matlab Tutorial by the University of New Hampshire
  • Matlab Tutorial by MIT
  • MathWorks - Matlab Tutorial
  • MathWorks - Student Center
  • MathWorks - HTML Documentation
• Data resources
  • Pattern recognition related archives
  • Computer vision test images
  • UCI Machine Learning Repository
  • Labeled databases for object detection
  • Image database from the University of Washington
  • Texture database from the University of Oulu
  • Document database from the University of Oulu
  • Other databases from the University of Oulu
  • Image databases from CMU Vision and Autonomous Systems Center
  • Various other datasets from the University of Washington
  • Face databases from CMU
  • Face databases from MIT
  • Another page for face databases
  • MNIST Database of handwritten digits
  • Shape database from Brown University
  • Reuters-21578 Text Categorization Collection
  • NIST Scientific and Technical Databases
  • RISC: Repository of Information on Semi-supervised Clustering
• Others
  • Pattern Recognition Information
  • International Association for Pattern Recognition (IAPR)
  • IEEE Computer Society Technical Committee on Pattern Analysis and Machine Intelligence (PAMI)
  • IAPR Technical Committee 1 on Statistical Techniques in Pattern Recognition
  • IAPR Technical Committee 2 on Structural and Syntactical Pattern Recognition
  • MathWorld (an online encyclopedia of mathematical resources)
  • International Society for Bayesian Analysis
  • Statistical Learning/Pattern Recognition Glossary
  • Statistical Data Mining Tutorials
  • Kernel Machines
  • Learning with Kernels
  • Engineering Statistics Handbook
  • Introductory Statistics: Concepts, Models, and Applications
  • The Probability Web

Please send questions/suggestions to .

URI for this page is http://www.cs.bilkent.edu.tr/~saksoy/courses/cs551-Spring2008/index.html.
Last updated on May 26, 2008.