基于对偶随机投影的线性核支持向量机

席 茜，张凤琴，李小青，管 桦，陈桂茸，王梦非

(空军工程大学 信息与导航学院，西安710077)

基于对偶随机投影的线性核支持向量机

席 茜*，张凤琴，李小青，管 桦，陈桂茸，王梦非

(空军工程大学 信息与导航学院，西安710077)

(*通信作者电子邮箱245594320@qq.com)

针对大型支持向量机(SVM)经随机投影特征降维后分类精度下降的问题，结合对偶恢复理论，提出了面向大规模分类问题的基于对偶随机投影的线性核支持向量机(drp-LSVM)。首先，分析论证了drp-LSVM相关几何性质，证明了在保持与基于随机投影降维的支持向量机(rp-LSVM)相近几何优势的同时，其划分超平面更接近于用全部数据训练得到的原始分类器。然后，针对提出的drp-LSVM快速求解问题，改进了传统的序列最小优化(SMO)算法，设计了基于改进SMO算法的drp-LSVM分类器。最后实验结果表明，drp-LSVM在继承rp-LSVM优点的同时，减小了分类误差，提高了训练精度，并且各项性能评价更接近于用原始数据训练得到的分类器；设计的基于改进SMO算法的分类器不但可以减少内存消耗，同时可以拥有较高的训练精度。

机器学习；支持向量机；随机投影；序列最小优化算法；降维

0 引言

支持向量机(Support Vector Machine, SVM)在1995年由Cortes等[1]首次提出，由于其拥有擅长处理小样本、非线性数据、高维模式识别的特点，并在一定程度下避免了“维数灾难”，所以基于SVM的分类器在文本分类领域中有着广泛的应用，在处理高维数据分类问题时也独占优势。与此同时应用于大型SVM的特征降维方法也成为研究热点。近年来，随机近似算法在大规模机器学习中应用广泛，其中随机投影(Random Projections, RP)方法可以快速有效地解决高维数据的降维问题，用以减少相关优化问题的计算代价。随机投影是通过控制精度来减少维度的方法，保持两个样本之间成对的距离，因此属于基于距离的方法。由于SVM也是基于距离的学习方法，故可以运用随机投影进行特征降维。2007年到2009年期间,Kumar等[2]和Jethava等[3]证明了基于高斯随机投影的SVM可以得到与原问题相近的相关误差，训练时间与投影矩阵和输入矩阵相关。2014年Paul等[4]证明了运用随机投影后的数据经过SVM训练，可以在保持特征空间的几何性质的同时保持分类器的最大间隔和最小闭包球的几何性质，维持了原有的泛化性能，并实践论证，同时从理论上证明了基于随机投影的线性核SVM(Linear kernel SVM based on random projection, rp-LSVM)训练时间与输入的非零数据的数量线性相关。

但随机投影后得到的最优解与原始问题的最优解存在一定误差，2012年Zhang等[5]将凸优化中的Fenchel对偶理论与随机投影相结合，得到一种基于对偶解恢复的随机机器学习方法，能有效地恢复原始优化问题的最优解。大规模的SVM问题本质也是大规模的优化问题，随即投影的降维方法在提升分类器训练效率的同时，也在一定程度下降低了对精度的要求。本文首先将对偶恢复思想应用于rp-LSVM中，提出基于对偶随机投影的线性核SVM(Linear kernel SVM based on dual random projection, drp-LSVM)，在保持了rp-LSVM优点的同时，解决了其精度下降的问题。理论分析证明drp-LSVM在几何上比rp-LSVM更接近于所有数据训练得到的原始分类器，证明了drp-LSVM的最大间隔超平面与最小闭包球保持了与rp-LSVM近似的几何性质，同样确保了与原始空间相近的泛化能力。本文还针对提出的drp-LSVM快速求解问题，改进了序列最小优化(Sequential Minimal Optimization, SMO)算法，设计了基于改进SMO算法的drp-LSVM分类器。最后的实验证明了drp-LSVM在继承rp-LSVM优点的同时，减小了训练误差，提高了训练精度，训练结果的各项性能评价更接近于用原始数据训练得到的分类器。基于改进SMO算法的drp-LSVM分类器在减少内存消耗的同时有较高的训练精度。

