Abstract
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 arcing algorithm shows that their explanation is not complete.
Keywords
MinimaxAlgorithmGeneralizationAdaBoostGeneralization errorMathematicsConvergence (economics)Set (abstract data type)Mathematical proofComputer scienceMathematical optimizationArtificial intelligenceArtificial neural network
Affiliated Institutions
Related Publications
Finite-Dimensional Approximation of Gaussian Processes
Gaussian process (GP) prediction suffers from O(n3) scaling with the data set size n. By using a finite-dimensional basis to approximate the GP predictor, the computational comp...
Simultaneous Regression Shrinkage, Variable Selection, and Supervised Clustering of Predictors with OSCAR
Summary Variable selection can be challenging, particularly in situations with a large number of predictors with possibly high correlations, such as gene expression data. In thi...
Quantifying the Sim-To-Real Gap in UAV Disturbance Rejection
Due to the safety risks and training sample inefficiency, it is often preferred to develop controllers in simulation. However, minor differences between the simulation and the r...
A Stochastic Algorithm for Self-Organization of Autonomous Swarms
In earlier work of the authors simulation results indicated the possibility of achieving self-organization of autonomous vehicles through Gibbs sampler-based simulated annealing...
Partial least squares regression and projection on latent structure regression (PLS Regression)
Abstract Partial least squares (PLS) regression ( a.k.a. projection on latent structures) is a recent technique that combines features from and generalizes principal component a...
Publication Info
- Year
- 1999
- Type
- article
- Volume
- 11
- Issue
- 7
- Pages
- 1493-1517
- Citations
- 535
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
535
OpenAlex
Cite This
Leo Breiman
(1999).
Prediction Games and Arcing Algorithms.
Neural Computation
, 11
(7)
, 1493-1517.
https://doi.org/10.1162/089976699300016106
Identifiers
- DOI
- 10.1162/089976699300016106