×

Multicategory classification via forward-backward support vector machine. (English) Zbl 1465.68231

Summary: 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.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
62H30 Classification and discrimination; cluster analysis (statistical aspects)
92C50 Medical applications (general)

Software:

LIBSVM; MSVMpack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allwein, EL; Schapire, RE; Singer, Y., Reducing multiclass to binary: a unifying approach for margin classifiers, J. Mach. Learn. Res., 1, 113-141 (2001) · Zbl 1013.68175
[2] Bartlett, PL; Jordan, MI; McAuliffe, JD, Convexity, classification, and risk bounds, J. Am. Stat. Assoc., 101, 473, 138-156 (2006) · Zbl 1118.62330 · doi:10.1198/016214505000000907
[3] Bredensteiner, E.J., Bennett, K.P.: Multicategory classification by support vector machines. In: Computational Optimization. Springer, pp. 53-79 (1999) · Zbl 1040.90574
[4] Chang, CC; Lin, CJ, Libsvm: a library for support vector machines, ACM Trans. Intell. Syst. Technol. (TIST), 2, 3, 27 (2011)
[5] Crammer, K.; Singer, Y., On the algorithmic implementation of multiclass kernel-based vector machines, J. Mach. Learn. Res., 2, 265-292 (2002) · Zbl 1037.68110
[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, 6, 7, e21896 (2011) · doi:10.1371/journal.pone.0021896
[7] Dietterich, TG; Bakiri, G., Solving multiclass learning problems via error-correcting output codes, J. Artif. Intell. Res., 2, 263-286 (1995) · Zbl 0900.68358 · doi:10.1613/jair.105
[8] Dogan, U.; Glasmachers, T.; Igel, C., A unified view on multi-class support vector classification, J. Mach. Learn. Res., 17, 1-32 (2016) · Zbl 1360.68669
[9] Hill, SI; Doucet, A., A framework for kernel-based multi-category classification, J. Artif. Intell. Res. (JAIR), 30, 525-564 (2007) · Zbl 1182.68197 · doi:10.1613/jair.2251
[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., 12, 2293-2296 (2011) · Zbl 1280.68175
[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., 99, 465, 67-81 (2004) · Zbl 1089.62511 · doi:10.1198/016214504000000098
[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., 101, 474, 500-509 (2006) · Zbl 1119.62341 · doi:10.1198/016214505000000781
[15] Liu, Y.; Yuan, M., Reinforced multicategory support vector machines, J. Comput. Graph. Stat., 20, 4, 901-919 (2011) · doi:10.1198/jcgs.2010.09206
[16] Steinwart, I.; Christmann, A., Support Vector Machines (2008), New York: Springer, New York · Zbl 1203.68171
[17] Tewari, A.; Bartlett, PL, On the consistency of multiclass classification methods, J. Mach. Learn. Res., 8, 1007-1025 (2007) · Zbl 1222.62079
[18] Vapnik, VN; Vapnik, V., Statistical Learning Theory (1998), New York: Wiley, New York · Zbl 0935.62007
[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, 6, 3, 202-211 (2010) · doi:10.1016/j.jalz.2010.03.007
[20] Weston, J.; Watkins, C., Support vector machines for multi-class pattern recognition, ESANN, 99, 219-224 (1999)
[21] Zhang, T., Statistical analysis of some multi-category large margin classification methods, J. Mach. Learn. Res., 5, 1225-1251 (2004) · Zbl 1222.68344
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.