![]() Princeton University
|
Computer Science 511
|
|
Numbers in brackets under "reading" refer to chapters or sections of Kearns & Vazirani.
# |
Date |
Topic |
Reading |
1 | Tu 2/7 | General introduction to machine learning; consistency model | scribe notes |
2 | Th 2/9 | Consistency model; review of probability; begin PAC model |
scribe notes for a very brief review of probability, see, for instance, Appendix C.2 and C.3 in Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. |
3 | Tu 2/14 | PAC model; simple special cases; begin Occam's razor | scribe notes [1], [2.1-2.2] |
4 | Th 2/16 | Prove Occam's razor; begin sample complexity for infinite hypothesis spaces | scribe notes [3.1] |
5 | Tu 2/21 | Growth function and sample complexity for infinite hypothesis spaces; beginVC-dimension; Sauer's lemma; upper bound on sample complexity | scribe notes [3.5] |
6 | Th 2/23 | VC-dimension; Sauer's lemma; upper bound on sample complexity; lower bounds on sample complexity | scribe notes [3.2-3.4], [3.6] |
7 | Tu 2/28 | Finish lower bound; handling inconsistent hypotheses; begin Chernoff bounds | scribe notes |
8 | Th 3/2 | Finish Chernoff bounds; McDiarmid's inequality; error bounds for inconsistent hypotheses; overfitting; begin boosting | scribe notes |
9 | Tu 3/7 | Boosting; training error bound; naive generalization bounds | scribe notes Robert E. Schapire. |
10 | Th 3/9 | Margins-based analysis of boosting | scribe notes Robert E. Schapire, Yoav Freund, Peter Bartlett
and Wee Sun Lee. |
11 | Tu 3/14 | Finish boosting; begin support-vector machines | scribe notes Excerpt from Vapnik's The nature of statistical learning theory. |
12 | Th 3/16 | Finish support-vector machines | scribe notes |
13 | Tu 3/28 | On-line learning; learning with expert advice; weighted majority algorithm | scribe notes Avrim Blum. "mind-reading" game based on on-line learning |
14 | Th 3/30 | Finish weighted majority algorithm; perceptron algorithm | scribe notes |
15 | Tu 4/4 | Winnow; begin regression | scribe notes |
16 | Th 4/6 | linear regression; Widrow-Hoff algorithm | scribe notes Jyrki Kivinen and Manfred K. Warmuth. |
17 | Tu 4/11 | finish Widrow-Hoff; EG; Converting on-line to batch | scribe notes |
Th 4/13 | (no class) | ||
18 | Tu 4/18 | modeling probability distributions; maximum likelihood; maximum entropy modeling of distributions | scribe notes There are a number of excellent papers and other
materials on maximum entropy
here. Stephen Della Pietra,
Vincent Della Pietra and John Lafferty. |
19 | Th 4/20 | finish maxent; begin on-line log loss | scribe notes |
20 | Tu 4/25 | on-line log loss and universal compression; Bayes algorithm | scribe notes |
21 | Th 4/27 | shifting experts | scribe notes Mark Herbster and Manfred K. Warmuth. |
22 | Tu 5/2 | portfolio selection | scribe notes Avrim Blum and Adam Kalai. For an opposing view to this approach, see the following short paper (and try to detect what is unusual about the writing): Paul A. Samuelson |
23 | Th 5/4 | game theory and learning | scribe notes Yoav Freund and Robert E. Schapire. Or, for more details, see: Yoav Freund and Robert E. Schapire. |