How boosting the margin can also boost classifier complexity

ABSTRACT

Boosting methods are known not to usually overfit training data even as the size of the generated classifiers becomes large. Schapire et al. attempted to explain this phenomenon in terms of the margins the classifier achieves on training examples. Later, however, Breiman cast serious doubt on this explanation by introducing a boosting algorithm, arc-gv, that can generate a higher margins distribution than AdaBoost and yet performs worse. In this paper, we take a close look at Breiman's compelling but puzzling results. Although we can reproduce his main finding, we find that the poorer performance of arc-gv can be explained by the increased complexity of the base classifiers it uses, an explanation supported by our experiments and entirely consistent with the margins theory. Thus, we find maximizing the margins is desirable, but not necessarily at the expense of other factors, especially base-classifier complexity.

REFERENCES

• 1: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• 2: Breiman, L. (1998). Arcing classifiers. The Annals of Statistics, 26, 801--849.
• 3: Leo Breiman, Prediction games and arcing algorithms, Neural Computation, v.11 n.7, p.1493-1517, Oct. 1, 1999 [doi>10.1162/089976699300016106]
• 4: Drucker, H., & Cortes, C. (1996). Boosting decision trees. Advances in Neural Information Processing Systems 8 (pp. 479--485).
• 5: 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]
• 6: Adam J. Grove , Dale Schuurmans, Boosting in the limit: maximizing the margin of learned ensembles, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.692-699, July 1998, Madison, Wisconsin, United States
• 7: Koltchinskii, V., & Panchenko, D. (2002). Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30.
• 8: Mason, L., Bartlett, P. L., & Golea, M. (2002). Generalization error of combined classifiers. Journal of Computer and System Sciences, 65, 415--438.
• 9: Ron Meir , Gunnar Rätsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY, 2003
• 10: Quinlan, J. R. (1996). Bagging, boosting, and C4.5. Proceedings of the Thirteenth National Conference on Artificial Intelligence (pp. 725--730).
• 11: Gunnar Rätsch , Manfred K. Warmuth, Maximizing the Margin with Boosting, Proceedings of the 15th Annual Conference on Computational Learning Theory, p.334-350, July 08-10, 2002
• 12: Rudin, C., Schapire, R. E., & Daubechies, T. (2004). Boosting based on a smooth margin. 17th Annual Conference on Learning Theory (pp. 502--517).
• 13: Schapire, R. E. (2002). The boosting approach to machine learning: An overview. Nonlinear Estimation and Classification. Springer.
• 14: Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26, 1651--1686.
• 15: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms