No Access

Multi-class $ℓ_{2}$ -Boost with the scoring coding

College of Mechatronic Engineering and Automation, National University of Defense Technology, Changsha 410073, P. R. China

E-mail Address: yelei@nudt.edu.cn

Search for more papers by this author

Can Wang

College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, P. R. China

E-mail Address: aezero@zju.edu.cn

Search for more papers by this author

Xin Xu

College of Mechatronic Engineering and Automation, National University of Defense Technology, Changsha 410073, P. R. China

E-mail Address: xinxu@nudt.edu.cn

Search for more papers by this author

, and

Wei Chen

College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, P. R. China

E-mail Address: chwei@zju.edu.cn

Search for more papers by this author

https://doi.org/10.1142/S0219691316500491Cited by:0 (Source: Crossref)

Abstract

Boosting, one of the best off-the-shelf classification methods, has evoked widespread interest in machine learning and statistics. However, the original algorithm was developed for binary classification problems. In this paper, we study multi-class boosting algorithms under the $ℓ_{2}$ -loss framework, and devise two multi-class $ℓ_{2}$ -Boost algorithms. These are based on coordinate descent and gradient descent to minimize the multi-class $ℓ_{2}$ -loss function. We derive a scoring coding scheme using optimal scoring constraints to encode class labels and a simple decoder to recover the true class labels. Our boosting algorithms are easily implemented and their results converge to the global optimum. Experiments with synthetic and real-world datasets show that, compared with several state-of-art methods, our algorithms provide more accurate results.

Keywords:

AMSC: 22E46, 53C35, 57S20

References

1. E. L. Allwein et al., Reducing multiclass to binary: A unifying approach for margin classifier, J. Mach. Learn. Res. 1(29) (2001) 113–141. Google Scholar
2. K. Bache and M. Lichman, Uci machine learning repository, [http://archive.ics.uci.edu/ml], (Irvine, CA: University of California, School of Information and Computer Science) 901 (2013) 113–141. Google Scholar
3. P. Buhlmann and B. Yu, Boosting with the $l_{2}$ loss: Regression and classification, J. Amer. Statist. Assoc. 98(462) (2003) 324–339. Crossref, Web of Science, Google Scholar
4. L. M. de Campos, A scoring function for learning bayesian networks based on mutual information and conditional independence tests, J. Mach. Learn. Res. 7(39) (2006) 2149–2187. Google Scholar
5. Y. Freund and R. E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, in Proc. 2nd European Conf. on Computational Learning Theory, London, UK (1995), pp. 23–37. Google Scholar
6. J. H. Friedman, Greedy function approximation: A gradient boosting machine, Ann. Statist. 29 (2001) 1189–1232. Crossref, Web of Science, Google Scholar
7. J. H. Friedman et al., Additive logistic regression: A statistical view of boosting, Ann. Statist. 38(2) (2000) 337–407. Crossref, Web of Science, Google Scholar
8. T. Gao and D. Koller, Multiclass boosting with hinge loss based on output coding, in Proc. 28th Int. Conf. on Machine Learning (ICML-11), New York, USA (2011), pp. 569–576. Google Scholar
9. A. Grubb and J. A. Bagnell, Generalized boosting algorithms for convex optimization, in Proc. 28th Int. Conf. on Machine Learning (ICML-11), New York, USA (2011), pp. 1209–1216. Google Scholar
10. Y. Gu, D. Zydek and Z. Jin, Active Learning Based on Random Forest and Its Application to Terrain Classification (Springer International Publishing, 2015). Crossref, Google Scholar
11. T. Hastie et al., Flexible discriminant analysis by optimal scoring, J. Amer. Statist. Assoc. 89 (1994) 1255–1270. Crossref, Web of Science, Google Scholar
12. L. Mason, J. Baxter, P. Bartlett and M. Frean, Boosting algorithms as gradient descent, in Advances in Neural Information Processing Systems (NIPS 1999), Vol. 12 (MIT, USA, 1999), pp. 512–518. Google Scholar
13. D. Mease and A. Wyner, Evidence contrary to the statistical view of boosting, J. Mach. Learn. Res. 9(26) (2008) 131–156. Google Scholar
14. Y. Mroueh et al., Multiclass learning with simplex coding, Advances in Neural Information Processing Systems (NIPS 2012), Vol. 25 (MIT, Lake Tahoe, 2012), pp. 2789–2797. Google Scholar
15. I. Mukherjee and R. Schapire, A theory of multiclass boosting, J. Mach. Learn. Res. 14(1) (2013) 437–497. Google Scholar
16. M. J. Saberian and N. Vasconcelos, Multiclass boosting: Theory and algorithms, in Advances in Neural Information Processing Systems (NIPS) (Granada Congress and Exhibition Centre, Granada Spain, 2011), pp. 2124–2132. Google Scholar
17. R. E. Schapire and Y. Freund, Boosting: Foundations and Algorithms (The MIT Press, 2012). Crossref, Google Scholar
18. B. Taskar et al., Learning structured prediction models: A large margin approach, Proc. 22nd Int. Conf. on Machine Learning, New York, USA (2005), pp. 896–903. Google Scholar
19. Z. Zhang and G. Dai, Optimal scoring for unsupervised learning, Advances in Neural Information Processing Systems (NIPS 2009), Vol. 22 (MIT, Vancouver, B. C., Canada, 2009), pp. 2241–2249. Google Scholar
20. Z. Zhang et al., Regularized discriminant analysis, ridge regression and beyond, J. Mach. Learn. Res. 11 (2010) 2199–2228. Web of Science, Google Scholar
21. Z. Zhang and M. I. Jordan, Multiway spectral clustering: A margin-based perspective, Statist. Sci. 23(3) (2008) 383–403. Crossref, Web of Science, Google Scholar
22. J. Zhu et al., Multi-class adaboost, Statist. Interface 2 (2009) 349–360. Crossref, Web of Science, Google Scholar