基于支持向量機的增量學習算法

摘要：分析了支持向量的性質和增量學習過程，提出了一種新的增量學習算法，舍棄了對最終分類無用的樣本，在保證測試精度的同時減少了訓練時間。最后的數值實驗和應用實例說明該算法是可行、有效的。

關鍵詞： 結構風險最小化; 支持向量; 增量學習

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2007)08－0048－02

支持向量機（support vector machine，SVM）由Vapnik及其合作者發明，在1992年計算學習理論會議上進入機器學習領域之后，便受到了廣泛關注。它建立在結構風險最小化原則基礎之上，具有很強的學習能力和泛化性能，能夠較好地解決小樣本、高維數、非線性、局部極小等問題，可以有效地進行分類、回歸、密度估計等。由于這些優點，其得到了全面深入的發展，現已成為機器學習和數據挖掘領域的標準工具。

增量學習技術（incremental learning technique）是一種得到廣泛應用的智能化數據挖掘與知識發現技術。其思想是當樣本逐步積累時，學習精度也要隨之提高。與傳統學習技術相比，增量學習技術可以充分利用歷史學習的結果，顯著節省后繼訓練時間。一種機器學習方法是否具有良好的增量學習功能已經成為評價其性能優劣的重要標準之一。經典的支持向量機理論與增量式學習并不具備直接的相容性。但是支持向量機訓練所得的支持向量能夠完全反映分類超平面的信息，而支持向量通常只占訓練樣本很小一部份，這對支持向量機增量學習算法的構建具有重要意義。

1支持向量機基本理論

支持向量機的理論最初來自對數據分類問題的處理。對于數據分類問題，如果采用通用的神經網絡方法來實現，其機理可以簡單地描述為：系統隨機產生一個超平面并移動它，直到訓練集中屬于不同分類的點正好位于平面的不同側面。這種處理機制決定了用神經網絡方法進行數據分類，最終獲得的分割平面將相當靠近訓練集中的點，而在絕大多數情況下，這并不是一個最優解。為此，SVM考慮尋找一個滿足分類要求的分割平面，并使訓練集中的點距離該分割平面盡可能地遠，即尋找一個分割平面，使其兩側的空白區域最大。

如果分類問題是非線性的，則采用一種稱為核函數（kernel function）的方法，使輸入空間映射到高維核函數特征空間，將非線性問題轉換為該空間中的線性分類問題。根據泛函理論，特征空間中對偶問題和得到的決策函數中的點積可以由輸入空間中的核函數來替換。 此時，決策函數為

2增量學習算法

當核函數類型及其參數確定后，支持向量集可以完全描述整個樣本集的分類特征，支持向量集和訓練樣本集之間的等價關系可以得到證明。但是隨著新樣本集的引入，打破了支持向量集和初始訓練樣本集的等價關系，使得原有的支持向量集已不能充分刻畫新訓練集的分類特征。

定理2表明，KKT條件比分類函數的分類判斷更合理，分類錯誤是樣本違反KKT條件的特定情況。只有違背KKT條件的樣本，才會影響增量學習后的支持向量集。因此，新增樣本可以分為違背KKT條件的樣本和滿足KKT條件的樣本兩部分。后者由于包含的信息已經被原來分類器所反映，可以不被學習。

3新的SVM增量學習算法

4實驗結果及分析

在上面研究的基礎上，本文對包含3 483個手工標定的文檔樣本，使用新的SVM增量學習算法進行電子文本的自動分類實驗。實驗中分別選取樣本空間中527個文檔作為測試樣本集，763個文檔作為初始訓練樣本集，并將剩余的文檔隨機分為五組，構成五個增量訓練樣本集。

從上面實驗可以看出，與傳統的SVM增量學習算法相比，新的SVM增量學習算法在不降低訓練精度的同時，顯著提高了學習速度。

5結束語

本文基于支持向量機的特性，研究了支持向量機的增量學習方法，并在此基礎上提出了使用ＫＫＴ條件進行增量學習的算法。實驗結果表明，這種學習方法在精確度和時間消耗上均優于傳統的SVM增量學習算法。

本文算法在訓練時只涉及全體樣本中的一小部分，但是那些沒有參加訓練的樣本仍然需要被存儲，占用計算機的內存，其中有一些樣本自始至終都沒有參加訓練。如何徹底放棄這一部分樣本，減少訓練所占用的空間是今后進一步研究的方向。 

參考文獻：

［1］VAPNIK V.The nature of statistical learning theory[M].New York:SpringerVerlag，1995.

[2］VAPNIK V， LEVIN E， CUN Y L. Measuring the VCdimension of a learning machine[J]. Neural Computation， 1994，6(5)：851－876.

[3］汪西莉，劉芳，焦李成.基于大規模數據的支持矢量機的訓練和分類[J].西安電子科技大學學報：自然科學版，2002，29（1）：123－127.

[4］焦李成，屈炳云，周偉達.一種基于支撐矢量機的多用戶檢測算法[J].電子學報，2002，30(10):1549－1551.[5］張學工.關于統計學習理論與支持向量機[J].自動化學報，2000，26（1）：31－42.

[6］曾文華，馬健.一種新的支持向量機增量學習算法[J].廈門大學學報：自然科學版，2002，41（6）：687－691.

[7］周偉達，張莉，焦李成.支撐矢量機推廣能力分析[J].電子學報，2001，29（5）：590－594.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”