劉恒源 倪中新 陸貴斌

(上海大學經(jīng)濟學院 上海 201800)

0 引 言

多類別概率估計不僅提供了分類結果,還提供了分類結果的可信度信息,因此在數(shù)據(jù)挖掘和實際應用中具有重要作用。例如,在癌癥診斷中,為調(diào)整治療方法和藥物劑量達到更好的效果,除了需要根據(jù)腫瘤的表型特征和基因組信息將患者標記為“A型”或“B型”之外,通常還希望報告一些有關分類決策的不確定性度量。一般來說,概率估計功能比分類功能更全面,也使分類任務更加靈活,體現(xiàn)在利用得到的條件概率pk(x)=p[Y=k|X=x],可以根據(jù)實際需求制定決策規(guī)則進行類別判斷(二分類決策規(guī)則等價于以閾值0.5為界進行分類)。另外,概率估計結果可用于ROC、AUC等指標的計算,為學習器的性能評估提供方面。

傳統(tǒng)上,對概率pk(x)=p[Y=k|X=x]的估計問題通常是通過多元logistic回歸之類的回歸技術或線性判別分析(LDA)和二次判別分析(QDA)之類的密度估計方法來解決。這些方法通常會對pk的函數(shù)形式(或其轉換形式)做出某些模型假設。例如,多元logistic回歸假設對數(shù)比率和X符合線性關系,LDA和QDA假設與每個子類關聯(lián)的協(xié)變量X服從多元高斯分布。因此,這些方法雖然被廣泛使用,但很難證明多元logistic回歸中協(xié)變量線性關系的假設是正確的,此外,通常多元數(shù)據(jù)的高斯分布假設也存在爭議。

支持向量機(SVM)由Vapnik等[1]提出,它不對數(shù)據(jù)分布進行假設,在文本分析[2-3]、生物醫(yī)藥[4-5]、圖像處理[6-7]和垃圾郵件檢測[8-9]等各種應用中顯示出較高的預測準確性,但標準的SVM(C-SVM)的限制在于它直接關注分類,而不提供類別的估計概率。為解決這一問題,Platt[10]假設二分類正類條件概率p(x)=p[Y=+1|X=x]與SVM輸出y∈0,1之間存在sigmoid連接函數(shù),形式為p(x)=1/(1+exp(ay+b)),但是這種較強線性的假設在實際應用中很難滿足。Wang等[11]提出了一種無模型的SVM概率估計方法,即沒有對pk(x)的形式或每個子類的數(shù)據(jù)分布進行任何假設。他們通過訓練一系列不同權重的二分類加權SVM(WSVM),然后結合所有WSVM的分類結果來構造p1(x),完成了二分類的SVM概率估計。Wu等[12]通過直接解決一系列多分類WSVM問題,將Wang等[11]的方案從二分類擴展應用到多分類。但由于直接求解多分類問題會增加復雜度,并且計算成本將隨類別數(shù)K指數(shù)增加。為了降低復雜度和計算成本,Wang等[13]將K分類任務分解為K(K-1)個一對一二分類任務,應用Wang等[11]的方法進行二分類概率估計,然后利用公式耦合得到多類別的概率估計。

盡管這些方法實現(xiàn)了SVM的概率估計功能,但由于標準的SVM基于無界的Hinge損失函數(shù),當某些樣本點遠離所屬類時(即訓練數(shù)據(jù)中的異常點或噪聲點),會造成較大的損失,因此SVM往往會受到這類樣本的強烈影響,導致分類和概率估計性能下降[14]。本文通過限制無邊界的Pinball損失提出一種穩(wěn)健的截斷Pinball損失并應用于SVM(T-Pin-SVM)以提高概率估計和分類的準確度。數(shù)值模擬表明所提出的T-Pin-SVM一定程度上彌補了C-SVM噪聲敏感的缺點,可以提供比C-SVM更高的概率估計精度。同時,相對于Pin-SVM,截斷也使得T-Pin-SVM的稀疏性增強,降低了測試階段的計算成本。另一方面,T-Pin-SVM涉及非凸優(yōu)化,這比C-SVM的二次凸規(guī)劃求解更具挑戰(zhàn)性,本文應用Difference Convex(DC)算法,通過求解一系列凸子問題解決非凸優(yōu)化。

1 方法和理論

本節(jié)提出了一種截斷Pinball損失函數(shù)應用于SVM(T-Pin-SVM),討論了它的噪聲魯棒性、稀疏性和Fisher一致性,并且給出了T-Pin-SVM應用于多分類概率估計的算法流程。

1.1 T-Pin-SVM模型

Pinball損失與分位數(shù)有關,其應用于SVM的合理性已在[15]中進行了全面的討論。我們提出了Pinball損失的改進版本,即截斷Pinball損失(見圖1),可以表示為:

