Robust Twin Parametric-Margin Support Vector Machine for Pattern Classification

doi:10.3778/j.issn.1002-8331.2104-0002

Abstract

Abstract: A robust twin parametric-margin support vector machine（R-TPMSVM） is proposed for the binary classification with uncertain domain. More specifically, considering the examples to be multivariate Gaussian distributions with known means and different covariance matrices, R-TPMSVM aims to find two nonparallel parametric-margin hyperplanes from a pair of smaller size convex optimization problems. These optimization problems are solved by stochastic gradient descent method. The formulation of R-TPMSVM approximates the TPMSVM formulation when the training example is an isotropic Gaussian with variance tends to zero. Experimental results show that the proposed approach has comparable generalization.

Key words: classification, uncertain data, twin support vector machine, parametric-margin, stochastic gradient descent

摘要： 针对不确定数据的二分类问题，提出了一种鲁棒双参数化间隔支持向量机。考虑样本是服从多元高斯分布，并给出了几种协方差矩阵的构造方式。提出的鲁棒双参数化间隔支持向量机通过处理一对较小规模的凸优化问题，寻找两个非平行的参数化间隔超平面，并针对优化问题设计了相应的随机梯度下降算法。当训练样本的方差趋近于零时，鲁棒双参数化间隔支持向量机可退化为传统的双参数化间隔支持向量机。数值实验结果表明，该方法具有较好的泛化性能。

关键词: 分类问题, 不确定数据集, 双支持向量机, 参数化间隔, 随机梯度下降

MA Tingting, YANG Zhixia, YE Junyou. Robust Twin Parametric-Margin Support Vector Machine for Pattern Classification[J]. Computer Engineering and Applications, 2022, 58(9): 74-82.

马婷婷, 杨志霞, 叶俊佑. 鲁棒双参数化间隔支持向量机[J]. 计算机工程与应用, 2022, 58(9): 74-82.

References

