Learning Ensembles from Bites: A Scalable and Accurate Approach

Nitesh V. Chawla, Lawrence O. Hall, Kevin W. Bowyer, W. Philip KegelmeyerJMLR 2004 · OpenReview

Abstract

This paper introduces DIvote and DRvote, distributed frameworks designed to scale ensemble learning to massive datasets. By training hundreds of classifiers on small "bites" of data across multiple processors without inter-processor communication, these methods achieve significant speedups and higher accuracy than single classifiers. The approach effectively bypasses the memory bottlenecks associated with traditional bagging and boosting, offering a robust solution for large-scale machine learning tasks.

Introduction

As datasets grew into the gigabyte and terabyte range, traditional machine learning algorithms hit a "memory wall." Standard ensemble methods like bagging (which requires multiple passes over the whole dataset) and boosting (which is inherently sequential) became computationally prohibitive.

The common workaround was data subsampling—simply throwing away data until it fit in memory. However, this often degrades accuracy and can cause the model to miss rare but important patterns. The authors sought a way to utilize all available data without needing to load it into a single machine's memory, while maintaining the high accuracy associated with ensemble methods.

Methods

The authors build upon Leo Breiman’s "pasting" technique, which involves building classifiers on small, random subsets of data (bites). They propose two distributed versions:

  1. DRvote (Distributed Rvote): The data is partitioned across $T$ processors. Each processor independently builds an ensemble by randomly sampling "bites" from its local partition.
  2. DIvote (Distributed Ivote): This more sophisticated variant uses importance sampling. Each processor evaluates its current local ensemble; if an instance is misclassified, it has a higher probability of being included in the next "bite." This forces the algorithm to focus on "hard" cases.

The key innovation: Unlike distributed boosting, which requires processors to communicate and synchronize weights after every iteration, DIvote and DRvote are "embarrassingly parallel." Processors work in total isolation until the very end, when their classifiers are combined via a simple majority vote.

Experimental Setup

The researchers evaluated their approach on a mix of classic benchmarks and two significant "massive" datasets. The scale and characteristics of these datasets are summarized in the table below:

Table 1: Summary of datasets used in the evaluation, including size, number of classes, and attributes.
  • UCI/Statlog Benchmarks: DNA, Satimage, LED, Pendigits, Letter, and Waveform.
  • Covtype: A dataset of forest cover types with over 581,000 instances.
  • Jones Dataset: A protein secondary structure prediction dataset (209,529 training elements). This is a particularly difficult, non-homogeneous task where traditional classifiers often overfit.

Key Insights and Results

Communication-Free Scaling

The most striking insight is that global coordination is not required to build a powerful ensemble. By letting each processor independently focus on its own slice of data using importance sampling, the aggregate ensemble becomes incredibly robust. Because each processor sees a disjoint partition and uses its own importance sampling path, the resulting classifiers are highly diverse—a critical factor in ensemble performance.

Performance and Speed

  • Accuracy Gains: DIvote consistently outperformed single classifiers. On the difficult Jones dataset, it provided an absolute accuracy improvement of 18% (a 34% relative improvement) over a single C4.5 decision tree.
  • Massive Speedups: DIvote was significantly faster than sequential Ivote. On the Jones dataset, DIvote was roughly 20 times faster while achieving better accuracy.
  • Overcoming Overfitting: On the Jones dataset, a single decision tree overfits massively (96.7% training vs. 52.2% test accuracy). The DIvote ensemble acts as a powerful regularizer, boosting test accuracy to nearly 70%.

Limitations

On the Covtype dataset, the authors initially found that DIvote performed worse than a single tree due to high class skew; very small bites did not contain enough representative samples of minority classes. Increasing the bite size resolved this, suggesting that the "bite" size must be tuned relative to the number of classes and their distribution.

Conclusion

DIvote and DRvote provide a scalable, communication-free alternative to traditional ensemble methods. By leveraging small data "bites" and importance sampling, these frameworks achieve high accuracy and significant speedups, effectively overcoming the memory limitations of traditional algorithms on massive datasets.

Summary updated

BibTeX
@article{chawla2004learning,
  author = {Nitesh V. Chawla and Lawrence O. Hall and Kevin W. Bowyer and W. Philip Kegelmeyer},
  title = {{Learning Ensembles from Bites: A Scalable and Accurate Approach}},
  journal = {J. Mach. Learn. Res.},
  year = {2004},
  url = {https://openreview.net/forum?id=nMShKasV9h0},
}
Figure