無偏置ν- SVM分類優(yōu)化問題研究

丁曉劍 趙銀亮

(西安交通大學(xué)電子與信息工程學(xué)院 西安 710049)

1 引言

C-SVM(Support Vector Machine)起源于文獻(xiàn)[1]提出的支持向量網(wǎng)絡(luò)(support vector networks)。在一般的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中，只需調(diào)節(jié)輸出向量和隱藏層連接的權(quán)重向量w就可以較好地?cái)M合訓(xùn)練樣本，而文獻(xiàn)[1]指出需要調(diào)節(jié)向量w和(b)才能得到最優(yōu)分類超平面，但在文中并沒有提到(b)存在的意義。Poggio等人[2]從核函數(shù)的正定理論分析得出如果核函數(shù)是正定的(positive definite)，在SVM優(yōu)化問題中是不需要(b)的，文獻(xiàn)[3]指出使用高斯核(gaussian kernel)等常用核函數(shù)的SVM優(yōu)化問題不需要(b)。Huang等人[4]提出了優(yōu)化極限學(xué)習(xí)機(jī)(Extreme Learning Machine, ELM)的分類方法，指出優(yōu)化極限學(xué)習(xí)機(jī)的模型和C-SVM是等價(jià)的，決策函數(shù)傾向于通過原點(diǎn)，即不需要(b)的存在。文獻(xiàn)[5]研究了(b)對(duì)C-SVM分類優(yōu)化問題泛化性能的影響，在實(shí)驗(yàn)中驗(yàn)證得到無(b)C-SVM優(yōu)化問題的泛化性能更好，對(duì)參數(shù)C不太敏感，計(jì)算代價(jià)更小等一系列性質(zhì)。雖然ν-SVM[6,7]與C-SVM的目標(biāo)優(yōu)化問題不同，約束條件也不同，但兩者得到的最優(yōu)分類超平面是等價(jià)的，即文獻(xiàn)[5]的結(jié)論應(yīng)該適用于ν -SVM。本文首先給出無(b)ν-SVM優(yōu)化問題的描述，然后給出了利用有效集方法求解無(b)ν-SVM優(yōu)化問題的子優(yōu)化問題求解方法，在標(biāo)準(zhǔn)數(shù)據(jù)集上的多個(gè)指標(biāo)的性能分析得到了理想的效果。

2 無(b)v-SVM優(yōu)化問題