1 相关概念

1.1 线性核支持向量机

设有训练集D={xi,yi}(i=1,2,…,n)，xi∈Rd，类标签yi∈{-1,+1}。对于线性可分的数据，SVM学习问题最基本的思想是基于训练集D在样本空间中找到一个拥有最大间隔的划分超平面[6]，转化为凸二次规划问题形式为：

(1)

s.t.yi〈w,xi〉≥1,∀i∈{1,2,…,n}

(2)

这是SVM的基本形，其中w为划分超平面的法向量。当加入软间隔与正则化思想并且核函数为线性核时，相应的拉格朗日对偶问题为：

(3)

(4)

其中αi为拉格朗日算子，C≥αi≥0,i=1,2,…,n，C为常数。

设样本数据集在半径为R的球内，支持向量到超平面的距离和(即SVM的间隔)为γ，则该假设集的VC维(Vapnik-Chervonenkis Dimension)是O(R2/γ2)，如此可以估计出泛化误差界。

1.2 随机投影

引理1 对任意的ε∈(0,1)及正整数n，m为正整数且满足:m≥4(ε2/2-ε3/3)-1ln(n)

定义P为上述RP，对任意的含n个点的集合X，对于所有的u,v∈X，有不等式成立：

(1-ε)‖u-v‖2≤‖P(u)-P(v)‖2≤ (1+ε)‖u-v‖2

(5)

定理1 令α∈Rd是x∈Rn经过标准高斯矩阵随机投影得到的，则有如下概率成立：

(6)

引理2[5]令0<ε≤1/2，δ∈(0,1)，V∈Rm×n是任意的正定矩阵，高斯随机矩阵A∈Rm×r，其中r=O(nε-2lg(n/δ))，则至少以1-σ的概率有如下不等式成立：‖VTV-VTAATV‖≤ε。

1.3SMO算法

SMO[10]是目前最快的求解二次规划问题的算法，特别针对LSVM和数据稀疏时性能更优。SVM训练中最核心的问题是求解二次规划问题，传统的方法利用Hessian矩阵求解最优值需要很大的计算和存储代价。SMO算法将大规模的优化问题转化为一系列包含两个变量的子问题，从而避免了复杂的数值解法，有效地节省了时间成本并降低了内存要求。SMO算法类似于坐标上升，每次启发式选择两个参数变量进行优化，不断循环，直到达到函数最优解。

SMO算法的关键步骤可以大概总结为：首先启发式选择两个参数，固定其余参数，整体视为一个二元函数，由约束条件将一个参数用另一个参数表示，视为一个一元函数，并对一元函数求极值点，最后根据上下界和约束条件，对原始解进行修剪，更新参数并取临界特殊情况，进行分析。

2 基于对偶随机投影的线性核支持向量机

2.1 随机投影的对偶恢复

设有如下目标优化问题：

(7)

则根据Fenchel对偶定理得到原优化问题的对偶问题：

(8)

代入原问题有：

用梯度求解法可求得：

(9)

(10)

(11)

(12)

易知新解与原优化问题最优解存在较大误差，即：

(13)

故将低维空间Fenchel对偶得到的最优解代入到原优化问题中，得到恢复后的最优解。

根据上述推导，得到基于对偶解的随机投影(drp)算法如下。

算法1 drp算法。

输入 训练集D={xi,yi}，样本维度m。

2)计算低维子空间下的最优解z*。

3)计算对偶解qi=▽L(yiz*Tαi) 。

2.2drp-LSVM

由于支持向量机问题可以转化为凸二次规划问题，使用拉格朗日乘子法可得到其对偶问题，类比Zhang等[5]提出的对偶随机投影算法中将低维优化问题的共轭对偶变量代入到原问题中恢复最优解的方法，将低维空间中解出的拉格朗日乘子代入到原始超平面的计算中去，得到恢复的最优超平面。

(14)

(15)

2.3drp-LSVM的性质分析

(16)

证明 令E=VTV-VTAATV

将上述式(14)、(15)问题经过奇异值分解(Singular Value Decomposition, SVD)分解得到：

(17)

(18)

由式(17)、(18)有如下不等式成立：

(19)

又由拉格朗日对偶函数的凹性可知：

(20)

