SVM算法推導及其分類的算法實現(xiàn)

SVM算法推導及其分類的算法實現(xiàn)摘要：本文從線性分類問題開始逐步的敘述支持向量機思想的形成，并提供相應的推導過程。簡述核函數(shù)的概念，以及kernel在SVM算法中的核心地位。介紹松弛變量引入的SVM算法原因，提出軟間隔線性分類法。概括SVM分別在一對一和一對多分類問題中應用?；赟VM在一對多問題中的不足，提出SVM的改進版本DAGSVM。Abstract：Thisarticlebeginswithalinearclassificationproblem,GraduallydiscussformationofSVM,andtheirderivation.Descriptiontheconceptofkernelfunction,andthecorepositioninSVMalgorithm.Describesthereasonsfortheintroductionofslackvariables,andproposesoft-marginlinearclassification.SummarytheapplicationofSVMinone-to-oneandone-to-manylinearclassification.BasedonSVMshortageinone-to-manyproblems,animprovedversionwhichcalledDAGSVMwasputforward.關鍵字：SVM、線性分類、核函數(shù)、松弛變量、DAGSVM1.SVM的簡介支持向量機（SupportVectorMachine）是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應用到函數(shù)擬合等其他機器學習問題中。支持向量機方法是建立在統(tǒng)計學習理論的VC維理論和結構風險最小原理基礎上的，根據有限的樣本信息在模型的復雜性（即對特定訓練樣本的學習精度，Accuracy）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力。對于SVM的基本特點，小樣本，并不是樣本的絕對數(shù)量少，而是與問題的復雜度比起來，SVM算法要求的樣本數(shù)是相對比較少的。非線性，是指SVM擅長處理樣本數(shù)據線性不可分的情況，主要通過松弛變量和核函數(shù)實現(xiàn)，是SVM的精髓。高維模式識別是指樣本維數(shù)很高，通過SVM建立的分類器卻很簡潔，只包含落在邊界上的支持向量。

