15-854 MACHINE LEARNING THEORY

Instructor: Avrim Blum
Time: MW 1:30-2:50
Place: Wean 4615A
12 Units, 1 CU
Course description: This course will focus on theoretical aspects of machine learning. We will examine questions such as: What kinds of guarantees can one prove about learning algorithms? What are good algorithms for achieving certain types of goals? Can we devise models that are both amenable to mathematical analysis and make sense empirically? What can we say about the inherent ease or difficulty of learning problems? Addressing these questions will require pulling in notions and ideas from statistics, complexity theory, cryptography, and on-line algorithms, and empirical machine learning research.

Text: An Introduction to Computational Learning Theory by Michael Kearns and Umesh Vazirani, plus papers and notes for topics not in the book.

Office hours: Just stop by my office or make an appointment.

Some ideas for presentations and projects.

Handouts

Lecture Notes

  1. 01/12:Overview, basic definitions, the consistency model
  2. 01/14:Consistency for simple neural net is NP-hard. Intro to Mistake-Bound model
  3. 01/19:Decision lists, Halving alg, Std Opt, Perceptron Alg
  4. 01/21:The Weighted-Majority Algorithm, Randomized Weighted Majority
  5. 01/26:Randomized WM contd, 2-player games, the Winnow algorithm
  6. 01/28:Learning from string-valued features, intro to PAC model
  7. 02/02:MB==>PAC, Occam's razor
  8. 02/04:Occam's razor cont, intro to VC-dim and C[m]. See also the slides.
  9. 02/09:VC-dim and splitting number: upper and lower bound proofs.
  10. 02/11:Probabilistic inequalities and proof of Chernoff, intro to weak-learning.
  11. 02/16:Weak and strong learning, Adaboost. Here are Yoav Freund's slides
  12. 02/18:Learning with noise.
  13. 02/23:The Statistical Query model.
  14. 02/25:Characterizing SQs with Fourier analysis.
  15. 03/04:Fourier analysis, intro to Memb queries, weak-learning DNF.
  16. 03/09:Finding large Fourier coeffs, Bshouty's alg for learning XOR of terms.
  17. 03/11:Learning deterministic finite-state environments. Text and Slides.
  18. 03/16:Learning finite-state environments contd, Intro to HMMs.
  19. 03/18:HMMs and weak learning of monotone functions.
  20. 03/30:Hardness results for learning based on cryptography and vice versa.
  21. 04/01:Query-by-Committee [Kamal]. Paper by Freund et al.
  22. 04/06:Probabilistic concepts [Haiqin]. Paper by Kearns & Schaipre.
  23. 04/08:The EM algorithm [Dimitris]. Paper by Xu and Jordan.
  24. 04/13:VC-dimension and "margins" [Goran]. Paper by Schapire et al.
  25. 04/15:Bias and variance [Chuck].
  26. 04/20:Piecemeal exploration [Michael].
  27. 04/22:Intro to Reinforcement Learning [Jovan].
  28. 04/27:Combining Reinforcement Learning with function approximation [Bryan]. Papers by Geoff Gordon: 1, 2, 3.
  29. 04/29:Projects [Paul, Jason, John].

Additional Readings

(Related papers that go into more detail on topics discussed in class)