基于選擇性抽樣的SVM增量學(xué)習(xí)算法的泛化性能研究

(1.湖北大學(xué) 計算機(jī)與信息工程學(xué)院，武漢 430062; 2.武漢晴川學(xué)院 計算機(jī)科學(xué)學(xué)院，武漢 430204)

0 引言

基于支持向量機(jī)(support vector machine,SVM)的分類算法[1]，不僅在解決非線性、小樣本、高維模式識別和克服“維數(shù)災(zāi)難”等問題上中表現(xiàn)出了特有的優(yōu)勢，而且還具有堅實(shí)的統(tǒng)計學(xué)習(xí)理論基礎(chǔ)[2-3]，簡潔的數(shù)學(xué)模型以及良好的泛化性能。因此，SVM被廣泛應(yīng)用到時間序列預(yù)測[4]、回歸分析[5]、人臉圖像識別等各個領(lǐng)域。盡管SVM理論基礎(chǔ)堅實(shí)，泛化性能良好，但經(jīng)典SVM算法是批量式處理，即訓(xùn)練樣本一次性被輸入到計算機(jī)內(nèi)存中，所以在處理大規(guī)模數(shù)據(jù)時會面臨內(nèi)存限制[6]以及學(xué)習(xí)效率低等問題。因此具有增量學(xué)習(xí)功能的數(shù)據(jù)分類技術(shù)應(yīng)運(yùn)而生，Syed等人[7]最早提出增量學(xué)習(xí)，其解決問題的核心在于每一次隨機(jī)選取算法能夠處理的數(shù)據(jù)量進(jìn)行訓(xùn)練，留下支持向量，再加入新的訓(xùn)練樣本繼續(xù)訓(xùn)練，依此過程訓(xùn)練學(xué)習(xí)。近年來，孔銳等人[8]提出一種新的SVM增量學(xué)習(xí)算法，該算法首先選擇可能成為支持向量的邊界向量，以達(dá)到減少訓(xùn)練的樣本數(shù)量。Li等人[9]提出基于超平面距離的支持向量機(jī)增量學(xué)習(xí)算法，采用Hyperplane-Distance方法提取樣本，選取最有可能成為支持向量的樣本構(gòu)成邊緣向量集以提高訓(xùn)練速度。

上述增量學(xué)習(xí)算法都是基于樣本是獨(dú)立同分布的假設(shè)，該假設(shè)無論在理論上，還是實(shí)際應(yīng)用中都是非常強(qiáng)的，因現(xiàn)實(shí)機(jī)器學(xué)習(xí)[10]中不服從獨(dú)立同分布的數(shù)據(jù)很是廣泛,所以為非獨(dú)立同分布的數(shù)據(jù)更適用于機(jī)器學(xué)習(xí)，減弱獨(dú)立同分布的假設(shè)得到了相關(guān)學(xué)者的關(guān)注，Zou等人[11]證明了具有一致遍歷馬爾可夫鏈樣本的ERM算法是一致的,且一致遍歷馬爾可夫鏈在SVM中也得到了應(yīng)用，如Xu等人[12]證明了SVM泛化性能馬氏抽樣要優(yōu)于隨機(jī)抽樣。針對樣本是獨(dú)立同分布的假設(shè)在實(shí)際應(yīng)用中相對牽強(qiáng)，且獨(dú)立隨機(jī)抽樣的時效普遍偏低，數(shù)據(jù)存在非全局性等缺點(diǎn)，提出一種新的SVM增量學(xué)習(xí)算法。該算法利用馬氏抽樣選取具有一致遍歷馬爾可夫鏈性質(zhì)的訓(xùn)練樣本集，研究增量學(xué)習(xí)的特性，并與基于隨機(jī)抽樣的SVM增量學(xué)習(xí)算法和文獻(xiàn)[15]提出的增量學(xué)習(xí)算法做出比較。分別從分類錯誤率、支持向量個數(shù)和抽樣與訓(xùn)練總時間三個方面對比增量學(xué)習(xí)算法性能，選用基準(zhǔn)數(shù)據(jù)集作為樣本數(shù)據(jù)，經(jīng)實(shí)驗(yàn)表明，基于選擇性抽樣的SVM增量學(xué)習(xí)算法泛化性能更好。

1 相關(guān)知識

