席 茜，張鳳琴，李小青，管 樺，陳桂茸，王夢非

(空軍工程大學 信息與導航學院，西安710077)

基于對偶隨機投影的線性核支持向量機

席 茜*，張鳳琴，李小青，管 樺，陳桂茸，王夢非

(空軍工程大學 信息與導航學院，西安710077)

(*通信作者電子郵箱245594320@qq.com)

針對大型支持向量機(SVM)經(jīng)隨機投影特征降維后分類精度下降的問題，結(jié)合對偶恢復理論，提出了面向大規(guī)模分類問題的基于對偶隨機投影的線性核支持向量機(drp-LSVM)。首先，分析論證了drp-LSVM相關幾何性質(zhì)，證明了在保持與基于隨機投影降維的支持向量機(rp-LSVM)相近幾何優(yōu)勢的同時，其劃分超平面更接近于用全部數(shù)據(jù)訓練得到的原始分類器。然后，針對提出的drp-LSVM快速求解問題，改進了傳統(tǒng)的序列最小優(yōu)化(SMO)算法，設計了基于改進SMO算法的drp-LSVM分類器。最后實驗結(jié)果表明，drp-LSVM在繼承rp-LSVM優(yōu)點的同時，減小了分類誤差，提高了訓練精度，并且各項性能評價更接近于用原始數(shù)據(jù)訓練得到的分類器；設計的基于改進SMO算法的分類器不但可以減少內(nèi)存消耗，同時可以擁有較高的訓練精度。

機器學習；支持向量機；隨機投影；序列最小優(yōu)化算法；降維

0 引言

支持向量機(Support Vector Machine, SVM)在1995年由Cortes等[1]首次提出，由于其擁有擅長處理小樣本、非線性數(shù)據(jù)、高維模式識別的特點，并在一定程度下避免了“維數(shù)災難”，所以基于SVM的分類器在文本分類領域中有著廣泛的應用，在處理高維數(shù)據(jù)分類問題時也獨占優(yōu)勢。與此同時應用于大型SVM的特征降維方法也成為研究熱點。近年來，隨機近似算法在大規(guī)模機器學習中應用廣泛，其中隨機投影(Random Projections, RP)方法可以快速有效地解決高維數(shù)據(jù)的降維問題，用以減少相關優(yōu)化問題的計算代價。隨機投影是通過控制精度來減少維度的方法，保持兩個樣本之間成對的距離，因此屬于基于距離的方法。由于SVM也是基于距離的學習方法，故可以運用隨機投影進行特征降維。2007年到2009年期間,Kumar等[2]和Jethava等[3]證明了基于高斯隨機投影的SVM可以得到與原問題相近的相關誤差，訓練時間與投影矩陣和輸入矩陣相關。2014年Paul等[4]證明了運用隨機投影后的數(shù)據(jù)經(jīng)過SVM訓練，可以在保持特征空間的幾何性質(zhì)的同時保持分類器的最大間隔和最小閉包球的幾何性質(zhì)，維持了原有的泛化性能，并實踐論證，同時從理論上證明了基于隨機投影的線性核SVM(Linear kernel SVM based on random projection, rp-LSVM)訓練時間與輸入的非零數(shù)據(jù)的數(shù)量線性相關。

但隨機投影后得到的最優(yōu)解與原始問題的最優(yōu)解存在一定誤差，2012年Zhang等[5]將凸優(yōu)化中的Fenchel對偶理論與隨機投影相結(jié)合，得到一種基于對偶解恢復的隨機機器學習方法，能有效地恢復原始優(yōu)化問題的最優(yōu)解。大規(guī)模的SVM問題本質(zhì)也是大規(guī)模的優(yōu)化問題，隨即投影的降維方法在提升分類器訓練效率的同時，也在一定程度下降低了對精度的要求。本文首先將對偶恢復思想應用于rp-LSVM中，提出基于對偶隨機投影的線性核SVM(Linear kernel SVM based on dual random projection, drp-LSVM)，在保持了rp-LSVM優(yōu)點的同時，解決了其精度下降的問題。理論分析證明drp-LSVM在幾何上比rp-LSVM更接近于所有數(shù)據(jù)訓練得到的原始分類器，證明了drp-LSVM的最大間隔超平面與最小閉包球保持了與rp-LSVM近似的幾何性質(zhì)，同樣確保了與原始空間相近的泛化能力。本文還針對提出的drp-LSVM快速求解問題，改進了序列最小優(yōu)化(Sequential Minimal Optimization, SMO)算法，設計了基于改進SMO算法的drp-LSVM分類器。最后的實驗證明了drp-LSVM在繼承rp-LSVM優(yōu)點的同時，減小了訓練誤差，提高了訓練精度，訓練結(jié)果的各項性能評價更接近于用原始數(shù)據(jù)訓練得到的分類器?；诟倪MSMO算法的drp-LSVM分類器在減少內(nèi)存消耗的同時有較高的訓練精度。

