支持向量機算法學(xué)習(xí)總結(jié)

題目：支持向量機的算法學(xué)習(xí)姓名：學(xué)號：專業(yè)：

指導(dǎo)教師：、日期：2012年6月20日支持向量機的算法學(xué)習(xí)理論背景基于數(shù)據(jù)的機器學(xué)習(xí)是現(xiàn)代智能技術(shù)中的重要方面，研究從觀測數(shù)據(jù)(樣本)出發(fā)尋找規(guī)律，利用這些規(guī)律對未來數(shù)據(jù)或無法觀測的數(shù)據(jù)進行預(yù)測。迄今為止，關(guān)于機器學(xué)習(xí)還沒有一種被共同接受的理論框架，關(guān)于其實現(xiàn)方法大致可以分為三種：第一種是經(jīng)典的(參數(shù))統(tǒng)計估計方法。包括模式識別、神經(jīng)網(wǎng)絡(luò)等在內(nèi)，現(xiàn)有機器學(xué)習(xí)方法共同的重要理論基礎(chǔ)之一是統(tǒng)計學(xué)。參數(shù)方法正是基于傳統(tǒng)統(tǒng)計學(xué)的，在這種方法中，參數(shù)的相關(guān)形式是已知的，訓(xùn)練樣本用來估計參數(shù)的值。這種方法有很大的局限性，首先，它需要已知樣本分布形式，這需要花費很大代價，還有，傳統(tǒng)統(tǒng)計學(xué)研究的是樣本數(shù)目趨于無窮大時的漸近理論，現(xiàn)有學(xué)習(xí)方法也多是基于此假設(shè)。但在實際問題中，樣本數(shù)往往是有限的，因此一些理論上很優(yōu)秀的學(xué)習(xí)方法實際中表現(xiàn)卻可能不盡人意。第二種方法是經(jīng)驗非線性方法，如人工神經(jīng)網(wǎng)絡(luò)(ANN。這種方法利用已知樣本建立非線性模型，克服了傳統(tǒng)參數(shù)估計方法的困難。但是，這種方法缺乏一種統(tǒng)一的數(shù)學(xué)理論。與傳統(tǒng)統(tǒng)計學(xué)相比，統(tǒng)計學(xué)習(xí)理論(StatisticalLearningTheory或SLT)是一種專門研究小樣本情況下機器學(xué)習(xí)規(guī)律的理論。該理論針對小樣本統(tǒng)計問題建立了一套新的理論體系，在這種體系下的統(tǒng)計推理規(guī)則不僅考慮了對漸近性能的要求，而且追求在現(xiàn)有有限信息的條件下得到最優(yōu)結(jié)果。V.Vapnik等人從六、七十年代開始致力于此方面研究[1]，到九十年代中期，隨著其理論的不斷發(fā)展和成熟，也由于神經(jīng)網(wǎng)絡(luò)等學(xué)習(xí)方法在理論上缺乏實質(zhì)性進展，統(tǒng)計學(xué)習(xí)理論開始受到越來越廣泛的重視。統(tǒng)計學(xué)習(xí)理論的一個核心概念就是VC維(VCDimension)概念，它是描述函數(shù)集或?qū)W習(xí)機器的復(fù)雜性或者說是學(xué)習(xí)能力(Capacityofthemachine)的一個重要指標(biāo)，在此概念基礎(chǔ)上發(fā)展出了一系列關(guān)于統(tǒng)計學(xué)習(xí)的一致性(Consistency)、收斂速度、推廣性能(GeneralizationPerformance)等的重要結(jié)論。支持向量機方法是建立在統(tǒng)計學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性(即對特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy)和學(xué)習(xí)能力(即無錯誤地識別任意樣本的能力)之間尋求最佳折衷，以期獲得最好的推廣能力(GeneralizatinAbility) 。支持向量機方法的幾個主要優(yōu)點有：1.它是專門針對有限樣本情況的，其目標(biāo)是得到現(xiàn)有信息下的最優(yōu)解而不僅僅是樣本數(shù)趨于無窮大時的最優(yōu)值；2.算法最終將轉(zhuǎn)化成為一個二次型尋優(yōu)問題，從理論上說，得到的將是全局最優(yōu)點，解決了在神經(jīng)網(wǎng)絡(luò)方法中無法避免的局部極值問題；3.算法將實際問題通過非線性變換轉(zhuǎn)換到高維的特征空間(FeatureSpace)，在高維空間中構(gòu)造線性判別函數(shù)來實現(xiàn)原空間中的非線性判別函數(shù)，特殊性質(zhì)能保證機器有較好的推廣能力，同時它巧妙地解決了維數(shù)問題，其算法復(fù)雜度與樣本維數(shù)無關(guān)；在SVM方法中，只要定義不同的內(nèi)積函數(shù)，就可以實現(xiàn)多項式逼近、貝葉斯分類器、徑向基函數(shù)(RadialBasicFunction或RBF)方法、多層感知器網(wǎng)絡(luò)等許多現(xiàn)有學(xué)習(xí)算法。方法SVM是從線性可分情況下的最優(yōu)分類面發(fā)展而來的， 基本思想可用圖1的兩維情況說明。圖中，實心點和空心點代表兩類樣本， H為分類線，H1、H2分別為過各類中離分類線最近的樣本且平行于分類線的直線， 它們之間的距離叫做分類間隔(margin)。所謂最優(yōu)分類線就是要求分類線不但能將兩類正確分開(訓(xùn)練錯誤率為0)，而且使分類間隔最大。分類線方程為xw+b=0，我們可以對它進行歸一化，使得對線性可分的樣本集3,%門=1,…n,x?Rd,*{4-1}，滿足yi[(wxjb]-1_0,i=1, ,n (1)2此時分類間隔等于 2/||W|，使間隔最大等價于使IWI最小。滿足條件⑴且使^IWII2最小的分類面就叫做最優(yōu)分類面，H1、H2上的訓(xùn)練樣本點就稱作支持向量。利用Lagrange優(yōu)化方法可以把上述最優(yōu)分類面問題轉(zhuǎn)化為其對偶問題，即：在約束條件(2a)(2b)和aj丄0i= ,n(2b)F對ai求解下列函數(shù)的最大值:n nn nmax'ai ajajyjyjXXj） （3）3 i 2i,j4ai為原問題中與每個約束條件（1）對應(yīng)的Lagrange乘子。這是一個不等式約束下二次函數(shù)尋優(yōu)的問題，存在唯一解。容易證明，解中將只有一部分（通常是少部分）a不為零，對應(yīng)的樣本就是支持向量。解上述問題后得到的最優(yōu)分類函數(shù)是fn* *】f(x)=sgn{(wx)b}=sgn'a*yi(xx)b*li4 J式中的求和實際上只對支持向量進行。 b*是分類閾值，可以用任一個支持向量（滿足（1）中的等號）求得，或通過兩類中任意一對支持向量取中值求得。???圖土1繪優(yōu)超平面Figure2.iTheOpiimaiHyperplane對非線性問題，可以通過非線性變換轉(zhuǎn)化為某個高維空間中的線性問題， 在變換空間求最優(yōu)分類面。這種變換可能比較復(fù)雜，因此這種思路在一般情況下不易實現(xiàn)。但是注意到，在上面的對偶問題中，不論是尋優(yōu)目標(biāo)函數(shù) （3）還是分類函數(shù)⑷都只涉及訓(xùn)練樣本之間的內(nèi)積運算匕xj）。設(shè)有非線性映射:Rd>H將輸入空間的樣本映射到高維（可能是無窮維）的特征空間H中。當(dāng)在特征空間H中構(gòu)造最優(yōu)超平面時，訓(xùn)練算法僅使用空間中的點積，即門Xj計Xj,而沒有單獨的GXj出現(xiàn)。因此，如果能夠找到一個函數(shù)K使得K(x,X=Pi(x「),這樣，在高維空間實際上只需進行內(nèi)積運算，而這種內(nèi)積運算是可以用原空間中的函數(shù)實現(xiàn)的，我們甚至沒有必要知道變換 ①的形式。根據(jù)泛函的有關(guān)理論，只要一種核函數(shù)K(x「Xj)滿足Mercer條件，它就對應(yīng)某一變換空間中的內(nèi)積。因此，在最優(yōu)分類面中采用適當(dāng)?shù)膬?nèi)積函數(shù)K(Xj,Xj)就可以實現(xiàn)某一非線性變換后的線性分類，而計算復(fù)雜度卻沒有增加，此時目標(biāo)函數(shù) (3)變?yōu)椋簄1nTOC\o"1-5"\h\zmax'aj-—vajaj^yjK^Xj) (5)ai 2i,j二而相應(yīng)的分類函數(shù)也變?yōu)閒n* *1f(x)=sgn{(wx)b}=sgn' x)b (6)liT J這就是支持向量機。這一特點提供了解決算法可能導(dǎo)致的“維數(shù)災(zāi)難”問題的方法：在構(gòu)造判別函數(shù)時，不是對輸入空間的樣本作非線性變換，然后在特征空間中求解；而是先在輸入空間比較向量(例如求點積或是某種距離)，對結(jié)果再作非線性變換。這樣,大的工作量將在輸入空間而不是在高維特征空間中完成。 SVM分類函數(shù)形式上類似于一個神經(jīng)網(wǎng)絡(luò)，輸出是s中間節(jié)點的線性組合，每個中間節(jié)點對應(yīng)一個支持向量，如圖2所示。輸出（決策規(guī)也hr=sgn(y'af)K(xb)WffL?fJ；基f-s個支持向Mx,申，…,-rf的菲44*-kl-KirrlnrftJ\輸入向T.X={J,一圖2支持向量機示意圖函數(shù)K稱為點積的卷積核函數(shù)，它可以看作在樣本之間定義的一種距離。顯然，上面的方法在保證訓(xùn)練樣本全部被正確分類，即經(jīng)驗風(fēng)險 Remp為0的前提下，通過最大化分類間隔來獲得最好的推廣性能。如果希望在經(jīng)驗風(fēng)險和推廣性能之間求得某種均衡，在。這時，約束（1）變?yōu)榭梢酝ㄟ^引入正的松弛因子i來允許錯分樣本的存yi[(wx)+b]一1i一0,i=1；,n(7)而在目標(biāo)最小化—1wn中加入懲罰項i，id這樣，Wolf對偶問題可以寫成：Maximize:maxan 1n'a-1'ajajyiyjK(XjXj) (8)i 2i,j壬s.tn' yiai=oi(9a)0-aj-C i=1,,n(9b)這就是SVM方法的最一般的表述。為了方便后面的陳述，這里我們對對偶問題的最優(yōu)解做一些推導(dǎo)。定義nTOC\o"1-5"\h\zw(a)二為yiai(xj (10)iF=w(a)(xj—y=為ajyjK(XjXj)沖 (11)j對偶問題的Lagrange函數(shù)可以寫成：1Lw(a)w(a)-'a-'、冋?'叫(耳-C)為aiyi (12)2 i i i iSVM算法中目前的研究狀況由于SVM方法較好的理論基礎(chǔ)和它在一些領(lǐng)域的應(yīng)用中表現(xiàn)出來的優(yōu)秀的

推廣性能，近年來，許多關(guān)于SVM方法的研究，包括算法本身的改進和算法的

實際應(yīng)用，都陸續(xù)提了出來。盡管SVM算法的性能在許多實際問題的應(yīng)用中得

到了驗證，但是該算法在計算上存在著一些問題，包括訓(xùn)練算法速度慢、算法復(fù)

雜而難以實現(xiàn)以及檢測階段運算量大等等。傳統(tǒng)的利用標(biāo)準(zhǔn)二次型優(yōu)化技術(shù)解決

對偶問題的方法可能是訓(xùn)練算法慢的主要原因： 首先，SVM方法需要計算和存儲核函數(shù)矩陣，當(dāng)樣本點數(shù)目較大時，需要很大的內(nèi)存，例如，當(dāng)樣本點數(shù)目超過4000時，存儲核函數(shù)矩陣需要多達128兆內(nèi)存；其次，SVM在二次型尋優(yōu)過程中要進行大量的矩陣運算，多數(shù)情況下，尋優(yōu)算法是占用算法時間的主要部分。SVM方法的訓(xùn)練運算速度是限制它的應(yīng)用的主要方面，近年來人們針對方法本身的特點提出了許多算法來解決對偶尋優(yōu)問題。大多數(shù)算法的一個共同的思想就是循環(huán)迭代：將原問題分解成為若干子問題，按照某種迭代策略，通過反復(fù)求解子問題，最終使結(jié)果收斂到原問題的最優(yōu)解。根據(jù)子問題的劃分和迭代策略的不同，又可以大致分為兩類。第一類是所謂的“塊算法” (chunkingalgorithm)?！皦K算法”基于的是這樣一個事實，即去掉Lagrange乘子等于零的訓(xùn)練樣本不會影響原問題的解。對于給定的訓(xùn)練樣本集，如果其中的支持向量是已知的，尋優(yōu)算法就可以排除非支持向量，只需對支持向量計算權(quán)值(即Lagrange乘子)即可。實際上支持向量是未知的，因此“塊算法”的目標(biāo)就是通過某種迭代方式逐步排除非支持向量。具體的作法是，選擇一部分樣本構(gòu)成工作樣本集進行訓(xùn)練， 剔除其中的非支持向量，并用訓(xùn)練結(jié)果對剩余樣本進行檢驗，將不符合訓(xùn)練結(jié)果(一般是指違反KKT條件)的樣本(或其中的一部分)與本次結(jié)果的支持向量合并成為一個新的工作樣本集，然后重新訓(xùn)練。如此重復(fù)下去直到獲得最優(yōu)結(jié)果。當(dāng)支持向量的數(shù)目遠遠小于訓(xùn)練樣本數(shù)目時，“塊算法”顯然能夠大大提高運算速度。然而，如果支持向量的數(shù)目本身就比較多，隨著算法迭代次數(shù)的增多，工作樣本集也會越來越大，算法依舊會變得十分復(fù)雜。因此第二類方法把問題分解成為固定樣本數(shù)的子問題：工作樣本集的大小固定在算法速度可以容忍的限度內(nèi)，迭代過程中只是將剩余樣本中部分“情況最糟的樣本”與工作樣本集中的樣本進行等量交換，即使支持向量的個數(shù)超過工作樣本集的大小，也不改變工作樣本集的規(guī)模，而只對支持向量中的一部分進行優(yōu)化。固定工作樣本集的方法和塊算法的主要區(qū)別在于：塊算法的目標(biāo)函數(shù)中僅包含當(dāng)前工作樣本集中的樣本， 而固定工作樣本集方法雖然優(yōu)化變量僅包含工作樣本， 其目標(biāo)函數(shù)卻包含整個訓(xùn)練樣本集，即工作樣本集之外的樣本的Lagrange乘子固定為前一次迭代的結(jié)果，而不是像塊算法中那樣設(shè)為0。而且固定工作樣本集方法還涉及到一個確定換出樣本的問題（因為換出的樣本可能是支持向量）。這樣，這一類算法的關(guān)鍵就在于找到一種合適的迭代策略使得算法最終能收斂并且較快地收斂到最優(yōu)結(jié)果。固定工作樣本集的方法最早大概是由 Osunaetal 提出的。其中，EdgarOsunal等人介紹了一種具體的算法并對人臉識別問題進行了實驗。將樣本集分為兩個集合B和N,集合B作為子問題工作樣本集進行SVM訓(xùn)練，集合N中所有樣本的Lagrange乘子均置為零。顯然，如果把集合B中對應(yīng)Lagrange乘子為零的樣本i（即冷=0，LB）與集合N中的樣本j（即：=0，jB）交換，不會改變子問題與原問題的可行性（即仍舊滿足約束條件） ；而且，當(dāng)且僅當(dāng)樣本滿足條件（Fi-Jy：_0時，替換后的子問題的最優(yōu)解不變。于是可以按照以下步驟迭代求解：1.選擇集合B，構(gòu)造子問題；2.求子問題最優(yōu)解：0,rB及b，并置：0，jN；3.計算Fj，jN找出其中不滿足條件（R-「）yi_0的樣本j,與B中滿足:0的樣本i交換，構(gòu)成新的子問題。并且證明了這種迭代算法的收斂性，并給出了兩階多項式分類器在人臉識別問題中的應(yīng)用結(jié)果。需要說明的是，文中沒有說明集合B的大小是否改變。作者期望的是支持向量的數(shù)目非常少，當(dāng)然可以固定B的大小，作者的意圖正是如此。不過為此需要選擇一個較大的B集合，這樣看來，其效率可能還不如塊算法。而且如果如果集合B不足以包括所有的支持向量，該算法沒有提出改變 B的大小的策略，有可能得不到結(jié)果。前面提到，固定工作樣本集方法的關(guān)鍵在于選擇一種合適的換入換出策略。Joachims指出如果采用某種啟發(fā)式的迭代策略將會提高算法的收斂速度。最近JohnC.Platt提出SMO（SequentialMinimalOptimization或SMO算法。將工作樣本集的規(guī)模減到最小 兩個樣本。之所以需要兩個樣本是因為等式線性約束的存在使得同時至少有兩個 Lagrange乘子發(fā)生變化。由于只有兩個變量，而且應(yīng)用等式約束可以將其中一個用另一個表示出來，所以迭代過程中每一步的子問題的最優(yōu)解可以直接用解析的方法求出來。這樣，算法避開了復(fù)雜的數(shù)值求解優(yōu)化問題的過程；此外，Platt還設(shè)計了一個兩層嵌套循環(huán)分別選擇進入工作樣本集的樣本，這種啟發(fā)式策略大大加快了算法的收斂速度。標(biāo)準(zhǔn)樣本集的實驗結(jié)果證明，SMO表現(xiàn)出在速度方面的良好性能。子問題的規(guī)模和迭代的次數(shù)是一對矛盾，SMO將工作樣本集的規(guī)模減少到2,一個直接的后果就是迭代次數(shù)的增加。所以SMO實際上是將求解子問題的耗費轉(zhuǎn)嫁到迭代上，然后在迭代上尋求快速算法。但是，SMO迭代策略的思想是可以用到其他迭代算法中的，可見，SMO還有改進的余地。SMO在實際應(yīng)用中取得了較好的效果，但它也存在著一些問題。 SMO算法每次迭代都要更新B值，但是該值有可能是無法確定的（例如不存在0：：：冷：：：C的樣本，盡管這種情況很少出現(xiàn)），這時SMO采用的方法是確定出B的上下界然后取平均值；另外，每一次迭代過程中的B值僅取決于上次迭代結(jié)果的兩個變量的最優(yōu)值，用這個B值判斷樣本是否滿足迭代結(jié)果，這就可能存在某些達到最優(yōu)值的樣本卻不滿足KKT條件的情況，從而影響了該算法的效率。解決算法速度問題的另一個途徑是采用序列優(yōu)化的思想。這種方