鄭世平,席文飛,王 梁

(1.內(nèi)蒙古電力(集團(tuán))有限責(zé)任公司,內(nèi)蒙古 呼和浩特 010020;2.華中科技大學(xué)材料科學(xué)與工程學(xué)院,湖北 武漢 430074)

0 引言

支持向量機(jī)[1](support vector machine,SVM)是一類(lèi)基于核理論的學(xué)習(xí)模型。相對(duì)于神經(jīng)網(wǎng)絡(luò),SVM 基于最大間隔思想,引入正則化技術(shù),進(jìn)而實(shí)現(xiàn)了模型的結(jié)構(gòu)風(fēng)險(xiǎn)極小化準(zhǔn)則。通過(guò)求解二次規(guī)劃問(wèn)題,它擁有全局最優(yōu)解。同時(shí),SVM 在處理小樣本數(shù)據(jù)上性能卓越,因而受到了學(xué)術(shù)界與工業(yè)界的青睞,且已被成功應(yīng)用到各大領(lǐng)域,比如圖像識(shí)別、信號(hào)分析、故障檢測(cè)、醫(yī)學(xué)診斷等。然而,在處理異構(gòu)數(shù)據(jù)分布學(xué)習(xí)任務(wù)上,SVM 的學(xué)習(xí)性能受到了較大的影響。為解決此問(wèn)題,Jayadeva 等[2]在機(jī)器學(xué)習(xí)期刊TPAMI 上提出一種全新的雙胞支持向量機(jī)(twin support vector machine,TWSVM)模型。相對(duì)于原始的SVM,基于非平行思想的TWSVM 模型[2]在處理異構(gòu)數(shù)據(jù)問(wèn)題上表現(xiàn)出卓越的泛化能力。因此,TWSVM 得到了國(guó)內(nèi)外很多學(xué)者的關(guān)注,并后續(xù)提出了很多優(yōu)秀的模型。例如雙胞界限支持向量機(jī)(twin bound support vector machine,TBSVM)[3]、最小二乘雙胞支持向量機(jī)(least squares twin support vector machines,LSTSVM)[4]、半監(jiān)督近端向量機(jī)(manifold proximal support vector machine,MPSVM)[5]、多標(biāo)簽雙胞支持向量機(jī)(multi-label twin support vector machines,MLTSVM)[6]、非平行支持向量機(jī)(nonparallel support vector machines,NPSVM)[7]等支持向量機(jī)模型。

投影雙胞支持向量機(jī)(projection twin support vector machine,PTSVM)[8]是近年來(lái)被提出的一個(gè)非平行學(xué)習(xí)分類(lèi)方法,擁有優(yōu)秀的泛化能力。然而,PTSVM 模型的對(duì)偶問(wèn)題存在矩陣求逆運(yùn)行,加重了模型的訓(xùn)練負(fù)擔(dān)。此外,矩陣求逆也將導(dǎo)致PTSVM 模型的不穩(wěn)定性。為此,受NPSVM 模型[7]啟發(fā),提出一個(gè)新的增強(qiáng)型投影雙胞支持向量機(jī)模型(improved projection twin support vector machine,IPTSVM)。該模型旨在尋找一對(duì)最優(yōu)非平行投影方向,使得新投影空間的每個(gè)投影上,同類(lèi)別的樣本點(diǎn)盡量聚集在類(lèi)內(nèi)投影中心附近;另一方面,其他類(lèi)樣本盡量遠(yuǎn)離當(dāng)前類(lèi)別中心。在IPTSVM 模型中,使用等式約束對(duì)類(lèi)內(nèi)樣本的損失函數(shù)進(jìn)行了重構(gòu)。然后,為提高模型穩(wěn)定性,正則項(xiàng)被引入IPTSVM 模型。相對(duì)于PTSVM 模型,IPTSVM 模型對(duì)偶問(wèn)題不再有矩陣求逆,進(jìn)而提高了模型的訓(xùn)練效率。

1 投影雙胞支持向量機(jī)回顧

本文符號(hào)約定如下:所有的向量都為列向量;上標(biāo)“T”表示轉(zhuǎn)置;I表示單位矩陣;0 和e分別表示全0 向量和全1 向量。

針對(duì)n維實(shí)數(shù)空間Rn的二分類(lèi)學(xué)習(xí)任務(wù)[1],給定訓(xùn)練數(shù)據(jù)集:

