Experimental comparisons of online and batch versions of bagging and boosting

ABSTRACT

Bagging and boosting are well-known ensemble learning methods. They combine multiple learned base models with the aim of improving generalization performance. To date, they have been used primarily in batch mode, i.e., they require multiple passes through the training data. In previous work, we presented online bagging and boosting algorithms that only require one pass through the training data and presented experimental results on some relatively small datasets. Through additional experiments on a variety of larger synthetic and real datasets, this paper demonstrates that our online versions perform comparably to their batch counterparts in terms of classification accuracy. We also demonstrate the substantial reduction in running time we obtain with our online algorithms because they require fewer passes through the training data.

REFERENCES

• 1: S.D. Bay. The UCI KDD archive, 1999. (URL: http://kdd.ics.uci.edu).
• 2: C. Blake, E. Keogh, and C.J. Merz. UCI repository of machine learning databases, 1999. (URL: http: / /www.ics.uci.edu /~mlearn /MLRepository.htmI).
• 3: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 4: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 5: O. L. Mangasarian, R. Setiono, and W. H. Wolberg. Pattern recognition via linear programming: Theory and application to medical diagnosis. In Thomas F. Coleman and Yuying Li, editors, Large-Scale Numerical Optimization, pages 22-30. SIAM Publications, 1990.
• 6: Nikunj C. Oza and Stuart Russell. Experimental comparisons of online and batch versions of bagging and boosting. Technical report, Electrical Engineering and Computer Science Department, University of California, Berkeley, CA. In prepaxation.
• 7: Nikunj C. Oza and Stuart Russell. Online bagging and boosting. In Artificial Intelligence and Statistics 2001, pages 105-112. Morgan Kanfmann, 2001.
• 8: Paul E. Utgoff , Neil C. Berkman , Jeffery A. Clouse, Decision Tree Induction Based on Efficient Tree Restructuring, Machine Learning, v.29 n.1, p.5-44, Oct. 1997 [doi>10.1023/A:1007413323501]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms, Design, Performance