適于大規模數據集的塊增量學習算法：ＢＩＳＶＭ

摘要：對支持向量機的大規模訓練問題進行了深入研究，提出一種類似SMO的塊增量算法。該算法利用increase和decrease兩個過程依次對每個輸入數據塊進行學習，避免了傳統支持向量機學習算法在大規模數據集情況下急劇增大的計算開銷。理論分析表明新算法能夠收斂到近似最優解。基于KDD數據集的實驗結果表明，該算法能夠獲得接近線性的訓練速率，且泛化性能和支持向量數目與LIBSVM方法的結果接近。

關鍵詞：支持向量機;塊增量算法；大規模訓練

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

文章編號：1001－3695(2008)01－0098－03

支持向量機是最新的基于結構化風險最小化原則的統計學習方法[1]。高精度的泛化性能使得SVM在文本分類、圖像檢索、入侵檢測等領域均取得了成功應用。然而，SVM方法在求解過程中需要解凸二次規劃問題，難以在大規模訓練數據條件下有效地學習和訓練。文獻[2]提出的SMO算法能夠將SVM的整體二次優化問題轉換成一系列小規模的二次優化問題(優化變量數目為2)，解決了由于核矩陣緩存而造成的存儲空間限制。然而，該方法存在收斂速率慢、效率低等不足[3]。

1支持向量機的基本問題

5結束語

本文提出一種用于訓練支持向量機的塊增量訓練算法，有效解決了其在大規模數據情況下的訓練困難。理論分析表明，算法的increase和decrease過程能夠有效地優化訓練樣本塊中的τ違反對，并收斂到支持向量機的近似最優解。實驗結果表明BISVM算法能夠獲得線性于問題規模的訓練速率，而且測試精度和支持向量數目非常接近LIBSVM的值。同時，LIBSVM采用的啟發式的shrinking和核caching策略也可以應用到BISVM算法的實現中，能夠進一步提升算法的訓練速度。

參考文獻：

［1］VAPNIK V N.統計學習理論的本質［M］.張學工，譯.北京:清華大學出版社，2000.

［2］PLATT J C.Fast training of support vector machines using sequential minimal optimization［C］//SCHOLKOPF B，BURGES C，SMOLA A.Advances in kernel methods: support vector machines.Cambridge:MIT Press，1998.

［3］CAO L J，KEERTHI S S，ONG C J，et al.Parallel sequential minimal optimization for the training of support vector machines［J］.IEEE Trans on Neural Network，2006，17(4):1039 1049.

［4］KEERTHI S S，SHEVADE S K，BHATTACHARYYA C，et al.Improvements to Platt’s SMO algorithm for SVM classifyier design［J］.Neural Computation，2001，13(3):637－649.

［5］LIN C J.Asymptotic convergence of an SMO algorithm without any assumptions［J］. IEEE Trans on Neural Networks，2002，13(1):248－250.

［6］KEERTHI S S，GILBERT E G.Convergence of a generalized SMO algorithm for SVM classifier design［J］.Machine Learning，2002，46(1/3):351－360.

［7］KDD cup 1999 data[EB/OL].(1999).http://kdd.ics.uci.edu/databases/ kddcup99/kddcup99.htmlUTH.

［8］TSANG I W，KWOK J T，CHEUNG P M.Core vector machines:fast SVM training on very large data sets［J］.Journal of Machine Lear ning Research，2005，6:363－392.

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