式中:l為訓(xùn)練數(shù)據(jù)集規(guī)模;xi為在Rn空間中的第i個(gè)訓(xùn)練樣本點(diǎn),xi∈Rn;yi為xi所對(duì)應(yīng)的類(lèi)別輸出,yi∈{-1,+1}。

記矩陣A和B分別為正類(lèi)和負(fù)類(lèi)樣本集,記I1和I2分別為屬于正類(lèi)和負(fù)類(lèi)的樣本集合索引,其規(guī)模分別為l1和l2。

采用PTSVM 模型[8]構(gòu)造如下二次規(guī)劃問(wèn)題:

式中:c1、c2為模型的罰參數(shù),c1≥0,c2≥0;ζ1和ζ2為樣本的松弛變量,用于度量樣本犯錯(cuò)程度;m1為正類(lèi)樣本中心,;m2為負(fù)類(lèi)樣本中心,。

為簡(jiǎn)化問(wèn)題,分別定義正類(lèi)和負(fù)類(lèi)的類(lèi)別散度矩陣:

則問(wèn)題(2)和問(wèn)題(3)可轉(zhuǎn)換為如下的矩陣形式:

為求解式(5)和式(6)的最優(yōu)解,將其轉(zhuǎn)換為對(duì)偶問(wèn)題:

求得對(duì)偶問(wèn)題(7)和對(duì)偶問(wèn)題(8)的最優(yōu)解和,可根據(jù)式(9)、式(10)求得原始問(wèn)題(5)和原始問(wèn)題(6)的解:

2 增強(qiáng)型投影雙胞支持向量機(jī)原理

由式(7)和式(8)可知,對(duì)偶問(wèn)題中的Hessian 矩陣存在運(yùn)算量較大的求逆操作。這將導(dǎo)致PTSVM 模型[8]的訓(xùn)練效率較低,且并不適合處理大規(guī)模學(xué)習(xí)問(wèn)題。為此,受NPSVM 模型[7]啟發(fā),提出了新的IPTSVM 模型。IPTSVM 模型的核心思想是,旨在尋找一對(duì)最優(yōu)的非平行投影方向w1和w2,使得新投影空間的每個(gè)投影上,同類(lèi)別的樣本點(diǎn)盡量聚集在類(lèi)內(nèi)投影中心附近;另一方面,其他類(lèi)樣本盡量遠(yuǎn)離當(dāng)前類(lèi)別中心。

為度量樣本點(diǎn)與類(lèi)別中心的偏移量,定義如下投影函數(shù):

式中:k為1 或2。

為每個(gè)類(lèi)別分別構(gòu)造如下的經(jīng)驗(yàn)風(fēng)險(xiǎn)函數(shù):

式中:c1、c2為懲罰參數(shù),用于調(diào)節(jié)損失函數(shù)式(12)和式(13)中各項(xiàng)損失的權(quán)重,c1>0,c2>0。

為度量類(lèi)內(nèi)散度,分別為正類(lèi)和負(fù)類(lèi)樣本引入松弛變量η1和η2,即類(lèi)內(nèi)樣本點(diǎn)離類(lèi)中心越遠(yuǎn)該松弛變量就越大,反之亦然。為此,結(jié)合經(jīng)驗(yàn)風(fēng)險(xiǎn)函數(shù)式(12)和式(13),IPTSVM 的模型可表示為:

為提高模型的泛化能力,在IPTSVM 模型中引入Tikhonov 正則項(xiàng),用于控制模型的復(fù)雜程度。進(jìn)一步,IPTSVM 模型的原始優(yōu)化問(wèn)題可表示為:

式中:λ1、λ2為正則項(xiàng)權(quán)衡參數(shù),用于調(diào)節(jié)損失函數(shù)和正則項(xiàng)權(quán)重,λ1>0,λ2>0。

針對(duì)IPTSVM 模型的正類(lèi)優(yōu)化問(wèn)題(17),給出詳細(xì)的幾何解釋。

①第1 項(xiàng)和第1 個(gè)約束條件使用了最小二乘法損失函數(shù),實(shí)現(xiàn)正類(lèi)樣本的經(jīng)驗(yàn)風(fēng)險(xiǎn)函數(shù)。對(duì)于偏離類(lèi)別中心的正類(lèi)樣本點(diǎn)xi,通過(guò)引入松弛變量η1i度量其誤差。極小化該項(xiàng),在新的投影空間中,期望所有正類(lèi)樣本能聚在正類(lèi)中心附近。