線性分類器及其求解線性分類器，是最簡單也很有效的分類器形式。在一個線性分類器中，可以看到SVM形成的思路，并接觸很多SVM的核心概念。用一個二維空間里僅有兩類樣本的分類問題來舉例。如圖1所示圖1圖1兩類樣本分類C1和C2是要區(qū)分的兩個類別，在二維平面中它們的樣本如圖1所示。中間的直線就是一個分類函數(shù)，它可以將兩類樣本完全分開。一般的，如果一個線性函數(shù)能夠將樣本完全正確的分開，就稱這些數(shù)據是線性可分的，否則稱為非線性可分的。很容易看出來，圖1中間那條分界線并不是唯一的，旋轉一下，只要不把兩類數(shù)據分錯，仍然可以達到分類的效果，稍微平移一下，也可以。對同一個問題存在多個分類函數(shù)的時候，哪一個函數(shù)更好呢？必須要先找一個指標來量化“好”的程度，通常使用分類間隔來衡量。設平面中的直線方程為：TOC\o"1-5"\h\z\o"CurrentDocument"g(x)=WX+b ⑴設x是一個有某一對象抽取出的n維向量，y為分類標記，則可以定義點到某一超平面的i i間隔：\o"CurrentDocument"6=y(wx+b) (2)i iwb用和替代(2)式中的w和b得：IIwIIIIwIIIg(x)Ii將（3）式得到的間隔稱為幾何間隔，幾何間隔所表示的正是點到超平面的歐氏距離，以上是單個點到某個超平面的距離定義，同樣可以定義一個點的集合（就是一組樣本）到某個超平面的距離為此集合中離超平面最近的點的距離。圖2更加直觀的展示出了幾何間隔的含義。HHlQooosoo□口-\o□、\□□iuarg]ii=2圖2分割超平面圖2中，H是分類面，H1和H2是平行于H,且過離H最近的兩類樣本的直線,H1與H，H2與H之間的距離就是幾何間隔。幾何間隔與樣本的誤分次數(shù)間存在關系：誤差分數(shù)＜（丁）2其中的5是樣本集合到分類面的間隔，R二max"*/'：-匕…,n，即r是所有樣本中向量長度最長的值。從上式可以看出，誤分次數(shù)的上界由幾何間隔決定。因此選擇幾何間隔來作為評價一個解優(yōu)劣的指標，幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了我們訓練階段的目標。從（3）式可知，幾何間隔與IIwll是成反比的，因此最大化幾何間隔與最小化IIwll等價。通常不是固定IIwII的大小而尋求最大幾何間隔，而是固定間隔（例如固定為1），尋找最小的IIwII。此時變成一個最優(yōu)化問題，若想尋找一個小IIwII,就可以用下面的式子表示:minIIwII但實際上對于這個目標，常常使用另一個完全等價的目標函數(shù)來代替，如下：min—||w||22如果直接來解這個求最小值問題，很容易看出當Ilwll=O的時候就得到了目標函數(shù)的最小值。反映在圖2中，就是竹與H2兩條直線間的距離無限大，這個時候,所有的樣本點都位于Hi和耳中間，而我們原本的意圖是，Hi右側的被分為正類，H2左側的被分為負類，位于兩類中間的樣本則拒絕分類。這樣，所有樣本點都進入了無法分類的灰色地帶。造成這種結果的原因是在描述問題的時候只考慮了目標，而沒有加入約束條件，于是可以添加約束條件：yi[(w-xi)+b]>l(i二12…,n)(n是總的樣本數(shù))于是可以將兩類分類轉化成數(shù)學形式，如下：?1min—IIwII2<2y[(W-x)+b]-1>0(i=1,2,...,n)i i (4)在這個問題中，自變量就是w,而目標函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)，這種規(guī)劃問題就是二次規(guī)劃(QuadraticProgramming，QP),由于它的可行域是一個凸集，因此它是一個凸二次規(guī)劃。樣本確定了w,用數(shù)學的語言描述，就是w可以表示為樣本的某種組合：w=ax+ax+...+ax1122nn (5)式子中的ai是拉格朗日乘子，而xi是樣本點，也是向量，n就是總樣本點的個數(shù)。為了方便描述，以下開始嚴格區(qū)別數(shù)字與向量的乘積和向量間的乘積，我會用aixi表示數(shù)字和向量的乘積，而用<xi'xj>表示向量xi'xj的內積。因此(1)式嚴格的形式應該是：6)g(x)=<w,x>+b6)w不僅跟樣本點的位置有關，還跟樣本的類別有關。因此用下面這個式子表示w：w=ayx+ayx+...+ayx111222nnn (7)其中的yi就是第i個樣本的標簽，它等于1或者-1。其實以上式子的拉格朗日乘子…,an中，只有很少的一部分不等于0這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在竹和H2上，也正是這部分樣本唯一的確定了分類函數(shù)。這部分可以確定分類的樣本點，就叫做支持向量。因此原來的g(x)表達式可以寫為：g(x)=<w,x>+b=<Y(ayx),x>+biiii=1 ， (8)w=Y(ayx)其中， i=1iii上式可以變形為：g(x)=Yay<x,x>+biiii=1 (9)此時消去了上式中的w，問題從求w變成了求a。這樣就簡化了原問題的求解，以這樣的形式描述問題以后，優(yōu)化問題少了很大一部分不等式約束。接下來看看SVM在線性分類器上所做的重大改進——核函數(shù)。SVM中的核函數(shù)根據模式識別理論，低維空間線性不可分的模式通過非線性映射到高維特征空間則可能實現(xiàn)線性可分，但是如果直接采用這種技術在高維空間進行分類或回歸，則存在確定非線性映射函數(shù)的形式和參數(shù)、特征空間維數(shù)等問題，而最大的障礙則是在高維特征空間運算時存在的“維數(shù)災難”。采用核函數(shù)技術可以有效地解決這樣問題。如圖3所示，當分類問題在低緯空間無法用線性分類方法解決時，可以通過e將低緯空間的數(shù)據映射到高緯特征空間中，從而達到線性可分的目的。:^feature H:^feature HK圖3低緯度向高緯度空間映射從低緯度向高緯度轉化關鍵在于尋在一個e函數(shù)，但對目前沒有一個系統(tǒng)的方法。對映射過程推導如下：<e(x,x)，e(XT,xT)>=<(z,z,z),(zT,zT,zT)>1 2 1 2 12 3 12 3=<(X2八：'2XX,X2),(XT2,%2XTXT,xT2)>11221122=X2XT2+2XXXTXT+x2XT211121222(10)=(XXT+xXT)21122=(<X,XT>)2=K(x,xt)從上式可以得出，我們只關心高維空間里內積的值，而核函數(shù)就是接受低空間的輸入，并計算出在高緯空間的內積值。K(X,XT)，就是我們要找的核函數(shù)。如圖4

