SVM-支持向量機算法概述-1

支持向量機（SupportVectorMachine）算法概述沈新蕊OutlineSVM的理論基礎線性判別函數和超平面間隔與幾何間隔核函數與松弛變量SVM的理論基礎支持向量機(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，從誕生至今才10多年，發展史雖短，但其理論研究和算法實現方面卻都取得了突破性進展，有力地推動機器學習理論和技術的發展。這一切與支持向量機具有較完備的統計學習理論基礎的發展背景是密不可分的。它在解決小樣本、非線性及高維模式識別中表現出許多特有的優勢，并能夠推廣應用到函數擬合等其他機器學習問題中。SVM支持向量機支持向量機方法是建立在統計學習理論的VC維理論和結構風險最小原理基礎上的，根據有限的樣本信息在模型的復雜性（即對特定訓練樣本的學習精度，Accuracy）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（或稱泛化能力）。VC維VC維是對函數類的一種度量，可以簡單的理解為問題的復雜程度，VC維越高，一個問題就越復雜。正是因為SVM關注的是VC維，SVM解決問題的時候，和樣本的維數是無關的。結構風險最小機器學習本質上就是一種對問題真實模型的逼近，真實模型一定是不知道的，那么我們選擇的假設與問題真實解之間究竟有多大差距，我們就沒法得知。這個與問題真實解之間的誤差，就叫做風險（更嚴格的說，誤差的累積叫做風險）。我們選擇了一個假設之后，真實誤差未知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數據上的分類的結果與真實結果之間的差值來表示。這個差值叫做經驗風險Remp(w)。結構風險最小以前的機器學習方法都把經驗風險最小化作為努力的目標，但后來發現很多分類函數能夠在樣本集上輕易達到100%的正確率，在真實分類時卻一塌糊涂（即推廣能力差，或泛化能力差）。此時的情況便是選擇了一個足夠復雜的分類函數，能夠精確的記住每一個樣本，但對樣本之外的數據一律分類錯誤。此原則適用的大前提是經驗風險要確實能夠逼近真實風險才行，但實際上能逼近么？不能，因為樣本數相對于現實世界要分類的文本數來說簡直九牛一毛，經驗風險最小化原則只在這占很小比例的樣本上做到沒有誤差，當然不能保證在更大比例的真實文本上也沒有誤差。泛化誤差界統計學習因此而引入了泛化誤差界的概念，就是指真實風險應該由兩部分內容刻畫，一是經驗風險，代表了分類器在給定樣本上的誤差；二是置信風險，代表了我們在多大程度上可以信任分類器在未知文本上分類的結果。顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區間，也使得整個誤差只能計算上界，無法計算準確的值（所以叫做泛化誤差界，而不叫泛化誤差）。置信風險與兩個量有關，一是樣本數量，顯然給定的樣本數量越大，我們的學習結果越有可能正確，此時置信風險越小；二是分類函數的VC維，顯然VC維越大，推廣能力越差，置信風險會變大。泛化誤差界泛化誤差界的公式為：R(w)≤Remp(w)+Ф(n/h)公式中R(w)就是真實風險，Remp(w)就是經驗風險，Ф(n/h)就是置信風險。統計學習的目標從經驗風險最小化變為了尋求經驗風險與置信風險的和最小，即結構風險最小。SVM正是這樣一種努力最小化結構風險的算法。其它概念小樣本，并不是說樣本的絕對數量少，而是說與問題的復雜度比起來，SVM算法要求的樣本數是相對比較少的。非線性，是指SVM擅長應付樣本數據線性不可分的情況，主要通過松弛變量（也叫懲罰變量）和核函數技術來實現，這一部分是SVM的精髓。關于文本分類這個問題究竟是不是線性可分的，尚沒有定論，因此不能簡單的認為它是線性可分的而作簡化處理，先當它是線性不可分的（反正線性可分也不過是線性不可分的一種特例）。其它概念高維模式識別是指樣本維數很高，例如文本的向量表示，如果沒有經過降維處理，出現幾萬維的情況很正常，其他算法基本就沒有能力應付了，SVM卻可以，主要是因為SVM產生的分類器很簡潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本），使得即使樣本維數很高，也不會給存儲和計算帶來大麻煩。線性判別函數和超平面線性分類器是最簡單也很有效的分類器形式。在一個線性分類器中，可以看到SVM形成的思路并接觸很多SVM的核心概念。用一個二維空間里僅有兩類樣本的分類問題來舉例。如下圖所示：線性函數C1和C2是要區分的兩個類別，在二維平面中它們的樣本如上圖所示。中間的直線就是一個分類函數，它可以將兩類樣本完全分開。一般的，如果一個線性函數能夠將樣本完全正確的分開，就稱這些數據是線性可分的，否則稱為非線性可分的。線性函數什么叫線性函數呢？在一維空間里就是一個點，在二維空間里就是一條直線，三維空間里就是一個平面，如果不關注空間的維數，這種線性函數還有一個統一的名稱——超平面（HyperPlane）。實際上，一個線性函數是一個實值函數（即函數的值是連續的實數），而我們的分類問題需要離散的輸出值，例如用1表示某個樣本屬于類別C1，而用0表示不屬于，這時候只需要簡單的在實值函數的基礎上附加一個閾值即可，通過分類函數執行時得到的值大于還是小于這個閾值來確定類別歸屬。線性函數

例如我們有一個線性函數：

g(x)=wx+b

取閾值為0，這樣當有一個樣本xi需要判別的時候，我們就看g(xi)的值。若g(xi)>0，就判別為類別C1，若g(xi)<0，則判別為類別C2（等于的時候就拒絕判斷）。此時也等價于給函數g(x)附加一個符號函數sgn()，即f(x)=sgn[g(x)]是我們真正的判別函數。線性函數注意：一，式中的x不是二維坐標系中的橫軸，而是樣本的向量表示，二，這個形式并不局限于二維的情況，在n維空間中仍然可以使用這個表達式，只是式中的w成為了n維向量（在二維的這個例子中，w是二維向量，為了表示起來方便簡潔）；三，g(x)不是中間那條直線的表達式，中間那條直線的表達式是g(x)=0，即wx+b=0，我們也把這個函數叫做分類面。間隔與幾何間隔中間那條分界線并不是唯一的，我們把它稍微旋轉一下，只要不把兩類數據分錯，仍然可以達到上面說的效果，稍微平移一下，也可以。此時就牽涉到一個問題，對同一個問題存在多個分類函數的時候，哪一個函數更好呢？顯然必須要先找一個指標來量化“好”的程度，通常使用的都是叫做“分類間隔”的指標。幾何間隔對于文本分類這樣的不適定問題（有一個以上解的問題稱為不適定問題），需要有一個指標來衡量解決方案（即我們通過訓練建立的分類模型）的好壞，而分類間隔是一個比較好的指標。在進行文本分類的時候，可以讓計算機這樣來看待我們提供給它的訓練樣本，每一個樣本由一個向量（那些文本特征所組成的向量）和一個標記（標示出這個樣本屬于哪個類別）組成。幾何間隔如：

Di=(xi,yi)

xi就是文本向量（維數很高），yi就是分類標記。在二元的線性分類中，這個表示分類的標記只有兩個值，1和-1（用來表示屬于還是不屬于這個類）。

定義一個樣本點到某個超平面的間隔：

δi=yi(wxi+b)幾何間隔首先注意到如果某個樣本屬于該類別的話，那么wxi+b>0，而yi也大于0；若不屬于該類別的話，那么wxi+b<0，而yi也小于0，這意味著yi(wxi+b)總是大于0的，而且它的值就等于|wxi+b|（也就是|g(xi)|）。現在把w和b進行一下歸一化，即用w/||w||和b/||w||分別代替原來的w和b，那么間隔就可以寫成：幾何間隔當用歸一化的w和b代替原值之后的間隔有一個專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點到超平面的歐氏距離，我們下面就簡稱幾何間隔為“距離”。圖更加直觀的展示出了幾何間隔的現實含義。H是分類面，而H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。幾何間隔與樣本誤分次數間的關系之所以如此關心幾何間隔這個東西，是因為幾何間隔與樣本的誤分次數間存在關系：其中的δ是樣本集合到分類面的間隔，R=max||xi||i=1,...,n，即R是所有樣本中向量長度最長的值。不必追究誤分次數的具體定義和推導過程，只要記得這個誤分次數一定程度上代表分類器的誤差。而從上式可以看出，誤分次數的上界由幾何間隔決定。由此說明為何要選擇幾何間隔來作為評價一個解優劣的指標，幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了我們訓練階段的目標。優化目標一個線性分類函數，有了判斷解優劣的標準——即有了優化的目標，這個目標就是最大化幾何間隔，但是一些關于SVM的論文的優化目標是要最小化||w||，這是怎么回事呢？間隔和幾何間隔的定義：間隔：δ=y(wx+b)=|g(x)|

幾何間隔：得：

δ=||w||δ幾何

幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||完全是一回事。常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是固定間隔（例如固定為1），尋找最小的||w||。求一個函數的最小值（或最大值）的問題都可以稱為尋優問題（也叫作一個規劃問題），又由于找最大值的問題總可以通過加一個負號變為找最小值的問題，因此下面討論針對找最小值的過程來進行。一個尋優問題最重要的部分是目標函數，就是指尋優的目標。目標函數例如尋找最小的||w||這件事，就可以用下面的式子表示：

但實際上對于這個目標，常常使用另一個完全等價的目標函數來代替，那就是：

不難看出當||w||2達到最小時，||w||也達到最小，反之亦然。這個式子是否能描述我們的問題呢？我們的問題是有一堆點，可以被分成兩類，我們要找出最好的分類面。如果直接來解這個求最小值問題，很容易看出當||w||=0的時候就得到了目標函數的最小值。但是無論給什么樣的數據，都是這個解。反映在圖中，就是H1與H2兩條直線間的距離無限大，這個時候，所有的樣本點（無論正樣本還是負樣本）都跑到了H1和H2中間。而我們原本的意圖是，H1右側的被分為正類，H2左側的被分為負類，位于兩類中間的樣本則拒絕分類（拒絕分類的另一種理解是分給哪一類都有道理，因而分給哪一類也都沒有道理）。但，所有樣本點都進入了無法分類的灰色地帶。約束條件造成這種結果的原因是在描述問題的時候只考慮了目標，而沒有加入約束條件。約束條件就是在求解過程中必須滿足的條件，體現在問題中就是樣本點必須在H1或H2的某一側（或者至少在H1和H2上），而不能跑到兩者中間。前文提到過把間隔固定為1，這是指把所有樣本點中間隔最小的那一點的間隔定為1，意味著集合中的其他點間隔都不會小于1，按照間隔的定義，滿足這些條件就相當于讓下面的式子總是成立：yi[(w·xi)+b]≥1(i=1,2,…,l)（l是總的樣本數）但我們常常習慣讓式子的值和0比較，因而經常用變換過的形式：

yi[(w·xi)+b]-1≥0(i=1,2,…,l)因此我們的兩類分類問題也被我們轉化成了它的數學形式，一個帶約束的最小值的問題：從最一般的定義上說，一個求最小值的問題就是一個優化問題，它同樣由兩部分組成，目標函數和約束條件，可以用下面的式子表示：

式1約束條件用函數c來表示。可以看出一共有p+q個約束條件，其中p個是不等式約束，q個等式約束。

式1式中的x是自變量，但不限定它的維數必須為1（視乎解決的問題空間維數）。要求f(x)在哪一點上取得最小值，不是在整個空間里找，而是在約束條件所劃定的一個有限的空間里找，這個有限的空間就是優化理論里所說的可行域。注意可行域中的每一個點都要求滿足所有p+q個條件，而不是滿足其中一條或幾條就可以，同時可行域邊界上的點有一個額外好的特性，它們可以使不等式約束取得等號。可行域還有個概念不得不提，那就是凸集：凸集是指有這么一個點的集合，其中任取兩個點連一條直線，這條線上的點仍然在這個合內部。再來看我們線性分類器問題的描述：

式2自變量就是w，而目標函數是w的二次函數，所有的約束條件都是w的線性函數。這種規劃問題有稱呼——二次規劃（QuadraticProgramming，QP），更進一步的說，由于它的可行域是一個凸集，因此它是一個凸二次規劃。凸二次規劃有全局最優解，由于我們想找的本來就是全局最優的解。對比（式2）和（式1）還可以發現，我們的線性分類器問題只有不等式約束，因此形式上看似乎比一般意義上的規劃問題要簡單，但解起來卻并非如此。讓我們再一次比較完整的重復一下要解決的問題：我們有屬于兩個類別的樣本點若干（并不限定這些點在二維空間中），如圖：圓形的樣本點定為正樣本，方形的點定為負類。我們想求得這樣一個線性函數（在n維空間中的線性函數）：g(x)=wx+b使得所有屬于正類的點x+代入以后有g(x+)≥1，而所有屬于負類的點x-代入后有g(x-)≤-1。代入g(x)后的值如果在1和-1之間，我們就拒絕判斷。求這樣的g(x)的過程就是求w（一個n維向量）和b（一個實數）兩個參數的過程。因此在求g(x)的時候，w才是變量。一旦求出了w（也就求出了b），那么中間的直線H就知道了，那么H1和H2也就知道了（因為三者是平行的，而且相隔的距離還是||w||決定的）。w是誰決定的？

顯然是已知的樣本決定的，一旦在空間中給出了那些個樣本點，三條直線的位置實際上就唯一確定了。樣本確定了w，用數學的語言描述，就是w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn式子中的αi是一個一個的數（在嚴格的證明過程中，α被稱為拉格朗日乘子），而xi是樣本點，因而是向量，n就是總樣本點的個數。為了方便描述，以下開始嚴格區別數字與向量的乘積和向量間的乘積，會用α1x1表示數字和向量的乘積，而用<x1,x2>表示向量x1,x2的內積。因此g(x)的表達式嚴格的形式應該是：g(x)=<w,x>+b上面的式子還不夠好，回想圖中正樣本和負樣本的位置，想像一下，不動所有點的位置，而只是把其中一個正樣本點定為負樣本點，結果怎么樣？三條直線都必須移動。這說明w不僅跟樣本點的位置有關，還跟樣本的類別有關（也就是和樣本的“標簽”有關）。因此用下面這個式子表示才算完整：

w=α1y1x1+α2y2x2+…+αnynxn其中的yi就是第i個樣本的標簽，它等于1或者-1。其實以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才對w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類函數。更嚴格的說，這些樣本的一部分就可以確定，例如確定一條直線，只需要兩個點就可以，即便有三五個都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點，就叫做支持（撐）向量。式子也可以用求和符號簡寫一下：因此原來的g(x)表達式可以寫為：注意式子中x才是變量，也就是要分類的，就把該文檔的向量表示代入到x的位置，而所有的xi統統都是已知的樣本。還注意到式子中只有xi和x是向量，因此一部分可以從內積符號中拿出來，得到g(x)的式子為：核函數與松弛變量之前一直在討論的線性分類器，只能對線性可分的樣本做處理。如果提供的樣本線性不可分，結果很簡單，線性分類器的求解程序會無限循環，永遠也解不出來。這必然使得它的適用范圍大大縮小，而它的很多優點我們實在不原意放棄，怎么辦呢？是否有某種方法，讓線性不可分的數據變得線性可分呢？有！其思想說來也簡單，來用一個二維平面中的分類問題作例子，一看就會明白。把橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負類。試問能找到一個線性函數把兩類正確分開么？不能，因為二維空間里的線性函數就是指直線，顯然找不到符合條件的直線。但我們可以找到一條曲線，例如下面這一條：顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類別（你在橫軸上隨便找一點，算算這一點的函數值，會發現負類的點函數值一定比0大，而正類的一定比0小）。這條曲線就是我們熟知的二次曲線，它的函數表達式可以寫為：這條曲線就是我們熟知的二次曲線，它的函數表達式可以寫為：問題只是它不是一個線性函數，但是，新建一個向量y和a：這樣g(x)就可以轉化為f(y)=<a,y>實際上f(y)的形式就是：g(x)=f(y)=ay在任意維度的空間中，這種形式的函數都是一個線性函數（其中的a和y都是多維向量），因為自變量y的次數不大于1。二維空間中一個線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉化，使其變得線性可分。而轉化最關鍵的部分就在于找到x到y的映射方法。遺憾的是，如何找到這個映射，沒有系統性的方法。具體到文本分類問題，文本被表示為上千維的向量，即使維數已經如此之高，也常常是線性不可分的，還要向更高的空間轉化。其中的難度可想而知。用一個具體文本分類的例子來看看這種向高維空間映射從而分類的方法如何運作，想象一下，我們文本分類問題的原始空間是1000維的（即每個要被分類的文檔被表示為一個1000維的向量），在這個維度上問題是線性不可分的。現在我們有一個2000維空間里的線性函數:

f(x’)=<w’,x’>+b式中的w’和x’都是2000維的向量，只不過w’是定值，而x’是變量。現在我們的輸入，是一個1000維的向量x，分類的過程是先把x變換為2000維的向量x’，然后求這個變換后的向量x’與向量w’的內積，再把這個內積的值和b相加，就得到了結果，看結果大于閾值還是小于閾值就得到了分類結果。我們其實只關心那個高維空間里內積的值，那個值算出來了，分類結果就算出來了。而從理論上說，x’是經由x變換來的，因此廣義上可以把它叫做x的函數。而w’是常量，它是一個低維空間里的常量w經過變換得到的，所以給了一個w和x的值，就有一個確定的f(x’)值與其對應。這讓我們幻想，是否能有這樣一種函數K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內積值<w’,x’>？如果有這樣的函數，那么當給了一個低維空間的輸入x以后，

g(x)=K(w,x)+b

f(x’)=<w’,x’>+b這兩個函數的計算結果就完全一樣，就用不著費力找那個映射關系，直接拿低維的輸入往g(x)里面代就可以了。這回的g(x)就不是線性函數啦，因為不能保證K(w,x)這個表達式里的x次數不高于1。萬幸，這樣的K(w,x)確實存在，它被稱作核函數（核，kernel）。核函數核函數的基本作用就是接受兩個低維空間里的向量，能夠計算出經過某個變換后在高維空間里的向量內積值。回顧之前求的線性分類器，它的形式應該是：現在這個就是高維空間里的線性函數（為了區別低維和高維空間里的函數和向量，改了函數的名字，并且給w和x都加上了）。我們就可以用一個低維空間里的函數來代替（這個低維空間里的函數就不再是線性的了）：f(x’)和g(x)里的α，y，b全都是一樣一樣的。這就是說，盡管給的問題是線性不可分的，但是我們就硬當它是線性問題來求解。只不過求解過程中，凡是要求內積的時候就用我們選定的核函數來算。這樣求出來的α再和選定的核函數一組合，就得到分類器啦！對核函數的選擇，現在還缺乏指導原則！各種實驗的觀察結果的確表明，某些問題用某些核函數效果很好，用另一些就很差。松弛變量如果使用核函數向高維空間映射后，問題仍然是線性不可分的，那怎么辦？現在我們已經把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的。就像下圖這樣：現在想象我們有另一個訓練集，只比原先這個訓練集多了一個數據點，映射到高維空間以后（也使用相同的核函數），也就多了一個樣本點，但是這個樣本的位置是這樣的：就是圖中黃色那個點，它是方形的，是負類的一個樣本，這單獨的一個樣