鲁棒支持向量机及其稀疏算法

doi:10.19665/j.issn1001-2400.2019.01.011

摘要/Abstract

摘要：

基于非凸光滑损失的鲁棒支持向量机分类模型对异常点具有鲁棒性,但已有求解算法需迭代求解二次规划,计算量大且收敛速度慢,不适合训练大规模数据问题。为了克服这些缺点,首先给出收敛速度更快的方法求解鲁棒支持向量机模型;然后基于最小二乘的思想,提出了一种推广的指数鲁棒最小二乘支持向量机模型及其快速收敛的求解算法,并从理论上解释了模型的鲁棒性;最后利用核矩阵的低秩近似,提出了适于处理大规模训练问题的稀疏鲁棒支持向量机算法和稀疏指数鲁棒最小二乘支持向量机算法。实验结果表明,新算法在收敛速度、测试精度和训练时间等方面均优于相关算法。

关键词: 鲁棒支持向量机, 非凸光滑损失, 稀疏解, 低秩近似

Abstract:

Based on nonconvex and smooth loss, the robust support vector machine (RSVM) is insenstive to outliers for classification problems. However, the existing algorithms for RSVM are not suitable for dealing with large-scale problems, because they need to iteratively solve quadratic programmings, which leads to a large amount of calculation and slow convergence. To overcome this drawback, the method with a faster convergence rate is used to solve the RSVM. Then, by using the idea of least square, a generalized exponentially robust LSSVM (ER-LSSVM) model is proposed, which is solved by the algorithm with a faster convergence rate. Moreover, the robustness of the ER-LSSVM is interpreted theoretically. Finally, ultilizing low-rank approximation of the kernel matrix, the sparse RSVM algorithm (SR-SVM) and sparse ER-LSSVM algorithm (SER-LSSVM) are proposed for handing large-scale problems. Many experimental results illustrate that the proposed algorithm outperforms the related algorithms in terms of convergence speed, test accuracy and training time.

Key words: robust support vector machines, nonconvex and smooth loss, sparse solution, low-rank approximation

中图分类号:

TP391

安亚利,周水生,陈丽,王保军. 鲁棒支持向量机及其稀疏算法[J]. 西安电子科技大学学报, 2019, 46(1): 64-72.

AN Yali,ZHOU Shuisheng,CHEN Li,WANG Baojun. Robust support vector machines and their sparse algorithms[J]. Journal of Xidian University, 2019, 46(1): 64-72.

图/表 6

图1

图2

表1

表2

表3

图3

参考文献 20

[1]	VAPNIK V N . The Nature of Statistical Learning Theory[J]. Technometrics, 1996,38(4):400. doi: 10.1080/00401706.1996.10484552
[2]	孙颖, 宋春晓 . 相空间重构的情感语音特征提取及优化[J]. 西安电子科技大学学报, 2017,44(6):162-168. doi: 10.3969/j.issn.1001-2400.2017.06.028
	SUN Ying, SONG Chunxiao . Emotional Speech Feature Extraction and Optimization of Phase Space Reconstruction[J]. Journal of Xidian University, 2017,44(6):162-168. doi: 10.3969/j.issn.1001-2400.2017.06.028
[3]	韩冰, 贾中华, 高新波 . 改进的主成分分析网络极光图像分类方法[J]. 西安电子科技大学学报, 2017,44(1):83-88. doi: 10.3969/j.issn.1001-2400.2017.01.015
	HAN Bing, JIA Zhonghua, GAO Xinbo . Improved PCANet for Aurora Images Classification[J]. Journal of Xidian University, 2017,44(1):83-88. doi: 10.3969/j.issn.1001-2400.2017.01.015
[4]	李美玲, 胡耀垓, 周晨 , 等. 支持向量机用于电离层foF2的短期区域预报[J]. 西安电子科技大学学报, 2015,42(5):147-153. doi: 10.3969/j.issn.1001-2400.2015.05.025
	LI Meiling, HU Yaogai, ZHOU Chen , et al. On the Short-term Regional Prediction of foF2 Based on the Support Vector Machine[J]. Journal of Xidian University, 2015,42(5):147-153. doi: 10.3969/j.issn.1001-2400.2015.05.025
