支持向量機SVM

1.1 SVM 概念

支持向量機SVM是一種原創性（非組合）的具有明顯直觀幾何意義的分類演算法，具有較高的準確率。源於Vapnik和Chervonenkis關於統計學習的早期工作（1971年），第一篇有關論文由Boser、Guyon、Vapnik發表在1992年。思想直觀，但細節異常複雜，內容涉及凸分析演算法，核函數，神經網路等高深的領域。通俗來講，它是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，即支持向量機的學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。

其思路是簡單情況，線性可分，把問題轉化為一個凸優化問題，可以用拉格朗日乘子法簡化，然後用既有的演算法解決。複雜情況，線性丌可分，用映射函數將樣本投射到高維空間，使其變成線性可分的情形。利用核函數來減少高維度計算量。

問題的提出：最優分離平面（決策邊界）

最大邊緣超平面（MMH）

    這裡我們考慮的是一個兩類的分類問題，數據點用 x 來表示，這是一個 n 維向量，w^T中的T代表轉置，而類別用 y 來表示，可以取 1 或者 -1 ，分別代表兩個不同的類。一個線性分類器的學習目標就是要在 n 維的數據空間中找到一個分類超平面，其方程可以表示為： 

 1.2 1或-1分類標準的起源：logistic回歸

    形式化表示就是 假設函數其中x是n維特征向量，函數g就是 logistic函數。， 而的圖像如下所示，將無窮映射到了(0,1)。

 而假設logistic函數就是特征屬於y=1的概率則有

當我們要判別一個新來的特征屬於哪個類時，只需求，若大於0.5就是y=1的類，反之屬於y=0類。

    只和有關，若>0，則，此時該特征屬於y=1類。g(z)只不過是用來映射，真實的類別決定權還在。還有當時，=1，反之=0。

如果我們只從出發，希望模型達到的目標無非就是讓訓練數據中y=1的特征， 而y=0的特征。 Logistic回歸就是要學習得到，使得正例的特征遠大於0，負例的特征遠小於0，強調在全部訓練實例上達到這個目標。

1.3 形式化標示

    這次使用的標簽是y=-1,y=1，替換在logistic回歸中使用的y=0和y=1。同時將替換成w和b。以前的，其中認為。現在我們替換為b，後面替換為（即）。這樣，我們讓，進一步。也就是說除了y由y=0變為y=-1，只是標記不同外，與logistic回歸的形式化表示沒區別。

    再明確下假設函數   

    上面提到過我們只需考慮的正負問題，而不用關心g(z)，因此我們這裡將g(z)做一個簡化，將其簡單映射到y=-1和y=1上。映射關係如下：

SVM的線性分類實際就是找gap最大，即決策邊界距離最遠

設x1,x2分別為上支撐邊界和下支撐邊界的兩點，則滿足兩式相減後根據內積定義，則可得到即，由上圖可得綜合有，此時問題就就變成了凸優化問題。凸優化可以由拉格朗日乘子法解決。

2.2 拉格朗日乘子法

背景：拉格朗日乘子法的幾何解釋

其中f(x,y)目標函數的投影，g(x,y)=c為約束條件。當相切點的目標函數梯度與約束條件函梯度互為相反數時，此時目標函數在此約束下達到最優。但是拉格朗日乘子法適用於約束條件等式成立。故解決此凸優化問題需要KTT條件。

2.3 KTT條件

KTT條件適用於以下優化問題

 其中，f(x)是需要最小化的函數，h(x)是等式約束，g(x)是不等式約束，p和q分別為等式約束和不等式約束的數量。同時，我們得明白以下兩個定理

• KKT條件的意義：它是一個非線性規劃（Nonlinear Programming）問題能有最優化解法的必要和充分條件。

  那到底什麼是所謂Karush-Kuhn-Tucker條件呢？KKT條件就是指上面最優化數學模型的標準形式中的最小點 x* 必須滿足下麵的條件：

經過論證，該問題是滿足 KKT 條件的（首先已經滿足Slater condition，再者f和gi也都是可微的，即L對w和b都可導），因此現在我們便轉化為求解第二個問題。即原問題通過滿足一定的條件，已經轉化成了對偶問題。求解這個對偶學習問題，分為3個步驟，首先要讓L(w，b，a) 關於w和b最小化，然後求對α的極大，最後利用SMO演算法求解對偶因數。

2.4 簡化為對偶問題

 將以上的梯度計算結果重新代入到拉格朗日函數

此時拉格朗日函數化簡為對偶問題，

顯然比之前的凸優化問題簡潔，可以用各種凸優化演算法加以解決，只有支持向量參與計算，所以計算規模遠低於我們的想象。拉格朗日函數只包含了一個變數，求對的極大，即可以求得關於對偶問題的最優化問題。根據，便能求出w和b。那麼分類函數也就可以輕而易舉的求出來了。

對偶公式中的未知數僅涉及拉格朗日乘子，而原問題中未知數還包含決策邊界幾何特征參數，未知數太多。待定乘子中實質有徆多為0，僅在“支持向量”處不為0，所以最後的出的函數表達式進比想象中簡單（但問題是預先無法知道哪些樣本點是“支持向量”）、

 2.5 SMO演算法

    對 拉格朗日乘子的值可能依然心存疑惑。實際上，關於的求解可以用一種快速學習演算法即SMO演算法，這裡先簡要介紹下。SMO演算法由Microsoft Research的John C. Platt在1998年提出，併成為最快的二 次規劃優化演算法，特別針對線性SVM和數據稀疏時性能更優。基本思路是每次只更新兩個乘子，迭代獲得最終解。計算流程可表示如下

具體的迭代過程和方法詳述可參照 JerryLead http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html

3.1 線性不可分的情形

接下來談談線性不可分的情況，因為線性可分這種假設實在是太有局限性了：下圖就是一個典型的線性不可分的分類圖，我們沒有辦法用一條直線去將其分成兩個區域，每個區域只包含一種顏色的點。 要想在這種情況下的分類器，有兩種方式，一種是用曲線去將其完全分開，曲線就是一種非線性的情況，跟之後將談到的核函數有一定的關係。 

3.1.1增加鬆弛變數和懲罰函數

另外一種還是用直線，不過不用去保證可分性，就是包容那些分錯的情況，不過我們得加入懲罰函數，使得點分錯的情況越合理越好。其實在很多時候，不是在訓練的時候分類函數越完美越好，因為訓練函數中有些數據本來就是雜訊，可能就是在人工加上分類標簽的時候加錯了，如果我們在訓練（學習）的時候把這些錯誤的點學習到了，那麼模型在下次碰到這些錯誤情況的時候就難免出錯了（假如老師給你講課的時候，某個知識點講錯了，你還信以為真了，那麼在考試的時候就難免出錯）。這種學習的時候學到了“雜訊”的過程就是一個過擬合（over-fitting），這在機器學習中是一個大忌，我們寧願少學一些內容，也堅決杜絕多學一些錯誤的知識。還是回到主題，用直線怎麼去分割線性不可分的點：

 我們可以為分錯的點加上一點懲罰，對一個分錯的點的懲罰函數就是這個點到其正確位置的距離 。在上圖中，藍色、紅色的直線分別為支持向量所在的邊界，綠色的線為決策函數，那些紫色的線表示分錯的點到其相應的決策面的距離，這樣我們可以在原函數上面加上一個懲罰函數，並且帶上其限制條件為

公式中藍色的部分為線上性可分問題的基礎上加上的懲罰函數部分，當xi在錯誤一邊的時候，若C的值很大那麼想要獲取最小值，只需要使得越小越好那麼就會越趨近1，也就是分錯點到決策面的距離越小。 當xi在正確一邊的時候，ε=0，R為全部的點的數目，C是一個由用戶去指定的繫數，表示對分錯的點加入多少的懲罰，當C很大的時候，分錯的點就會更少，但是過擬合的情況可能會比較嚴重，當C很小的時候，分錯的點可能會很多，不過可能由此得到的模型也會不太正確，所以如何選擇C是有很多學問的，不過在大部分情況下就是通過經驗嘗試得到的。

