Georgia Tech, 8803 Machine Learning Theory, Spring 2010
MACHINE LEARNING THEORY
Time: Tues/Thurs 3:05-4:25, Place:
Skiles 168.
Course description: Machine learning studies automatic methods
for learning to make accurate predictions or useful decisions based on
past observations and experience, and it has become a highly successful
discipline with applications in many areas such as natural language
processing, speech recognition, computer vision, or gene discovery.
This course on the design and theoretical analysis of machine learning
methods will cover a broad range of important problems studied in
theoretical machine learning. It will provide a basic arsenal of
powerful mathematical tools for their analysis, focusing on both
statistical and computational aspects. We will examine questions such
as "What guarantees can we prove on the performance of learning
algorithms? " and "What can we say about the inherent ease or
difficulty of learning problems?". In addressing these and related
questions we will make connections to statistics, algorithms,
complexity theory, information theory, game theory, and empirical
machine learning research.
Recommended (but not required) textbooks:
Additionally, we will use a number of survery articles and tutorials.
Office hours: Just stop by my office or make an appointment.
Final
Exam: Here it the
exam. It's due at 4:00 PM on May 6th.
Homeworks
Lecture Notes & Handouts
- 01/12: Introduction.
The
consistency model and PAC model for passive supervised learning.
See also Chapter 1 in the Kearns-Vazirani book.
- 01/14: PAC
model. Perceptron algorithm for learning linear separators.
- 01/19: The
margin perceptron algorithm. The mistake bound model.
- 01/21: The
mistake bound model (cont'd). The Winnow algorithm.
See also: An
Online learning survey by A. Blum. The
original Winnow paper by N. Littlestone.
- 01/26: Tail
inequalities. Simple
sample complexity results.
- 01/28: Sample
complexity results for infinite hypotheses spaces.
- 02/02: Sample
complexity results for infinite hypotheses spaces(cont'd). Sauer's lemma.
See
also Chapter 3 in the Kearns-Vazirani book.
- 02/04: Lower
bounds on
the complexity of passive supervised learning.
- 02/09: Boosting
I: Weak to strong learning, Schapire's original method. See Avrim
Blum's
notes.
See also Chapter 4 in the Kearns-Vazirani book.
- 02/11: Boosting
II: Adaboost.
See Rob
Schapire's
notes.
- 02/16: Boosting
and margins.
- 02/18:
Semi-supervised Learning.
See: A
Discriminative
Model
for
Semi-Supervised
Learning.
- 02/23: Generalization bounds based on the Rademacher Complexity.
- 02/25: Properties of the Rademacher Complexity.
See Introduction
to
Statistical
Learning
Theory by O. Bousquet, S. Boucheron,
and G. Lugosi.
- 03/02: Kernels and Margins.
- 03/04:
Kernels and Margins (cont'd).
See: Kernels
as
Features:
On
Kernels,
Margins,
and
Low-dimensional
Mappings.
- 03/09: More
examples of kernels. ANOVA kernels and diffusion kernels.
- 03/11: Model Selection.
See Model
Selection and
Error Estimation by P. Bartlett, S. Boucheron, and G. Lugosi.
- 03/16: Support Vector Machines See Andrew
Ng's
notes. See also Boyd’s
lectures.
- 03/18: Limitations
of
Kernel
Methods.
- 03/29: The Random
Classification Noise Model.
- 04/01: The Random
Classification Noise Model (cont'd). The Statistical Query model. See Avrim
Blum's
notes.
See
also Chapter 5 in the Kearns-Vazirani book.
- 04/06: Fourier-based learning and learning with Membership
queries: the KM
algorithm. See Ron
Rivest's lecture notes.
- 04/08: Fourier-based learning and learning with Membership
queries: the KM
algorithm(con't). See Ron
Rivest's lecture notes.
See also
Yishay Mansour's survey.
- 04/13:
Incorporating Unlabeled Data in the Learning Process.
- 04/15: Active Learning
Slides and Notes.
- 04/20: Project Presentations.
- 04/22: Project Presentations.
- 04/27: Sample Complexity Results for Active Learning. See Shai
Shalev-Shwartz's notes.
- 04/29: The
Weighted Majority Algorithm. Course Retrospective.
Additional
Readings
& More Information
Books and tutorials: