An Empirical Evaluation of Bagging and Boosting

AAAI 1997

TL;DR

This paper empirically evaluates Bagging and Boosting, two popular ensemble methods for machine learning, using both neural networks and decision trees. They find that while Bagging consistently improves performance over single classifiers and is robust to overfitting, it doesn't significantly outperform a simple ensemble of randomly initialized networks. Boosting, however, shows more varied results, sometimes achieving substantial gains but also proving susceptible to noise and overfitting.

What Problem Does This Paper Address?

The core problem this paper addresses is understanding the effectiveness and trade-offs of two prominent ensemble learning techniques: Bagging and Boosting. Ensembles combine multiple individual models to achieve better predictive performance than any single model. While previous work has shown their efficacy, particularly for decision trees, there was a need for a comprehensive empirical evaluation using neural networks, especially for the newer Boosting algorithms. The authors aim to clarify how these methods perform across different classifier types and data characteristics, and to identify potential pitfalls like overfitting.

Methods

The paper compares several ensemble methods:

  • Single Classifier: A baseline using just one neural network or decision tree.
  • Simple Ensemble (Neural Networks): An ensemble where each neural network is trained on the same original training data but differs only in its randomly initialized weights. This serves as a baseline for comparison against more sophisticated ensemble techniques.
  • Bagging (Bootstrap Aggregating): This method creates an ensemble by training each classifier on a randomly resampled version of the original training set (sampling with replacement). This ensures each classifier sees a slightly different view of the data.
  • Boosting (Arcing and Ada-Boosting): These methods create a sequence of classifiers. Crucially, the training data for subsequent classifiers is weighted based on the performance of previous classifiers. Examples that were misclassified by earlier models are given higher probability of being selected for training later models, aiming to correct past errors. The paper specifically examines two variants: Arcing (using a power-based weighting scheme) and Ada-Boosting (using exponential weighting).

The evaluation uses both neural networks and decision trees (specifically C4.5) as the base classifiers.

Datasets

The authors evaluated their methods on 23 diverse datasets drawn from the UCI Machine Learning Repository. These datasets vary in:

  • Feature types: Continuous, discrete, or a mix.
  • Number of output classes: Ranging from binary to multi-class problems.
  • Number of examples: From a few hundred to tens of thousands.

The paper includes a table summarizing these characteristics, along with the neural network architectures (input, output, hidden units) and training parameters (epochs) used for each dataset. No new benchmarks were introduced; the focus was on evaluating existing methods on established datasets.

Key Insights and Ideas

  • Bagging's Robustness vs. Simple Ensembles: Bagging consistently improves performance over single classifiers and is remarkably resistant to overfitting. However, for neural networks, its performance is surprisingly similar to a simple ensemble where networks only differ by random weight initialization. This suggests that for neural networks, simply varying initial conditions can achieve much of the benefit of more complex resampling.
  • Boosting's Double-Edged Sword: Boosting (both Arcing and Ada-Boosting) can achieve significantly better results than Bagging and single classifiers, especially on multi-class problems. However, its performance is highly variable.
  • Boosting's Sensitivity to Noise: The paper provides strong evidence that Boosting methods, particularly Ada-Boosting, are susceptible to noise in the training data. As noise levels increase, Boosting's performance can degrade or even become worse than a single classifier, suggesting overfitting. This is attributed to the weighted sampling and weighted voting mechanisms.
  • Classifier Independence: The performance of Bagging and Boosting on neural networks generally correlates with their performance on decision trees. This implies that the advantages and disadvantages of these ensemble methods are largely independent of the base classifier and more dependent on the characteristics of the data domain.

Key Results

  • Bagging: Almost always produced better classifiers than any individual component classifier and was relatively impervious to overfitting. However, for neural networks, it did not generalize any better than a baseline neural-network ensemble method (simple random initialization).
  • Boosting (Arcing & Ada-Boosting): Showed more varied results. Sometimes it offered little gain over individual classifiers, while other times it provided significant gains, even over Bagging. For instance, on datasets like kr-vs-kp, letter, segmentation, and vehicle, Boosting significantly outperformed Bagging. Ada-Boosting, in particular, showed extreme results, sometimes yielding significant gains but also producing worse results than single classifiers on other datasets.
  • Noise Impact: In experiments with introduced noise, the efficacy of Simple and Bagging ensembles generally increased, while Arcing and Ada-Boosting ensembles showed smaller gains or even decreases in performance as noise levels rose. This effect was more pronounced for Ada-Boosting.

Limitations and Future Work

  • Limitations: The authors acknowledge that Boosting's poor performance on certain datasets might be explained by overfitting noise. They also note that the comparison between neural networks and decision trees was "nearly equivocal," with neither consistently outperforming the other across all datasets.
  • Future Work: The authors plan to conduct further experiments to pinpoint whether Boosting's overfitting is due to over-emphasizing noisy examples or weighted voting, or a combination. They also aim to investigate novel approaches to Boosting that retain its benefits while preventing overfitting on noisy data. Additionally, they plan to compare Bagging and Boosting with more recent methods like Stacking and ensemble approaches that use genetic search.

Summary updated

BibTeX
@inproceedings{1997empirical,
  title = {{An Empirical Evaluation of Bagging and Boosting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1997},
}
Figure