兩階段不定核支持向量機*

史 娜，薛 暉+，汪云云

1.東南大學(xué) 計算機科學(xué)與工程學(xué)院，南京 211189

2.東南大學(xué) 計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室，南京 211189

3.南京郵電大學(xué) 計算機學(xué)院，南京 210023

1 引言

支持向量機（support vector machine，SVM）作為一種有效的分類技術(shù)，已經(jīng)在實際應(yīng)用中取得了非常好的效果。尤其在引入核技巧后，SVM 的性能進一步提高[1]。在經(jīng)典的核SVM（kernel SVM，KSVM）算法中，通常要求核矩陣正定，即核函數(shù)滿足Mercer定理。但是近年來，在計算機視覺和生物信息等領(lǐng)域，出現(xiàn)了越來越多的非正定度量手段[2-5]，例如：利用最長公共子序列，度量兩個基因序列相似性；利用BLAST 評分函數(shù)，度量兩個蛋白質(zhì)序列相似性；利用集合操作的交、并等，度量兩個事務(wù)的相似性；利用人類先驗知識，判斷兩個概念或者單詞之間的相似性；計算機視覺領(lǐng)域中的利用正切距離和形狀匹配等，度量兩個圖形的相似性。上述的度量手段往往導(dǎo)致核矩陣的不定，進而使得經(jīng)典的KSVM 算法無法對這些問題進行有效的求解[6-7]。針對上述問題，越來越多的學(xué)者對不定核支持向量機（indefinite kernel support vector machine，IKSVM）展開了廣泛的研究。目前IKSVM 的求解算法主要分為兩大類：（1）基于核矩陣修正的求解；（2）基于原始不定核矩陣的求解。第一類算法是將不定核矩陣修正為正定矩陣，從而使得經(jīng)典的KSVM 算法仍然適用。例如，將核矩陣的所有負特征值置零的“Clip”算法、將核矩陣的所有負特征值取絕對值的“Flip”算法、將核矩陣的特征值加上一個正常數(shù)以使得所有特征值大于零的“Shift”算法，以及將所有特征值取平方的“Squared”算法等[8]。除了上述將矩陣修正和KSVM 問題求解分開進行的做法外，另一種比較常見的做法就是將矩陣修正和經(jīng)典KSVM 分類進行聯(lián)合求解。Chen 等人[9]將原始的不定核矩陣視作一個未知正定矩陣的帶噪聲形式，并將該正定矩陣的擬合和經(jīng)典KSVM 分類聯(lián)合起來作為最終的優(yōu)化目標(biāo)。Gu 等人[10]認為不定核矩陣具有低秩的正定近似，從而將核矩陣的低秩正定近似求解和經(jīng)典KSVM 問題求解聯(lián)系起來，并進行迭代優(yōu)化。然而，上述基于核矩陣的正定近似進行IKSVM 問題求解的算法，會使得不定核矩陣的一些有用信息丟失，因此在實際應(yīng)用中效果并不理想[11-12]。第二類算法直接利用不定核矩陣進行求解，從而解決矩陣的修正過程帶來的信息丟失問題。Alabdulmohsin 等人[7]將核矩陣K的每一行看作樣本的特征，從而將IKSVM 問題轉(zhuǎn)化成普通的線性規(guī)劃問題進行求解。Hochreiter 等人[13]將KKT的行看作特征，從而可以利用現(xiàn)有的凸優(yōu)化算法進行求解。Loosli等人[12]通過探究再生核Kre?n 空間（reproducing kernel Kre?n space，RKKS）和再生核Hilbert 空間（reproducing kernel Hilbert spaces，RKHS）之間的關(guān)系，提出可以將IKSVM的解與KSVM 的解通過一個映射矩陣聯(lián)系起來，從而達到IKSVM問題的間接求解。Xu等人[14]從IKSVM優(yōu)化的主問題出發(fā)，提出可以將IKSVM 問題刻畫成一個凸差規(guī)劃問題，從而能夠利用現(xiàn)有相關(guān)的凸差算法進行求解。Oglic 等人[15]將IKSVM 問題轉(zhuǎn)化成一個約束特征值問題，從而可以利用特征值方程進行問題的求解。然而，上述的IKSVM 算法，均不能較好地解決高維數(shù)據(jù)所帶來的信息冗余和樣本稀疏問題。因此，在實際處理高維數(shù)據(jù)時，通常會采用主成分分析（principal component analysis，PCA）作為數(shù)據(jù)的預(yù)處理方式，然后再進行IKSVM 的處理。但是，這種處理方式也有其局限性，即處理的數(shù)據(jù)必須是樣本的向量表示形式，若給定度量矩陣的結(jié)構(gòu)化數(shù)據(jù)集，該種處理方式將無法應(yīng)用。

