Foundations of Machine Learning

Instructor: Mehryar Mohri

TA: Chopra Sumit

Mailing List

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.

- Corinna Cortes and Vladimir Vapnik, Support-Vector Networks, Machine Learning, 20, 1995.
- Robert E. Schapire. The boosting approach to machine learning: An overview. In MSRI Workshop on Nonlinear Estimation and Classification, 2002.
- Jon M. Kleinberg. An Impossibility Theorem for Clustering. NIPS 2002.
- Francis R. Bach, Michael I. Jordan. Learning Spectral Clustering. NIPS 2003.
- Benjamin Taskar, Carlos Guestrin, Daphne Koller. Max-Margin Markov Networks. NIPS 2003.

Homework assignments

- Homework 1 [solution] Generalization bounds, PAC model.
- Homework 2 [solution] VC dimension, support vector machines.
- Homework 3 [solution] Kernel methods, boosting.