支持向量機(jī)訓(xùn)練算法綜述

支持向量機(jī)訓(xùn)練算法綜述

支持向量機(jī)最初由瓦普和其他人在1995年提出。這是一種基于vc維理論和結(jié)構(gòu)風(fēng)險最小化原則的研究機(jī)器。它在解決小樣本、非線性和高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢,并在一定程度上克服了“維數(shù)災(zāi)難”和“過學(xué)習(xí)”等傳統(tǒng)困難,再加上它具有堅實的理論基礎(chǔ),簡單明了的數(shù)學(xué)模型,使得支持向量機(jī)從提出以來受到廣泛的關(guān)注,并取得了長足的發(fā)展。支持向量機(jī)的訓(xùn)練算法歸結(jié)為求解一個受約束的QP問題。對于小規(guī)模的QP問題,它體現(xiàn)出了十分優(yōu)秀的學(xué)習(xí)能力,但當(dāng)將其應(yīng)用到大規(guī)模的QP問題時,就會表現(xiàn)出訓(xùn)練速度慢、算法復(fù)雜、效率低下等問題。現(xiàn)在主要的訓(xùn)練算法都是將原有大規(guī)模的QP問題分解成一系列小的QP問題。但是如何進(jìn)行分解以及選擇合適的工作集是這些算法面臨的主要問題,并且這也是各個算法優(yōu)劣的表現(xiàn)所在。另外一些算法主要是增加函數(shù)項、變量或系數(shù)等方法使公式變形,使其具有某一方面的優(yōu)勢,或者有一定應(yīng)用范圍。目前研究的大規(guī)模問題訓(xùn)練算法并不能夠徹底解決所面臨的問題,因此在原有算法上進(jìn)行合理的改進(jìn)或者研究新的訓(xùn)練算法勢在必行。本文對主要的訓(xùn)練算法以及SVM擴(kuò)展算法進(jìn)行了綜述,并在此基礎(chǔ)上對未來研究的方向進(jìn)行了展望。1svm的對偶優(yōu)化支持向量機(jī)最初是在模式識別中提出的。假定訓(xùn)練樣本集合(xi,yi),i=1,…,l,xi∈Rn,y∈{-1,+1},可以被超平面x·w+b=0無錯誤地分開,并且離超平面最近的向量離超平面的距離是最大的,則這個超平面稱為最優(yōu)超平面。而SVM的主要思想是通過某種事先選擇的非線性映射將輸入向量x映射到一個高維特征空間Z,并在這個空間中構(gòu)造最優(yōu)超平面。但是如何求解得到這個最優(yōu)超平面以及如何處理高維空間中經(jīng)常遇到的維數(shù)災(zāi)難問題?針對第一個問題,主要將訓(xùn)練SVM算法歸結(jié)成一個QP問題,并且該問題的解由下面的拉格朗日函數(shù)的鞍點給出:并且問題的解在鞍點處滿足對w和b的偏導(dǎo)為0,然后將該QP問題轉(zhuǎn)化為相應(yīng)的對偶問題即:解得決策函數(shù)為:從對偶表達(dá)式中,可以看出只有一部分αi>0,稱它對應(yīng)的訓(xùn)練點為支持向量。如何處理高維特征空間中維數(shù)災(zāi)難?研究發(fā)現(xiàn)在特征空間Z中構(gòu)造最優(yōu)超平面,并不需要以顯式形式來考慮特征空間,而只需要能夠計算支持向量與特征空間中向量的內(nèi)積,但是如何計算特征空間中的內(nèi)積?SVM不直接進(jìn)行計算該內(nèi)積,而是用滿足Mercer定理的核函數(shù)來代替,如下:式中,Υ(·)是輸入向量到特征空間的一個非線性映射。因此,只要將原空間中對偶問題表達(dá)式的內(nèi)積形式用核函數(shù)K(x·xj)代替,即是特征空間中對偶問題的表達(dá)形式。2svm算法的研究2.1工作集的改進(jìn)方法經(jīng)過上面的討論,我們知道QP問題的解僅依賴于與支持向量對應(yīng)的那些訓(xùn)練樣本點,但是當(dāng)訓(xùn)練樣本增大時,就會過多占用內(nèi)存,從而導(dǎo)致訓(xùn)練時間過長和效果不佳,因此設(shè)計適合于大量樣本的算法成為SVM研究中的重要內(nèi)容。這其中主要有:(1)chunking算法Boser和Vapnik首先提出的chunking算法的目標(biāo)是通過某種迭代方式逐步排除非支持向量,從而降低訓(xùn)練過程對存儲器容量的要求。具體的算法是將訓(xùn)練集分成若干個子集,然后任選一個子集,運(yùn)用標(biāo)準(zhǔn)的QP方法求解對偶問題,得到支持向量,保留支持向量對應(yīng)的樣本點,舍去其他的樣本點。然后用得到的決策函數(shù)去檢驗剩余的樣本,將最不滿足KKT條件的M個樣本與先前得到的支持向量組成新的一個塊,構(gòu)成新的子QP問題,直到滿足某一個停機(jī)準(zhǔn)則。如果在某一步中,不滿足KKT條件的樣本數(shù)不足M個,則將這些樣本全部加入到新的QP問題中。顯然,這種方法有利于降低問題的復(fù)雜程度,尤其是支持向量遠(yuǎn)遠(yuǎn)小于訓(xùn)練樣本時。然而,如果支持向量的數(shù)目本身就比較多,隨著算法迭代次數(shù)的增多,工作集樣本也會越來越大,算法依舊會變得十分復(fù)雜。(2)分解算法Osuna等人首先提出了分解方法,主要思想是將訓(xùn)練樣本分成工作集B和非工作集N,并保持大小不變。在解決每個子QP問題前,從B中移出一個樣本,然后再從N中移進(jìn)一個不滿足KKT條件的樣本,然后求解關(guān)于B的子QP問題。該算法的關(guān)鍵是工作集的選取一定要最優(yōu),但Osuna在工作集的選取中采用了隨機(jī)的方法,因此限制了算法的收斂速度。針對這個問題,Joachims系統(tǒng)地改進(jìn)了Osuna的方法,主要體現(xiàn)在工作集的選擇上。其基本思想是,如果存在不滿足KKT條件的樣本,利用最速下降法,在最速下降方向中存在q個樣本,然后以這q個樣本構(gòu)成工作集,在此工作集上解決QP問題,直到所有樣本滿足KKT條件。Joachims的改進(jìn)有助于提高算法收斂速度,并且他利用這些方法實現(xiàn)了SVMlight。(3)SMO算法Platt提出了分解算法的極端情形——SMO算法;該算法工作集中只有2個樣本,即將一個大的優(yōu)化問題分解為一系列只含兩個變量的子優(yōu)化問題,由于子優(yōu)化問題只涉及兩個變量,而且應(yīng)用等式約束可以將一個變量用另一個變量線性表示出來,因此在每一步求解QP問題時,不必要在迭代中求解,只要將每一步的子問題的最優(yōu)解直接用解析的方法表示出來。雖然迭代的次數(shù)增加了很多,但由于兩個變量間直接可以用解析式表示,因此每次迭代的時間非常短,大大縮短了訓(xùn)練時間。同時在工作集的選擇上,它采用了兩種啟發(fā)式方法進(jìn)行搜索,而不是傳統(tǒng)的最速下降法。主要采用兩個嵌套的循環(huán):外層循環(huán)首先遍歷非邊界樣本,調(diào)整不滿足KKT條件的樣本,當(dāng)所有的非邊界樣本滿足KKT條件時;再進(jìn)行內(nèi)層循環(huán),而內(nèi)層循環(huán)是針對以上違反KKT條件的樣本來選擇另一個樣本與它配對優(yōu)化,其選擇的準(zhǔn)則是使選擇的一對樣本能夠?qū)Q策函數(shù)得到最大的優(yōu)化步長。SMO算法主要耗時在最優(yōu)條件的判斷上和在非線性情況下誤差的重置方面,所以應(yīng)尋找最合理即計算代價最低的最優(yōu)條件判別式。SMO算法提出后,許多學(xué)者對它進(jìn)行了有效的改進(jìn)。文獻(xiàn)提出了在內(nèi)循環(huán)中每次優(yōu)化3個變量,因為3個變量的優(yōu)化問題同樣可以解析求解。實驗表明該算法比SMO的訓(xùn)練時間更短。文獻(xiàn)提出了一種新的停止準(zhǔn)則,它可以使訓(xùn)練速度更塊。(4)增量學(xué)習(xí)方法增量學(xué)習(xí)是機(jī)器學(xué)習(xí)系統(tǒng)在處理新增樣本時,只對原學(xué)習(xí)結(jié)果中與新樣本有關(guān)的部分進(jìn)行增加、修改或刪除操作,與之無關(guān)的部分則不被觸及。增量訓(xùn)練算法的一個突出特點是SVM的學(xué)習(xí)是一個數(shù)據(jù)逐一加入反復(fù)優(yōu)化的過程。Cauwenberghs提出了一種用于模式識別的增量式學(xué)習(xí)方法,它考慮了增加或減少一個訓(xùn)練樣本對拉格朗日系數(shù)和SVM的影響;其缺點是當(dāng)樣本無限增多時,還必須拋棄一些樣本,使其能夠使用。Ralaivola提出了另一種增量式學(xué)習(xí)方法,其思想是基于高斯核的局部特性,只更新對學(xué)習(xí)機(jī)器輸出影響最大的Lagrange系數(shù),以減少計算復(fù)雜度。Y.G.Liu把增量學(xué)習(xí)過程定義成為一個二次優(yōu)化問題。另外李忠偉等也提出了一種增量式學(xué)習(xí)的SVM訓(xùn)練方法。(5)粒度支持向量機(jī)粒度支持向量機(jī)是近年來興起的一種新的訓(xùn)練算法,它是由Y.C.Tang首先提出來的。它是以粒度計算(GrC)理論和統(tǒng)計學(xué)習(xí)理論為基礎(chǔ)的一種新型學(xué)習(xí)模型。其主要思想是通過常用的粒劃分方法構(gòu)建?？臻g獲得一系列信息粒,然后在每個信息粒上進(jìn)行學(xué)習(xí),最后通過聚合信息粒上的信息(如數(shù)據(jù)、規(guī)則、知識、屬性等)獲得最終的SVM決策函數(shù)。這一學(xué)習(xí)機(jī)制通過數(shù)據(jù)?；梢詫⒁粋€線性不可分問題轉(zhuǎn)化為一系列線性可分問題,也就是說將一個大規(guī)模的QP問題,通過粒度劃分,分解為一系列小的QP問題;同時,也使得數(shù)據(jù)的泛化性能增強(qiáng),即可在SVM訓(xùn)練中得到間隔更寬的超平面。如何進(jìn)行粒度劃分是粒度支持向量機(jī)研究的主要問題。目前,主要的研究都是在原空間上進(jìn)行粒度劃分,主要有:基于關(guān)聯(lián)規(guī)則的粒度支持向量機(jī),其基本思想是通過將徑向基核函數(shù)進(jìn)行麥克勞林展開,從展開式中學(xué)習(xí)關(guān)聯(lián)關(guān)系,通過這些關(guān)聯(lián)關(guān)系進(jìn)行粒度劃分,進(jìn)而在各個粒上進(jìn)行SV訓(xùn)練基于聚類的粒度支持向量機(jī)的基本思想是通過常用的聚類方法對訓(xùn)練樣本集進(jìn)行粒度劃分,然后選擇包含支持向量較多的粒參與分類或回歸?；谏炭臻g的粒度支持向量機(jī)的基本思想是首先對訓(xùn)練樣本集進(jìn)行粗粒度的選擇SV,去除一部分對構(gòu)造最優(yōu)分類超平面無用的樣本點,然后再對粗選后的樣本進(jìn)行細(xì)粒度的SV訓(xùn)練。此外還有基于樹形層次結(jié)構(gòu)的粒度支持向量機(jī)等。雖然在原空間上粒度劃分算法的研究取得了不錯的成果,但我們也發(fā)現(xiàn)在原空間上進(jìn)行粒度劃分,然后再映射到核空間會導(dǎo)致數(shù)據(jù)在原空間的分布與在核空間的分布不一致的問題,從而降低了算法的泛化性。以上幾種訓(xùn)練算法的共同點都是將一個大規(guī)模的QP問題分解為一系列小的子QP問題,最后實現(xiàn)對原問題的求解不同的是對原問題的分解策略以及工作集的選取策略,這也是導(dǎo)致算法優(yōu)劣的原因。經(jīng)過上面的分析,我們也可以將chunking算法、分解算法、SMO算法、增量學(xué)習(xí)算法這4種算法看作特殊的粒度支持向量機(jī)算法,不同的是各自劃分粒度的方法不一樣,而且粒度的精度也不同。隨著SVM訓(xùn)練算法的不斷完善成熟,基于二次規(guī)劃求解SVM問題會逐漸向?qū)嵱没l(fā)展,但同時我們也發(fā)現(xiàn)完美地實現(xiàn)用二次規(guī)劃求解SVM問題仍有很長的路要走。(6)模糊支持向量機(jī)模糊SVM(FSVM)是將模糊數(shù)學(xué)和支持向量機(jī)相結(jié)合的學(xué)習(xí)方法,主要用來處理訓(xùn)練樣本中的噪聲數(shù)據(jù)。其主要的思想是:計算每個樣本屬于各類的隸屬度,噪聲數(shù)據(jù)屬于該類的隸屬度較低,由此來降低噪聲對最優(yōu)超平面的影響。模糊支持向量機(jī)中,訓(xùn)練數(shù)據(jù)中多了一項si,它表示樣本xi屬于yi的隸屬度。其目標(biāo)函數(shù)變?yōu)閷ε夹问街兄皇铅羒的范圍變成O≤αi≤C·si。FSVM主要存在的問題是如何確定隸屬度值,即如何確定各個樣本的權(quán)重。雖然不少研究者在這方面做了很多的工作,但還沒有一個可遵循的一般性準(zhǔn)則,這其中主要有兩類方法:一類是基于時間序列的度量方法,這類方法以訓(xùn)練樣本的采集時間順序來確定模糊隸屬度,然而該類方法缺乏堅實的理論依據(jù),并且僅僅使用于序列學(xué)習(xí)的情況。另一類是基于樣本空間的度量方法,其中比較有代表性的是基于KNN的模糊隸屬度度量方法,該方法具有較少的計算量及較強(qiáng)的魯棒性。另外文獻(xiàn)提出了基于樣本到類中心的距離來度量其隸屬度的大小,但這可能會導(dǎo)致將含噪聲或野值的樣本與有效樣本賦予相同的隸屬度。文獻(xiàn)提出了一種基于密度法的FS-VM,在SVM中引入樣本密度模糊參數(shù),樣本密度定義為一個樣本的某一鄰域內(nèi)樣本的個數(shù),考慮了支持向量和孤立點、噪聲點兩方面的因素來產(chǎn)生模糊參數(shù)。此外,SVM訓(xùn)練算法還有Yang提出的訓(xùn)練SVM的幾何方法,提出了“衛(wèi)向量”(Guard-vector)的概念,通過衛(wèi)向量構(gòu)成傳統(tǒng)的QP問題解出支持向量。張學(xué)工等提出了CSVM(CentralSVM)算法等。2.2廣義svm算法隨著支持向量機(jī)研究的深入,人們提出了一些SVM的擴(kuò)展算法。這些擴(kuò)展算法主要是增加函數(shù)項、變量或系數(shù)等方法使公式變形,產(chǎn)生出有某一方面的優(yōu)勢,或者有一定應(yīng)用范圍的算法,如v-SVM,廣義SVM(GSVM)等。vSVM算法中用參數(shù)v取代C,v表示邊界支持向量數(shù)量的上限和支持向量數(shù)量的下限,即參數(shù)v可以控制支持向量的數(shù)量和誤差,它具有較好的魯棒性,容易選擇。GSVM直接以優(yōu)化系數(shù)和核矩陣構(gòu)造出一個不等式約束的非線性優(yōu)化問題,其對偶形式與標(biāo)準(zhǔn)的SVM等價,但GSVM并不是直接求解此優(yōu)化問題或者其對偶形式,而是構(gòu)造出若干特例,如光滑SVM、近似SVM、簡化SVM等。此外還有LS-SVM,加權(quán)SVM,PSVM,One-classSVM,WSVM等。2.3svm的發(fā)展方向SVM主要運(yùn)用在模式分類,回歸問題兩方面。其中在分類問題中,主要有線性分類和非線性分類,線性分類中又分為線性可分和線性不可分兩種情況。線性不可分相對于線性可分來說,就是引入了一個松弛變量ξ。線性分類是在原空間中進(jìn)行樣本分類,而非線性分類是將向量從原空間映射到特征空間,并用核函數(shù)代替內(nèi)積運(yùn)算,在特征空間中進(jìn)行樣本分類?；貧w問題是通過把樣本集因變量進(jìn)行上下平移ε,將回歸問題轉(zhuǎn)化為分類問題?；貧w問題有線性回歸和非線性回歸,非線性回歸是在線性回歸的基礎(chǔ)上引入兩個松弛變量ξ,ξ*來控制誤差大小。結(jié)束語雖然SVM目前發(fā)展得很好,但其仍然存在一些目前無法解決的問題,比如:SVM自選參數(shù)目前尚缺乏結(jié)構(gòu)化方法來實現(xiàn)參數(shù)的最優(yōu)選擇;對于具體的應(yīng)用,如何選取最合