式中:l1(u)=max{u-a,0},當α→+∞時,截斷Pinball等價于Pinball損失;當α→+∞且τ=0時,等價于Hinge損失,因此本文提出的截斷Pinball是Hinge和Pinball的廣義形式。

考慮K=2的二分類問題,標簽y被編碼為-1、1,SVM分類器表示為f(x)=wTφ(x)+b,其中φ(·)∈HK表示可再生內(nèi)核希爾伯特空間(RKHS),它可以將低維空間映射到高維空間,為解決線性不可分問題提供了可能。應用截斷Pinball損失的SVM稱為T-Pin-SVM,可以表示為:

(1)

某個權重πm(m=1,2,…,M)下的加權T-Pinball-SVM可以表示為:

(2)

式中:1-πm、πm(0≤π≤1)分別表示類別1、-1的權重。

1.1.1噪聲魯棒性和稀疏性

一般不要超過兩行。在二分類任務中,基于Hinge損失(l(u)=max{0,u})的C-SVM模型求解等價于兩類點到超平面的最小距離之和取最大,這意味著最終影響超平面的僅與少數(shù)具有最小距離的點有關,并且這些點通常位于超平面附近,因此C-SVM對超平面附近的噪聲敏感。另一方面,注意到當u≥0且遞增時,Hinge損失線性增長且無界的,這意味著當某些異常點完全偏離本身類別而混入其他類別時(如標簽錯誤),對其的懲罰較大而影響整體的損失函數(shù),因此C-SVM對這些位置的點同樣敏感。

基于Pinball損失(lτ(u)=max{u,-τu},0≤τ≤1)的Pin-SVM模型求解等價于兩類點到超平面的q分位數(shù)距離之和取最大。圖1顯示了基于兩種SVM的分類差異。在Pin-SVM中,由于某一類樣本點到超平面距離的集合取q分位數(shù)的點才會影響到超平面,因此即使超平面附近有噪聲點,其占比也相對較少,這使得Pin-SVM本身就具有一定的噪聲不敏感性,然而和Hinge損失相似,Pinball損失對錯誤分類的樣本懲罰是無界的。因此,為了增強噪聲魯棒性,本文利用參數(shù)a截斷Pinball損失以避免錯分類樣本的無界懲罰。a的取值決定了截斷的位置并影響了SVM的表現(xiàn),更多細節(jié)將會在實驗部分介紹。另外它與左側截斷不同[16],右側截斷更關注那些嚴重偏離所屬類的樣本點。

圖1 基于Hinge和Pinball的SVM分類差異

由于Pinball損失沒有水平區(qū)域,其次梯度在任何地方都不等于零,因此Pin-SVM失去了稀疏性,這將導致測試階段較高的計算成本。而對于T-Pin-SVM而言,式(1)的最優(yōu)化條件可以表示為:

0∈w-∑?L(1-yif(xi))

式中:0表示全0向量;?L(·)定義為次梯度函數(shù)。

結合圖2可以發(fā)現(xiàn),當a減小,更多的樣本點傾向于落入損失函數(shù)水平,次梯度為0,意味著w的分量為0,稀疏性增強。反之,a增大,稀疏性降低。因此,本文定義w的分量不等于0的樣本為支持向量(SVs),并用支持向量占訓練樣本的比例(SVs%)衡量稀疏性(在概率估計中通過平均所有權重下的支持向量比例后再平均K(K-1)個二分類任務的比例得到)。由于Pinball損失沒有水平區(qū)域,所以Pin-SVM的支持向量比例為常數(shù)。

圖2 Hinge、Pinball和截斷Pinball三種損失函數(shù)

1.1.2Fisher一致性

當0

當1

當a>2時:

1.2 T-Pinball-SVM多分類概率估計

1.2.1T-Pinball-SVM二分類概率估計

(3)

輸入:C,σ,a,τ,πm,max_iter

(1) 初始化β0=0;

(2) for t=1 tomax_iterdo

(6) 通過yi(wTφ(xi)+b)=1求解b*;

(7) 平均所有b*得到b;

(9) 利用式(6)更新βi;

(10) ifβt=βt-1then

(11) Break;

具體過程如下:

對于式(2)的非凸問題,可以表示為min(Qvex+Qcav),其中:

(4)

(5)

定義:

(6)

式中:s=1-a;Iyif(xi)

(7)

構建拉格朗日函數(shù):

∑αi(ξi-1+yif(xi))

求導得到:

將解得的w代入拉格朗日函數(shù)得到對偶方程:

(8)

1.2.2概率耦合

在得到K(K-1)個二分類的成對條件概率估計后,可以通過概率耦合得到K個類別的概率估計,其中類別概率定義為pj(x)=p(Y=j|X=x),j=1,2,…,k。由于qj|(j,j′)(x)+qj′|(j,j′)(x)=1,可以得到:

(9)

從而對于任意類別j∈{1,2,…,K},j′≠j,可以通過式(9)完成多類別的概率值估計。