針對SVM增量學(xué)習(xí)所涉及到的概念以及一致遍歷馬爾可夫鏈等內(nèi)容，本節(jié)將給予介紹以及給出相關(guān)的定義。

1.1 支持向量機(jī)

基于SVM的二分類器，是在給定的空間下，尋找能夠分割兩類樣本且具有最大間隔的超平面。設(shè)帶有類別標(biāo)記的輸入模式集X?Rn為二分類數(shù)據(jù)集，類別標(biāo)簽為Y={+1,-1}，輸入集的每一個數(shù)據(jù)點(diǎn)，都有一個類別標(biāo)簽與之對應(yīng)即X→Y，從中取大小為l的樣本作為原始空間訓(xùn)練集:S={s1=(x1,y1),s2=(x2,y2),…,sl=(xl,yl)}，其中xi∈X,yi∈Y,i=1,2,…,l。SVM目標(biāo)是求解可以分割兩類樣本點(diǎn)的超平面wx+b=0的最優(yōu)解，將求解問題可以歸納為式(1)二次規(guī)劃問題：

(1)

其中:C正則化參數(shù)，ε為松弛變量。

借助Lagrange乘子法，轉(zhuǎn)化為對偶問題：

(2)

只需求解式(2)即可獲取最優(yōu)分類面，若原始空間中求取的分類面效果不佳，依據(jù)泛函理論知識。存在一種滿足Mercer核條件的核函數(shù)：K(xi,xj)=<Φ(xi)·Φ(xj)>，可通過線性映射Φ:Rn→H，x→Φ(x)將輸入空間映射到Hilber空間中，則相應(yīng)的決策函數(shù)為：

其中非零的拉格朗日乘子(αi≠0)對應(yīng)的樣本點(diǎn)稱作為支持向量。支持向量個數(shù)越少，則表明SVM的分類器越稀疏。

1.2 增量學(xué)習(xí)

傳統(tǒng)的增量學(xué)習(xí)算法樣本的選擇是隨機(jī)抽樣，選取的樣本之間不具備關(guān)聯(lián)性。在第2節(jié)將介紹一種基于選擇性抽樣的SVM增量學(xué)習(xí)算法。

1.3 一致遍歷馬爾可夫鏈

實(shí)際應(yīng)用中很多模型產(chǎn)生的樣本在本質(zhì)上是自然涌現(xiàn)的而非獨(dú)立同分布，如市場預(yù)測，語音識別等，這些數(shù)據(jù)并不符合機(jī)器學(xué)習(xí)中數(shù)據(jù)獨(dú)立同分布的假設(shè)。所以通過減弱樣本是獨(dú)立同分布的情形，利用一致遍歷馬爾可夫鏈模型進(jìn)行算法泛化性能研究。如下給出一致遍歷馬爾可夫鏈的概念：

定義(Z,E)為一個可測空間，則一個隨機(jī)變量序列{Zt}t≥1以及一系列轉(zhuǎn)移概率測度Pn(S|zi),S∈E,zi∈Z共同構(gòu)成一個馬爾可夫鏈，假定：

Pn(S|zi):=P{Zn+i∈S|Zj,j

記Pn(S|zi)為n步轉(zhuǎn)移概率：從初始狀態(tài)為zi的時刻i開始，經(jīng)過n步迭代后狀態(tài)為zn+i屬于集合S的概率。若轉(zhuǎn)移概率不依賴于在時刻i之前的Zj狀態(tài)集，稱具有馬爾可夫性質(zhì)，即:Pn(S|zi):=P{Zn+i∈S|Zi=zi}，故馬爾可夫鏈特性：若給定當(dāng)前狀態(tài)，則馬爾可夫鏈的將來和過去狀態(tài)都是獨(dú)立的。

假設(shè)給定測度空間(Z,E)上的兩個測度為μ1和μ2，將測度μ1和μ2的全變差定義為：

2 基于選擇性抽樣的增量學(xué)習(xí)算法

基于選擇性抽樣的SVM增量學(xué)習(xí)算法中利用馬氏抽樣選取增量樣本集，馬氏抽樣通過定義每一次抽樣的轉(zhuǎn)移概率來選擇樣本數(shù)據(jù)，構(gòu)建出具有馬爾可夫性質(zhì)的樣本集。記DTR為訓(xùn)練集，DTE為測試集，T為增量學(xué)習(xí)次數(shù)，N為每次增量樣本的大小，損失函數(shù)[13]定義為l(f,z)=(1-f(x)y)+?；谶x擇性抽樣的SVM增量學(xué)習(xí)算法步驟如下:

算法1：SVM增量學(xué)習(xí)算法

輸入：DTR，DTE，T，N，q。

4)令k=2。

