支持向量機訓練算法綜述

支持向量機訓練算法綜述

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