2 實驗與結果分析

為了衡量三種SVM概率估計性能,我們使用l1范數(shù)誤差和l2范數(shù)誤差以評估對比模型差異,由于實際數(shù)據(jù)沒有真實的概率值,本文使用準確率ACC評估分類結果以反映概率估計的表現(xiàn),其中分類結果根據(jù)概率值最大的標簽確定。對于每一數(shù)據(jù)集,我們測試了不同參數(shù)組合下T-Pin-SVM的表現(xiàn),其中τ∈{0.2,0.5,0.8},a∈{1.5,2,2.5}。每組參數(shù)下的性能評估結果均利用隨機訓練集訓練,對同一測試集重復測試50次得到,括號中數(shù)值為標準差,結果均乘以100展示。

ACC=(TP+TN)/(TP+FN+TN+FP)

式中:TP和TN表示真陽和真陰數(shù);FN和FP表示假陰和假陽數(shù)。

(1) 模擬數(shù)據(jù)1生成:定義任意樣本點(x1,x2)滿足方程:

對于模擬數(shù)據(jù),均隨機抽取500個樣本,其中30%作為測試集,其余70%作為調(diào)整集和訓練集用于C的選擇和模型訓練。另外,對于500個樣本,隨機選擇20%將其標簽以相等概率的更改為其他任意類別以增加噪聲。

2.1 截斷位置a的影響

T-Pin-SVM和Pin-SVM的主要區(qū)別在于T-Pin-SVM通過截斷位置a對損失進行截斷以限制錯誤分類樣本的無界損失,因此a影響了T-Pin-SVM概率估計的性能,另外a的取值也影響了落入損失函數(shù)水平區(qū)域樣本的數(shù)量,決定了T-Pin-SVM的稀疏性。表1顯示了T-Pin-SVM和Pin-SVM模型的概率估計結果。可以發(fā)現(xiàn),當固定相同的τ值,a的不同設定,5個數(shù)據(jù)集的大多數(shù)概率估計誤差指標(l1和l2)均會下降,這表明截斷會提升Pin-SVM的噪聲魯棒性,顯示了T-Pin-ball在概率估計中的良好表現(xiàn)。另外,在模擬數(shù)據(jù)和實際數(shù)據(jù)Pima中,T-Pin-SVM的SVs均小于Pin-SVM,且隨a減少而降低,稀疏性增強。同樣,在實際數(shù)據(jù)Vote和Ionosphere中,相比后兩種a的取值,a=1.5也會引起稀疏性增強。而在a=2和a=2.5參數(shù)條件下,T-Pin-SVM的稀疏性指標SVs均與Pin-SVM無差異,表明在這兩個數(shù)據(jù)集中,損失均小于2,截斷不起作用。

表1 不同參數(shù)組合下T-Pin-SVM和Pin-SVM模型的

續(xù)表1

2.2 不同SVM模型的性能評估

表2顯示了T-Pin-SVM、Pin-SVM和C-SVM在5個數(shù)據(jù)集中的概率估計對比結果?？梢园l(fā)現(xiàn),C-SVM在稀疏性指標SVs上的表現(xiàn)明顯優(yōu)于T-Pin-SVM,這是由于在C-SVM中,對于正確分類的點Hinge損失梯度為0,且在所有數(shù)據(jù)集中,正確分類的點顯然多于噪聲點,在T-Pin-SVM中,高于某一損失值的噪聲點(取決于a)才對應零梯度,而在Pin-SVM不存在零梯度。C-SVM這種強稀疏性也使得測試和調(diào)整參數(shù)階段較少的計算成本,T-Pin-SVM的計算成本也少于Pin-SVM。對于類別概率的估計,除Pima數(shù)據(jù)集外,T-Pin-SVM的結果均優(yōu)于其他兩個模型。

表2 T-Pin-SVM、Pin-SVM和C-SVM概率估計性能對比

3 結 語

針對SVM在多類別概率估計中存在的噪聲敏感問題,本文提出了一種截斷的Pinball損失,討論了它的噪聲魯棒性和稀疏性,并證明了基于該損失的T-Pin-SVM具有Fisher一致性。另外,為降低求解復雜度和計算成本,本文將K類別概率估計任務劃分為K(K-1)個二分類任務,利用Fisher一致性得到二分類概率估計后,再利用耦合公式實現(xiàn)了多類別概率估計。對于截斷Pinball損失導致的非凸問題,本文應用了DC算法求解。模擬數(shù)據(jù)和實際數(shù)據(jù)表明,相比于C-SVM、Pin-SVM,本文所提出的T-Pin-SVM可以降低概率估計的誤差,提高分類準確性,并且相對于無邊界的Pinball損失,它的稀疏性更強。

另外,類不平衡對SVM也有較大影響,進一步的研究可以結合類不平衡提高SVM概率估計準確性。