Multicategory Classification Via Forward–Backward Support Vector Machine

Abstract

In this paper, we propose a new algorithm to extend support vector machine (SVM) for binary classification to multicategory classification. The proposed method is based on a sequential binary classification algorithm. We first classify a target class by excluding the possibility of labeling as any other classes using a forward step of sequential SVM; we then exclude the already classified classes and repeat the same procedure for the remaining classes in a backward step. The proposed algorithm relies on SVM for each binary classification and utilizes only feasible data in each step; therefore, the method guarantees convergence and entails light computational burden. We prove Fisher consistency of the proposed forward–backward SVM (FB-SVM) and obtain a stochastic bound for the predicted misclassification rate. We conduct extensive simulations and analyze real-world data to demonstrate the superior performance of FB-SVM, for example, FB-SVM achieves a classification accuracy much higher than the current standard for predicting conversion from mild cognitive impairment to Alzheimer’s disease.

Keywords

Multicategory classification / Fisher consistency / Classification rate / Risk bound / Alzheimer’s disease

References

[1] Allwein EL, Schapire RE, Singer Y. Reducing multiclass to binary: a unifying approach for margin classifiers. J. Mach. Learn. Res.. 2001, 1 113-141

[2] Bartlett PL, Jordan MI, McAuliffe JD. Convexity, classification, and risk bounds. J. Am. Stat. Assoc.. 2006, 101 473 138-156

[3] Bredensteiner, E.J., Bennett, K.P.: Multicategory classification by support vector machines. In: Computational Optimization. Springer, pp. 53–79 (1999)

[4] Chang CC, Lin CJ. Libsvm: a library for support vector machines. ACM Trans. Intell. Syst. Technol. (TIST). 2011, 2 3 27

[5] Crammer K, Singer Y. On the algorithmic implementation of multiclass kernel-based vector machines. J. Mach. Learn. Res.. 2002, 2 265-292

[6] Cui Y, Liu B, Luo S, Zhen X, Fan M, Liu T, Zhu W, Park M, Jiang T, Jin JS . Identification of conversion from mild cognitive impairment to Alzheimer’s disease using multivariate predictors. PLoS ONE. 2011, 6 7 e21896

[7] Dietterich TG, Bakiri G. Solving multiclass learning problems via error-correcting output codes. J. Artif. Intell. Res.. 1995, 2 263-286

[8] Dogan U, Glasmachers T, Igel C. A unified view on multi-class support vector classification. J. Mach. Learn. Res.. 2016, 17 1-32

[9] Hill SI, Doucet A. A framework for kernel-based multi-category classification. J. Artif. Intell. Res. (JAIR). 2007, 30 525-564

[10] Kreßel, U.H.G.: Pairwise classification and support vector machines. In: Advances in Kernel Methods. MIT Press, pp. 255–268 (1999)

[11] Lauer F, Guermeur Y. Msvmpack: a multi-class support vector machine package. J. Mach. Learn. Res.. 2011, 12 2293-2296

[12] Lee Y, Lin Y, Wahba G. Multicategory support vector machines: theory and application to the classification of microarray data and satellite radiance data. J. Am. Stat. Assoc.. 2004, 99 465 67-81

[13] Liu, Y.: Fisher consistency of multicategory support vector machines. In: International Conference on Artificial Intelligence and Statistics, pp. 291–298 (2007)

[14] Liu Y, Shen X. Multicategory $\psi $-learning. J. Am. Stat. Assoc.. 2006, 101 474 500-509

[15] Liu Y, Yuan M. Reinforced multicategory support vector machines. J. Comput. Graph. Stat.. 2011, 20 4 901-919

[16] Steinwart I, Christmann A. Support Vector Machines. 2008 New York: Springer

[17] Tewari A, Bartlett PL. On the consistency of multiclass classification methods. J. Mach. Learn. Res.. 2007, 8 1007-1025

[18] Vapnik VN, Vapnik V. Statistical Learning Theory. 1998 New York: Wiley

[19] Weiner MW, Aisen PS, Jack CR, Jagust WJ, Trojanowski JQ, Shaw L, Saykin AJ, Morris JC, Cairns N, Beckett LA . The Alzheimer’s disease neuroimaging initiative: progress report and future plans. Alzheimer’s Dementia. 2010, 6 3 202-211

[20] Weston J, Watkins C . Support vector machines for multi-class pattern recognition. ESANN. 1999, 99 219-224

[21] Zhang T. Statistical analysis of some multi-category large margin classification methods. J. Mach. Learn. Res.. 2004, 5 1225-1251

Funding

National Institutes of Health(R01GM124104)

National Institutes of Health(NS082062)

Gillings Innovation Lab