Spring 2009
Foundations of Machine
Learning
Course#: G22.2566-001
Instructor: Mehryar Mohri
Grader: Ashish Rastogi
Mailing
List
Course Description
This course introduces the fundamental concepts and methods of machine
learning, including the description and analysis of several modern
algorithms, their theoretical basis, and the illustration of their
applications. Many of the algorithms described have been successfully
used in text and speech processing, bioinformatics, and other areas in
real-world products and services. The main topics covered are:
- Probability and general bounds
- PAC model
- VC-dimension
- Perceptron, Winnow
- Support vector machines (SVMs)
- Kernel methods
- Decision trees
- Boosting
- Regression problems and algorithms
- Ranking problems and algorithms
- Halving algorithm, weighted majority algorithm, mistake bounds
- Learning automata, Angluin-type algorithms
- Reinforcement learning, Markov decision processes (MDPs)
Note: except from a few common topics only briefly addressed in
G22.2565-001, the material covered by these two courses have no
overlap.
Location and Time
Room 101 Warren Weaver Hall,
251 Mercer Street.
Tuesdays 5:00 PM - 6:50 PM.
Prerequisite
Familiarity with basics in linear algebra, probability, and analysis
of algorithms.
Projects and Assignments
There will be roughly 4 assignments and a project. The final grade is
essentially the average of the assignment and project grades. The
standard high level of integrity
is expected from all students, as with all CS courses.
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
- Invited lecture by Prof. Yishay Mansour: [Regret minimization]
- 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
An extensive list of recommended papers for further reading is
provided in the lecture slides.
Homework
Previous years