Elamur Research
☰
home / papers / 1996 / Bagging Predictors

Bagging Predictors

Summary

Bagging ("bootstrap aggregating") builds several versions of a predictor by training each on a bootstrap resample of the training set and then combines them, by voting for classification or averaging for regression. The paper argues that the gain comes from reducing variance: learners whose output changes a lot with small perturbations of the data, such as decision trees or subset selection in regression, benefit most, whereas stable learners such as nearest neighbours gain little or nothing. Experiments on real and simulated datasets show substantial error reductions for unstable methods. The idea became a foundation of later ensemble methods such as random forests.

How Mova uses it

Effectiveness in Mova

Measured on SVAMP on the idea test bench (architecture notes, table of ideas from papers):

👨‍🔬💥

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "free access at the publisher/repository (Machine Learning, publishedVersion), no licence stated — read only" does not allow redistributing the text itself. Original — link.springer.com/content/pdf/10.1007/BF00058655.pdf

Summary

Breiman asks how to make a single learned predictor more accurate when only one training set is available. His answer is bagging, short for bootstrap aggregating. Many bootstrap samples are drawn with replacement from the learning set, and the same base method is trained on each sample. The resulting models are then combined: averaging for numeric targets, plurality voting for class labels.

He tests the idea mainly with CART classification and regression trees. The experiments draw on seven UCI-style data sets (soybean, glass, diabetes, ionosphere, breast cancer, heart, and waveform), along with four larger Statlog sets (letters, satellite, shuttle, DNA) and several regression problems (Boston Housing, Ozone, Friedman #1–#3). Subset selection in linear regression on simulated data is also studied.

Bagging cut tree error by large margins on almost every data set. A short argument based on the inequality E[Z²] ≥ (E[Z])² explains why. Averaging helps most when the base method is unstable, meaning small changes to the training data produce very different models. Stable methods gain little and may even get slightly worse. This gives a cheap, general recipe for improving high-variance learners.

Key points

  • Classification trees: bagging lowered test misclassification by 6% to 77% across data sets. On waveform, error fell from 29.1% to 19.3%. The best attainable error there is 14%, so bagging removed about two-thirds of the excess error.
  • Diabetes: the gain was small (25.3% → 23.9%). Breiman suggests this is because the result is already near the best error any of the 22 Statlog classifiers achieved on it (22.3%).
  • Statlog comparison: on letters, satellite, shuttle and DNA, bagged trees placed 1st or 2nd on each set. Their average rank was 1.8; the next-best method averaged 6.3, and C4.5, k-NN and neural nets ranked lower still.
  • Regression trees: with 25 bootstrap replicates, bagging cut mean squared error by 21% to 46%. On Boston Housing, for example, it fell from 20.0 to 11.6.
  • Evaluation protocol: classification used 50 bootstrap trees. Results were averaged over 100 random learning/test splits, and standard errors were reported for every number.

Interesting ideas

  • Instability as the deciding factor. Whether to bag depends on how sensitive a learner is to perturbations of its training data. Checking this sensitivity first is a quick way to predict whether ensembling any model, such as a parser or tagger, is worth the extra compute.
  • Prune bootstrap models on the original data. Each tree is grown on a bootstrap sample but pruned using the full original learning set. This reuses all available data for model selection without carving out an additional holdout.
  • A minimal proof of why averaging helps. The Jensen-type inequality shows the averaged predictor's squared error can never exceed the average squared error of the individual predictors. The gap grows with model variability, which gives a clean intuition for any averaging ensemble.
  • Judge gains against a performance ceiling. Breiman compares each improvement to the known optimal error or the best published result, and frames progress as the share of excess error removed. This avoids misreading a small gain near the ceiling as a weakness.
  • Repeated random splits with standard errors. Averaging over 100 splits and reporting spread makes comparisons far more trustworthy than a single cross-validation. Breiman explicitly notes that single-split estimates made the Statlog comparisons unreliable.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.1007/bf00058655

@inproceedings{breiman1996bagging,
  title = {{Bagging Predictors}},
  author = {Breiman, Leo},
  booktitle = {Machine Learning},
  year = {1996},
  doi = {10.1007/bf00058655},
  url = {https://doi.org/10.1007/bf00058655}
}

References

16 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Belsley, D., Kuh, E.. & Welsch, R. (1980). "Regression Diagnostics", John Wiley and Sons. find
  2. Breiman, L. (1994). Heuristics of instability in model selection, Technical Report, Statistics Department, University of California at Berkeley (to appear, Annals of Statistics). find
  3. Breiman, L , Friedman, J., Olshen. R., & Stone, C. (1984). "Classification and Regression Trees", Wadsworth. find
  4. Breiman, L. & Friedman, J. (1985). Estimating optimal transformations in multiple regression and correlation (with discussion), Journal of the American Statistical Association, 80, 580-619 . find
  5. Breiman, L. & Spector, P (1992). Submodel Selection and Evaluation in Regression - the X-Random Case, International Statistical Review, 3, 291-319 */~ + B untine, W. (1991). "Learning classification trees", Artificial Intelligence Frontiers in Statistics, ed D.J. Hand, Chapman and Hall, London, 182-… find
  6. Dietterich, T.G. & Bakiri, G. (1991). Error-correcting output codes: A general method for improving multiclass inductive learning programs, Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91 ), Anaheim, CA: AAA1 Press. find
  7. Efron, B., & Tibshirani, R. (1993). "An Introduction to the Bootstrap". Chapman and Hall. find
  8. Friedman, J. (1991). Multivariate adaptive regression splines (with discussion), Annals of Statistics, 19, 1-141. find
  9. Heath, D., KasiC S., & Salzberg, S. (1993). k-dt: a multi-tree learning method. Proceedings of the Second International Workshop on Multi strategy Learning, 1002-1007, Chambery, France, Morgan Kaufman. find
  10. Kwok, S., & Carter, C. (1990). Multiple decision trees, Uncertainty in Artificial Intelligence 4, ed. Shachter, R., Levitt, T, Kanal, L., and Lemrner, J., North-Holland, 327-335. find
  11. Michie, D., Spiegelhalter, D.J. & Taylor, C.C. (19~4). Machine Learning, Neural and Statistical Classification. Ellis Horwood Limited. find
  12. Olshen, R., Gilpin, A., Henning, H., LeWinter, M., Collins, D., & Ross, J. (1985). Twelve-month prognosis following myocardial infarction: Classification trees, logistic regression, and stepwise linear discrimination. Proceedings of the Berkeley conference in honor of Jerzy Neyman and Jack Kiefer, L… find
  13. Smith, J., Everhart, J., Dickson, W., Knowler, W., & Johannes, R. (1988). Using the ADAP learning algorithm to forecast the onset of diabetes mellitus. In Proceedings of the Symposium on Computer Applications and Medical Care 261-265. IEEE Computer Society Press. find
  14. Sigillito, V. G., Wing, S. P., Hutton, L. V., & Baker, K. B. (1989). Classification of radar returns from the ionosphere using neural networks. Johns Hopkins APL Technical Digest, 10, 262-266. find
  15. Wolberg, W. & Mangasarian, O (1990). Multisurface method of pattern separation for medical diagnosis applied to breast cytology, Proceedings of the National Academy of Sciences, U.S.A., Volume 87, December 1990, pp 9193-9196. find
  16. Received September 19, 1994 Accepted January 2, 1995 Final Manuscript November 21, 1995 find