5)令u=1。

8)若P=1,y*yu=-1或P<1,則依轉(zhuǎn)移概率P接受樣本z*；若P=1、y*yu=1則依轉(zhuǎn)移概率P′=min{1,e-y*fk-1/e-yufk-1}接受樣本z*；若有連續(xù)n個候選樣本z*不能被接受，此時依轉(zhuǎn)移概率P″=min{1,qP}接受樣本z*，如果z*不能被接受，返回步驟7)，否則令u=u+1,zu=z*。

10)若k≤T，返回步驟5)，否則，獲取抽樣與訓(xùn)練總時間，支持向量數(shù)目，并使用分類模型fT計

算在測試集DTE中錯分率。

輸出：錯分率、支持向量個數(shù)、抽樣與訓(xùn)練總時間

評注1：算法1利用數(shù)據(jù)子集分類模型的均值來定義起始轉(zhuǎn)移概率，可以避免因初始轉(zhuǎn)移概率的定義而導(dǎo)致算法可能會具有的較大波動性。為快速生成馬氏樣本集，根據(jù)文獻(xiàn)[12]的研究，在算法1中引進(jìn)了兩個參數(shù)n和q，其中n為候選樣本連續(xù)被拒絕的次數(shù)，q為解決當(dāng)損失函數(shù)l(f,z)值較小時，在以概率接收候選樣本時需要花費(fèi)大量的時間而引入的常數(shù)。

3 數(shù)值實(shí)驗(yàn)

本章將對實(shí)驗(yàn)選取的數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)分析做出闡述，為讓實(shí)驗(yàn)更具有效性與說服力，在實(shí)驗(yàn)中，對于同一個數(shù)據(jù)集，均在數(shù)據(jù)子集劃分、增量次數(shù)、每次增量數(shù)據(jù)量完全相同的情況下進(jìn)行實(shí)驗(yàn)。

在實(shí)驗(yàn)結(jié)果比較中，記“iid”為基于隨機(jī)抽樣的SVM增量學(xué)習(xí)算法，“Markov”為基于選擇性抽樣的SVM增量學(xué)習(xí)算法。

3.1 實(shí)驗(yàn)參數(shù)及數(shù)據(jù)集

實(shí)驗(yàn)選取Matlab2016a作為編程軟件,在CPU為Inter(R)Core(TM)i7-7500 @2.7 GHz，RAM為8 G的環(huán)境中編程(因計算機(jī)內(nèi)存限制，其中數(shù)據(jù)集Skin在CPU為Intel(R)Xeon(R) E5-1603-v4@2.8 GHz，RAM為32 G的環(huán)境中實(shí)驗(yàn))。處理高維數(shù)據(jù)時映射核函數(shù)選用高斯徑向基函數(shù)[14]，算法通過10倍交叉驗(yàn)證從候選集[-0.01,-0.1,0,1,10,100, 1000,10000]中選取正則化參數(shù)C=1000。為更好證明算法的泛化能力，實(shí)驗(yàn)分別選取3維至300維的二分類數(shù)據(jù)集進(jìn)行算法的泛化能力研究。實(shí)驗(yàn)所選取的9個數(shù)據(jù)集如表1所示。

表1 9個實(shí)驗(yàn)數(shù)據(jù)集

3.2 與隨機(jī)抽樣增量學(xué)習(xí)算法對比

為讓實(shí)驗(yàn)更具說服力，實(shí)驗(yàn)中對于同一個數(shù)據(jù)集分別進(jìn)行三次增量實(shí)驗(yàn)，即T值分別取10,20,30次，且每次增量樣本會依據(jù)算法步驟1劃分出的數(shù)據(jù)子集規(guī)模而定義較大的值，即N值。