由式(19)、(20)两个不等式得到：

(21)

即：

(22)

结合引理2可得：

(23)

将低位空间的最优解转换高维空间后有关系：

(24)

则易求得：

(25)

由式(23)、(25)可以看出，drp-LSVM求得的最优解比直接经过随机投影降维的LSVM的最优解更接近原始最优解，即从几何上更接近于原始分类器。

下面论证drp-LSVM最大间隔超平面的几何性质。

利用SVD有:

(26)

即有不等式(27)如下：

(27)

易得不等式(28)如下：

(28)

将(28)代入(27)则有：

(29)

(30)

由不等式(28)可知：

(31)

结合式(25)、(31)得到：

(32)

即：

由引理2可得：

(33)

同样可以利用SVD和引理2证明最小闭包球(Minimum Enclosing Ball, MEB)的性质如下。

由于LSVM的MEB的拉格朗日对偶问题为：

max{αT(diag(XXT))-αTXXTα}

(34)

s.t.αT1=1,α≥0

设闭包球半径为R，球心向量为xc，则：

R2=αT(diag(XXT))-αTXXTα

(35)

(36)

经随机投影后：

(37)

对偶恢复后：

结合引理2易推得：

(38)

由上述理论分析可以得到，drp-LSVM的间隔和最小闭包球半径与rp-LSVM相近，同样保持了与原始空间的ε相关误差，维持了与原空间相似的泛化性能。

3 基于改进SMO算法的drp-LSVM分类器

虽然LSVM的训练和测试速度相对较快，但与KSVM相同，LSVM中最核心的问题还是求解二次规划问题，本文为求解基于对偶随机投影的LSVM设计了基于对偶随机投影的SMO算法，主要思想如下：

第一步 计算上下界H和L：

(39)

第二步 计算Ws的二阶导η，并更新Ws：

η=x1TAATx1+x2TAATx2-2x1TAATx2

(40)

(41)

ei=g(xi)-yi

(42)

(43)

(44)

第四步 在原空间下更新：

(45)

收敛条件为在界内的样例都能够满足卡罗需-库恩-塔克(Karush-Kuhn-Tucker, KTT)条件，且其对应的αi只在极小范围内变动，设计流程如图1所示。

图1 分类器设计流程

4 实验验证与分析

实验环境为2.6GHzIntelCorei5处理器，8GB内存，操作系统为Linux，开发工具为Python、Java。实验数据来自lib-SVMData[11]，实验一基于Liblinear库[12]进行drp-SVM相关性能测试，参数设置为默认参数。实验二测试基于改进SMO算法的drp-SVM性能。数据集D1、D2分别为gisette_scale[13]、rcv1.binary[14]。D1含训练样本6 000，测试样本1 000，样本维数为5 000，满足中等规模数据量及维数的特征；D2含训练样本202 421，测试样本677 399，维数为47 236，满足大规模高维度数据特征。为保证实验的准确度和可信度，相关实验重复5次，最终实验数据取平均值。

4.1 实验一

针对中等规模数据集D1，为检验分类器效果，考虑到数据集维数为5 000，则取四种不同投影维数512、1 024、2 048、4 096，在各种目标维数下分别计算drp-SVM，rp-SVM和原分

类器(即用全部数据训练出来的支持向量机，图中用full表示)的相关评估参数。图2分别为三种分类器在不同维度下精度(Accuracy,ACC)、均方误差(MeanSquareError,MSE)及平方相关系数(SquaredCorrelationCoefficient,SCC)的关系。

由图2可看出，相比于rp-SVM，drp-SVM的各项训练指标都更接近于所有训练数据得到的原始分类器。

针对较大规模数据集D2，结合数据集维数47 236，取四种不同投影维数1 024、2 048、4 096、8 192，在各种目标维数下分别计算drp-SVM、rp-SVM和原分类器(即用全部数据训练出来的支持向量机，图中用full表示)的相关评估参数。图3分别为三种分类器在不同维度下精度(ACC)、均方误差(MSE)及平方相关系数(SCC)的关系。

由图3可看出，在大规模更高维度的数据集环境下，drp-SVM的各项训练指标更优于rp-SVM，同时更加接近原始分类器。

图2 D1数据集下不同维数各分类器的性能指标

