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!
| Introduction | |||
| 3/30 | Adam Kalai | Basic Online Learning setting, Perceptron algorithm | The first lecture was a summary of the first two lectures from a course of Avrim Blum (notes). The program "and". |
| 4/1 | John Langford | Test Set Bound/Occam's Razor bound | A tutorial (We cover pages 1-16). Slides. A bound calculation program. |
| 4/6 | John Langford | Assorted reductions to Classification | slides A paper on reducing importance weighted classification to classification. A paper on general supervised learning reductions. |
| 4/8 | Partha Niyogi | Least squares & discriminant analysis | |
| Kernel Based Machines | |||
| 4/13 | Partha Niyogi | What are RKHSs?, least squares regularization | |
| 4/15 | Partha Niyogi | SVMs | |
| 4/20 | Partha Niyogi | Eigenvalue problems in RKHSs | a paper and another paper. |
| 4/22 | Partha Niyogi | Generalization Analysis | |
| Reductions | |||
| 4/27 | John Langford | Boosting | slides Schapire's overview Dietterich's survey paper boosting.org |
| 4/29 | John Langford | Reinforcement Learning to Classification | slides a RLGen paper PSDP paper sparse sampling paper Ng's flying helicopter |
| 5/4 | Midterm | ||
| Online Learning | |||
| 5/6 | Adam Kalai | Weighted Majority | Notes The program weighted majority |
| 5/11 | Adam Kalai | Winnow | Notes |
| Generalization Bounds | |||
| 5/13 | John Langford | PAC-MDL bound & applications | slides PAC-MDL bound paper PAC-MDL applied to clustering A program to calculate the bound. |
| 5/18 | John Langford | Generalization wrapup, methods for overfitting | slides |
| 5/20 | Partha Niyogi | Algorithmic stability bounds | |
| Unsupervised Learning | |||
| 5/25 | Partha Niyogi | Manifolds | |
| 5/27 | Partha Niyogi | Clustering, Spectral Graph partitioning | |
| 6/1 | Partha Niyogi | Dimensionality Reduction | |
| 6/3 | Partha Niyogi | EM Algorithm |