COMS 4771 Machine Learning (Spring 2008)

Announcements (Blog)

Lectures and Homeworks

Date Topic Notes (pdf)
Sam Roweis's probability and statistics review
Iain Murray's crib-sheet
Andrew Moore's probability review

Thomas Minka's Glossary of ML concepts

Tue, Jan 22 Lecture 1
What is machine learning? Basic concepts, types of prior information, types of learning problems, loss function semantics. Netflix competition.

See also Yann LeCun's slides and Sam Roweis's tutorial.

Thu, Jan 24 Lecture 2
Decision tree learning, overfitting, bias-variance decomposition

Tom Mitchell's book (Chapter 3)
Quinlan's seminal paper (>5000 citations)
Tom Dietterich's writeup on overfitting, and a paper on bias.

Tue, Jan 29 Lecture 3
Bayesian Learning

Homework 1 (with solutions, before class; 10% of the grade)


Zoubin Ghahramani's tutorial and a short introduction with useful links

Thu, Jan 31 Lecture 4
Regression: linear regression, least squares and other loss functions, regularized regression (Cynthia)

Tikhonov regularization

Donoho's result on l1 regularization forcing sparsity (here, and here)

More on sparsity: An overview of compressed sensing at Terence Tao's blog

Quantile regression

Mean, median and all that

Tue, Feb 5 Lecture 5
Reductions between Problems (or how to solve homework problem 1)

Reading list

Thu, Feb 7 Lecture 6

Learning Theory block begins.
Mistake-bound model. Halving and the standard optimal algorithm.

slides (reload)

(we will follow Avrim Blum's lectures)
Basic definitions (from Avrim's class) + survey

Littlestone, Learning quickly when irrelevant attributes abound

Tue, Feb 12 Lecture 7 Winnow and Weighted Majority.
Homework 1 is due

Homework 2 is assigned (due Feb 26, extended)


Littlestone and Warmuth, The Weighted Majority Algorithm.

Thu, Feb 14 Lecture 8 Randomized Weighted Majority and Perceptron
slides (please reload)

Large Margin Classification Using the Perceptron Algorithm, by Freund and Schapire

Tue, Feb 19 Lecture 9 (Cynthia)
AdaBoost and Logistic Regression, margins theory for Boosting (Part I)
Cynthia's notes and slides

A short introduction to boosting, by Freund and Schapire

Rob Schapire's Boosting page

Thu, Feb 21 Lecture 10 (Cynthia)
AdaBoost and Logistic Regression, margins theory for Boosting (Part II)
Cynthia's slides and notes

Tue, Feb 26 Lecture 11
Support vector machines and kernel methods (Sanjoy)

Homework 2 is due (solutions)

Thu, Feb 28 Lecture 12
Support vector machines (Sanjoy)
Chris Burges's tutorial on SVMs
Tue, Mar 4 Lecture 13
We will go to Sanjoy's talk on "Projection Pursuit, Gaussian Scale Mixtures, and the EM Algorithm"
Thu, Mar 6 Lecture 14
Learning to rank (Cynthia)
Tue, Mar 11 Lecture 15
Prediction bounds (John)

Practical Prediction Theory for Classification: Tutorial

Test set bound implementation in matlab (by Pantelis Monogioudis)

Thu, Mar 13 MIDTERM

grade statistics

Tue, Mar 18 Spring Break
Thu, Mar 20 Spring Break
Tue, Mar 25 Lecture 16
PAC learning, VC-dimension

Avrim Blum's notes
Rob Schapire's class notes
Shai Ben-David's notes

Valiant's original Theory of the Learnable paper
Original Occam's Razor paper

Thu, Mar 27 Lecture 17
Active Learning
slides (reload)


Tue, Apr 1 Lecture 18
Large Scale Learning (John)

links to the code

Thu, Apr 3 Lecture 19
Nearest Neighbor Methods


Fri, Apr 4 Final Projects
Tue, Apr 8 Lecture 20
Multi-Armed Bandits

Thu, Apr 10 Lecture 21
Reinforcement Learning (John)

additional material

Tue, Apr 15 Lecture 22
Modular Learning (John)

Thu, Apr 17

Tue, Apr 22

Thu, Apr 24

Tue, Apr 29

Lectures 23-26
Graphical Models and Hidden Markov Models (Tony)
slides 1

slides 2

slides 3

slides 4

slides 5

slides 6

slides 7

An introduction to Graphical Models, by Michael Jordan and Chris Bishop (you should receive an email with the password)

Thu, May 1 FINAL EXAM Solutions, comments and grading information