Foundations of Machine Learning
Instructor: Mehryar Mohri
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:
It is strongly recommended to those who can to also attend
Machine Learning Seminar.
- Probability and general bounds
- PAC model
- Rademacher complexity, VC-dimension
- Perceptron, Winnow
- Support vector machines (SVMs)
- Kernel methods
- Decision trees
- Regression problems and algorithms
- Ranking problems and algorithms
- Halving algorithm, weighted majority algorithm, mistake bounds
- Learning automata and transducers
- Reinforcement learning, Markov decision processes (MDPs)
Location and Time
Warren Weaver Hall Room 109,
251 Mercer Street.
Mondays 5:00 PM - 6:50 PM.
Familiarity with basics in linear algebra, probability, and analysis
Projects and Assignments
There will be 3 to 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.
- Lecture 01: Introduction to machine learning, probability review.
02: PAC model, sample complexity for finite hypothesis sets,
03: Rademacher complexity, VC-dimension, learning
bounds for infinite hypothesis sets, model selection.
04: Support vector machines (SVMs), margin bounds.
- Lecture 05: Kernel methods.
- Lecture 06: Boosting.
- Lecture 07: On-line learning.
- Lecture 08: Regression.
- Lecture 09: Multi-class classification.
- Lecture 10: Ranking.
- Lecture 11: Reinforcement learning.
- Lecture 12: Learning languages.
The following is the required textbook for the class. It covers all
the material presented (and a lot more):
An extensive list of recommended papers for further reading is
provided in the lecture slides.
- Homework 1 [solution]
- Homework 2 [solution]
- Homework 3 [solution]