Bagging Using Statistical Queries

Anneleen Van Assche, Hendrik Blockeel

Introduction

Bagging (Bootstrap Aggregating) is a cornerstone of ensemble learning, renowned for its ability to reduce variance and improve the stability of machine learning models. Traditionally, bagging relies on the availability of raw data to perform resampling with replacement. However, in many modern contexts—such as privacy-preserving data mining or large-scale databases utilizing optimized structures like AD-trees—direct access to individual records is often restricted. This paper introduces "Simulated Bagging" (SB), a novel approach that enables ensemble learning by operating directly on summary statistics rather than physical data points.

Problem Statement

The fundamental challenge addressed is performing bagging when raw data is inaccessible. In "learning from statistics" scenarios, an algorithm might only have access to an oracle that provides frequency counts or summary statistics. Because individual rows cannot be sampled, traditional bootstrap methods fail. The authors propose a method to bridge this gap by simulating the statistical effects of resampling.

Methodology: Simulated Bagging

The core innovation of this work is the shift from resampling data to resampling statistics. The authors model the counts of class/attribute combinations as a multinomial distribution. If one were to sample $n$ instances with replacement from a dataset, the resulting counts would follow this distribution, with parameters derived from the original summary statistics.

Extracted figure from page 5 of Bagging Using Statistical Queries

To implement this efficiently, the algorithm generates new frequency counts for each decision tree node using the BTPE algorithm (Binomial Threshold Processor Estimation). A significant technical hurdle is attribute correlation; a perfect simulation would require the full joint distribution of all attributes, which is computationally prohibitive. To maintain efficiency, the authors adopt an independence assumption, sampling the distribution for each attribute's heuristic (such as Information Gain) independently. This "Simulated Bagging" was integrated into the WEKA framework using the ID3 algorithm as the base learner.

Key Insights and Theoretical Approximations

A primary theoretical contribution is the conceptualization of heuristics like Information Gain (IG) as stochastic variables. By understanding the resampling process, the distribution of these heuristics becomes mathematically predictable.

Distribution of Information Gain for different tests, illustrating its stochastic nature.

While the independence assumption theoretically risks inaccuracy by ignoring attribute dependencies, experimental results suggest the approximation is remarkably robust. The "noise" introduced by independent sampling provides sufficient diversity to create an effective ensemble, mimicking the variance-reduction benefits of traditional bagging. Furthermore, the authors identified that SB initially produced larger trees because it lacked the natural data reduction of standard bagging (where a bootstrap contains only ~63% of unique instances). To correct this, they introduced SB_stop, a modified stopping criterion that simulates reduced data volume to maintain manageable tree sizes.

Experimental Results

The researchers evaluated SB on 12 UCI repository datasets with nominal attributes, ranging from small sets like breast-cancer to large ones like connect-4.

  • Accuracy: SB achieved predictive accuracy nearly identical to traditional bagging across all test cases, occasionally outperforming it in datasets like primary-tumor.
  • Efficiency: SB proved highly efficient. By avoiding multiple passes over raw data or expensive data movement, it often outperformed traditional resampling in runtime, particularly on larger datasets.
  • Tree Complexity: With the SB_stop adjustment, the complexity of the generated trees was comparable to those produced by standard bagging methods.

Conclusion and Future Work

Simulated Bagging demonstrates that ensemble diversity can be achieved through statistical simulation rather than physical resampling. This approach is not only effective for privacy-restricted environments but also offers computational advantages for large-scale data mining. Future research may extend this logic to numerical attributes and other resampling-based techniques, such as cross-validation or pruning, in environments where raw data remains hidden.

Summary updated

Abstract

Bagging is an ensemble method that relies on random resampling of a data set to construct models for the ensemble. When only statistics about the data are available, but no individual examples, the straightforward resampling procedure cannot be implemented. The question is then whether bagging can somehow be simulated. In this paper we propose a method that, instead of computing certain heuristics (such as information gain) from a resampled version of the data, estimates the probability distribution of these heuristics under random resampling, and then samples from this distribution. The resulting method is not entirely equivalent to bagging because it ignores certain dependencies among statistics. Nevertheless, experiments show that this “simulated bagging” yields similar accuracy as bagging, while being as efficient and more generally applicable.
BibTeX
@inproceedings{assche2006bagging,
  author = {Anneleen Van Assche and Hendrik Blockeel},
  title = {{Bagging Using Statistical Queries}},
  booktitle = {ECML},
  year = {2006},
  doi = {10.1007/11871842\_83},
}
Figure