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.12.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; beginVCdimension; Sauer's lemma; upper bound on sample complexity  scribe notes [3.5] 
6  Th 2/23  VCdimension; Sauer's lemma; upper bound on sample complexity; lower bounds on sample complexity  scribe notes [3.23.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  Marginsbased analysis of boosting  scribe notes Robert E. Schapire, Yoav Freund, Peter Bartlett
and Wee Sun Lee. 
11  Tu 3/14  Finish boosting; begin supportvector machines  scribe notes Excerpt from Vapnik's The nature of statistical learning theory. 
12  Th 3/16  Finish supportvector machines  scribe notes 
13  Tu 3/28  Online learning; learning with expert advice; weighted majority algorithm  scribe notes Avrim Blum. "mindreading" game based on online 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; WidrowHoff algorithm  scribe notes Jyrki Kivinen and Manfred K. Warmuth. 
17  Tu 4/11  finish WidrowHoff; EG; Converting online 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 online log loss  scribe notes 
20  Tu 4/25  online 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. 