Lectures

• Lecture 01: Introduction to machine learning, probability review
• Lecture 02: PAC model, sample complexity for finite hypothesis space, general bounds and inequalities
• Lecture 03: VC dimension
• Lecture 04: Support vector machines
• Lecture 05: Support vector machines, kernel methods
• Lecture 06: Perceptron algorithm, quadratic optimization algorithms
• Lecture 07: Decision trees
• Lecture 08: Boosting, on-line learning algorithms
• Lecture 09: Multi-class classification algorithms
• Lecture 10: Regression problems and algorithms
• Lecture 11: Ranking problems and algorithms
• Lecture 12: Learning automata, Angluin-type algorithms
• Lecture 13: Reinforcement learning
• Lecture 14: Empirical evaluation

Textbooks

There is no single textbook covering the material presented in this course. Here is a list of books recommended for further reading:

• Luc Devroye, Laszlo Gyorfi, Gabor Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.
• Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.
• Tom M. Mitchell. Machine learning. McGraw-Hill, 1997.
• Bernhard Schoelkopf and Alex Smola. Learning with Kernels. MIT Press, Cambridge, MA, 2002.
• Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer, 1995.
• Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998.

Technical Papers

Here is a list of recommended papers for further reading.

• A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929--865, 1989.
• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, (chapters 4 and 5), Cambridge University Press, 2005.
• Corinna Cortes and Vladimir Vapnik, Support-Vector Networks, Machine Learning, 20, 1995.
• Corinna Cortes, Patrick Haffner, and Mehryar Mohri, Rational Kernels: Theory and Algorithms. Journal of Machine Learning Research, 5:1035-1062, 2004.
• Benjamin Taskar, Carlos Guestrin, Daphne Koller. Max-Margin Markov Networks. NIPS 2003.
• Leo Breiman, Random forests, Machine Learning, 45, 2001.
• Robert E. Schapire. The boosting approach to machine learning: An overview. In MSRI Workshop on Nonlinear Estimation and Classification, 2002.
• Ralf Herbrich, Thore Graepel, Klaus Obermayer, Support Vector Learning for Ordinal Regression. Proceedings of the Ninth International Conference on Artificial Neural Networks 97--102, 1999.
• Michael Kearns , Leslie Valiant, Cryptographic Limitations on Learning Boolean Formulae and Finite Automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994.
• Dana Ron, Yoram Singer, and Naftali Tishby. The power of amnesia: Learning probabilistic automata with variable memory length. Machine Learning, 25, 1996.
• Jon M. Kleinberg. An Impossibility Theorem for Clustering. NIPS 2002.

Homework assignments

• Homework 1 [solution] Probability review, PAC learning.
• Homework 2 [solution] VC dimension, sample complexity.
• Homework 3 [solution] Support vector machines, kernel methods.
• Homework 4 [solution] Perceptron, boosting.