給定一個(gè)含有m個(gè)樣本的訓(xùn)練樣本集{xi,，其中輸入為d維向量x∈Rd，輸出為y∈iiR。通常訓(xùn)練樣本集在輸入空間中是線性不可分的，需要引入映射函數(shù)φ(x)將xi映射到高維空間 φ(xi)中。訓(xùn)練無(b)ν-SVM分類問題等價(jià)于求解如下優(yōu)化問題：

引入拉格朗日函數(shù)：

其中 αi, βi, δ為非負(fù)拉格朗日乘子。

對(duì)L關(guān)于變量w,ξ,ρ求偏導(dǎo)數(shù)，下列條件都滿足時(shí)得到式(1)的最優(yōu)解：

將式(3)和式(4)代入拉格朗日函數(shù)L，可得無(b)ν-S VM 的對(duì)偶優(yōu)化問題：

2.1 Karush-Kuhn-Tucker條件

為了得到原始優(yōu)化問題式(1)的最優(yōu)解，需要推導(dǎo)出它的完整Karush-Kuhn-Tucker(KKT)條件：

初始可行性：

對(duì)偶可行性：

對(duì)偶與原問題的補(bǔ)條件：

由于f(x)為無(b)ν-SVM的決策函數(shù)，令fi為無(b)ν-SVM分類器對(duì)樣本xi預(yù)測(cè)的值，并有fi=由最優(yōu)解條件和補(bǔ)條件可得

如果 αi=0，由式(11)可知 ξi=0，由最優(yōu)解條件和δρ=0可知ρ=0，再由式(8)可知fi≥ ρ ，進(jìn)而有fi≥ 0。如果 αi=1/m，由式(10)可知fi?ρ+ξi=0，由最優(yōu)解條件和補(bǔ)條件δρ=0可知ρ=0，又由式(8)可知fi=?ξi≤ 0。如果0 ＜αi＜1/m，由補(bǔ)條件式(10)可知fi?ρ+ξi=0，由式(11)可知 ξi=0，再由式(8)可知fi=ρ≥ 0。綜上，式(3)的最優(yōu)解滿足下列條件：

3 優(yōu)化問題求解方法

文獻(xiàn)[8]利用有效集算法來求解C-SVM優(yōu)化問題，該有效集算法將C-SVM對(duì)偶優(yōu)化問題分解為一系列子優(yōu)化問題來求解，其主要計(jì)算代價(jià)是每次迭代過程中求解子優(yōu)化問題，是一種高效簡(jiǎn)便的算法。由于無(b)ν-SVM的對(duì)偶優(yōu)化問題都與C-SVM對(duì)偶優(yōu)化問題不同，文獻(xiàn)[8]中的有效集算法無法直接應(yīng)用，在本節(jié)將推導(dǎo)無(b)ν-SVM子優(yōu)化問題的求解方法。

式(8)為無(b)ν-SVM的對(duì)偶優(yōu)化問題，為方便推導(dǎo)求解，將式(8)寫成下面緊湊的形式：

其中H=KYYT∈RN×N,K為式(7)中對(duì)應(yīng)的核矩陣，

同樣由向量α0,αm的定義可知α0,αm元素的值是固定的，求解式(13)等價(jià)于求解下式：

其中Hww和Hwm為H的子矩陣，行和列相應(yīng)的集合Sm和Swork標(biāo)識(shí)。同理由于式(14)是對(duì)αwork求最小值，由αwork的定義可知αwork中分量的值都在區(qū)間(0,1/m)中，即約束0 ≤ αi≤ 1/m必然滿足，這樣式(14)就變?yōu)榈仁郊s束優(yōu)化問題：

其中δ=αwork,Q=Hww,c=Hwmαm,A=[1,… ,1]T∈Rn,n為αwork中元素的個(gè)數(shù)，t=ν?∑αm。

式(13)可以通過解條件問題的乘子法來求解，構(gòu)造拉格朗日函數(shù)：

令L1(δ,λ)對(duì)δ和λ的導(dǎo)數(shù)為零，得到線性方程組：

現(xiàn)已將無(b)ν-SVM子優(yōu)化問題轉(zhuǎn)化為與C-SVM 子優(yōu)化問題相同的形式。有效集算法利用2層循環(huán)來求解目標(biāo)優(yōu)化問題式(13)：外循環(huán)判斷α中邊界約束元素是否都滿足KKT條件式(12)，如果都滿足，算法終止。如果不滿足，則選取違反KKT條件的變量進(jìn)入內(nèi)循環(huán)求解；而內(nèi)循環(huán)目標(biāo)是求解子優(yōu)化問題式(15)，使得最優(yōu)解αwork滿足上下界約束。

4 實(shí)驗(yàn)與結(jié)果分析

為了研究(b)對(duì)ν-SVM分類性能的影響(本文僅討論兩類分類問題)，本文將用有效集算法對(duì)ν -SVM (nu-AS)和無(b) ν-SVM(nbnu-AS)進(jìn)行多個(gè)指標(biāo)的比較，算法是在 Pentium 4, 2.53 GHz,CPU, MATLAB 2007環(huán)境下實(shí)現(xiàn)，實(shí)驗(yàn)數(shù)據(jù)集分別來自UCI數(shù)據(jù)庫(kù)[9]，Statlog數(shù)據(jù)庫(kù)[10]，所有樣本的輸入都?xì)w一化到[0,1]之間。

4.1 參數(shù)設(shè)定