-.Tj,鬲),嵐舄HX；〕>=<(云 二;&；｝>=<〔￡,厲絢Xjr￡\(才、払A；,昇｝>=珀屮十知眄曲坨十吧址=(占珀十嶺￡)=(<^,x>)^k(x,x) kernelfunction圖4在映射過程中的核函數(shù)g(x)=￡ayK(x,x)+b于是上式，可以表示為 匸i''i 。盡管給的問題是線性不可分的，但凡是要求內積的時候我們就選定的核函數(shù)來算。這樣求出來的a再和你選定的核函數(shù)一組合，就可以得到線性分類器。但是任然存在以下兩個問題：既然有很多的核函數(shù)，針對具體問題該怎么選擇？如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么辦？第一個問題：對核函數(shù)的選擇，現(xiàn)在還缺乏指導原則！各種實驗的觀察結果的確表明，某些問題用某些核函數(shù)效果很好，用另一些就很差，但是一般來講，徑向基核函數(shù)是不會出太大偏差的一種，首選。對第二個問題的解決則引出了SVM中的另一個概念：松弛變量。SVM中的松弛變量假設有另一個訓練集，只比原先這個訓練集多了一個樣本，映射到高維空間以后，也就多了一個樣本點，但是這個樣本的位置是這樣的，如圖5：HiUtilIJHiUtilIJm—2'圖5新增加了一個樣本后分類的結果就是圖中黃色那個點，它是方形的，因而它是負類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數(shù)點線性不可分）叫做“近似線性可分”的問題。對于人類思維，在大量的樣本基礎上，可能會認為圖5中的黃點是錯誤的，是噪聲，會自動的剔除掉。人的思維對于噪聲數(shù)據具有容錯性，可程序沒有。由于我們原本的優(yōu)化問題的表達式中，確實要考慮所有的樣本點，在此基礎上尋找正負類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。說明硬間隔的分類法其結果容易受少數(shù)點的控制。針對硬間隔的問題，解決方法也很明顯，就是仿照人的思路，允許一些點到分類平面的距離不滿足原先的要求。由于不同的訓練集各點的間距尺度不太一樣，因此用間隔（而不是幾何間隔）來衡量有利于我們表達形式的簡潔。原先對樣本點的要求是：(11)y[(wx)+b]>1(i二1,2,...,n)(n是樣本數(shù)(11)i i該式說明，離分類面最近的樣本點函數(shù)間隔也要比1大。如果要引入容錯性，就給1這個硬性的閾值加一個松弛變量，即允許：y[(wx)+b]>1-g(i二1,2,...,n)(n是樣本數(shù))i i ig>0i因為松弛變量是非負的，因此最終的結果是要求間隔可以比1小。但是當某些點出現(xiàn)這種間隔比1小的情況時(這些點也叫離群點)，意味著放棄了對這些點的精確分類，而這對分類器來說是種損失。但是放棄這些點也帶來了好處，那就是使分類面不必向這些點的方向移動，因而可以得到更大的幾何間隔。顯然必須權衡這種損失和好處。得到的分類間隔越大，好處就越多。原始的硬間隔分類對應的優(yōu)化問題：(13)min—IIwII2(13)<2ST.y[(w-x)+b]-1>0(i=l,2,...,n)i iIIwII2就是目標函數(shù)，希望它越小越好，因而損失就必然是一個能使之變大的量。那如何來衡量損失，有兩種常用的方式，兩種方法沒有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做二階軟間隔分類器，第二種就叫做一階軟間隔分類器。把損失加入到目標函數(shù)里的時候，就需要一個懲罰因子，原來的優(yōu)化問題就變成了下面這樣：?1min—IIwII22<ST.y[(w-x)+b]>1—匚(i=1,2,...,n) (14)i i i匚>0i這個式子有這么幾點要注意：一是并非所有的樣本點都有一個松弛變量與其對應。實際上只有“離群點”才有，沒離群的點松弛變量都等于0。二是松弛變量的值實際上標示出了對應的點到底離群有多遠，值越大，點就越遠。三是懲罰因子C決定了你有多重視離群點帶來的損失，顯然當所有離群點的松弛變量的和一定時，定的C越大，對目標函數(shù)的損失也越大，此時就暗示著不愿意放棄這些離群點，最極端的情況是你把C定為無限大，這樣只要稍有一個點離群，目標函數(shù)的值馬上變成無限大，馬上讓問題變成無解，這就退化成了硬間隔問題。四是懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個你必須事先指定的值。五是盡管加了松弛變量這么一說，但這個優(yōu)化問題仍然是一個優(yōu)化問題，解的過程比起原始的硬間隔問題來說，沒有任何更加特殊的地方。從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w,也就是確定了前面圖中的三條直線，這時看看間隔有多大，又有多少點離群，把目標函數(shù)的值算一算，再換一組三條直線，再把目標函數(shù)的值算一算，如此往復（迭代），直到最終找到目標函數(shù)最小時的w。松弛變量也就是個解決線性不可分問題的方法罷了，核函數(shù)的引入不也是為了解決線性不可分的問題么？為什么要為了一個問題使用兩種方法呢？其實兩者還有微妙的不同。一般的情況下，在原始的低維空間中，樣本相當?shù)牟豢煞郑瑹o論怎么找分類平面，總會有大量的離群點，此時用核函數(shù)向高維空間映射一下，雖然結果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)，此時再用松弛變量處理那些少數(shù)“冥頑不化”的離群點，就簡單有效得多了。至此一個比較完整的支持向量機框架就有了，簡單說來，支持向量機就是使用了核函數(shù)的軟間隔線性分類法。懲罰因子和數(shù)據偏斜偏斜問題，也叫數(shù)據集偏斜（unbalanced），它指的是參與分類的兩個類別（也可以指多個類別）樣本數(shù)量差異很大。比如說正類有10，000個樣本，而負類只給了100個，這會引起的問題顯而易見，如圖7：圖6數(shù)據集偏斜現(xiàn)象方形的點是負類。H,Hl,H2是根據給的樣本算出來的分類面，由于負類的樣本很少很少，所以有一些本來是負類的樣本點沒有提供，比如圖7中兩個灰色的方形點，如果這兩個點有提供的話，那算出來的分類面應該是H',H2'和H1，他們顯然和之前的結果有出入，實際上負類給的樣本點越多，就越容易出現(xiàn)在灰色點附近的點，算出的結果也就越接近于真實的分類面。但現(xiàn)在由于偏斜的現(xiàn)象存在，使得數(shù)量多的正類可以把分類面向負類的方向“推”，因而影響了結果的準確性。解決數(shù)據集偏斜問題的方法之一就是在懲罰因子上作文章，那就是給樣本數(shù)量少的負類更大的懲罰因子，表示我們重視這部分樣本，因此我們的目標函數(shù)中因松弛變量而損失的部分就變成了：C另匚+C另匚+ 1 -j （15）i=1 j=P+1匚＞0i其中i=1???p都是正樣本，j=p+1…p+q都是負樣本。那C和C怎么確定呢？它+-們的大小是試出來的（參數(shù)調優(yōu)），但是他們的比例可以有些方法來確定。但是這樣并不夠好，如圖6,發(fā)現(xiàn)正類之所以可以“欺負”負類，其實并不是因為負類樣本少，真實的原因是負類的樣本分布的不夠廣（沒擴充到負類本應該有的區(qū)域）。比如，現(xiàn)在想給政治類和體育類的文章做分類，政治類文章很多，而體育類只提供了幾篇關于籃球的文章，這時分類會明顯偏向于政治類，如果要給體育類文章增加樣本，但增加的樣本仍然全都是關于籃球的。雖然體育類文章在數(shù)量上可以達到與政治類一樣多，但過于集中了，結果仍會偏向于政治類！所以給C+和C確定比例更好的方法應該是衡量他們分布的程度。比如可以算算他們在空間中占據了多大的體積，例如給負類找一個超球，它可以包含所有負類的樣本，再給正類找一個超球，比比兩個球的半徑，就可以大致確定分布的情況。顯然半徑大的分布就比較廣，就給小一點的懲罰因子。6.SVM的改進DAGSVMSVM是一種典型的兩類分類器，而現(xiàn)實中要解決的問題，往往是多類的問題，比如文本分類，數(shù)字識別。如何由兩類分類器得到多類分類器，就是一個值得研究的問題。以文本分類為例，現(xiàn)成的方法有很多，其中一種一勞永逸的方法，就是真的一次性考慮所有樣本，并求解一個多目標函數(shù)的優(yōu)化問題，一次性得到多個分類面，就像下圖這樣：圖7對任意兩個類構建一個分類器多個超平面把空間劃分為多個區(qū)域，每個區(qū)域對應一個類別，給一篇文章，看它落在哪個區(qū)域就知道了它的分類。這樣一次性求解的方法計算量實在太大，大到無法實用的地步?！耙活悓ζ溆唷钡姆椒ǎ褪敲看稳匀唤庖粋€兩類分類的問題。比如有5個類別，第一次就把類別1的樣本定為正樣本，其余2，3，4，5的樣本合起來定為負樣本，這樣得到一個兩類分類器，它能夠指出一篇文章是還是不是第1類的；第二次我們把類別2的樣本定為正樣本，把1,3,4,5的樣本合起來定為負樣本，得到一個分類器，如此下去，可以得到5個這樣的兩類分類器。這種方法的好處是每個優(yōu)化問題的規(guī)模比較小，而且分類的時候速度很快。但有時也會出現(xiàn)兩種很尷尬的情況，例如拿一篇文章每一個分類器都說它是屬于它那一類的，或者每一個分類器都說它不是它那一類的，前者叫分類重疊現(xiàn)象，后者叫不可分類現(xiàn)象。對于分類重疊倒，隨機選一個結果都不至于太離譜，或者看看這篇文章到各個超平面的距離，哪個遠就判給哪個。不可分類現(xiàn)象就著實難辦了，只能把它分給第6個類別了，本來各個類別的樣本數(shù)目是差不多的，但“其余”的那一類樣本數(shù)總是要數(shù)倍于正類，這就人為的造成了“數(shù)據集偏斜”問題。再退一步，還是解兩類分類問題，還是每次選一個類的樣本作正類樣本，而負類樣本則變成只選一個類，這就避免了偏斜。因此過程就是算出這樣一些分類器，第一個只回答“是第1類還是第2類”，第二個只回答“是第1類還是第3類”，第三個只回答“是第1類還是第4類”，如此下去，可以馬上得出，這樣的分類器應該有5X4/2=10個。雖然分類器的數(shù)目多了，但是在訓練階段所用的總時間卻比“一類對其余”方法少很多，在真正用來分類的時候，把一篇文章扔給所有分類器，第一個分類器會投票說它是“1”或者“2”，第二個會說它是“1”或者“3”，讓每一個都投上自己的一票，最后統(tǒng)計票數(shù)，如果類別“1”得票最多，就判這篇文章屬于第1類。這種方法顯然也會有分類重疊的現(xiàn)象，但不會有不可分類現(xiàn)象，因為總不可能所有類別的票數(shù)都是0。這還是類別數(shù)為5的時候，類別數(shù)如果是1000，要調用的分類器數(shù)目會上升至約500,000個。再退一步，還是像一對一方法那樣來訓練，只是在對一篇文章進行分類之前，先按照圖8的樣子來組織分類器圖8DAGSVM訓練方法這樣在分類時，就可以先問分類器“1對5”，如果它回答5,就往左走，再問“2對5”這個分類器，如果它還說是“5”，就繼續(xù)往左走，這樣一直問下去，就可以得到分類結果。優(yōu)點是，只調用了4個分類器，分類速度快，且沒有分類重疊和不可分類現(xiàn)象！缺點是，假如最一開始的分類器回答錯誤，那么后面的分類器是無論如何也無法糾正它的錯誤的，其實對下面每一層的分類器都存在這種錯誤向下累積的現(xiàn)象。DAG方法好于它們的地方就在于，累積的上限，不管是大是小，總是有定論的，有理論證明。而一對其余和一對一方法中，盡管每一個兩類分類器的泛化誤差限是知道的，但是合起來做多類分類的時候，誤差上界是多少，無法知道，這意味著準確率低到0也是有可能的。而且現(xiàn)在DAG方法根節(jié)點的選取，也有一些方法可以改善整體效果，我們總希望根節(jié)點少犯錯誤為好，因此參與第一次分類的兩個類別，最好是差別特別特別大，大到以至于不太可能把他們分錯；或者就總取在兩類分類中正確率最高的那個分類器作根節(jié)點，或者我們讓兩類分類器在分類的時候，不光輸出類別的標簽，還輸出一個類似“置信度”等。參考文獻.BahlmannC,HaasdonkB,BurkhardtH.Onlinehandwritingrecognitionwithsupportvectormachines-akernelapproach[C]//FrontiersinHandwritingRecognition,2002.Proceedings.EighthInternationalWorkshopon.IEEE,2002:49-54..MandelMI,EllisDPW.Song-levelfeaturesandsupportvectormachinesformusicclassification[C]//ISMIR2005:6thInternationalConferenceonMusicInformationRetrieval:Proc