×

Safe sample screening rules for multicategory angle-based support vector machines. (English) Zbl 07533784

Summary: Support vector machines are popular techniques for classification problems, where the optimal separating hyperplane only depends on a subset of training data. To reduce computational costs, safe sample screening rules are proposed in the literature, which enable us to remove redundant samples prior to the training phase. However, existing works on safe sample screening rules mainly focus on binary classification. The multicategory angle-based support vector machine (MASVM) is a computationally efficient method for multicategory classification problems, which constructs a decision function without the sum-to-zero constraint. To further reduce computational costs in linear MASVM, two safe sample screening methods are proposed: the gap safe rule (MAGSR) and the dual screening with variational inequalities (MADVI). A two-stage screening framework combining MAGSR and MADVI together is then developed. Extensive simulations and real applications show the great advantage of the proposed methods in computation, compared with existing approaches.

MSC:

62-XX Statistics

Software:

LIBSVM; LIBLINEAR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bonnefoy, A.; Emiya, V.; Ralaivola, L.; Gribonval, R., A dynamic screening principle for the Lasso, (22nd European Signal Processing Conference (2014)), 6-10
[2] Boser, B. E.; Guyon, I. M.; Vapnik, V. N., A training algorithm for optimal margin classifiers, (Proceedings of the Fifth Annual Workshop on Computational Learning Theory (1992)), 144-152
[3] Chang, C.-C.; Lin, C.-J., LIBSVM: a library for support vector machines, ACM Trans. Intell. Syst. Technol., 2, 3, 1-27 (2011)
[4] Cortes, C.; Vapnik, V., Support-vector networks, Mach. Learn., 20, 3, 273-297 (1995) · Zbl 0831.68098
[5] Crammer, K.; Singer, Y., On the algorithmic implementation of multiclass kernel-based vector machines, J. Mach. Learn. Res., 2, Dec, 265-292 (2001) · Zbl 1037.68110
[6] Fan, R.-E.; Chang, K.-W.; Hsieh, C.-J.; Wang, X.-R.; Lin, C.-J., LIBLINEAR: a library for large linear classification, J. Mach. Learn. Res., 9, 1871-1874 (2008) · Zbl 1225.68175
[7] Fan, Y.; Lu, X.; Liu, Y.; Zhao, J., Angle-based hierarchical classification using exact label embedding, J. Am. Stat. Assoc. (2020)
[8] Goudjil, M.; Koudil, M.; Bedda, M.; Ghoggali, N., A novel active learning method using SVM for text classification, Int. J. Autom. Comput., 15, 3, 290-298 (2018)
[9] Güler, O., Foundations of Optimization (2010), Springer Science & Business Media · Zbl 1220.90001
[10] Guyon, I.; Boser, B.; Vapnik, V., Automatic capacity tuning of very large VC-dimension classifiers, (Advances in Neural Information Processing Systems (1993)), 147-155
[11] Joachims, T., Text categorization with support vector machines: learning with many relevant features, (European Conference on Machine Learning (1998)), 137-142
[12] Lange, K.; Tong Wu, T., An MM algorithm for multicategory vertex discriminant analysis, J. Comput. Graph. Stat., 17, 3, 527-544 (2008)
[13] 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
[14] Lin, Y.; Lv, F.; Zhu, S.; Yang, M.; Cour, T.; Yu, K.; Cao, L.; Huang, T., Large-scale image classification: fast feature extraction and SVM training, (Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2011)), 1689-1696
[15] Liu, J.; Zhao, Z.; Wang, J.; Ye, J., Safe screening with variational inequalities and its application to lasso, (International Conference on Machine Learning (2014)), 289-297
[16] Liu, Y.; Wen, K.; Gao, Q.; Gao, X.; Nie, F., SVM based multi-label learning with missing labels for image annotation, Pattern Recognit., 78, 307-317 (2018)
[17] Liu, Y.; Yuan, M., Reinforced multicategory support vector machines, J. Comput. Graph. Stat., 20, 4, 901-919 (2011)
[18] Ndiaye, E.; Fercoq, O.; Gramfort, A.; Salmon, J., Gap safe screening rules for sparsity enforcing penalties, J. Mach. Learn. Res., 18, 1, 4671-4703 (2017) · Zbl 1442.62161
[19] Ogawa, K.; Suzuki, Y.; Takeuchi, I., Safe screening of non-support vectors in pathwise SVM computation, (International Conference on Machine Learning (2013)), 1382-1390
[20] Pan, X.; Xu, Y., A novel and safe two-stage screening method for support vector machine, IEEE Trans. Neural Netw. Learn. Syst., 30, 8, 2263-2274 (2018)
[21] Pan, X.; Yang, Z.; Xu, Y.; Wang, L., Safe screening rules for accelerating twin support vector machine classification, IEEE Trans. Neural Netw. Learn. Syst., 29, 5, 1876-1887 (2017)
[22] Peng, X.; Chen, D.; Kong, L., A clipping dual coordinate descent algorithm for solving support vector machines, Knowl.-Based Syst., 71, 266-278 (2014)
[23] Platt, J., Sequential minimal optimization: a fast algorithm for training support vector machines (1998), Technical Report MSR-TR-98-14
[24] Wang, J.; Wonka, P.; Ye, J., Scaling SVM and least absolute deviations via exact data reduction, (International Conference on Machine Learning (2014)), 523-531
[25] Wang, L.; Shen, X., On \(L_1\)-norm multiclass support vector machines: methodology and theory, J. Am. Stat. Assoc., 102, 478, 583-594 (2007) · Zbl 1172.62317
[26] Wang, Z.; Crammer, K.; Vucetic, S., Breaking the curse of kernelization: budgeted stochastic gradient descent for large-scale SVM training, J. Mach. Learn. Res., 13, 1, 3103-3131 (2012) · Zbl 1433.68383
[27] Wu, T. T.; Lange, K., Multicategory vertex discriminant analysis for high-dimensional data, Ann. Appl. Stat., 4, 4, 1698-1721 (2010) · Zbl 1220.62086
[28] Yang, Z.; Xu, Y., A safe sample screening rule for Laplacian twin parametric-margin support vector machine, Pattern Recognit., 84, 1-12 (2018)
[29] Yang, Z.; Xu, Y., A safe screening rule for Laplacian support vector machine, Eng. Appl. Artif. Intell., 67, 309-316 (2018)
[30] Zhang, C.; Liu, Y., Multicategory angle-based large-margin classification, Biometrika, 101, 3, 625-640 (2014) · Zbl 1335.62110
[31] Zhao, J.; Xu, Y., A safe sample screening rule for Universum support vector machines, Knowl.-Based Syst., 138, 46-57 (2017)
[32] Zhao, Y.; Zeng, D.; Rush, A. J.; Kosorok, M. R., Estimating individualized treatment rules using outcome weighted learning, J. Am. Stat. Assoc., 107, 499, 1106-1118 (2012) · Zbl 1443.62396
[33] Zheng, J.; Shen, F.; Fan, H.; Zhao, J., An online incremental learning support vector machine for large-scale data, Neural Comput. Appl., 22, 5, 1023-1035 (2013)
[34] Zhu, L.-P.; Li, L.; Li, R.; Zhu, L.-X., Model-free feature screening for ultrahigh-dimensional data, J. Am. Stat. Assoc., 106, 496, 1464-1475 (2011) · Zbl 1233.62195
[35] Zimmert, J.; de Witt, C. S.; Kerg, G.; Kloft, M., Safe screening for support vector machines, (NIPS 2015 Workshop on Optimization in Machine Learning (OPT) (2015))
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.