實(shí)驗(yàn)結(jié)果如表2所示，其中表的第二列為“數(shù)字/數(shù)字”,如數(shù)據(jù)集Skin中的10/8000，表示數(shù)據(jù)集Skin增量10次(10個子集)，每次增量的樣本數(shù)為8000；20/5000則表示數(shù)據(jù)集Skin增量20次(20個子集)，每次增量的樣本數(shù)為5000；為充分的表明基于選擇性抽樣的SVM增量學(xué)習(xí)算法的泛化能力，實(shí)驗(yàn)分別從錯誤分類率，支持向量個數(shù)，抽樣與訓(xùn)練總時間三個方面對比基于選擇性抽樣的SVM增量學(xué)習(xí)算法和基于隨機(jī)抽樣的SVM增量學(xué)習(xí)算法。

由表3的實(shí)驗(yàn)結(jié)果可以看出，基于選擇性抽樣的SVM的增量學(xué)習(xí)算法無論在T與N取何值時錯誤分類率均低于基于隨機(jī)抽樣的SVM增量學(xué)習(xí)算法，且能在保證錯分率低的同時，能大幅度減少支持向量個數(shù)和抽樣與訓(xùn)練總時間。因?yàn)榛谶x擇性抽樣的SVM的增量學(xué)習(xí)算法中增量樣本非隨機(jī)選取，而是通過計算樣本之間的轉(zhuǎn)移概率判斷是否接

表2 數(shù)值實(shí)驗(yàn)結(jié)果

受樣本，所以通過馬氏抽樣選取的樣本之間具有關(guān)聯(lián)性，可以很大程度的避開噪聲等因素對數(shù)據(jù)的影響。

為更好地展示實(shí)驗(yàn)效果，圖1給出了基于選擇性抽樣的SVM的增量學(xué)習(xí)算法和基于隨機(jī)抽樣的SVM增量學(xué)習(xí)算法的實(shí)驗(yàn)數(shù)據(jù)集部分錯分率詳細(xì)對比圖、支持向量對比圖、抽樣與訓(xùn)練總時間對比圖。

從圖1的(a)與(d)中可以看出，基于選擇性抽樣的SVM增量學(xué)習(xí)算法，在增量樣本相同的情況下，隨著增量次數(shù)的增加，錯分率總體呈下降趨勢，且錯分率逐漸趨于平穩(wěn)，而基于隨機(jī)抽樣的SVM增量學(xué)習(xí)算法，波動較大。

從圖1的(b)與(e)中可以看出，無論增量次數(shù)T和增量樣本量N取何值，基于選擇性抽樣的SVM增量學(xué)習(xí)算法比基于隨機(jī)抽樣SVM增量學(xué)習(xí)算法的支持向量數(shù)目要少，即分類模型更稀疏。

從圖1的(c)與(f)中可以看出無論增量次數(shù)T和增量樣本量N取何值，基于選擇性抽樣的SVM增量學(xué)習(xí)算法學(xué)習(xí)效率有很大程度的提升。

圖1 實(shí)驗(yàn)結(jié)果詳細(xì)對比圖

3.3 與文獻(xiàn)[15]中算法對比

1)算法對比：自Syed等人[7]提出增量學(xué)習(xí)算法以來，以其優(yōu)異的算法性能得到了許多學(xué)者的青睞，同時很多改進(jìn)的增量學(xué)習(xí)算法也相繼被提出，雖然在算法性能上有一定程度的優(yōu)化，但基本都是建立在樣本是獨(dú)立同分布的假設(shè)情形，本質(zhì)并沒有改變。

Xu等人[15]提出的增量學(xué)習(xí)算法，其核心也是利用馬氏抽樣選取樣本進(jìn)行增量學(xué)習(xí)(X-ISVM)?；谶x擇性抽樣的SVM增量學(xué)習(xí)算法(M-ISVM)與之最大的區(qū)別有以下幾點(diǎn)：

(1)X-ISVM算法在訓(xùn)練集上沒有進(jìn)行子集劃分，在整體訓(xùn)練集進(jìn)行樣本選取。M-ISVM算法則是在每一個數(shù)據(jù)子集上選取樣本。

(2)X-ISVM算法馬氏抽樣的初始轉(zhuǎn)移概率是依據(jù)第一次隨機(jī)抽樣的分類模型定義，M-ISVM算法是通過合成2→T的數(shù)據(jù)子集的分類模型來定義馬氏抽樣的初始轉(zhuǎn)移概率。