[5]	SUYKENS J A K, VANDEWALLE J . Least Squares Support Vector Machine Classifiers[J]. Neural Processing Letters, 1999,9(3):293-300. doi: 10.1023/A:1018628609742
[6]	GAO Y F, SHAN X, HU Z X , et al. Extended Compressed Tracking via Random Projection Based on MSERs and Online LS-SVM Learning[J]. Pattern Recognition, 2016,59:245-254. doi: 10.1016/j.patcog.2016.02.012
[7]	RIZVI S Z, VELNI J M, ABBASI F , et al. State-space LPV Model Identification Using Kernelized Machine Learning[J]. Automatica, 2018,88:38-47. doi: 10.1016/j.automatica.2017.11.004
[8]	SHEN X T, TSENG G C, ZHANG X G , et al. On ψ-Learning[J]. Journal of the American Statistical Association, 2003,98(463):724-734. doi: 10.1198/016214503000000639
[9]	WU Y C, LIU Y F . Robust Truncated Hinge Loss Support Vector Machines[J]. Journal of the American Statistical Association, 2007,102:974-983. doi: 10.1198/016214507000000617
[10]	WANG K N, ZHONG P . Robust Non-convex Least Squares Loss Function for Regression with Outliers[J]. Knowledge-Based Systems, 2014,71:290-302. doi: 10.1016/j.knosys.2014.08.003
[11]	CHEN L, ZHOU S S . Sparse Algorithm for Robust LSSVM in Primal Space[J]. Neurocomputing, 2018,275:2880-2891. doi: 10.1016/j.neucom.2017.10.011
[12]	FENG Y L, YANG Y, HUANG X L , et al. Robust Support Vector Machines for Classification with Nonconvex and Smooth Losses[J]. Neural Computation, 2016,28(6):1217-1247. doi: 10.1162/NECO_a_00837 pmid: 27137357
[13]	YUILLE A, RANGARAJAN A . The Concave-convex Procedure[J]. Neural Computation, 2003,15(4):915-936. doi: 10.1162/08997660360581958
[14]	ZHOU S S . Sparse LSSVM in Primal Using Cholesky Factorization for Large Scale Problems[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016,27(4):783-795. doi: 10.1109/TNNLS.2015.2424684
[15]	SCHÖLKOPF B, HERBRICH R, SMOLA A J. A Generalized Representer Theorem [C]// Lecture Notes in Computer Science: 2111. Heidelberg: Springer Verlag, 2001: 416-426.
[16]	LEE C P, LIN C J . A Study on L2-Loss (Squared Hinge-Loss) Multiclass SVM[J]. Neural Computation, 2013,25(5):1302-1323. doi: 10.1162/NECO_a_00434
[17]	PHAM DINH T, LE H M, LE THI H A , et al. A Difference of Convex Functions Algorithm for Switched Linear Regression[J]. IEEE Transactions on Automatic Control, 2014,59(8):2277-2282. doi: 10.1109/TAC.2014.2301575
[18]	HE B S, YUAN X M . On the O(1/n) Convergence Rate of the Douglas-rachford Alternating Direction Method[J]. SIAM Journal on Numerical Analysis, 2012,50(2):700-709. doi: 10.1137/110836936
[19]	SRIPERUMBUDUR B K, LANCKRIET G R G . A Proof of Convergence of the Concave-convex Procedure Using Zangwill’s Theory[J]. Neural Computation, 2012,24(6):1391-1407. doi: 10.1162/NECO_a_00283 pmid: 22364501
[20]	SRIPERUMBUDUR B K, LANCKRIET G R G . On the Convergence of the Concave-convex Procedure [C]//Advances in Neural Information Processing Systems 22. Red Hook: Curran Associates Inc, 2009: 1759-1767.

算法	参数(λ,σ,τ)	支持向量个数	训练时间/s	迭代次数
RSVM	(2⁵,10^-4,1.0)	199	0.4927	10
DC-RSVM	(2⁵,10^-4,1.2)	199	0.0797	6
SR-SVM	(2⁵,10^-4,1.2)	20	0.0006	6
SER-LSSVM	(2⁴,10^-4,1.2)	20	0.0005	4

算法	Haber (204/120/3)	Inonspher (234/117/34)	Breast (455/228/10)	German (667/333/24)	Svmguide1 (3089/4000/4)
参数取值(τ,λ,σ)
LSSVM	(2^-6,10^-6,/)	(2^-5,10^-5,/)	(2^-6,10^-4,/)	(2^-10,10^-5,/)	(2,10^-5,/)
SR-LSSVM	(2^-6,10^-5,1.2)	(2^-4,10^-4,1.0)	(2^-4,10^-8,0.8)	(2^-6,10^-4,0.8)	(2,10^-4,1.2)
RSVM	(2^-5,10^-5,0.6)	(2^-3,10^-4,0.6)	(2^-3,10^-3,0.8)	(2^-5,10^-5,1.4)	(22,10^-6,1.0)
SR-SVM	(2^-7,10^-7,0.6)	(2^-5,10^-8,0.6)	(2^-8,10^-8,0.8)	(2^-9,10^-5,1.2)	(22,10^-4,1.0)
SER-LSSVM	(2^-6,10⁷,1.0)	(2^-5,10^-5,0.6)	(2^-6,10^-8,1.0)	(2^-9,10^-5,1.2)	(2,10^-5,0.8)
测试精度/%
LSSVM	69.33(0.23)	91.89 (0.73)	96.20(0.62)	72.98(0.94)	80.19(1.01)
SR-LSSVM	74.82(0.87)	92.49(0.94)	96.89(1.01)	75.96(0.96)	88.24(0.66)
RSVM	70.59(0.97)	92.79(1.24)	95.52(0.79)	75.11(0.76)	89.57(0.45)
SR-SVM	76.17(0.75)	93.01(0.77)	97.07(0.46)	77.01(0.42)	90.99(0.30)
SER-LSSVM	76.53(0.65)	93.29(0.85)	97.37(0.39)	77.09(0.39)	90.87(0.25)
训练时间/s
LSSVM	0.040(0.014)	0.098(0.076)	0.294(0.244)	2.112(1.210)	2.001(0.110)
SR-LSSVM	0.002(0.001)	0.003(0.001)	0.022(0.007)	0.039(0.005)	0.078(0.008)
RSVM	0.843(0.210)	0.201(0.125)	1.294(0.457)	9.921(0.919)	37.24(1.406)
SR-SVM	0.002(0.000)	0.003(0.000)	0.021(0.003)	0.036(0.003)	0.067(0.014)
SER-LSSVM	0.001(0.000)	0.002(0.000)	0.022(0.008)	0.032(0.003)	0.064(0.020)

算法	Cod-RNA (59535/271617/8)	Ijcnn1 (49990/91701/22)	W8a (49749/14591/300)	Skin-nonskin (163371/81686/3)	Covtype (387341/193671/54)
参数取值(τ,λ,σ)
SR-LSSVM	(2^-1,10^-10,1.0)	(2^-8,10^-4,2.0)	(2^-7,10^-8,2.0)	(2^-2,10^-9,1.4)	(2^-5,10^-8,0.8)
SR-SVM	(2^-2,10^-7,0.8)	(2^-8,10^-8,1.2)	(2^-7,10^-9,1.8)	(2^-3,10^-7,1.0)	(2^-6,10^-5,1.2)
SER-LSSVM	(2^-2,10^-9,1.6)	(2^-8,10^-3,1.8)	(2^-8,10^-8,1.8)	(2^-1,10^-3,1.4)	(2^-6,10^-9,1.0)
测试精度/%
SR-LSSVM	96.03(0.01)	94.92(0.03)	98.05(0.00)	99.89(0.01)	87.92(0.04)
SR-SVM	96.59(0.02)	94.99(0.03)	98.14(0.01)	99.91(0.01)	87.67(0.48)
SER-LSSVM	97.06(0.01)	94.98(0.02)	98.19(0.01)	99.95(0.00)	87.96(0.01)
训练时间/s
SR-LSSVM	6.923(0.023)	2.174(0.241)	8.297(0.012)	22.246(1.020)	64.764(1.460)
SR-SVM	6.996(0.010)	2.095(0.117)	7.943(0.009)	23.497(0.198)	63.991(0.241)
SER-LSSVM	6.872(0.011)	1.985(0.131)	7.940(0.007)	22.599(0.092)	62.271(0.190)