接下來就是同樣的，求解一個拉格朗日對偶問題，得到一個原問題的對偶問題的表達式：

 藍色的部分是與線性可分的對偶問題表達式的不同之處。線上性不可分情況下得到的對偶問題，不同的地方就是α的範圍從[0, +∞)，變為了[0, C]，增加的懲罰ε沒有為對偶問題增加什麼複雜度。

 3.1.2 核函數

  剛剛在談不可分的情況下，提了一句，如果使用某些非線性的方法，可以得到將兩個分類完美劃分的曲線，比如接下來將要說的核函數。

    我們可以讓空間從原本的線性空間變成一個更高維的空間，在這個高維的線性空間下，再用一個超平面進行劃分。這兒舉個例子，來理解一下如何利用空間的維度變得更高來幫助我們分類的（例子以及圖片來自pluskid的kernel函數部分）：

    下圖是一個典型的線性不可分的情況

 但是當我們把這兩個類似於橢圓形的點映射到一個高維空間後，映射函數為：    用這個函數可以將上圖的平面中的點映射到一個三維空間（z1,z2,z3)，並且對映射後的坐標加以旋轉之後就可以得到一個線性可分的點集了。

  用另外一個哲學例子來說：世界上本來沒有兩個完全一樣的物體，對於所有的兩個物體，我們可以通過增加維度來讓他們最終有所區別，比如說兩本書，從(顏色，內容)兩個維度來說，可能是一樣的，我們可以加上 作者 這個維度，是在不行我們還可以加入 頁碼，可以加入 擁有者，可以加入 購買地點，可以加入 筆記內容等等。當維度增加到無限維的時候，一定可以讓任意的兩個物體可分了。

  回憶剛剛得到的對偶問題表達式：

公式中紅字的地斱要使用映射後的樣本向量代替做內積,最初的特征是n維的，我們將其映射到n^2維，然後再計算，這樣需要的時間從原先的O（n）變成O（n^2）,這樣就造成了災難維度

造成災難維度後就需要核函數出馬了。其中令映射到高維函數為左圖，核函數k(x,z)如右圖，這時發現只計算原始樣本x和z內積的平方（時間複雜度是O(n)），就等價於計算映射後高維樣本的內積。計算兩個向量在隱式映射過後的空間中的內積的函數叫做核函數 (Kernel Function) 。

例子1：

例子2：

核函數能簡化映射空間的內積運算，而恰好SVM中的數量計算是由內積形式表出的。則根據在低維空間的分類函數，可得

則關於a的對偶最優化問題就可表示為

這樣對偶優化問題的計算問題就解決了，避開了在高維空間中的計算，但是計算結果是相同的。當然，因為我們這裡的例子非常簡單，所以我可以構造出對應於的核函數出來，如果對於任意一個映射，想要構造出對應的核函數就很困難了。所以需要驗證高維映射構造出的核函數的有效性。

4.1 核函數有效判定

問題：給定一個函數K，我們能否使用K來替代計算，也就說，是否能夠找出一個，使得對於所有的x和z，都有？

比如給出了，是否能夠認為K是一個有效的核函數。

下麵來解決這個問題，給定m個訓練樣本，每一個對應一個特征向量。那麼，我們可以將任意兩個和帶入K中，計算得到。I可以從1到m，j可以從1到m，這樣可以計算出m*m的核函數矩陣（Kernel Matrix）。為了方便，我們將核函數矩陣和都使用K來表示。

如果假設K是有效地核函數，那麼根據核函數定義

可見，矩陣K應該是個對稱陣。讓我們得出一個更強的結論，首先使用符號來表示映射函數的第k維屬性值。那麼對於任意向量z，得

最後一步和前面計算時類似。從這個公式我們可以看出，如果K是個有效的核函數（即和等價），那麼，在訓練集上得到的核函數矩陣K應該是半正定的（）

這樣我們得到一個核函數的必要條件：

K是有效的核函數 ==> 核函數矩陣K是對稱半正定的。

可幸的是，這個條件也是充分的，由Mercer定理來表達。

Mercer定理：

如果函數K是上的映射（也就是從兩個n維向量映射到實數域）。那麼如果K是一個有效核函數（也稱為Mercer核函數），那麼當且僅當對於訓練樣例，其相應的核函數矩陣是對稱半正定的。

Mercer定理表明為了證明K是有效的核函數，那麼我們不用去尋找，而只需要在訓練集上求出各個，然後判斷矩陣K是否是半正定（使用左上角主子式大於等於零等方法）即可。

以上僅能作為支持向量的學習筆記

參考 博客園JerryLead,C博客Mac Track 以及煉數成金機器學習支持向量機內容