增強型投影雙胞支持向量機設計

鄭世平,席文飛,王 梁

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

0 引言

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

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

1 投影雙胞支持向量機回顧

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

針對n維實數空間Rn的二分類學習任務[1],給定訓練數據集:

式中:l為訓練數據集規模;xi為在Rn空間中的第i個訓練樣本點,xi∈Rn;yi為xi所對應的類別輸出,yi∈{-1,+1}。

記矩陣A和B分別為正類和負類樣本集,記I1和I2分別為屬于正類和負類的樣本集合索引,其規模分別為l1和l2。

采用PTSVM 模型[8]構造如下二次規劃問題:

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

為簡化問題,分別定義正類和負類的類別散度矩陣:

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

為求解式(5)和式(6)的最優解,將其轉換為對偶問題:

求得對偶問題(7)和對偶問題(8)的最優解和,可根據式(9)、式(10)求得原始問題(5)和原始問題(6)的解:

2 增強型投影雙胞支持向量機原理

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

為度量樣本點與類別中心的偏移量,定義如下投影函數:

式中:k為1 或2。

為每個類別分別構造如下的經驗風險函數:

式中:c1、c2為懲罰參數,用于調節損失函數式(12)和式(13)中各項損失的權重,c1>0,c2>0。

為度量類內散度,分別為正類和負類樣本引入松弛變量η1和η2,即類內樣本點離類中心越遠該松弛變量就越大,反之亦然。為此,結合經驗風險函數式(12)和式(13),IPTSVM 的模型可表示為:

為提高模型的泛化能力,在IPTSVM 模型中引入Tikhonov 正則項,用于控制模型的復雜程度。進一步,IPTSVM 模型的原始優化問題可表示為:

式中:λ1、λ2為正則項權衡參數,用于調節損失函數和正則項權重,λ1>0,λ2>0。

針對IPTSVM 模型的正類優化問題(17),給出詳細的幾何解釋。

①第1 項和第1 個約束條件使用了最小二乘法損失函數,實現正類樣本的經驗風險函數。對于偏離類別中心的正類樣本點xi,通過引入松弛變量η1i度量其誤差。極小化該項,在新的投影空間中,期望所有正類樣本能聚在正類中心附近。

②第2 項和第2、第3 個約束條件使用了Hinge 鉸鏈損失函數,實現負類樣本的經驗風險函數。極小化該項,在新的投影空間中,期望負類樣本盡量地遠離正類別中心;如果距離小于1,則通過引入松弛變量來度量其誤差。d1(xj)越大,則代表負類樣本與正類中心的間隔越大,那么模型的泛化能力將會越強。

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

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

3 模型優化與求解

為簡化計算,針對模型求解優化問題(16),首先定義各類數據到類別中心mk的偏差矩陣:

則優化問題(16)與優化問題(17)可進一步轉換為如下的矩陣形式:

由于優化問題(16)與優化問題(17)具有類似形式,篇幅有限,下文只關注優化問題(16)的求解。優化問題(17)可采用類似的方法。考慮優化問題(16)的Lagrange 函數:

式中:α1、β1、γ1為Lagrange 乘子。

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

由此可得:

將上述參數代入L(ω1,η1,ζ1,α1,β1,γ1),并結合KKT 條件(23)和KKT 條件(30),可得優化問題(20)的對偶問題:

對偶問題(34)的最優解(α1,β1)可由二次規劃(quadric programming,QP)工具包求解。當得到最優解(α1,β1)后,可根據式(31)得到原始問題(16)的最優解ω1。

同理,針對優化問題,可推得其對偶問題:

當得到問題的最優解(α2,β2)時,可根據式(37)得到原始問題的最優解ω2。

對于新樣本x的預測,其類別的判別依據如下決策函數:

4 試驗結果分析

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

表1 給出了SVM、PTSVM 和IPTSVM 模型在UCI數據集的分類準確率。

表1 SVM、PTSVM 和IPTSVM 模型在UCI 數據集的分類準確率Tab.1 Classification accuracy of the SVM、PTSVM、IPTSVM models in UCI dataset %

表1 中,最好的分類準確率以加粗標識。試驗結果表明:本文所提出的IPTSVM 模型,擁有與原PTSVM模型相近的分類性能。在9 個UCI 數據集中,有6 個數據上分類性能超過PTSVM。例如在Cancer 數據集上,相對于PTSVM 為96.13%,IPTSVM 的準確率為96.81%。從分類穩定性上看,本文所提的IPTSVM 模型在大部分的數據集的十折分類方差都比PTSVM 模型低。這主要歸因于正則項的引入控制了IPTSVM 模型的復雜度,可防止模型過擬合,進一步提高了IPTSVM 模型的穩定性。

圖2 給出了SVM、PTSVM 和IPTSVM 模型在UCI數據集的平均學習時間。

圖2 SVM、PTSVM 和IPTSVM 模型在UCI 數據集的平均學習時間Fig.2 Average learning time of the SVM、PTSVM、IPTSMVM models in UCI dataset

試驗結果表明:本文所提的IPTSVM 模型的訓練時間最短,其次是PTSVM,而SVM 訓練時間最長。由于PTSVM 在構造二次規劃問題時,需要對Hessian 矩陣進行求逆運算,大大增加了訓練負擔;而IPTSVM 模型的改進使得其對偶不存在求逆,進而提高了模型的學習效率。此外,SVM 通過構造一個優化問題來求解分類超平面,而PTSVM 和IPTSVM 則繼承了非平行學習范式,將較大規模的問題分解為較小規模的問題求解,使得它們的學習效率相對SVM 更高。

上述試驗結果驗證了IPTSVM 模型的有效性。

5 結論

PTSVM 模型的求逆運算加重了模型的訓練負擔,容易引起模型的不穩定性。為此,本文提出了新的增強型投影雙胞支持向量機,即IPTSVM。該模型旨在尋找一對最優非平行投影方向,在新的投影空間中,使得在每個投影上同類別的樣本點盡量聚集在類內投影中心附近,而其他類樣本盡量遠離當前類別中心。該模型有效地避免了矩陣求逆問題,提高了模型的訓練效率。模型中的正則項提高了模型的泛化能力,保障了模型解的穩定性。UCI 公共數據集的仿真結果驗證了IPTSVM 模型的有效性。