為了解決高維數(shù)據(jù)所帶來的信息冗余和樣本稀疏等問題，本文基于Loosli 等人[12]對IKSVM 穩(wěn)定化問題的定義，從理論上證明了IKSVM 問題的求解等價為IKPCA（indefinite kernel principal component analysis）和SVM 的依次執(zhí)行，并提出了一種求解IKSVM問題的新型學(xué)習(xí)框架：TP-IKSVM（two-phase indefinite kernel support vector machine）。該學(xué)習(xí)框架將IKSVM 問題的求解分為兩個階段：第一階段應(yīng)用IKPCA 技術(shù)進行非線性降維以提取數(shù)據(jù)的主要信息，同時緩解信息冗余和樣本稀疏等問題[16]；第二階段在降維后的特征空間進行SVM，從而進一步挖掘低維空間中判別信息。另外，由于本學(xué)習(xí)框架不涉及樣本的原始向量表示形式，因此TP-IKSVM 的應(yīng)用更加靈活。在真實數(shù)據(jù)集上的實驗表明，TP-IKSVM在分類性能上優(yōu)于現(xiàn)有的IKSVM 算法。

2 相關(guān)工作

2.1 Kre?n 空間和RKKS

Kre?n 空間K 是由兩個Hilbert 空間(H+,H-)張成的內(nèi)積空間，并且滿足[12，15]：

（1）?f∈K,f=f++f-

（2）?f,g∈K,

其中，f+，g+∈H+，f-，g-∈H-。

如果這里的H+、H-均為RKHS，那么Kre?n 空間K 就是一個RKKS，可以看出RKKS 是Kre?n 空間的特例。假設(shè)實值對稱函數(shù)k可以對應(yīng)到一個RKKS，那么滿足k=k+-k-，其中k+和k-是可以分別對應(yīng)到H+和H-的實值函數(shù)。

為后續(xù)描述的方便，這里將Kre?n 空間限定為有限維空間，并用pE表示（有限維的Kre?n 空間又稱偽歐空間，用pE表示）。具體地，pE可以表示為兩個歐式空間的直和R(p,q)=Rp⊕Rq，其中Rp和Rq均為Hilbert 空間，相應(yīng)的內(nèi)積操作為。引入J=diag(1p′-1q)，則pE空間中的內(nèi)積可以進一步表示為，其中運算符“*”代表pE空間的內(nèi)積操作，J代表了pE空間的維度特性，并且滿足J=JT=J-1[17]。

2.2 IKPCA

IKPCA[16]是一種非線性降維技術(shù)，旨在RKKS 中尋找一組投影方向，使得樣本投影點之間的差異最大化。

假設(shè)樣本在RKKS 中可以表示為Φ={φ(x1),φ(x2),…,φ(xn)}，其中φ為映射函數(shù)；特征均值為μ=。設(shè)Φ已經(jīng)中心化，即φ(xi)=φ(xi)-μ。定義RKKS 中全散度矩陣Sκ：

其中，S|κ|=ΦΦT為與RKKS 相應(yīng)的RKHS 中的全散度矩陣。

因此，IKPCA 的目標(biāo)函數(shù)可表示為：

最后，對K進行特征分解，得到式（3）的最優(yōu)解：

3 TP-IKSVM

為了引出求解IKSVM 問題的新型學(xué)習(xí)框架TPIKSVM，本章首先對IKSVM 問題進行形式化的定義，然后基于該定義給出TP-IKSVM 的證明。

3.1 IKSVM

Loosli 等人[12]的研究表明，IKSVM 的求解可以表示成RKKS 中的穩(wěn)定化問題，即：

將式（6）的極大化部分等價轉(zhuǎn)換為負的極小化問題，得到：

最后，將上述約束最小化問題轉(zhuǎn)換成等價的無約束問題，得到：

上式記為IKSVM 問題的主問題P-IKSVM。

根據(jù)表示定理，得到相應(yīng)的對偶問題，并記為DIKSVM：

其中，K是不定核矩陣，Ki代表核矩陣的第i行，K+、K-是根據(jù)核函數(shù)k+、k-所得到的正定核矩陣，并且滿足k=k+-k-，K=K+-K-。

3.2 TP-IKSVM 的證明