[1] BOSER B E，GUYON I M，VAPNIK V N.A training algorithm for optimal margin classifiers[C]//HAUSSLER D.Proceedings of the 5th Annual Workshop on Computational Learning Theory（COLT’92）.Pittsburgh，PA，USA：ACM Press，July 1992：144-152.
[2] BURGES C　J C.A tutorial on support vector machines for pattern recognition[J].Data Mining and Knowledge Discovery，1998，2：121-167.
[3] SHAWE-TAYLOR J，CHRISTIANINI　V.An introduction to support vector machines[M].Cambridge：Cambridge University Press，2002.
[4] VAPNIK V N.The nature of statistical learning theory[M].New York：Springer，1995.
[5] VAPNIK V N.Statistical learning theory[J].New York：Wiley，1998.
[6] JOACHIMS T.Text categorization with support vector machines：learning with many relevant features[C]//NéDELLEC C，ROUVEIROL C.European Conference on Machine Learning.Berlin，Heidelberg：Springer，1998：137-142.
[7] OSUNA E，FREUND R，GIROSIT F.Training support vector machines：an application to face detection[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition，1997：130-136.
[8] HUANG Z，CHEN H，HSU C J，et al.Credit rating analysis with support vector machines and neural networks：a market comparative study[J].Decision Support Systems，2004，37（4）：543-558.
[9] HUR A B，CHENG S，SONNENBURG S.Support vector machines and kernels for computational biology[J].PLoS Computational Biology，2008，4（10）：1000173.
[10] ZHANG J J，ZHONG P.Learning biased SVM with weighted within-class scatter for lmbalanced classification[J].Neural Processing Letters，2020，51（1）：797-817.
[11] NIU Y T，SHANG Y，TIAN Y J.Multi-view SVM classification with feature selection[J].Procedia Computer Science，2019，162：405-412.
[12] MANGASARIAN O L，WILD E W.Multisurface proximal support vector machine classification via generalized eigenvalues[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28（1）：69-74.
[13] KHEMCHANDANI J R，CHANDRA S.Twin support vector machines for pattern classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29：905-910.
[14] PENG X J.TPMSVM：a novel twin parametric-margin support vector machine for pattern recognition[J].Pattern Recognition，2011，44（10/11）：2678-2692.
[15] XU Y T，YANG Z J，PAN X L.A novel twin support-vector machine with pinball loss[J].IEEE Transactions on Neural Networks and Learning Systems，2017，28（2）：359-370.
[16] YAN H，YE Q L，YU D J.Efficient and robust TWSVM classification via a minimum [l1]-norm distance metric criterion[J].Machine Learning，2018：180（6）：993-1018.
[17] MA J，YANG L M，SUN Q.Adaptive robust learning framework for twin support vector machine classification[J].Knowledge-Based Systems，2020，211：106536.
[18] GOLDFARB D，IYENGAR G.Robust convex quadratically constrained programs[J].Mathematical Programming，2002，97：495-515.
[19] SHIVASWAMY P K，BHATTACHARYYA C，SMOLA A J.Second order cone programming approaches for handling missing and uncertain data[J].Journal of Machine Learning Research，2006，7：1283-1314.
[20] BHATTACHARYYA C，SHIVASWAMY P，SMOLA A.A second order cone programming formulation for classifying missing data[C]//Proceedings of the 17th International Conference on Neural Information Processing Systems，2004：153-160.
[21] ZHONG P，FUKUSHIMA M.Second order cone programming formulations for robust multi-class classification[J].Neural Computation，2007，19（1）：258-282.
[22] QI Z Q，TIAN Y J，SHI Y.Robust twin support vector machine for pattern classification[J].Pattern Recognition，2013，46（1）：305-316.
[23] XU H，CARAMANIS C，MANNOR S.Robustness and regularization of support vector machines[J].The Journal of Machine Learning Research，2009，10：1485-1510.
[24] XU H，MANNOR S.Robustness and generalization[J].Machine Learning，2012，86：391-423.
[25] BI J B，ZHANG T.Support vector classification with input data uncertainty[C]//International Conference on Neural Information Processing Systems，2004.
[26] TZELEPIS C，MEZARIS V，PATRAS I.Linear maximum margin classifier for learning from uncertain data[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2018，40（12）：2948-2962.
[27] COUELLAN N，JAN S.Feature uncertainty bounds for explicit feature maps and large robust nonlinear SVM classifiers[J].Annals of Mathematics and Artificial Intelligence，2019，88（1）：1-21.
[28] HAMIDZADEH J，MOSLEMNEJAD S.Identification of uncertainty and decision boundary for SVM classification training using belief function[J].Applied Intelligence，2019，49（6）：2030-2045.
[29] TZELEPIS C，MEZARIS V，PATRAS I.Video event detection using kernel support vector machine with isotropic Gaussian sample uncertainty（KSVM-iGSU）[C]//International Conference on Multimedia Modeling，2016：3-15.
[30] SHWARTZ S S，SINGER Y，SREBRO N，et al.Pegasos：primal estimated sub-gradient solver for SVM[J].Mathematical Programming，2011，127：3-30.
[31] LE T，NGUYEN T D，NGUYEN V，et al.Approximation vector machines for largescale online learning[J].Journal of Machine Learning Research，2016，18：1-55.
[32] DUA D，GRAFF C.UCI machine learning repository[D].CA：University of California，Irvine，Sciences，2017.
[33] BHATTACHARYYA C，GRATE L R，JORDAN M I，et al.Robust sparse hyperplane classifiers：application to uncertain molecular profiling data[J].Journal of Computational Biology，2004，11（6）：1073-1089.
[34] PASSALIS N，LAAKOM F，RAITOHARJU J.Graph embedding with data uncertainty[J].arXiv：2009.00505，2020.
[35] ZHANG W Y，YU S X，TENG S H.Power SVM：generalization with exemplar classification uncertainty[C]//Proceedings/CVPR，IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2012：2144-2151.