基于選擇性抽樣的SVM增量學習算法的泛化性能研究

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

0 引言

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

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

1 相關知識

針對SVM增量學習所涉及到的概念以及一致遍歷馬爾可夫鏈等內容，本節將給予介紹以及給出相關的定義。

1.1 支持向量機

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

(1)

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

借助Lagrange乘子法，轉化為對偶問題：

(2)

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

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

1.2 增量學習

傳統的增量學習算法樣本的選擇是隨機抽樣，選取的樣本之間不具備關聯性。在第2節將介紹一種基于選擇性抽樣的SVM增量學習算法。

1.3 一致遍歷馬爾可夫鏈

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

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

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

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

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

2 基于選擇性抽樣的增量學習算法

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

算法1：SVM增量學習算法

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

4)令k=2。

5)令u=1。

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

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

算在測試集DTE中錯分率。

輸出：錯分率、支持向量個數、抽樣與訓練總時間

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

3 數值實驗

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

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

3.1 實驗參數及數據集

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

表1 9個實驗數據集

3.2 與隨機抽樣增量學習算法對比

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

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

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

表2 數值實驗結果

受樣本，所以通過馬氏抽樣選取的樣本之間具有關聯性，可以很大程度的避開噪聲等因素對數據的影響。

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

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

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

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

圖1 實驗結果詳細對比圖

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

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

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

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

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

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

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

表3 T次(T=10)增量學習后實驗結果對比

表4 T次(T=10)增量學習后實驗結果對比

表5 T次(T=20)增量學習后實驗結果對比

表6 T次(T=20)增量學習后實驗結果對比

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

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

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

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

4 結束語

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