TP-IKSVM 學(xué)習(xí)框架是一種解決IKSVM 問題的新型求解思路。TP-IKSVM 將IKSVM 的求解拆分為IKPCA 和線性SVM 兩個階段。其中第一階段的IKPCA 作為一種經(jīng)典的降維技術(shù)首先將原始的高維樣本數(shù)據(jù)投影到一個低維空間，從而緩解由于樣本維度與樣本個數(shù)比值較小產(chǎn)生的樣本稀疏問題，然后在降維后的空間中進行第二階段SVM，能夠更好地挖掘低維數(shù)據(jù)的分類信息。為了說明TP-IKSVM學(xué)習(xí)框架的合理性，引入下面的定理1。

定理1 設(shè)α為原始pE空間中D-IKSVM 問題的解，為樣本經(jīng)過IKPCA 降維后pE1空間中的SVM問題的解，則。

證明 記經(jīng)過IKPCA 降維后，特征空間由原始的pE∈(p,q) 變?yōu)閜E1∈(p1,q1)，樣本特征由Φ(xi) 變?yōu)椋矗?/p>

在pE1空間進行SVM，可以表示為如下優(yōu)化問題：

將式（12）等價變換為無約束的優(yōu)化問題：

通過定理1，可以發(fā)現(xiàn)分兩階段求解的TPIKSVM 和直接求解IKSVM 等價。但是，考慮率到pE1空間的未知，因此求解相對復(fù)雜，為了簡化第二階段問題的求解，引入命題1。

證明 在pE1空間對應(yīng)的Hilbert 空間中進行SVM，等價于下述問題的求解：

根據(jù)Hilbert空間的性質(zhì)可知：

由命題1 可知TP-IKSVM 第二階段的pE1空間SVM 可以簡化為對應(yīng)Hilbert空間中的SVM。

結(jié)合定理1 和命題1，可以看出IKSVM 的求解本質(zhì)是在IKPCA 降維后的空間中進行SVM。另外，通過IKPCA 階段的降維，可以很好地處理高維數(shù)據(jù)中的信息冗余，并且也一定程度地緩解了樣本稀疏的問題。基于該結(jié)論，設(shè)計出求解IKSVM 問題的新型學(xué)習(xí)框架TP-IKSVM，具體算法的描述如下：

輸入：K，不定核矩陣；Y，類別標(biāo)簽；p1+q1，IKPCA 所要降到的維度；λ，規(guī)則化參數(shù)；k(·,x*)，所有訓(xùn)練樣本與測試樣本x*核相似性度量。

輸出：y*，x*的預(yù)測標(biāo)簽。

（1）利用式（4）計算Q，并保留對應(yīng)特征值前(p1+q1)大的特征向量。

（4）計算x*的低維映射特征。

4 實驗及結(jié)果分析

本章通過在兩種數(shù)據(jù)類型向量形式的數(shù)據(jù)、結(jié)構(gòu)化的數(shù)據(jù)上的實驗，檢驗所提TP-IKSVM 算法的性能。實驗選擇如下主流IKSVM 方法作為對比算法：

（1）1-normIKSVM[7]：通過特征空間的嵌入，將IKSVM 問題轉(zhuǎn)化成線性規(guī)劃問題進行求解。

（2）ESVM[12]：首先求解相應(yīng)的正定核支持向量機問題，然后通過映射矩陣P將KSVM 的解映射到IKSVM 問題的解。

（3）IKSVM-DC[14]：通過非凸優(yōu)化算法——凸差規(guī)劃進行求解。

（4）Kre?n[15]：將IKSVM 的學(xué)習(xí)問題轉(zhuǎn)化成帶約束的特征值問題進行求解。

4.1 向量形式的數(shù)據(jù)集上的實驗

本組實驗采用6個向量形式的高維數(shù)據(jù)集（http://featureselection.asu.edu/datasets.php）:Leukemia、ALLAML、Colon、Prostate_GE、TOX_171 和CLL_SUB_111_2，數(shù)據(jù)集的詳細統(tǒng)計信息如表1 所示。

Table 1 Description of 6 vectorial datasets表1 6 個向量形式的數(shù)據(jù)集描述

由于本組實驗數(shù)據(jù)集是向量形式的樣本，因此這里需要手動構(gòu)造不定核矩陣。這里選用最常用的“sigmoid”核作為相似性度量核函數(shù)：

其中，核參數(shù)η的設(shè)置參照文獻[15]的選取方式，即:

本組的TOX_171 數(shù)據(jù)集是一個四分類問題，而IKSVM 本身是處理二分類問題的技術(shù)，因此本節(jié)將類別標(biāo)簽為1、2 的樣本作為正例樣本，標(biāo)簽為3、4 的作為負例樣本。相關(guān)參數(shù)的取值范圍設(shè)置為C∈{20,21,…,26},λ∈{2-6,2-5,…,26}。將數(shù)據(jù)集隨機劃分為數(shù)量大致相等的訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集，并且進行10 輪的隨機劃分，實驗結(jié)果取自10 輪實驗的平均值。實驗結(jié)果見表2。

