一種基于KKT條件和殼向量的SVM增量學(xué)習(xí)算法

茅嫣蕾,魏　赟,賈　佳

(1.上海理工大學(xué) 光電信息與計算機工程學(xué)院,上海　200093;2.上海生物信息技術(shù)研究中心,上海　201202)

?

一種基于KKT條件和殼向量的SVM增量學(xué)習(xí)算法

茅嫣蕾1,2,魏赟1,賈佳2

(1.上海理工大學(xué) 光電信息與計算機工程學(xué)院,上海200093;2.上海生物信息技術(shù)研究中心,上海201202)

摘要針對傳統(tǒng)支持向量機(SVM)增量算法,在學(xué)習(xí)過程中因基于局部最優(yōu)解而可能舍棄含隱性信息的非支持向量樣本,以及對于新增樣本需全部進行訓(xùn)練的缺點,文中提出一種基于KKT條件和殼向量的SVM增量學(xué)習(xí)算法。該方法利用殼向量的特性保留了訓(xùn)練樣本集中可能含隱性信息的非支持向量,并只將違反KKT條件的增量樣本加入新的訓(xùn)練集,從而提高運算效率。通過對公共數(shù)據(jù)集Abalone和 Balance Scale的實驗表明,新算法在屬性列數(shù)較多的數(shù)據(jù)集上分類效果更明顯。

關(guān)鍵詞SVM;增量學(xué)習(xí);KKT條件;殼向量

支持向量機(Support Vector Machines,SVM)是由Vapnik等人提出的一種有監(jiān)督的機器學(xué)習(xí)算法。其基于結(jié)構(gòu)風(fēng)險最小化原則和統(tǒng)計學(xué)中的VC維理論,在解決非線性和高維問題時表現(xiàn)出良好的特性。近年來在文本分類[1]、目標(biāo)識別[2]、時間序列的預(yù)測[3]等領(lǐng)域得到廣泛應(yīng)用。與傳統(tǒng)的學(xué)習(xí)相比,增量學(xué)習(xí)在加入增量樣本進行新的訓(xùn)練過程中充分利用歷史訓(xùn)練結(jié)果,減少了訓(xùn)練時間同時又降低了存儲空間[4]。

基于SVM的增量學(xué)習(xí)概念最早是由Syed提出的,在文獻[5]中提出了一種分塊增量學(xué)習(xí)SVM算法,該算法的基本思想是在每次增量學(xué)習(xí)后保留支持向量(Support Vector,SV),舍棄非支持向量,并將本次支持向量集與新增樣本作為下一次學(xué)習(xí)的訓(xùn)練樣本。……