An Ensemble Technique for Stable Learners with Performance Bounds

Ian DavidsonAAAI 2004

Introduction

Ensemble methods like bagging and boosting are standard tools for improving "unstable" models such as decision trees. However, for "stable" learners like Naïve Bayes—where small changes in training data do not significantly alter the resulting model—these traditional techniques often fail to provide gains. This paper introduces Bootstrap Model Averaging (BMA), a strategy designed to boost stable learners by approximating the Optimal Bayes Classifier (OBC) with rigorous theoretical performance bounds.

The Challenge of Stable Learners

In machine learning, instability is often a virtue for ensembles. Bagging works because small data perturbations lead to diverse models; averaging these reduces variance. Stable learners, conversely, are relatively insensitive to such changes. Bagging them often results in nearly identical models, yielding zero improvement. Furthermore, determining the optimal number of models usually relies on heuristics rather than theory. This paper seeks to turn stability into a mathematical advantage.

Methodology: Bootstrap Model Averaging (BMA)

BMA leverages the stability of these learners to provide a predictable framework for ensemble performance. The process involves:

  1. Bootstrap Sampling: Generating $T$ samples with replacement from the original data.
  2. Model Training: Training a stable learner on each sample.
  3. Joint Probability Summation: Instead of simple voting, BMA sums the joint probabilities of instances and classes across all models.
  4. Decision Rule: Selecting the class with the highest aggregate sum.

By applying the Bayesian Central Limit Theorem, the paper proves that the posterior distribution of these models is approximately Gaussian. This allows for Monte Carlo integration to approximate the OBC. Using Chebychev bounds, researchers can quantify the proximity of the ensemble's error to the optimal error based on the number of models $T$, turning model training into a resource management problem.

Experimental Setup

The technique was evaluated using two distinct approaches:

  • UCI Benchmarks: Five standard datasets including Iris, Breast Cancer, Soybean, Crx, and Adult.
  • Artificial Data: A Cancer Belief Network (Figure 1) was used to compare BMA against true underlying probabilities, a ground truth unavailable in real-world data.
Figure 1: The Cancer Belief Network structure used for artificial data experiments to validate BMA against ground truth probabilities.

Key Results

Empirical tests confirmed that while standard bagging provides negligible improvement for Naïve Bayes, BMA consistently delivers statistically significant error reductions.

Figure 3: Performance of Bootstrap Model Averaging across various datasets, demonstrating statistically significant error reduction compared to baseline training data.
  • Performance Gains: While bagging often showed 0% improvement, BMA showed significant gains across all tested datasets. For instance, on the Soybean dataset, BMA achieved a notable reduction in error where traditional methods failed.
  • OBC Approximation: In artificial network tests, the BMA approach matched the Optimal Bayes Classifier's predictions 98% of the time with 500 models.
  • Bound Validity: Theoretical Chebychev bounds held in practice; actual errors exceeded predicted bounds only 3-4% of the time, consistent with the 95% confidence level used in the study.

Conclusion and Future Work

BMA turns learner stability into a feature, providing a predictable framework for ensemble performance. While highly effective for stable learners, it is not intended for unstable models like decision trees where Gaussian assumptions fail. Future research will explore extending these bounds to scenarios involving latent variables and non-deterministic learning environments.

Summary updated

BibTeX
@inproceedings{davidson2004ensemble,
  author = {Ian Davidson},
  title = {{An Ensemble Technique for Stable Learners with Performance Bounds}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2004},
}
Figure