1 相關概念

1.1 線性核支持向量機

設有訓練集D={xi,yi}(i=1,2,…,n)，xi∈Rd，類標簽yi∈{-1,+1}。對于線性可分的數(shù)據(jù)，SVM學習問題最基本的思想是基于訓練集D在樣本空間中找到一個擁有最大間隔的劃分超平面[6]，轉(zhuǎn)化為凸二次規(guī)劃問題形式為：

(1)

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

(2)

這是SVM的基本形，其中w為劃分超平面的法向量。當加入軟間隔與正則化思想并且核函數(shù)為線性核時，相應的拉格朗日對偶問題為：

(3)

(4)

其中αi為拉格朗日算子，C≥αi≥0,i=1,2,…,n，C為常數(shù)。

設樣本數(shù)據(jù)集在半徑為R的球內(nèi)，支持向量到超平面的距離和(即SVM的間隔)為γ，則該假設集的VC維(Vapnik-Chervonenkis Dimension)是O(R2/γ2)，如此可以估計出泛化誤差界。

1.2 隨機投影

引理1 對任意的ε∈(0,1)及正整數(shù)n，m為正整數(shù)且滿足: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經(jīng)過標準高斯矩陣隨機投影得到的，則有如下概率成立：

(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]是目前最快的求解二次規(guī)劃問題的算法，特別針對LSVM和數(shù)據(jù)稀疏時性能更優(yōu)。SVM訓練中最核心的問題是求解二次規(guī)劃問題，傳統(tǒng)的方法利用Hessian矩陣求解最優(yōu)值需要很大的計算和存儲代價。SMO算法將大規(guī)模的優(yōu)化問題轉(zhuǎn)化為一系列包含兩個變量的子問題，從而避免了復雜的數(shù)值解法，有效地節(jié)省了時間成本并降低了內(nèi)存要求。SMO算法類似于坐標上升，每次啟發(fā)式選擇兩個參數(shù)變量進行優(yōu)化，不斷循環(huán)，直到達到函數(shù)最優(yōu)解。

SMO算法的關鍵步驟可以大概總結(jié)為：首先啟發(fā)式選擇兩個參數(shù)，固定其余參數(shù)，整體視為一個二元函數(shù)，由約束條件將一個參數(shù)用另一個參數(shù)表示，視為一個一元函數(shù)，并對一元函數(shù)求極值點，最后根據(jù)上下界和約束條件，對原始解進行修剪，更新參數(shù)并取臨界特殊情況，進行分析。

2 基于對偶隨機投影的線性核支持向量機

2.1 隨機投影的對偶恢復

設有如下目標優(yōu)化問題：

(7)

則根據(jù)Fenchel對偶定理得到原優(yōu)化問題的對偶問題：

(8)

代入原問題有：

用梯度求解法可求得：

(9)

(10)

(11)

(12)

易知新解與原優(yōu)化問題最優(yōu)解存在較大誤差，即：

(13)

故將低維空間Fenchel對偶得到的最優(yōu)解代入到原優(yōu)化問題中，得到恢復后的最優(yōu)解。

根據(jù)上述推導，得到基于對偶解的隨機投影(drp)算法如下。

算法1 drp算法。

輸入 訓練集D={xi,yi}，樣本維度m。

2)計算低維子空間下的最優(yōu)解z*。

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

2.2drp-LSVM

由于支持向量機問題可以轉(zhuǎn)化為凸二次規(guī)劃問題，使用拉格朗日乘子法可得到其對偶問題，類比Zhang等[5]提出的對偶隨機投影算法中將低維優(yōu)化問題的共軛對偶變量代入到原問題中恢復最優(yōu)解的方法，將低維空間中解出的拉格朗日乘子代入到原始超平面的計算中去，得到恢復的最優(yōu)超平面。

(14)

(15)

2.3drp-LSVM的性質(zhì)分析

(16)

證明 令E=VTV-VTAATV