由表2 可知，本文算法在本組數(shù)據(jù)集上的分類精度性能均優(yōu)于其他對比算法，并且算法執(zhí)行速度和1-normIKSVM、Kre?n 大致相當(dāng)。本組實驗的數(shù)據(jù)集樣本數(shù)量較少而特征維度較大，并且包含較多冗余信息，使得現(xiàn)有IKSVM 算法的性能表現(xiàn)不佳。而TP-IKSVM 通過兩階段的學(xué)習(xí)框架，能夠充分發(fā)揮IKPCA 在處理高維數(shù)據(jù)方面的優(yōu)勢，使得數(shù)據(jù)的冗余信息得到削弱。同時，經(jīng)過IKPCA 的操作使得樣本點分布在一個較低維的空間，使得樣本稀疏問題得到了一定程度的緩解，從而使得本文算法的性能得到進一步提升。

4.2 結(jié)構(gòu)化的數(shù)據(jù)集上的實驗

本節(jié)實驗數(shù)據(jù)集是由代爾夫特理工大學(xué)模式識別實驗提供的給定不定性度量矩陣[18]的結(jié)構(gòu)化數(shù)據(jù)，并且本組數(shù)據(jù)集主要涉及生物信息和計算機視覺等領(lǐng)域的高維特征度量問題。數(shù)據(jù)集的詳細統(tǒng)計信息見表3。

Table 2 Performance comparison of vectorial datasets表2 向量形式的數(shù)據(jù)集性能對比

Table 3 Description of 7 structured datasets表3 7 個結(jié)構(gòu)化數(shù)據(jù)集描述

通過表3 的描述可知，本組數(shù)據(jù)集包含多分類問題，因此需要將多分類問題改為二分類問題，本文參照文獻[14]的設(shè)置方式，即選取一半的類別標(biāo)簽作為正類，余下類別標(biāo)簽作為負類。比如將DelftGestures數(shù)據(jù)集中標(biāo)簽為1～10 的樣本作為正類，11～20 的作為負類。其余相關(guān)參數(shù)設(shè)置同4.1 節(jié)。將核矩陣隨機選取一半的行及相應(yīng)的列所組成的子矩陣作為訓(xùn)練數(shù)據(jù)集，用余下列與之前選取的行所組成的子矩陣構(gòu)成測試數(shù)據(jù)集，并將數(shù)據(jù)集隨機進行10 輪劃分，并取10 輪實驗結(jié)果平均值作為最終的結(jié)果度量。實驗結(jié)果見表4。

從表4 可以看出，TP-IKSVM 算法的分類精度優(yōu)于所有對比算法，Kre?n 算法次優(yōu)，并且本文算法的運行速度明顯高于IKSVM-DC。在Zongker、Catcortex 和Chickenpieces數(shù)據(jù)集上的分類精度分別提高了4.5%、4.1%和14.9%左右。分析可知Zongker、Catcortex和Chickenpieces等數(shù)據(jù)集所提供的數(shù)據(jù)可能包含較多的冗余或者噪聲信息，使得普通的IKSVM 算法性能受限，而TP-IKSVM 通過將IKSVM 問題拆分為IKPCA 和SVM 兩個階段進行，使得信息冗余問題得到緩解，進一步使模型精度得到改善。同時，本組實驗也驗證了本文所提模型不僅在處理高維數(shù)據(jù)本身的冗余信息時有效，在處理由核的引入而導(dǎo)致的潛在高維特征空間中的信息冗余和樣本稀疏問題仍然有效。

Table 4 Performance comparison of structured datasets表4 結(jié)構(gòu)化數(shù)據(jù)集性能對比

5 結(jié)束語

鑒于現(xiàn)有IKSVM 算法無法較好地處理高維數(shù)據(jù)的研究現(xiàn)狀，本文首先基于RKKS 中對IKSVM 的穩(wěn)定化問題的定義，證明了IKSVM 問題的求解可以等價為IKPCA 和SVM 的依次執(zhí)行，并且進一步提出了一種求解IKSVM 問題的新型學(xué)習(xí)框架TP-IKSVM。TP-IKSVM 將IKSVM 問題的求解分解為IKPCA 和SVM 兩個階段。TP-IKSVM 不僅發(fā)揮了SVM 在分類問題上良好泛化性能的優(yōu)勢，而且結(jié)合了IKPCA在處理高維數(shù)據(jù)方面的降低冗余信息和緩解樣本稀疏的優(yōu)勢。最后，真實數(shù)據(jù)集上的實驗驗證了本文所提算法能夠有效改善IKSVM 的實際泛化性能。