基于驅動錯誤準則的SVM增量學習研究
2012-04-29 00:00:00文波單甘霖段修生
計算技術與自動化 2012年3期
摘要：增量學習廣泛運用于人工智能、模式識別等諸多領域，是解決系統在訓練初期樣本量少而隨時間推移性能降低的有效方法。本文針對經典支持向量機當訓練樣本數量多而運算速度較慢的缺點，在分析支持向量機的基礎上，提出基于驅動錯誤準則的增量學習方法，實驗結果表明，該算法不僅能保證學習機器的精度和良好的推廣能力，而且算法的學習速度比經典的SVM算法快，可以進行增量學習。
關鍵詞：機器學習；驅動錯誤準則；SVM；增量學習
中圖分類號：TP391 文獻標識碼：A
Research of Incremental Learning Algorithm Based on Drive Error Criterion
WEN Bo， SHAN Ganlin， DUAN Xiusheng
（Dept. of Optical and Electronic Engineering， Ordnance Engineering College Shijiazhuang Hebei050003， China）
Abstract：Incremental learning is widely used in artificial intelligence， pattern recognition and other fields. It is an effective method to solve the problem that the efficiency of the system declines in the process of studying training samples which is of a small number in the beginning. For the disadvantage of the classical support vector machine getting slower when the number of training samples gets larger， this thesis proposes an incremental learning algorithm based on Drive error criterion. The experimental results show that this algorithm not only guarantees the precision and good generalization ability of the learning machine， but also faster than the classic SVM algorithm. Therefore， it can be used in incremental learning.
Key words：machine learning； drive error criterion； SVM； incremental learning
1引言
支持向量機（SVM）[1]是Vapnik等人在統計學習理論的基礎上提出的一種普適學習機模型，具有強大的非線性處理能力和良好的推廣能力，廣泛應用于人工智能、模式識別等諸多領域，目前，SVM越來越受到廣泛的重視，形成了國際上的研究熱潮[2—3]。機器學習作為人工智能領域的基本問題，許多學習系統在學習初期所能獲得的樣本量較少，隨著時間的推移與樣本的不斷累積，系統的工作效率降低，這時系統需納入新增樣本進行增量學習提升系統的性能，標準的支持向量機沒有增量學習的能力，但其定義的支持向量具有良好的增量學習效果。因此研究有效的支持向量機增量學習方法具有重要的意義[1]。
Syed[4]對樣本集的支持向量進行了分析，提出了一種簡單支持向量機增量學習算法。在該算法中，增量訓練由SV樣本組成，再訓練只需要進行一次即可完成，所有的非SV樣本點都拋棄。這樣減少了計算復雜度，但是忽略了歷史樣本集的非SV最終可能成為支持向量的問題。趙耀紅[5]等人提出將違背Karush.Kuhn.Tucker（KKT）條件的樣本和SV集一起訓練的新算法，更能體現樣本的分布狀態對學習結果的影響。該算法分別對樣本和新增樣本訓練得到分類器T1、T2和支持向量集SV1、SV2，在歷史樣本中找到違背T2的KKT條件的樣本，加入到SV1、SV2一起訓練得到最終分類器。該算法雖然比Syed的分類精度提高了2個百分點左右，但訓練時間沒有明顯減少，需要占用大量內存空間，文獻[6—8]中也分別介紹了幾種SVM增量學習算法，文獻[9]對SVM增量學習的研究進行了總結和分析。通過總結與歸納，這些算法都存在一個共同的特征即需要對過多的歷史樣本進行學習，需要大量的存儲空間，直接影響到后繼增量學習的效率。如何從歷史樣本集和新增樣本集中提取少而有價值的樣本，而非全部樣本進行訓練，是個值得研究的問題。
本文在上述研究的基礎上，提出了基于錯誤驅動的增量學習算法。實驗結果表明本文的算法不僅保證了學習機器的精度，而且顯著地提高了學習的速度，具有良好的推廣能力。
2問題的描述
2.1支持向量機及KKT條件[10]
支持向量機最早由線性情況下的分類問題而來，利用支持向量機分類的目的就是要尋找最優超平面，最優超平面就是最大間隔超平面，即在將兩類樣本正確分類的同時，使得分類間隔最大，如圖1所示。
圖1最優分類超平面示意圖
通過求解凸半正定二次規劃
max W（α）=∑li=1αi—12∑li，j=1yiyjαiαjK（xi，xj）
s.t. C≥αi≥0，∑li=1yiαi=0（1）
計算技術與自動化2012年9月
第31卷第3期文波等：基于驅動錯誤準則的SVM增量學習研究
其中，K（xi，xj）為核函數。
可以得到SVM分類器的決策函數
f（x，α）=sign∑support vectoryiα0iK（xi，xj）+b（2）
在分類學習中只有那些是支持向量的樣本才對最優超平面和決策函數有貢獻，即支持向量集能夠充分描述整個訓練樣本集的特征，對它的劃分等價于對整個樣本集的劃分。大多數情況下，支持向量只占訓練樣本集的很少一部分，因此可以使用支持向量集取代訓練樣本集進行學習，在不影響分類精度的同時降低訓練時間及存儲空間。
對于上述問題，α是拉格朗日乘子，當且僅當對每一個x都滿足KKT條件時，α=[α1，…，αi]才是上述規劃的最優解
αi=0→ynf（xn）>10<αi 即 αi=0→f（xn）>1或f（xn）<—10<αi f（x）=0為分類面，f（x）=±1為分類間隔的邊界。α=0對應的樣本分布在SVM分類間隔外，0<α 文獻[10]中的證明表明，新增訓練樣本違背KKT條件的充要條件為新增樣本位于ynf（xn）區域中。 2.2最小驅動錯誤準則 一個誤分類測度的最簡單的形式，是對兩類問題進行分類的Bayes判別形式，其誤分類測度[11]可定義為： d（x）=P（C2|x）—P（C1|x） （5） 這里，P（C2|x）（i=1，2）是假設已知的后驗概率。上式給出了將屬于類1的觀測樣本誤分類為類2時的可能性，其最優決策邊界是方程d（x）=0的解。對于未知分布的多類情況（N>2），并不能象上面的這種兩類Bayes判別那樣定義一個誤分類測度。Amari定義了一種誤分類測度為： dk（x）=∑x∈Sk1mk[gi（x；Λ）—gk（x；Λ）]（6） 其中， Sk={i|gi（x；Λ）>gk（x；Λ）}是混淆類集，mk為Sk中的混淆個數。由于Sk是不固定的，它隨著參數集Λ以及樣本x的變化而變化，所以上式對Λ是不連續的，不能求導，故不適合梯度運算。有很多方法可以定義連續的誤分類測度，其中一種選擇為： dk（x）=—gk（x；Λ）+ [1N—1∑j，η≠kgi（x；Λ）η]1η（7） 上式右邊第二項是所有其它競爭類似然度的幾何平均值。參數η可被看成為一個調整其它競爭類對整個判別函數貢獻的權系數。在搜索分類器參數Λ的過程中，通過變化η值可以找到許多潛在的分類，一個極端的情況是當η→ SymboleB@ 時，上式右邊第二項中一個最大競爭類的判別函數將起主導作用，即 η→ SymboleB@ 時， [1N—1∑j，η≠kgj（x；Λ）η]1η=max j，η≠kgj（x；Λ） （8） 誤分類測度變為： dk（x）=—gk（x；Λ）+gj（x；Λ）（9） 其中Ci是除Ck外，所有其它類中具有最大判別值所代表的類，這是因為（N—1）1/ SymboleB@ 1。顯然，在上面這種情況下， dk（x）>0隱含著為誤分類， dk（x）≤0為正確分類，這樣，決策規則就變為一個標量值的判定問題了。 3算法的設計及實驗分析 3.1算法的設計 設初始訓練樣本集合A={x1，x2，…，xM}，其中每個xm（m=1，2，…，M）是一個K維向量，并且屬于N個類Ci（i=1，2，…，N）中的某一類。對通常包含一個參數集和一個決策規則的分類器來說，最小驅動錯誤分類器設計的任務就是：基于給定的初始訓練樣本集A，找出分類器的參數集Λ以及相關的決策規則，使得誤分類任何樣本xm（m=1，2，…，M）的概率最小，一般地，誤分類的概率用誤識率來近似。如果假設存在與誤分類有關的懲罰或代價，則這種分類器設計的目標就變為：找出合適的分類器參數集Λ和相關的決策規則使得期望的代價最小。 算法如下： 1） 初始化參數Λ，置t=1選擇歷史樣本集A和新增樣本集It，確定最小錯誤分類準則集B。訓練B得到初始支持向量集SV0和決策函數f0； 2） 如果，It=，算法終止；否則轉（3）； 3） 尋找It中違反決策函數ft—1的KKT條件的樣本，確定集合Ivt； 4） 如果Ivt=，置SVt=SVt—1，ft=ft—1，t=t+1，轉（2）；否則轉（5）； 5） 對T=SVt—1∪Ivt進行增量學習得到新的決策函數ft支持向量集SVt，置t=t+1，轉（2）。 3.2實驗結果與分析 3.2.1不同核函數類型對結果的影響 分別采用RBF、Linear、Ploy核函數訓練SVM，對UCI數據庫中的數據集進行分類實驗。實驗時，利用數據集中大約1/3的樣本進行訓練，其余樣本用來對SVM分類器進行分類性能測試，測試結果如表1所示。 表1不同核函數時的分類結果 數據 RBF Linear Poly Breastcancer 0.9765 0.9756 0.9775 Echocardiogram 0.9345 0.8953 0.9052 Dermatology 0.9756 0.9543 0.9669 Wine 0.9392 0.8716 0.8716 Zoo 0.9348 0.9348 0.9348 試驗結果顯示，核函數的類型對SVM分類性能有一定影響；總體來看，選擇RBF核函數訓練得到SVM往往能取得較好的泛化能力和分類性能。 3.2.2本文增量學習算法（DRSVM）與SMO算法比較 在經典的優化算法中，SMO算法[12]的性能較好，分別使用UCI標準數據庫中的Breastcancer數據集與在某電路板上的采集的故障數據集進行實驗。 1）Breastcancer數據集，共有 699 個樣本，樣本維數為 11，所用訓練樣本數為 370，測試樣本數為 329。 2）某電路板上的故障數據當中的每一分量都服從Gauss分布，共有800個樣本，取訓練樣本為450，測試樣本數為350，其中正例樣樣本維數為 7 維，樣本類別數為 4。 為確保實驗結果的精確性，實驗采用平均法—同樣條件下運行10次，取平均值作為測試結果。實驗中時間均以秒（s）為單位，分類精度以%為單位。采用徑向基核函數，C=10，γ=0.4。 表2和表3給出了實驗結果，表中的符號含義如下：N初始代表初始樣本個數，N增量代表增量樣本個數，t訓練代表訓練時間，ACR代表平均分類正確率， DRSVM代表本文的增量算法，SMO代表文獻[12]中的增量算法。 表2Breastcancer 數據集實驗結果 N初始 N增量 DRSVM SMO t訓練 ACR t訓練 ACR 100 50 1.79 97.7 2.40 97.5 50 100 1.83 97.9 4.03 98.2 110 80 2.23 98.0 4.26 97.5 110 100 2.30 97.1 4.50 97.0 120 40 2.40 98.1 3.66 98.2 130 90 2.85 97.9 4.95 97.7 表3電路板故障數據集實驗結果 N初始 N增量 DRSVM SMO t訓練 ACR t訓練 ACR 50 100 13.25 96.9 26.7 96.8 150 100 29.7 98.0 57.6 97.4 200 50 12.1 97.3 23.0 96.0 200 200 14.5 96.3 34.3 97.0 400 100 25.4 95.7 42.9 96.1 300 200 22.75 97.5 44.5 97.1 從上面實驗可以看出，本文的DRSVM與SMO相比，本文算法不僅能保證學習機器的精度，而且算法的學習速度有顯著的提高適合于大規模訓練樣本的增量學習。 4結束語 本文基于支持向量機的特性，研究了支持向量機的增量學習方法，并在此基礎上提出了基于驅動錯誤準則的增量學習算法。實驗結果表明，該算法不僅能保證學習機器的精度和良好的推廣能力，而且算法的學習速度比經典的SVM算法快，可以進行增量學習。 參考文獻 [1]VAPNIK V.The nature of statistical learning theory[M ].New York：SpringerPress， 1995. [2]ZHU H B，CAI Y. Text categorization based on active learning support vector machines [J]. Computer Engineering and Application，2009，45（2）：134—136. [3]Mu Xinguo， Hao Wenning， Zhao Enlai. An incremental LSSVM learning algorithm ILSSVM[C]. 2011 International Conference on EBusiness and EGovernment （ICEE）.2011，314—317. [4]SYED N A，LIU H，SUNG K K.Incremental learning with support vector machines[C].Proc Int Joint Conf on Artificial Intelligenee，1999. [5]趙耀紅，王快妮，鐘萍，等.快速支持向量機增量學習算法[J]. 計算機工程與設計，2010，1（6）：161—163，171. [6]徐海龍，王曉丹，史朝輝，等.一種基于距離比值的支持向量機增量訓練算法[J].空軍工程大學學報，2008，9（4）：29—33. [7]白冬嬰，王曉丹，馬飛. 支持向量機增量學習方法及應用[J].航空計算技術，2007，37（4）：23—26. [8]申曉勇，雷英杰等. 一種SVM增量學習淘汰算法[J].計算機工程與應用，2007，43（6）：171—173. [9]李祥納，艾青，秦玉平，等.支持向量機增量學習算法綜述[J].渤海大學學報，2007，9（4）：187—189. [10]周偉達，張莉，焦李成.支撐向量機推廣能力分析[J].電子學報，2001，29（5） ：590—594. [11]韓紀慶，基于最小分類錯誤準則的判別學習方法[J] .計算機應用，2001，27（2）：1—3，12. [12]PLATT J.Fast Training of Support Vector MachinesUsing Sequential Minimal Optimization[A].Advancesin Kernel MethodsSupport Vector Learning[C].Cambridge，MA：MIT Press，1999：185—208.