對(duì)于nu-AS算法和nbnu-AS算法性能比較使用高斯核(注：此處公式已作改動(dòng))作為核函數(shù)，需要合適的核參數(shù)和代價(jià)參數(shù)ν才能得到盡量好的分類性能。代價(jià)參數(shù)ν的選擇按照文獻(xiàn)[6]的選擇方法，10個(gè)參數(shù)ν值分別取：0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0。對(duì)高斯核，對(duì)于每個(gè)數(shù)據(jù)集選取15個(gè)γ值和10個(gè)ν值，共有150種參數(shù)對(duì)，并選擇性能最好的組合(ν, γ)，參照文獻(xiàn)[11]中的參數(shù)選擇方法，15個(gè)γ值分別取：0.001, 0.01, 0.1, 0.2, 0.4, 0.8, 1, 2, 5, 10, 20, 50, 100,1000, 10000。對(duì)于每個(gè)數(shù)據(jù)集采用50次測(cè)試，每次測(cè)試隨機(jī)訓(xùn)練樣本數(shù)目和測(cè)試樣本數(shù)目。實(shí)驗(yàn)指標(biāo)包括平均訓(xùn)練時(shí)間(ATT)，平均測(cè)試精度(ATA)，標(biāo)準(zhǔn)方差(DEV)和平均的支持向量數(shù)目(ASV)。

4.2 實(shí)驗(yàn)性能比較

表1是nu-AS和nbnu-AS算法的性能指標(biāo)比較。在13個(gè)數(shù)據(jù)集中，nbnu-AS算法在其中10個(gè)數(shù)據(jù)集上的平均測(cè)試精度要好，nu-AS算法在Monk’s Problem 1數(shù)據(jù)集上的平均測(cè)試精度要好，在另外兩個(gè)數(shù)據(jù)集上兩個(gè)算法的平均測(cè)試精度一致。兩個(gè)算法在所有數(shù)據(jù)集上的平均訓(xùn)練時(shí)間相差都不大。

表1 標(biāo)準(zhǔn)數(shù)據(jù)集上的性能比較

ν-S VM和無(b)ν-SVM的求解是將原始優(yōu)化問題轉(zhuǎn)化為對(duì)偶優(yōu)化問題來求解，由于對(duì)偶間隙的存在，對(duì)偶優(yōu)化問題的最優(yōu)解并非一定為原始優(yōu)化問題的最優(yōu)解。盡管無(b)ν-SVM在Monk’s Problem 1數(shù)據(jù)集上得到更小的函數(shù)值(見表2)，但是無(b)ν -SVM得測(cè)試精度仍然低于ν-SVM。

4.3 ν-SVM和無(b)ν-SVM優(yōu)化問題最優(yōu)解比較

由于ν-SVM優(yōu)化問題與無(b)ν-SVM優(yōu)化問題多出一個(gè)約束條件：TY=0α，從優(yōu)化問題的解空間上分析后者應(yīng)該能得到比前者更優(yōu)的解。本節(jié)從實(shí)驗(yàn)上分析該約束條件對(duì)優(yōu)化問題最優(yōu)解影響，利用有效集算法和最優(yōu)函數(shù)值指標(biāo)對(duì)兩個(gè)優(yōu)化問題進(jìn)行比較。為了使兩個(gè)目標(biāo)優(yōu)化問題相同(約束條件不同)，nu-AS和nbnu-AS的參數(shù)須設(shè)置一致(從而優(yōu)化問題中的核矩陣也相同)，在此將兩個(gè)算法的參數(shù)對(duì)都設(shè)為nu-AS的最優(yōu)參數(shù)對(duì)，表2為比較結(jié)果。在前10個(gè)數(shù)據(jù)集上，nu-AS算法在兩個(gè)核函數(shù)上都取得了更優(yōu)的解，而在后3個(gè)數(shù)據(jù)集上，兩個(gè)算法在兩個(gè)核函數(shù)上的最優(yōu)解都相同。設(shè)nu-AS算法的解空間為S1, nbnu-AS算法的解空間為S2，則有S1?S2。

表2 nu-AS和nbnu-AS算法的最優(yōu)函數(shù)值比較

4.4 參數(shù)敏感性分析

本節(jié)比較核參數(shù)和代價(jià)參數(shù)ν對(duì)算法測(cè)試精度的影響，實(shí)驗(yàn)數(shù)據(jù)選取Pwlinear數(shù)據(jù)集，高斯核的參數(shù)值按照4.1節(jié)選取。