②第2 項(xiàng)和第2、第3 個(gè)約束條件使用了Hinge 鉸鏈損失函數(shù),實(shí)現(xiàn)負(fù)類(lèi)樣本的經(jīng)驗(yàn)風(fēng)險(xiǎn)函數(shù)。極小化該項(xiàng),在新的投影空間中,期望負(fù)類(lèi)樣本盡量地遠(yuǎn)離正類(lèi)別中心;如果距離小于1,則通過(guò)引入松弛變量來(lái)度量其誤差。d1(xj)越大,則代表負(fù)類(lèi)樣本與正類(lèi)中心的間隔越大,那么模型的泛化能力將會(huì)越強(qiáng)。

IPTSVM 模型的幾何解釋如圖1 所示。

圖1 IPTSVM 模型的幾何解釋Fig.1 Geometric interpretation of the IPTSVM model

3 模型優(yōu)化與求解

為簡(jiǎn)化計(jì)算,針對(duì)模型求解優(yōu)化問(wèn)題(16),首先定義各類(lèi)數(shù)據(jù)到類(lèi)別中心mk的偏差矩陣:

則優(yōu)化問(wèn)題(16)與優(yōu)化問(wèn)題(17)可進(jìn)一步轉(zhuǎn)換為如下的矩陣形式:

由于優(yōu)化問(wèn)題(16)與優(yōu)化問(wèn)題(17)具有類(lèi)似形式,篇幅有限,下文只關(guān)注優(yōu)化問(wèn)題(16)的求解。優(yōu)化問(wèn)題(17)可采用類(lèi)似的方法?？紤]優(yōu)化問(wèn)題(16)的Lagrange 函數(shù):

式中:α1、β1、γ1為L(zhǎng)agrange 乘子。

根據(jù)Wolfe 對(duì)偶理論[1],對(duì)L(ω1,η1,ζ1,α1,β1,γ1)關(guān)于變量ω1、η1、ζ1、α1、β1、γ1求偏導(dǎo),并令它們的偏導(dǎo)為0。由此可得如下karush-kuhn-Tucker(KKT)充分必要條件:

由此可得:

將上述參數(shù)代入L(ω1,η1,ζ1,α1,β1,γ1),并結(jié)合KKT 條件(23)和KKT 條件(30),可得優(yōu)化問(wèn)題(20)的對(duì)偶問(wèn)題:

對(duì)偶問(wèn)題(34)的最優(yōu)解(α1,β1)可由二次規(guī)劃(quadric programming,QP)工具包求解。當(dāng)?shù)玫阶顑?yōu)解(α1,β1)后,可根據(jù)式(31)得到原始問(wèn)題(16)的最優(yōu)解ω1。

同理,針對(duì)優(yōu)化問(wèn)題,可推得其對(duì)偶問(wèn)題:

當(dāng)?shù)玫絾?wèn)題的最優(yōu)解(α2,β2)時(shí),可根據(jù)式(37)得到原始問(wèn)題的最優(yōu)解ω2。

對(duì)于新樣本x的預(yù)測(cè),其類(lèi)別的判別依據(jù)如下決策函數(shù):

4 試驗(yàn)結(jié)果分析

所有試驗(yàn)均以Matlab 2017a 為軟件平臺(tái),以Intel Core i3 處理器、8 GB 內(nèi)存的計(jì)算機(jī)為硬件平臺(tái)。為驗(yàn)證本文所提的IPTSVM 模型的有效性,以分類(lèi)準(zhǔn)確率和訓(xùn)練時(shí)間為指標(biāo),選取來(lái)自加州大學(xué)爾灣分校(University of California Irvine,UCI)的9 個(gè)公共數(shù)據(jù)集,對(duì)SVM[1]和PTSVM[8]進(jìn)行性能對(duì)比試驗(yàn)。SVM、PTSVM 和IPTSVM 的優(yōu)化問(wèn)題都采用Matlab 二次規(guī)劃求解器quadprog 求解;PTSVM 的Hessian 矩陣求逆采用求逆‘/’運(yùn)算符。選擇徑向基函數(shù)(radial basis function,RBF)核作為非線性學(xué)習(xí)核函數(shù):k(x1,x2)=。其中,φ為核參數(shù)。為簡(jiǎn)化尋參過(guò)程,試驗(yàn)中設(shè)置PTSVM 的參數(shù)c1=c2=c、IPTSVM的參數(shù)c1=c2=c和λ1=λ2=λ。模型的選參使用十折交叉驗(yàn)證法[1]。參數(shù)包括:SVM 模型中的c;PTSVM 模型中的c、IPTSVM 模型中的c、λ、非線性RBF 核參數(shù)φ,選參范圍為{2-6,2-5,...,25,26}。