图3 D2数据集下不同维数各分类器的性能指标

表1～2分别为针对数据集D1和D2训练不同分类器在最优投影维数下训练时间(用time表示，单位为s)、最大间隔(γ)、5次交叉检验(5-fold)后的精度以及分类错误率(errorRate)的统计。

从表1～2可以看出，相比于rp-SVM，drp-SVM保留了其训练时间减少和保持最大间隔的优点，并在此基础上提高了训练精度，减小了误差。

4.2 实验二

用数据集D1来测试基于改进SMO算法的drp-SVM性能，为方便对比，将三种算法的训练时间(用time表示，单位为h)、训练中消耗内存比(用memory表示)及分类错误率(用errorRate表示)在一张图中展现，如图4所示。

表1 D1训练的三种分类器的各项参数

表2 D2训练的三种分类器的各项参数

图4 基于SMO算法的三种分类器性能比较

由图4可以看出，运用改进的算法(drp-SMO)的分类器比运用所有数据训练的基于SMO算法的分类器(full-SMO)的分类器更高效、更节省内存，且相比直接经过随机投影的SMO分类器(rp-SMO)准确度更接近原始分类器。

5 结语

本文针对特征降维后的支持向量机精度下降等问题，设计了基于对偶随机投影的线性核支持向量机(drp-LSVM)相关算法，并从理论分析的角度证明了求解drp-LSVM问题得到的最优解比rp-LSVM的最优解更接近于原始分类器得到的最优解，保证了在特征降维后，训练得到的分类器能够保持与原分类器相似的几何性质。文中还证明了drp-LSVM的最大间隔超平面与最小闭包球保持了与rp-LSVM近似的ε相关误差，同样确保了与原始空间相近的泛化能力。文中提出针对drp-LSVM的改进SMO算法，设计了基于改进SMO算法的分类器。大规模高维的数据集的实验证明了drp-LSVM在降维特征提高训练速度的同时，训练效果及性能评价更接近于原始分类器，改进SMO算法在保持了算法稳定性的同时拥有较高的训练速度和精度。本文仅围绕特殊的线性核支持向量机以及高斯投影进行了针对性研究，并没有考虑非线性核及其他种类的随机投影特征降维情况。大规模机器学习仍是目前主流的挑战，有关随机机器学习的技术方法有待进一步深入研究。

)

[1]CORTESC,VAPNIKV.Support-vectornetworks[J].MachineLearning, 1995, 20(3): 273-297.

[2]KUMARK,BHATTACHARYYAC,HARIHARANR.Arandomizedalgorithmforlargescalesupportvectorlearning[EB/OL]. [2016- 10- 09].http://hariharan-ramesh.com/papers/krichiram_nips_07.pdf.

[3]JETHAVAV,SURESHK,BHATTACHARYYAC,etal.RandomizedalgorithmsforlargescaleSVMs[EB/OL]. [2016- 10- 09].https://www.researchgate.net/publication/45873558_Randomized_Algorithms_for_Large_scale_SVMs.

[4]PAULS,BOUTSIDISC,MAGDON-ISMAILM,etal.Randomprojectionsforlinearsupportvectormachines[J].ACMTransactionsonKnowledgeDiscoveryfromData, 2014, 8(4):ArticleNo. 22.

[5]ZHANGLJ,MAHDAVIM,JINR,etal.Recoveringtheoptimalsolutionbydualrandomprojection[J].JournalofMachineLearningResearch, 2012, 30: 135-157.

[6] 周志华.机器学习[M].北京:清华大学出版社,2016:121-145.(ZHOUZH.MachineLearning[M].Beijing:TsinghuaUniversityPress, 2016: 121-145.)

[7] 刘红,刘蓉,李书玲.基于随机投影的加速度手势识别[J].计算机应用,2015,35(1):189-193.(LIUH,LIUR,LISL.Accelerationgesturerecognitionbasedonrandomprojection[J].JournalofComputerApplications, 2015, 35(1): 189-193.)

[8] 王萍,蔡思佳,刘宇.基于随机投影技术的矩阵填充算法的改进[J].计算机应用,2014,34(6):1587-1590.(WANGP,CAISJ,LIUY.Improvementofmatrixcompletionalgorithmbasedonrandomprojection[J].JournalofComputerApplications, 2014, 34(6): 1587-1590.)