將上述式(14)、(15)問題經(jīng)過奇異值分解(Singular Value Decomposition, SVD)分解得到：

(17)

(18)

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

(19)

又由拉格朗日對偶函數(shù)的凹性可知：

(20)

由式(19)、(20)兩個不等式得到：

(21)

即：

(22)

結(jié)合引理2可得：

(23)

將低位空間的最優(yōu)解轉(zhuǎn)換高維空間后有關系：

(24)

則易求得：

(25)

由式(23)、(25)可以看出，drp-LSVM求得的最優(yōu)解比直接經(jīng)過隨機投影降維的LSVM的最優(yōu)解更接近原始最優(yōu)解，即從幾何上更接近于原始分類器。

下面論證drp-LSVM最大間隔超平面的幾何性質(zhì)。

利用SVD有:

(26)

即有不等式(27)如下：

(27)

易得不等式(28)如下：

(28)

將(28)代入(27)則有：

(29)

(30)

由不等式(28)可知：

(31)

結(jié)合式(25)、(31)得到：

(32)

即：

由引理2可得：

(33)

同樣可以利用SVD和引理2證明最小閉包球(Minimum Enclosing Ball, MEB)的性質(zhì)如下。

由于LSVM的MEB的拉格朗日對偶問題為：

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

(34)

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

設閉包球半徑為R，球心向量為xc，則：

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

(35)

(36)

經(jīng)隨機投影后：

(37)

對偶恢復后：

結(jié)合引理2易推得：

(38)

由上述理論分析可以得到，drp-LSVM的間隔和最小閉包球半徑與rp-LSVM相近，同樣保持了與原始空間的ε相關誤差，維持了與原空間相似的泛化性能。

3 基于改進SMO算法的drp-LSVM分類器

雖然LSVM的訓練和測試速度相對較快，但與KSVM相同，LSVM中最核心的問題還是求解二次規(guī)劃問題，本文為求解基于對偶隨機投影的LSVM設計了基于對偶隨機投影的SMO算法，主要思想如下：

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

(39)

第二步 計算Ws的二階導η，并更新Ws：

η=x1TAATx1+x2TAATx2-2x1TAATx2

(40)

(41)

ei=g(xi)-yi

(42)

(43)

(44)

第四步 在原空間下更新：

(45)

收斂條件為在界內(nèi)的樣例都能夠滿足卡羅需-庫恩-塔克(Karush-Kuhn-Tucker, KTT)條件，且其對應的αi只在極小范圍內(nèi)變動，設計流程如圖1所示。

圖1 分類器設計流程

4 實驗驗證與分析

實驗環(huán)境為2.6GHzIntelCorei5處理器，8GB內(nèi)存，操作系統(tǒng)為Linux，開發(fā)工具為Python、Java。實驗數(shù)據(jù)來自lib-SVMData[11]，實驗一基于Liblinear庫[12]進行drp-SVM相關性能測試，參數(shù)設置為默認參數(shù)。實驗二測試基于改進SMO算法的drp-SVM性能。數(shù)據(jù)集D1、D2分別為gisette_scale[13]、rcv1.binary[14]。D1含訓練樣本6 000，測試樣本1 000，樣本維數(shù)為5 000，滿足中等規(guī)模數(shù)據(jù)量及維數(shù)的特征；D2含訓練樣本202 421，測試樣本677 399，維數(shù)為47 236，滿足大規(guī)模高維度數(shù)據(jù)特征。為保證實驗的準確度和可信度，相關實驗重復5次，最終實驗數(shù)據(jù)取平均值。

4.1 實驗一

針對中等規(guī)模數(shù)據(jù)集D1，為檢驗分類器效果，考慮到數(shù)據(jù)集維數(shù)為5 000，則取四種不同投影維數(shù)512、1 024、2 048、4 096，在各種目標維數(shù)下分別計算drp-SVM，rp-SVM和原分

類器(即用全部數(shù)據(jù)訓練出來的支持向量機，圖中用full表示)的相關評估參數(shù)。圖2分別為三種分類器在不同維度下精度(Accuracy,ACC)、均方誤差(MeanSquareError,MSE)及平方相關系數(shù)(SquaredCorrelationCoefficient,SCC)的關系。

由圖2可看出，相比于rp-SVM，drp-SVM的各項訓練指標都更接近于所有訓練數(shù)據(jù)得到的原始分類器。

