Instructor: Rob Schapire
TA: Donna Gabai
Time: Tue / Thurs 11:00-12:20
Place: Frick Lab room 124

General course information.
Preparing scribe notes.
Final project information.


Lecture notes

  1. Feb. 4: Introduction, basic definitions, the consistency model. ps pdf
  2. Feb. 6: Review of probability; PAC learning model. ps pdf
  3. Feb. 11: Examples of PAC learnable classes; Sample complexity for finite hypothesis spaces; Occam's razor. ps pdf
  4. Feb. 13: General bounds on sample complexity for infinite hypothesis spaces. ps pdf
  5. Feb. 18: Sample complexity bound in terms of the growth function; VC-dimension; Sauer's Lemma. ps pdf
  6. Feb. 20: A lower bound on sample complexity using VC-dimension; handling inconsistent hypotheses; beginning of Chernoff bounds. ps pdf
  7. Feb. 25: Chernoff bounds proof; McDiarmid's inequality; error bounds for inconsistent hypotheses; overfitting. ps pdf
  8. Feb. 27: Boosting: Introduction and bounding the training error. ps pdf
  9. Mar. 4: Generalization error of boosting. ps pdf
  10. Mar. 6: Finished generalization error of boosting; support-vector machines. ps pdf
  11. Mar. 11: Finished support-vector machines; learning with expert advice; the halving algorithm. ps pdf
  12. Mar. 13: Continued learning with expert advice; the weighted majority algorithm. ps pdf
  13. Mar. 25: Perceptron and winnow. ps pdf
  14. Mar. 27: Analysis of winnow; square loss; beginning linear regression. ps pdf
  15. Apr. 1: Finish linear regression; Widrow-Hoff and other on-line algorithms for linear regression. ps pdf
  16. Apr. 3: Converting on-line to batch; neural networks; modelling probability distributions. ps pdf
  17. Apr. 8: Maximum likelihood and maximum entropy modeling of distributions. ps pdf
  18. Apr. 10: Analysis of maximum entropy; Bayes algorithm for on-line learning with log loss. ps pdf
  19. Apr. 15: Bayes algorithm; switching experts; beginning investment portfolios. ps pdf
  20. Apr. 17: Cover's universal portfolio algorithm; tips on running machine learning experiments. ps pdf
  21. Apr. 22: Membership and equivalence queries; Angluin's algorithm for learning finite automata. ps pdf
  22. Apr. 24: Angluin's algorithm continued; begin reinforcement learning and Markov decision processes. ps pdf
  23. Apr. 29: Reinforcement learning. ps pdf
  24. May 1: More reinforcement learning. ps pdf

Additional Readings

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


Here is a list of optional books for further background reading. All of these are being placed on reserve at the Engineering Library.