ABC-boost: adaptive base class boost for multi-class classification

ABSTRACT

We propose abc-boost (adaptive base class boost) for multi-class classification and present abc-mart, an implementation of abc-boost, based on the multinomial logit model. The key idea is that, at each boosting iteration, we adaptively and greedily choose a base class. Our experiments on public datasets demonstrate the improvement of abc-mart over the original mart algorithm.

REFERENCES

• 1: Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001 [doi>10.1162/15324430152733133]
• 2: Bartlett, P., Freund, Y., Lee, W. S., & Schapire, R. E. (1998). Boosting the margin: a new explanation for the effectiveness of voting methods. The Annals of Statistics, 26, 1651--1686.
• 3: Cossock, D., & Zhang, T. (2006). Subset ranking using regression. Conf. on Learning Theory, 605--619.
• 4: Yoav Freund, Boosting a weak learning algorithm by majority, Information and Computation, v.121 n.2, p.256-285, Sept. 1995 [doi>10.1006/inco.1995.1136]
• 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: Friedman, J. H. (2001). Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29, 1189--1232.
• 7: Friedman, J. H., Hastie, T. J., & Tibshirani, R. (2000). Additive logistic regression: a statistical view of boosting. The Annals of Statistics, 28, 337--407.
• 8: Lee, Y., Lin, Y., & Wahba, G. (2004). Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data. J. of Amer. Stat. Asso., 99, 67--81.
• 9: Li, P., Burges, C. J., & Wu, Q. (2008). Mcrank: Learning to rank using classification and gradient boosting. Neur. Inf. Proc. Sys. Conf. 897--904.
• 10: Mason, L., Baxter, J., Bartlett, P., & Frean, M. (2000). Boosting algorithms as gradient descent. Neur. Inf. Proc. Sys. Conf. 512--518.
• 11: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 12: 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]
• 13: Robert E. Schapire , Yoram Singer, BoosTexter: A Boosting-based Systemfor Text Categorization, Machine Learning, v.39 n.2-3, p.135-168, May-June 2000 [doi>10.1023/A:1007649029923]
• 14: Ambuj Tewari , Peter L. Bartlett, On the Consistency of Multiclass Classification Methods, The Journal of Machine Learning Research, 8, p.1007-1025, 12/1/2007
• 15: Tong Zhang, Statistical Analysis of Some Multi-Category Large Margin Classification Methods, The Journal of Machine Learning Research, 5, p.1225-1251, 12/1/2004
• 16: Zheng, Z., Zha, H., Zhang, T., Chapelle, O., Chen, K., Sun, G. (2008). A General Boosting Method and its Application to Learning Ranking Functions for Web Search Neur. Inf. Proc. Sys. Conf. 1697--1704.
• 17: Zou, H., Zhu, J., & Hastie, T. (2008). New multi-category boosting algorithms based on multicategory fisher-consistent losses. The Annals of Applied Statistics, 2, 1290--1306.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory