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.
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.
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_stopadjustment, 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