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

0 引言

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

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

1 相關(guān)知識

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

1.1 支持向量機

基于SVM的二分類器，是在給定的空間下，尋找能夠分割兩類樣本且具有最大間隔的超平面。設(shè)帶有類別標記的輸入模式集X?Rn為二分類數(shù)據(jù)集，類別標簽為Y={+1,-1}，輸入集的每一個數(shù)據(jù)點，都有一個類別標簽與之對應(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目標是求解可以分割兩類樣本點的超平面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)的樣本點稱作為支持向量。支持向量個數(shù)越少，則表明SVM的分類器越稀疏。

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

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

1.3 一致遍歷馬爾可夫鏈

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

定義(Z,E)為一個可測空間，則一個隨機變量序列{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)都是獨立的。

假設(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ù)文獻[12]的研究，在算法1中引進了兩個參數(shù)n和q，其中n為候選樣本連續(xù)被拒絕的次數(shù)，q為解決當(dāng)損失函數(shù)l(f,z)值較小時，在以概率接收候選樣本時需要花費大量的時間而引入的常數(shù)。

3 數(shù)值實驗

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

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

3.1 實驗參數(shù)及數(shù)據(jù)集

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

表1 9個實驗數(shù)據(jù)集

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

為讓實驗更具說服力，實驗中對于同一個數(shù)據(jù)集分別進行三次增量實驗，即T值分別取10,20,30次，且每次增量樣本會依據(jù)算法步驟1劃分出的數(shù)據(jù)子集規(guī)模而定義較大的值，即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ù)，抽樣與訓(xùn)練總時間三個方面對比基于選擇性抽樣的SVM增量學(xué)習(xí)算法和基于隨機抽樣的SVM增量學(xué)習(xí)算法。

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

表2 數(shù)值實驗結(jié)果

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

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

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

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

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

圖1 實驗結(jié)果詳細對比圖

3.3 與文獻[15]中算法對比

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

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

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

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

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

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

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

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

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

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

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

表5為在T=20,N=300時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xùn)練的總時間的實驗數(shù)據(jù)；表6為在T=20N依據(jù)數(shù)據(jù)子集規(guī)模取值時X-ISVM算法和M-ISVM算法的平均錯分率、方差、平均支持向量和5次抽樣與訓(xù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)定性好。因為M-ISVM算法在馬氏抽樣起始轉(zhuǎn)移概率的定義上利用了2→T的數(shù)據(jù)子集的分類模型，而X-ISVM算法只利用了第一次隨機抽樣的分類模型，在每次增量的數(shù)據(jù)上，M-ISVM算法分別從每一次數(shù)據(jù)子集中選取，而X-ISVM則在整體訓(xùn)練集中選取，所以M-ISVM算法能更好地兼顧全局性，很大程度上避免實驗結(jié)果的偶然性。實驗結(jié)果表明，M-ISVM算法的泛化性能優(yōu)于X-ISVM算法。

4 結(jié)束語

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