(3)文獻(xiàn)[15]實(shí)驗(yàn)中數(shù)據(jù)集都以T=10,N=500(T=20,N=300;T=20,N=400;T=30,N=200)為基準(zhǔn)進(jìn)行增量學(xué)習(xí)，增量樣本數(shù)據(jù)量選取數(shù)據(jù)量較小，不具備說服力；M-ISVM算法則是根據(jù)數(shù)據(jù)子集規(guī)模的大小來定義N的值，且N值一般定義較大。

2)數(shù)值實(shí)驗(yàn)與結(jié)果：為更好地比較兩種算法的泛化能力，在基準(zhǔn)數(shù)據(jù)集下，對于每一個數(shù)據(jù)集分別進(jìn)行T=10,N=500(T=10N依據(jù)劃分的數(shù)據(jù)子集規(guī)模定義較大值)；T=20,N=300(T=20N依據(jù)數(shù)據(jù)子集規(guī)模定義較大值)的實(shí)驗(yàn),對于每個數(shù)據(jù)集實(shí)驗(yàn)重復(fù)5次，然后根據(jù)每次實(shí)驗(yàn)增量最后的分類模型求取五次實(shí)驗(yàn)的平均錯分率，平均支持向量和5次抽樣與訓(xùn)練的總時間(s)。

表3 T次(T=10)增量學(xué)習(xí)后實(shí)驗(yàn)結(jié)果對比

表4 T次(T=10)增量學(xué)習(xí)后實(shí)驗(yàn)結(jié)果對比

表5 T次(T=20)增量學(xué)習(xí)后實(shí)驗(yàn)結(jié)果對比

表6 T次(T=20)增量學(xué)習(xí)后實(shí)驗(yàn)結(jié)果對比

表3為在T=10,N=500時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xùn)練的總時間的實(shí)驗(yàn)數(shù)據(jù)；表5為在T=10N依據(jù)數(shù)據(jù)子集規(guī)模取值時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xùn)練的總時間的實(shí)驗(yàn)數(shù)據(jù)。

表5為在T=20,N=300時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xùn)練的總時間的實(shí)驗(yàn)數(shù)據(jù)；表6為在T=20N依據(jù)數(shù)據(jù)子集規(guī)模取值時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xùn)練的總時間的實(shí)驗(yàn)數(shù)據(jù)。

表中的第一列為“數(shù)據(jù)集名-數(shù)字”，如“Skin-500”表示從Skin數(shù)據(jù)集中每次增量500個訓(xùn)練樣本，即算法中N=500。

從表3～6中可以看出，M-ISVM算法，在增量次數(shù)相同的情況下，增量的樣本量無論大小，平均錯分率，平均支持向量，抽樣與訓(xùn)練總時間表現(xiàn)都優(yōu)于X-ISVM算法，且方差更低，說明算法穩(wěn)定性好。因?yàn)镸-ISVM算法在馬氏抽樣起始轉(zhuǎn)移概率的定義上利用了2→T的數(shù)據(jù)子集的分類模型，而X-ISVM算法只利用了第一次隨機(jī)抽樣的分類模型，在每次增量的數(shù)據(jù)上，M-ISVM算法分別從每一次數(shù)據(jù)子集中選取，而X-ISVM則在整體訓(xùn)練集中選取，所以M-ISVM算法能更好地兼顧全局性，很大程度上避免實(shí)驗(yàn)結(jié)果的偶然性。實(shí)驗(yàn)結(jié)果表明，M-ISVM算法的泛化性能優(yōu)于X-ISVM算法。

4 結(jié)束語

傳統(tǒng)的增量學(xué)習(xí)都是建立在樣本是獨(dú)立同分的假設(shè)情形下，樣本的選取都是基于獨(dú)立隨機(jī)抽樣，這種假設(shè)并不能完全符合實(shí)際環(huán)境中樣本的分布情況?；谶x擇性抽樣的SVM增量學(xué)習(xí)算法，通過減弱樣本是獨(dú)立同分布的假設(shè)情形，利用馬氏抽樣方式選取具有一致遍歷馬爾可夫鏈性質(zhì)的樣本進(jìn)行增量學(xué)習(xí)，文章中與基于隨機(jī)抽樣的SVM增量學(xué)習(xí)算法和文獻(xiàn)[15]提出的算法做出比較。實(shí)驗(yàn)結(jié)果表明，基于選擇性抽樣的SVM增量學(xué)習(xí)算法在SVM分類問題上泛化性能更好。