Boosting: Foundations and Algorithms

Contents......Page 8
Series Foreword......Page 12
Preface......Page 14
1 Introduction and Overview......Page 18
1.1 Classification Problems and Machine Learning......Page 19
1.2 Boosting......Page 21
1.3 Resistance to Overfitting and the Margins Theory......Page 31
1.4 Foundations and Algorithms......Page 34
I CORE ANALYSIS......Page 38
2 Foundations of Machine Learning......Page 40
2.1 A Direct Approach to Machine Learning......Page 41
2.2 General Methods of Analysis......Page 47
2.3 A Foundation for the Study of Boosting Algorithms......Page 60
3 Using AdaBoost to Minimize Training Error......Page 70
3.1 A Bound on AdaBoost’s Training Error......Page 71
3.2 A Sufficient Condition for Weak Learnability......Page 73
3.3 Relation to Chernoff Bounds......Page 77
3.4 Using and Designing Base Learning Algorithms......Page 79
4.1 Using VC Theory to Bound the Generalization Error......Page 92
4.2 Compression-Based Bounds......Page 100
4.3 The Equivalence of Strong and Weak Learnability......Page 103
5 The Margins Explanation for Boosting’s Effectiveness......Page 110
5.1 Margin as a Measure of Confidence......Page 111
5.2 A Margins-Based Analysis of the Generalization Error......Page 114
5.3 Analysis Based on Rademacher Complexity......Page 123
5.4 The Effect of Boosting on Margin Distributions......Page 128
5.5 Bias, Variance, and Stability......Page 134
5.6 Relation to Support-Vector Machines......Page 139
5.7 Practical Applications of Margins......Page 145
II FUNDAMENTAL PERSPECTIVES......Page 156
6 Game Theory, Online Learning, and Boosting......Page 158
6.1 Game Theory......Page 159
6.2 Learning in Repeated Game Playing......Page 162
6.3 Online Prediction......Page 170
6.4 Boosting......Page 174
6.5 Application to a “Mind-Reading” Game......Page 180
7 Loss Minimization and Generalizations of Boosting......Page 192
7.1 AdaBoost’s Loss Function......Page 194
7.2 Coordinate Descent......Page 196
7.3 Loss Minimization Cannot Explain Generalization......Page 201
7.4 Functional Gradient Descent......Page 205
7.5 Logistic Regression and Conditional Probabilities......Page 211
7.6 Regularization......Page 219
7.7 Applications to Data-Limited Learning......Page 228
8 Boosting, Convex Optimization, and Information Geometry......Page 244
8.1 Iterative Projection Algorithms......Page 245
8.2 Proving the Convergence of AdaBoost......Page 260
8.3 Unification with Logistic Regression......Page 269
8.4 Application to Species Distribution Modeling......Page 272
III ALGORITHMIC EXTENSIONS......Page 286
9 Using Confidence-Rated Weak Predictions......Page 288
9.1 The Framework......Page 290
9.2 General Methods for Algorithm Design......Page 292
9.3 Learning Rule-Sets......Page 304
9.4 Alternating Decision Trees......Page 307
10 Multiclass Classification Problems......Page 320
10.1 A Direct Extension to the Multiclass Case......Page 322
10.2 The One-against-All Reduction and Multi-label Classification......Page 327
10.3 Application to Semantic Classification......Page 333
10.4 General Reductions Using Output Codes......Page 337
11 Learning to Rank......Page 358
11.1 A Formal Framework for Ranking Problems......Page 359
11.2 A Boosting Algorithm for the Ranking Task......Page 362
11.3 Methods for Improving Efficiency......Page 368
11.4 Multiclass, Multi-label Classification......Page 378
11.5 Applications......Page 381
IV ADVANCED THEORY......Page 392
12 Attaining the Best Possible Accuracy......Page 394
12.1 Optimality in Classification and Risk Minimization......Page 395
12.2 Approaching the Optimal Risk......Page 399
12.3 How Minimizing Risk Can Lead to Poor Accuracy......Page 415
13 Optimally Efficient Boosting......Page 432
13.1 The Boost-by-Majority Algorithm......Page 433
13.2 Optimal Generalization Error......Page 449
13.3 Relation to AdaBoost......Page 465
14 Boosting in Continuous Time......Page 476
14.1 Adaptiveness in the Limit of Continuous Time......Page 477
14.2 BrownBoost......Page 485
14.3 AdaBoost as a Special Case of BrownBoost......Page 493
14.4 Experiments with Noisy Data......Page 500
A.1 General Notation......Page 508
A.2 Norms......Page 509
A.4 Limits......Page 510
A.5 Continuity, Closed Sets, and Compactness......Page 511
A.6 Derivatives, Gradients, and Taylor’s Theorem......Page 512
A.7 Convexity......Page 513
A.8 The Method of Lagrange Multipliers......Page 514
A.9 Some Distributions and the Central Limit Theorem......Page 515
Bibliography......Page 518
Index of Algorithms, Figures, and Tables......Page 528
Subject and Author Index......Page 530