適于大規(guī)模數(shù)據(jù)集的塊增量學(xué)習(xí)算法：ＢＩＳＶＭ

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

關(guān)鍵詞：支持向量機(jī);塊增量算法；大規(guī)模訓(xùn)練

中圖分類號(hào)：TP18; TP301．6文獻(xiàn)標(biāo)志碼：A

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

支持向量機(jī)是最新的基于結(jié)構(gòu)化風(fēng)險(xiǎn)最小化原則的統(tǒng)計(jì)學(xué)習(xí)方法[1]。高精度的泛化性能使得SVM在文本分類、圖像檢索、入侵檢測(cè)等領(lǐng)域均取得了成功應(yīng)用。然而，SVM方法在求解過程中需要解凸二次規(guī)劃問題，難以在大規(guī)模訓(xùn)練數(shù)據(jù)條件下有效地學(xué)習(xí)和訓(xùn)練。文獻(xiàn)[2]提出的SMO算法能夠?qū)VM的整體二次優(yōu)化問題轉(zhuǎn)換成一系列小規(guī)模的二次優(yōu)化問題(優(yōu)化變量數(shù)目為2)，解決了由于核矩陣緩存而造成的存儲(chǔ)空間限制。然而，該方法存在收斂速率慢、效率低等不足[3]。

1支持向量機(jī)的基本問題

5結(jié)束語

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

參考文獻(xiàn)：

［1］VAPNIK V N.統(tǒng)計(jì)學(xué)習(xí)理論的本質(zhì)［M］.張學(xué)工，譯.北京:清華大學(xué)出版社，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.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”