Prediction Games and Arcing Algorithms
Leo Breiman · Neural Computation · 1999
The theory behind the success of adaptive reweighting and combining algorithms (arcing) such as Adaboost (Freund & Schapire, 1996a, 1997) and others in reducing generalization error has not been well understood. By formulating prediction as a game where one player makes a selection from instances in the training set and the other a convex linear combination of predictors from a finite set, existing arcing algorithms are shown to be algorithms for finding good game strategies. The minimax theorem is an essential ingredient of the convergence proofs. An arcing algorithm is described that converges to the optimal strategy. A bound on the generalization error for the combined predictors in terms of their maximum error is proven that is sharper than bounds to date. Schapire, Freund, Bartlett, and Lee (1997) offered an explanation of why Adaboost works in terms of its ability to produce generally high margins. The empirical comparison of Adaboost to the optimal arching algorithm shows that their explanation is not complete.
Cited by 530 works. doi:10.1162/089976699300016106
Authors
References
- Bagging Predictors
- A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
- Experiments with a new boosting algorithm
- Advances in neural information processing systems 7
- Bagging predictors
- Advances in neural information processing systems 7
- An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants
- Bagging, boosting, and C4.S
- Theory of Games and Statistical Decisions.
- Boosting Decision Trees