Princeton University |
Computer Science 598A |
Spring
|
This syllabus is constantly evolving as the semester progresses, so check back often (and let me know if it seems not to be up to date).
# |
Date |
Topic |
Readings
|
| 1 | Tu, 2/7 | General introduction to boosting |
1 slides |
|
2 3 |
Th, 2/9 Tu, 2/14 |
Foundations of machine learning; methods of analysis; PAC learning | 2 |
| 4 | Th, 2/16 | Training error of AdaBoost; sufficient conditions for weak learning; relation to Chernoff bounds | 3.1-3.3 |
| 5 | Tu, 2/21 |
Design of weak learning algorithms; direct bounds on generalization error |
3.4; 4.1 |
| 6 | Th, 2/23 | Compression-based bounds; equivalence of strong and weak learning | 4.2-4.3 |
| 7 | Tu, 2/28 | Margins; analysis of generalization error |
5.1-5.2 margins movie |
| 8 | Th, 3/1 | Rademacher complexity; effect of boosting on margins | 5.3-5.4 |
| 9 | Tu, 3/6 | Maximizing minimum margin; SVMs; other margin topics | 5.5-5.7 |
| 10 | Th, 3/8 | Classical game theory; repeated games; MW algorithm and analysis | 6.1-6.2.3 |
| Tu, 3/13 | MIDTERM (in class) | ||
| 11 | Th, 3/15 | Finish MW analysis; minmax theorem; online learning | 6.2.4-6.3 |
| 12 | Tu, 3/27 |
Game theory and boosting; begin boosting as loss minimization |
6.4-6.5; begin 7 |
|
13 14 |
Th, 3/29 Tu, 4/3 |
boosting as loss minimization | 7 |
| 15 | Th, 4/5 |
Finish boosting as loss minimization; begin iterative projection algorithms |
begin 8 |
|
16 17 |
Tu, 4/10 Th, 4/12 |
Iterative projection algorithms; information geometry | 8 |
| 18 | Tu, 4/17 |
Quick look at confidence-rated weak hypotheses (and other topics); Bayes error and minimum risk |
9.1; 9.2.6; 12.1 |
| 19 | Tu, 4/24 |
Consistency of AdaBoost; "breaking" AdaBoost with just a little noise |
12.2; 12.3 |
|
20 21 |
Th, 4/26 Tu, 5/1 |
Optimal boosting | 13 |
| 22 | Th, 5/3 | Boosting in continuous time | 14 |