從圖1和圖2可以看出，nu-AS在高斯核上的不同參數(shù)選取對(duì)于測(cè)試精度影響很大，而且沒有規(guī)律。nbnu-AS算法則對(duì)參數(shù)ν不太敏感，曲面比較光滑。在實(shí)際參數(shù)選取中，對(duì)于參數(shù)ν可以擴(kuò)大參數(shù)選取值的間隔，利用較少的參數(shù)值對(duì)就可以找到最優(yōu)測(cè)試精度。

圖1 nu-AS在高斯核上的測(cè)試精度

圖2 nbnu-AS在高斯核上的測(cè)試精度

5 結(jié)束語(yǔ)

由于ν-SVM引入了有實(shí)際意義的參數(shù)ν，在機(jī)器學(xué)習(xí)的各個(gè)領(lǐng)域中有廣泛的應(yīng)用和實(shí)際的指導(dǎo)意義。本文研究對(duì)比了ν-SVM和無(b)的ν-SVM優(yōu)化問題，從多個(gè)性能指標(biāo)的實(shí)驗(yàn)上分析得出無(b)的ν -SVM 的泛化性能要好于ν-SVM，在同等目標(biāo)優(yōu)化問題下ν-SVM只能得到無(b)的ν-SVM的次優(yōu)解，無(b)的ν-SVM對(duì)參數(shù)ν不太敏感，在較少的參數(shù)值對(duì)中就可以找到最佳的測(cè)試精度。

本文的工作適用于ν-SVM的改進(jìn)算法，可以將無(b)的ν-SVM應(yīng)用于現(xiàn)有的對(duì)ν-SVM進(jìn)行改進(jìn)的算法。在以后的研究工作中將無(b)的ν-SVM應(yīng)用于文本挖掘，圖像識(shí)別等實(shí)際領(lǐng)域中，進(jìn)一步驗(yàn)證無(b)的ν-SVM的有效性。

[1] Cortes C and Vapnik V. Support vector networks.Machine Learning, 1995, 20(3): 273-297.

[2] Poggio T, Mukherjee S, Rifkin R,et al.. “b”. (A.I. Memo No.2001-011, CBCL Memo 198, Artificial Intelligence Laboratory,Massachusetts Institute of Technology), 2001.

[3] Evgeniou T, Pontil M, and Poggio T. Regularization networks and support vector machines.Advances in Computational Mathematics, 2000, 13(1): 1-50.

[4] Huang G B, Ding X J, and Zhou H M. Optimization method based extreme learning machine for classification.Neurocomputing, 2010, 74(1/3): 155-163.

[5] 丁曉劍, 趙銀亮. b對(duì)支持向量機(jī)分類問題泛化性能的影響.自動(dòng)化學(xué)報(bào), 待發(fā)表.

[6] Sch?lkopf B, Smola A J, Williamson R, and Bartlett P L.New support vector algorithms.Neural Computation, 2000,12(5): 1207-1245.

[7] 王娜, 李霞. 基于類加權(quán)的雙ν支持向量機(jī). 電子與信息學(xué)報(bào),2007, 29(4): 859-862.Wang Na and Li Xia. A new dual ν support vector machine based on class-weighted.Journal of Electronics and Information Technology, 2007, 29(4): 859-862.

[8] Scheinberg K. An efficient implementation of an active set method for SVMs.Journal of Machine Learning Research,2006, 7(10): 2237-2257.

[9] Blake C L and Merz C J. UCI repository of machine learning databases. http://www.ics.uci.edu/～mlearn/MLRepository.html, Department of Information and Computer Sciences,University of California, Irvine, USA, 2010.

[10] Michie D, Spiegelhalter D J, and Taylor C C. UCI Machine Learning Repository: Statlog Data Set, available: http://archive.ics.uci.edu/ml/datasets/Statlog+(Landsat+Satellite),2010.

[11] Ghanty P, Paul S, and Pal N R. NEUROSVM: an architecture to reduce the effect of the choice of kernel on the performance of SVM.Journal of Machine Learning Research,2009, 10(3): 591-622.