針對較大規(guī)模數(shù)據(jù)集D2，結(jié)合數(shù)據(jù)集維數(shù)47 236，取四種不同投影維數(shù)1 024、2 048、4 096、8 192，在各種目標維數(shù)下分別計算drp-SVM、rp-SVM和原分類器(即用全部數(shù)據(jù)訓練出來的支持向量機，圖中用full表示)的相關評估參數(shù)。圖3分別為三種分類器在不同維度下精度(ACC)、均方誤差(MSE)及平方相關系數(shù)(SCC)的關系。

由圖3可看出，在大規(guī)模更高維度的數(shù)據(jù)集環(huán)境下，drp-SVM的各項訓練指標更優(yōu)于rp-SVM，同時更加接近原始分類器。

圖2 D1數(shù)據(jù)集下不同維數(shù)各分類器的性能指標

圖3 D2數(shù)據(jù)集下不同維數(shù)各分類器的性能指標

表1～2分別為針對數(shù)據(jù)集D1和D2訓練不同分類器在最優(yōu)投影維數(shù)下訓練時間(用time表示，單位為s)、最大間隔(γ)、5次交叉檢驗(5-fold)后的精度以及分類錯誤率(errorRate)的統(tǒng)計。

從表1～2可以看出，相比于rp-SVM，drp-SVM保留了其訓練時間減少和保持最大間隔的優(yōu)點，并在此基礎上提高了訓練精度，減小了誤差。

4.2 實驗二

用數(shù)據(jù)集D1來測試基于改進SMO算法的drp-SVM性能，為方便對比，將三種算法的訓練時間(用time表示，單位為h)、訓練中消耗內(nèi)存比(用memory表示)及分類錯誤率(用errorRate表示)在一張圖中展現(xiàn)，如圖4所示。

表1 D1訓練的三種分類器的各項參數(shù)

表2 D2訓練的三種分類器的各項參數(shù)

圖4 基于SMO算法的三種分類器性能比較

由圖4可以看出，運用改進的算法(drp-SMO)的分類器比運用所有數(shù)據(jù)訓練的基于SMO算法的分類器(full-SMO)的分類器更高效、更節(jié)省內(nèi)存，且相比直接經(jīng)過隨機投影的SMO分類器(rp-SMO)準確度更接近原始分類器。

5 結(jié)語

本文針對特征降維后的支持向量機精度下降等問題，設計了基于對偶隨機投影的線性核支持向量機(drp-LSVM)相關算法，并從理論分析的角度證明了求解drp-LSVM問題得到的最優(yōu)解比rp-LSVM的最優(yōu)解更接近于原始分類器得到的最優(yōu)解，保證了在特征降維后，訓練得到的分類器能夠保持與原分類器相似的幾何性質(zhì)。文中還證明了drp-LSVM的最大間隔超平面與最小閉包球保持了與rp-LSVM近似的ε相關誤差，同樣確保了與原始空間相近的泛化能力。文中提出針對drp-LSVM的改進SMO算法，設計了基于改進SMO算法的分類器。大規(guī)模高維的數(shù)據(jù)集的實驗證明了drp-LSVM在降維特征提高訓練速度的同時，訓練效果及性能評價更接近于原始分類器，改進SMO算法在保持了算法穩(wěn)定性的同時擁有較高的訓練速度和精度。本文僅圍繞特殊的線性核支持向量機以及高斯投影進行了針對性研究，并沒有考慮非線性核及其他種類的隨機投影特征降維情況。大規(guī)模機器學習仍是目前主流的挑戰(zhàn)，有關隨機機器學習的技術方法有待進一步深入研究。

)

[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會員，主要研究方向：數(shù)據(jù)挖掘、機器學習； 張鳳琴(1964—)，女，山西芮城人，副教授，碩士， CCF會員，主要研究方向：數(shù)據(jù)挖掘、復雜網(wǎng)絡、分布式數(shù)據(jù)庫； 李小青(1982—)，女，陜西涇陽人，講師，博士，主要研究方向：數(shù)據(jù)智能處理； 管樺(1963—)，男，湖北孝感人，教授，碩士，主要研究方向：指揮自動化； 陳桂茸(1970—)，女，陜西合陽人，講師，碩士，主要研究方向：復雜網(wǎng)絡； 王夢非(1992—)，男，山東濟南人，碩士研究生，主要研究方向：復雜網(wǎng)絡、機器學習。

1001- 9081(2017)06- 1680- 06

10.11772/j.issn.1001- 9081.2017.06.1680

TP181

A