Machine Learning and Learning Theory (Class: CMSC 35400-1)

University of Chicago Computer Science and Statistics Spring 2004 Tuesday and Thursday 10:30-12:00 Reyerson 277

Instructors: John Langford, and Partha Niyogi

guest lecturer: Adam Kalai

This is an advanced graduate level class covering the union of machine learning and learning theory with the following topics:

1) Online learning
2) Kernel based machines
3) Prediction bounds
4) Reductions between learning problems
5) Unsupervised learning

We emphasize those techniques which are both theoretically analyzable and practically useful for a multitude of problems. Significant side notes and ancillary programs will be available online for future reference.

At the end of this class, students will have a working understanding of how to build (and avoid pitfalls of) working machine learning systems. For the covered topics, students will have an understanding of the state of the art sufficient to contribute to further academic development.

Anything which hasn't happened is speculation!
3/30Adam KalaiBasic Online Learning setting, Perceptron algorithmThe first lecture was a summary of the first two lectures from a course of Avrim Blum (notes). The program "and".
4/1John LangfordTest Set Bound/Occam's Razor boundA tutorial (We cover pages 1-16). Slides. A bound calculation program.
4/6John LangfordAssorted reductions to Classificationslides A paper on reducing importance weighted classification to classification. A paper on general supervised learning reductions.
4/8Partha NiyogiLeast squares & discriminant analysis
Kernel Based Machines
4/13Partha NiyogiWhat are RKHSs?, least squares regularization
4/15Partha NiyogiSVMs
4/20Partha NiyogiEigenvalue problems in RKHSsa paper and another paper.
4/22Partha NiyogiGeneralization Analysis
4/27John LangfordBoostingslides Schapire's overview Dietterich's survey paper
4/29John LangfordReinforcement Learning to Classificationslides a RLGen paper PSDP paper sparse sampling paper Ng's flying helicopter
Online Learning
5/6Adam KalaiWeighted MajorityNotes The program weighted majority
5/11Adam KalaiWinnowNotes
Generalization Bounds
5/13John LangfordPAC-MDL bound & applicationsslides PAC-MDL bound paper PAC-MDL applied to clustering A program to calculate the bound.
5/18John LangfordGeneralization wrapup, methods for overfittingslides
5/20Partha NiyogiAlgorithmic stability bounds
Unsupervised Learning
5/25Partha NiyogiManifolds
5/27Partha NiyogiClustering, Spectral Graph partitioning
6/1Partha NiyogiDimensionality Reduction
6/3Partha NiyogiEM Algorithm