[9]PLATTJC.Fasttrainingofsupportvectormachinesusingsequentialminimaloptimization[M].Cambridge,MA:MITPress, 1999: 185-208.

[10]CHANGCC,LINCJ.LIBSVM:alibraryforsupportvectormachines[J].ACMTransactionsonIntelligentSystems&Technology, 2011, 2(3):ArticleNo. 27.

[11]FANRE,CHANGKW,HSIEHCJ,etal.LIBLINEAR:alibraryforlargelinearclassification[J].JournalofMachineLearningResearch, 2008, 9: 1871-1874.

[12]GOLUBTR,SLONIMDK,TAMAYOP,etal.Molecularclassificationofcancer:classdiscoveryandclasspredictionbygeneexpressionmonitoring[J].Science, 1999, 286(5439): 531-537.

[13]LEWISDD,YANGY,ROSETG,etal.RCV1:anewbenchmarkcollectionfortextcategorizationresearch[J].JournalofMachineLearningResearch, 2004, 5: 361-397.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(71503260),theNaturalScienceFoundationofShaanxiProvince(2014JM8345).

XI Xi, born in 1993, M. S. candidate. Her research interests include data mining, machine learning.

ZHANG Fengqin, born in 1964, M. S., associate professor. Her research interests include data mining, complex network, distributed database.

LI Xiaoqing, born in 1982, Ph. D., lecturer. Her research interests include intelligent data processing.

GUAN Hua, born in 1963, M. S., professor. His research interests include command automation.

CHEN Guirong, born in 1970, M. S., lecturer. Her research interests include complex network.

WANG Mengfei, born in 1992, M. S. candidate. His research interests include complex network, machine learning.

Linear kernel support vector machine based on dual random projection

XI Xi*, ZHANG Fengqin, LI Xiaoqing, GUAN Hua, CHEN Guirong, WANG Mengfei

(InformationandNavigationCollege,AirForceEngineeringUniversity,Xi’anShaanxi710077,China)

Aiming at the low classification accuracy problem of large-scale Support Vector Machine (SVM) after random-projection-based feature dimensionality reduction, Linear kernel SVM based on dual random projection (drp-LSVM) for large-scale classification problems was proposed with the introduction of the dual recovery theory. Firstly, the relevant geometric properties of drp-LSVM were analyzed and demonstrated. It’s proved that, with maintaining the similar geometric advantages of Linear kernel SVM based on dual random projection (rp-LSVM), the divided hyperplane of drp-LSVM was more close to the primitive classifier trained by complete data. Then, in view of the fast solution to drp-LSVM, the traditional Sequential Minimal Optimization (SMO) algorithm was improved and the drp-LSVM classifier based on improved SMO algorithm was completed. Finally, the experimental results show that, drp-LSVM inherits the advantages of rp-LSVM, reduces classification error, improves training accuracy, and all its performance indexes are more close to the classifier trained by primitive data; the classifier designed based on the improved SMO algorithm can reduce memory consumption and achieve higher training accuracy.

machine learning; Support Vector Machine (SVM); random projection; Sequential Minimal Optimization (SMO) algorithm; dimensionality reduction

2016- 11- 10;

2016- 12- 29。

国家自然科学基金资助项目(71503260)；陕西省自然科学基金资助项目(2014JM8345)。

席茜(1993—)，女，山西新绛人，硕士研究生， CCF会员，主要研究方向：数据挖掘、机器学习； 张凤琴(1964—)，女，山西芮城人，副教授，硕士， CCF会员，主要研究方向：数据挖掘、复杂网络、分布式数据库； 李小青(1982—)，女，陕西泾阳人，讲师，博士，主要研究方向：数据智能处理； 管桦(1963—)，男，湖北孝感人，教授，硕士，主要研究方向：指挥自动化； 陈桂茸(1970—)，女，陕西合阳人，讲师，硕士，主要研究方向：复杂网络； 王梦非(1992—)，男，山东济南人，硕士研究生，主要研究方向：复杂网络、机器学习。

1001- 9081(2017)06- 1680- 06

10.11772/j.issn.1001- 9081.2017.06.1680

TP181

A