表1 給出了SVM、PTSVM 和IPTSVM 模型在UCI數(shù)據(jù)集的分類(lèi)準(zhǔn)確率。

表1 SVM、PTSVM 和IPTSVM 模型在UCI 數(shù)據(jù)集的分類(lèi)準(zhǔn)確率Tab.1 Classification accuracy of the SVM、PTSVM、IPTSVM models in UCI dataset %

表1 中,最好的分類(lèi)準(zhǔn)確率以加粗標(biāo)識(shí)。試驗(yàn)結(jié)果表明:本文所提出的IPTSVM 模型,擁有與原PTSVM模型相近的分類(lèi)性能。在9 個(gè)UCI 數(shù)據(jù)集中,有6 個(gè)數(shù)據(jù)上分類(lèi)性能超過(guò)PTSVM。例如在Cancer 數(shù)據(jù)集上,相對(duì)于PTSVM 為96.13%,IPTSVM 的準(zhǔn)確率為96.81%。從分類(lèi)穩(wěn)定性上看,本文所提的IPTSVM 模型在大部分的數(shù)據(jù)集的十折分類(lèi)方差都比PTSVM 模型低。這主要?dú)w因于正則項(xiàng)的引入控制了IPTSVM 模型的復(fù)雜度,可防止模型過(guò)擬合,進(jìn)一步提高了IPTSVM 模型的穩(wěn)定性。

圖2 給出了SVM、PTSVM 和IPTSVM 模型在UCI數(shù)據(jù)集的平均學(xué)習(xí)時(shí)間。

圖2 SVM、PTSVM 和IPTSVM 模型在UCI 數(shù)據(jù)集的平均學(xué)習(xí)時(shí)間Fig.2 Average learning time of the SVM、PTSVM、IPTSMVM models in UCI dataset

試驗(yàn)結(jié)果表明:本文所提的IPTSVM 模型的訓(xùn)練時(shí)間最短,其次是PTSVM,而SVM 訓(xùn)練時(shí)間最長(zhǎng)。由于PTSVM 在構(gòu)造二次規(guī)劃問(wèn)題時(shí),需要對(duì)Hessian 矩陣進(jìn)行求逆運(yùn)算,大大增加了訓(xùn)練負(fù)擔(dān);而IPTSVM 模型的改進(jìn)使得其對(duì)偶不存在求逆,進(jìn)而提高了模型的學(xué)習(xí)效率。此外,SVM 通過(guò)構(gòu)造一個(gè)優(yōu)化問(wèn)題來(lái)求解分類(lèi)超平面,而PTSVM 和IPTSVM 則繼承了非平行學(xué)習(xí)范式,將較大規(guī)模的問(wèn)題分解為較小規(guī)模的問(wèn)題求解,使得它們的學(xué)習(xí)效率相對(duì)SVM 更高。

上述試驗(yàn)結(jié)果驗(yàn)證了IPTSVM 模型的有效性。

5 結(jié)論

PTSVM 模型的求逆運(yùn)算加重了模型的訓(xùn)練負(fù)擔(dān),容易引起模型的不穩(wěn)定性。為此,本文提出了新的增強(qiáng)型投影雙胞支持向量機(jī),即IPTSVM。該模型旨在尋找一對(duì)最優(yōu)非平行投影方向,在新的投影空間中,使得在每個(gè)投影上同類(lèi)別的樣本點(diǎn)盡量聚集在類(lèi)內(nèi)投影中心附近,而其他類(lèi)樣本盡量遠(yuǎn)離當(dāng)前類(lèi)別中心。該模型有效地避免了矩陣求逆問(wèn)題,提高了模型的訓(xùn)練效率。模型中的正則項(xiàng)提高了模型的泛化能力,保障了模型解的穩(wěn)定性。UCI 公共數(shù)據(jù)集的仿真結(jié)果驗(yàn)證了IPTSVM 模型的有效性。