# 支持向量機 ##第一層、了解SVM 支持向量機，因其英文名為support vector machine，故一般簡稱SVM，通俗來講，它是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。 ###*1.1、線性分類* 理解SVM，咱們必須先弄清楚一個概念：線性分類器。 ####1.1.1、分類標準 考慮一個二類的分類問題，數據點用x來表示，類別用y來表示，可以取1或者-1，分別代表兩個不同的類，且是一個n 維向量，w^T中的T代表轉置。一個線性分類器的學習目標就是要在n維的數據空間中找到一個分類[超平面][a]，其方程可以表示為： [a]:http://zh.wikipedia.org/wiki/%E8%B6%85%E5%B9%B3%E9%9D%A2  可能有讀者對類別取1或-1有疑問，事實上，這個1或-1的分類標準起源于logistic回歸，為了過渡的自然性，咱們就再來看看這個logistic回歸。 ####1.1.2、1或-1分類標準的起源：logistic回歸 Logistic回歸目的是從特征學習出一個0/1分類模型，而這個模型是將特性的線性組合作為自變量，由于自變量的取值范圍是負無窮到正無窮。因此，使用logistic函數（或稱作sigmoid函數）將自變量映射到(0,1)上，映射后的值被認為是屬于y=1的概率。 假設函數  其中x是n維特征向量，函數g就是logistic函數。 而的圖像是  可以看到，通過logistic函數將自變量從無窮映射到了(0,1)，而假設函數就是特征屬于y=1的概率。  從而，當我們要判別一個新來的特征屬于哪個類時，只需求，若大于0.5就是y=1的類，反之屬于y=0類。 再審視一下，發現只和有關，>0，那么>0.5，g(z)只不過是用來映射，真實的類別決定權還在。還有當>>0時，=1，反之=0。如果我們只從出發，希望模型達到的目標無非就是讓訓練數據中y=1的特征>>0，而是y=0的特征<<0。Logistic回歸就是要學習得到，使得正例的特征遠大于0，負例的特征遠小于0，強調在全部訓練實例上達到這個目標。 ####1.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上。映射關系如下：  于此，想必已經解釋明白了為何線性分類的標準一般用1 或者-1 來標示。 ###*1.2、線性分類的一個例子* 假定現在有一個一個二維平面，如下圖所示，平面上有兩種不同的點，分別用兩種不同的顏色表示，一種為紅顏色的點，另一種為藍顏色的點，如果我們要在這個二維平面上找到一個可行的超平面的話，那么這個超平面可以是下圖中那根紅顏色的線(在二維空間中，超平面就是一條直線)。  從上圖中我們可以看出，這條紅顏色的線作為一個超平面，把紅顏色的點和藍顏色的點分開來了，在超平面一邊的數據點所對應的y全是 -1 ，而在另一邊全是1。 接著，我們可以令分類函數：  顯然，如果 f(x)=0 ，那么x是位于超平面上的點。我們不妨要求對于所有滿足 f(x)<0 的點，其對應的 y 等于 -1 ，而 f(x)>0 則對應 y=1 的數據點。  注：上圖中，定義特征到結果的輸出函數，與我們之前定義的實質是一樣的。為什么？因為無論是，還是，不影響最終優化結果。下文你將看到，當我們轉化到優化的時候，為了求解方便，會把yf(x)令為1，即yf(x)是y(w^x + b)，還是y(w^x - b)，對我們要優化的式子max1/||w||已無影響。 從而在我們進行分類的時候，將數據點 x代入 f(x) 中，如果得到的結果小于 0 ，則賦予其類別 -1 ，如果大于 0 則賦予類別 1 。如果 f(x)=0，則很難辦了，分到哪一類都不是。 此外，有些時候，或者說大部分時候數據并不是線性可分的，這時滿足這樣條件的超平面可能就根本不存在，這里咱們先從最簡單的情形開始推導，就假設數據都是線性可分的，亦即這樣的超平面是存在的。 ###*1.3、函數間隔Functional margin與幾何間隔Geometrical margin* 一般而言，一個點距離超平面的遠近可以表示為分類預測的確信或準確程度。 * 在超平面w\*x+b=0確定的情況下，|w\*x+b|能夠相對的表示點x到距離超平面的遠近，而w\*x+b的符號與類標記y的符號是否一致表示分類是否正確，所以，可以用量y\*(w\*x+b)的正負性來判定或表示分類的正確性和確信度。 于此，我們便引出了定義樣本到分類間隔距離的函數間隔functional margin的概念。 ####1.3.1、函數間隔Functional margin 我們定義函數間隔functional margin 為：  接著，我們定義超平面(w，b)關于訓練數據集T的函數間隔為超平面(w，b)關于T中所有樣本點(xi，yi)的函數間隔最小值，其中，x是特征，y是結果標簽，i表示第i個樣本，有： = mini (i=1，...n) 然與此同時，問題就出來了：上述定義的函數間隔雖然可以表示分類預測的正確性和確信度，但在選擇分類超平面時，只有函數間隔還遠遠不夠，因為如果成比例的改變w和b，如將他們改變為2w和2b，雖然此時超平面沒有改變，但函數間隔的值f(x)卻變成了原來的2倍。 事實上，我們可以對法向量w加些約束條件，使其表面上看起來規范化，如此，我們很快又將引出真正定義點到超平面的距離--幾何間隔geometrical margin的概念（很快你將看到，幾何間隔就是函數間隔除以個||w||，即yf(x) / ||w||）。 ####1.3.2、點到超平面的距離定義：幾何間隔Geometrical margin 對于一個點 x ，令其垂直投影到超平面上的對應的為 x0 ，w 是垂直于超平面的一個向量，為樣本x到分類間隔的距離，  我們有  其中，||w||表示的是范數。 又由于 x0 是超平面上的點，滿足 f(x0)=0 ，代入超平面的方程即可算出：  不過這里的是帶符號的，我們需要的只是它的絕對值，因此類似地，也乘上對應的類別 y即可，因此實際上我們定義 幾何間隔geometrical margin 為(注：別忘了，上面的定義，=y(wTx+b)=yf(x) )：  代人相關式子可以得出：yi*(w/||w|| + b/||w||)。 綜上，函數間隔y*(wx+b)=y*f(x)實際上就是|f(x)|，只是人為定義的一個間隔度量；而幾何間隔|f(x)|/||w||才是直觀上的點到超平面距離。 ###*1.4、最大間隔分類器Maximum Margin Classifier的定義* 由上，我們已經知道，函數間隔functional margin 和 幾何間隔geometrical margin 相差一個的縮放因子。按照我們前面的分析，對一個數據點進行分類，當它的 margin 越大的時候，分類的 confidence 越大。對于一個包含 n 個點的數據集，我們可以很自然地定義它的 margin 為所有這n個點的 margin 值中最小的那個。于是，為了使得分類的 confidence 高，我們希望所選擇的超平面hyper plane 能夠最大化這個 margin 值。  且 1. functional margin 明顯是不太適合用來最大化的一個量，因為在 hyper plane 固定以后，我們可以等比例地縮放 w 的長度和 b 的值，這樣可以使得的值任意大，亦即 functional margin可以在 hyper plane 保持不變的情況下被取得任意大， 2. 而 geometrical margin 則沒有這個問題，因為除上了這個分母，所以縮放 w 和 b 的時候的值是不會改變的，它只隨著 hyper plane 的變動而變動，因此，這是更加合適的一個 margin 。 這樣一來，我們的 maximum margin classifier 的目標函數可以定義為：  當然，還需要滿足一定的約束條件：  其中 (等價于= /||w||，故有稍后的 =1 時， = 1 / ||w||)，處于方便推導和優化的目的，我們可以令=1(對目標函數的優化沒有影響) ，此時，上述的目標函數轉化為：  其中，s.t.，即subject to的意思，它導出的是約束條件。 通過求解這個問題，我們就可以找到一個 margin 最大的 classifier ，通過最大化 margin ，我們使得該分類器對數據進行分類時具有了最大的 confidence，從而設計決策最優分類超平面。 如下圖所示，中間的紅色線條是 Optimal Hyper Plane ，另外兩條線到紅線的距離都是等于的(便是上文所定義的geometrical margin，當令=1時，便為1/||w||，而我們上面得到的目標函數便是在相應的約束條件下，要最大化這個1/||w||值)：  ###*1.5、到底什么是Support Vector* 通過上節1.4節最后一張圖：  我們可以看到兩個支撐著中間的 gap 的超平面，到中間的純紅線separating hyper plane 的距離相等，即我們所能得到的最大的 geometrical margin，而“支撐”這兩個超平面的必定會有一些點，而這些“支撐”的點便叫做支持向量Support Vector。 換言之，Support Vector便是下圖中那藍色虛線和粉紅色虛線上的點： [b]:http://ijcai13.org/files/tutorial_slides/te2.pdf  很顯然，由于這些 supporting vector 剛好在邊界上，所以它們滿足，而對于所有不是支持向量的點，也就是在“陣地后方”的點，則顯然有。 ##第二層、深入SVM ### 2.1、從線性可分到線性不可分 ####*2.1.1、從原始問題到對偶問題的求解* 根據我們之前得到的目標函數（subject to導出的則是約束條件）：  由于求的最大值相當于求的最小值，所以上述目標函數等價于：  - 這樣，我們的問題成為了一個凸優化問題，因為現在的目標函數是二次的，約束條件是線性的，所以它是一個凸二次規劃問題。這個問題可以用任何現成的 [QP (Quadratic Programming)](http://en.wikipedia.org/wiki/Quadratic_programming) 的優化包進行求解，一言以蔽之：在一定的約束條件下，目標最優，損失最小。 - 進一步，雖然這個問題確實是一個標準的 QP 問題，但由于它的特殊結構，我們可以通過 [Lagrange Duality](http://en.wikipedia.org/wiki/Lagrange_duality#The_strong_Lagrangian_principle:_Lagrange_duality) 變換到對偶變量 (dual variable) 的優化問題，這樣便可以找到一種更加有效的方法來進行求解，而且通常情況下這種方法比直接使用通用的 QP 優化包進行優化要高效得多。 換言之，除了用解決QP問題的常規方法之外，還可以通過求解對偶問題得到最優解，這就是線性可分條件下支持向量機的對偶算法，這樣做的優點在于：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。 那什么是Lagrange duality？簡單地來說，通過給每一個約束條件加上一個 Lagrange multiplier(拉格朗日乘值)，即引入拉格朗日乘子，如此我們便可以通過拉格朗日函數將約束條件融和到目標函數里去(也就是說把條件融合到一個函數里頭，現在只用一個函數表達式便能清楚的表達出我們的問題)：  然后我們令  容易驗證： - 當某個約束條件不滿足時，例如，那么我們顯然有（只要令即可）。 - 而當所有約束條件都滿足時，則有，亦即我們最初要最小化的量。 因此，在要求約束條件得到滿足的情況下最小化，實際上等價于直接最小化（當然，這里也有約束條件，就是≥0,i=1,…,n） ，因為如果約束條件沒有得到滿足，會等于無窮大，自然不會是我們所要求的最小值。 具體寫出來，我們現在的目標函數變成了：  這里用表示這個問題的最優值，這個問題和我們最初的問題是等價的。不過，現在我們來把最小和最大的位置交換一下：  當然，交換以后的問題不再等價于原問題，這個新問題的最優值用來表示。并且，我們有≤ ，這在直觀上也不難理解，最大值中最小的一個總也比最小值中最大的一個要大。總之，第二個問題的最優值在這里提供了一個第一個問題的最優值的一個下界，在滿足某些條件的情況下，這兩者相等，這個時候我們就可以通過求解第二個問題來間接地求解第一個問題。 也就是說，下面我們可以先求L 對w、b的極小，再求L 對的極大。而且，之所以從minmax的原始問題，轉化為maxmin的對偶問題，一者因為是的近似解，二者，轉化為對偶問題后，更容易求解。 ####*2.1.2、KKT條件* 與此同時，上段說“在滿足某些條件的情況下”，這所謂的“滿足某些條件”就是要滿足KKT條件。那KKT條件的表現形式是什么呢？ 據維基百科：[KKT 條件](http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions)的介紹，一般地，一個最優化數學模型能夠表示成下列標準形式：  其中，f(x)是需要最小化的函數，h(x)是等式約束，g(x)是不等式約束，p和q分別為等式約束和不等式約束的數量。同時，我們得明白以下兩個定理： * 凸優化的概念：為一凸集，  為一凸函數。凸優化就是要找出一點 ，使得每一  滿足 。 * KKT條件的意義：它是一個非線性規劃（Nonlinear Programming）問題能有最優化解法的必要和充分條件。 而KKT條件就是指上面最優化數學模型的標準形式中的最小點 x* 必須滿足下面的條件：  經過論證，我們這里的問題是滿足 KKT 條件的（首先已經滿足Slater condition，再者f和gi也都是可微的，即L對w和b都可導），因此現在我們便轉化為求解第二個問題。 也就是說，現在，咱們的原問題通過滿足一定的條件，已經轉化成了對偶問題。而求解這個對偶學習問題，分為3個步驟，首先要讓L(w，b，a) 關于 w 和 b 最小化，然后求對α的極大，最后利用SMO算法求解對偶因子。 ####*2.1.3、對偶問題求解的3個步驟* **1）**、首先固定，要讓 L 關于 w 和 b 最小化，我們分別對w，b求偏導數，即令 ?L/?w 和 ?L/?b 等于零（對w求導結果的解釋請看本文評論下第45樓回復）：  以上結果代回上述的 L：  得到：  提醒：有讀者可能會問上述推導過程如何而來？說實話，其具體推導過程是比較復雜的，如下圖所示：  最后，得到：  如 jerrylead所說：“倒數第4步”推導到“倒數第3步”使用了線性代數的轉置運算，由于ai和yi都是實數，因此轉置后與自身一樣。“倒數第3步”推導到“倒數第2步”使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法運算法則。最后一步是上一步的順序調整。 L( 從上面的最后一個式子，我們可以看出，此時的拉格朗日函數只包含了一個變量，那就是，然后下文的第2步，求出了便能求出w，和b，由此可見，上文第1.2節提出來的核心問題：分類函數也就可以輕而易舉的求出來了。 **2）**、求對的極大，即是關于對偶問題的最優化問題，從上面的式子得到： (不得不提醒下讀者：經過上面第一個步驟的求w和b，得到的拉格朗日函數式子已經沒有了變量w，b，只有，而反過來，求得的將能導出w，b的解，最終得出分離超平面和分類決策函數。為何呢？因為如果求出了，根據，即可求出w。然后通過，即可求出b )  **3）**、如前面所說，這個問題有更加高效的優化算法，即我們常說的SMO算法。 ####*2.1.4、序列最小最優化SMO算法* 細心的讀者讀至上節末尾處，怎么拉格朗日乘子的值可能依然心存疑惑。實際上，關于的求解可以用一種快速學習算法即SMO算法，這里先簡要介紹下。 OK，當：  要解決的是在參數上求最大值W的問題，至于和都是已知數（其中 是一個參數，用于控制目標函數中兩項（“尋找 margin 最大的超平面”和“保證數據點偏差量最小”）之間的權重。和上文最后的式子對比一下，可以看到唯一的區別就是現在 dual variable  多了一個上限 C ，關于C的具體由來請查看下文第2.3節）。 要了解這個SMO算法是如何推導的，請跳到下文第3.5節、SMO算法。 到目前為止，我們的 SVM 還比較弱，只能處理線性的情況，下面我們將引入核函數，進而推廣到非線性分類問題。 ###2.2、核函數Kernel ####*2.2.1、特征空間的隱式映射：核函數* 在線性不可分的情況下，支持向量機通過某種事先選擇的非線性映射(核函數)將輸入變量映射到一個高維特征空間，在這個空間中構造最優分類超平面。我們使用SVM進行數據集分類工作的過程首先是同預先選定的一些非線性映射將輸入空間映射到高維特征空間(下圖很清晰的表達了通過映射到高維特征空間，而把平面上本身不好分的非線性數據分了開來)：  使得在高維屬性空間中有可能最訓練數據實現超平面的分割，避免了在原輸入空間中進行非線性曲面分割計算，且在處理高維輸入空間的分類時，這種方法尤其有效，其工作原理如下圖所示：  而在我們遇到核函數之前，如果用原始的方法，那么在用線性學習器學習一個非線性關系，需要選擇一個非線性特征集，并且將數據寫成新的表達形式，這等價于應用一個固定的非線性映射，將數據映射到特征空間，在特征空間中使用線性學習器，因此，考慮的假設集是這種類型的函數：  這里?：X->F是從輸入空間到某個特征空間的映射，這意味著建立非線性學習器分為兩步： 1. 首先使用一個非線性映射將數據變換到一個特征空間F， 2. 然后在特征空間使用線性學習器分類。 這意味著假設可以表達為訓練點的線性組合，因此決策規則可以用測試點和訓練點的內積來表示：  如果有一種方式可以在特征空間中直接計算內積〈φ(xi · φ(x)〉，就像在原始輸入點的函數中一樣，就有可能將兩個步驟融合到一起建立一個非線性的學習器，這樣直接計算法的方法稱為核函數方法，于是，核函數便橫空出世了。 定義：核是一個函數K，對所有x，z(-X，滿足，這里φ是從X到內積特征空間F的映射。 ####*2.2.2、核函數：如何處理非線性數據* 我們已經知道，如果是線性方法，所以對非線性的數據就沒有辦法處理。舉個例子來說，則是如下圖所示的兩類數據，分別分布為兩個圓圈的形狀，這樣的數據本身就是線性不可分的，此時咱們該如何把這兩類數據分開呢？  此時，一個理想的分界應該是一個“圓圈”而不是一條線（超平面）。如果用 X1 和 X2 來表示這個二維平面的兩個坐標的話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：  如果我們構造另外一個五維的空間，其中五個坐標的值分別為 Z1=X1, Z2=X21, Z3=X2, Z4=X22, Z5=X1X2，那么顯然，上面的方程在新的坐標系下可以寫作：  關于新的坐標 Z ，這正是一個 hyper plane 的方程！也就是說，如果我們做一個映射 ?:R2→R5 ，將 X 按照上面的規則映射為 Z ，那么在新的空間中原來的數據將變成線性可分的，從而使用之前我們推導的線性分類算法就可以進行處理了。這正是 Kernel 方法處理非線性問題的基本思想。 再進一步描述 Kernel 的細節之前，不妨再來看看這個例子映射過后的直觀例子。具體來說，我這里的超平面實際的方程是這個樣子（圓心在 X2 軸上的一個正圓）：  因此我只需要把它映射到 Z1=X21, Z2=X22, Z3=X2 這樣一個三維空間中即可，下圖即是映射之后的結果，將坐標軸經過適當的旋轉，就可以很明顯地看出，數據是可以通過一個平面來分開的：  回憶一下，我們上一次2.1節中得到的最終的分類函數是這樣的：  映射過后的空間是：  而其中的 α 也是通過求解如下 dual 問題而得到的：  這樣一來問題就解決了嗎？其實稍想一下就會發現有問題：在最初的例子里，我們對一個二維空間做映射，選擇的新空間是原始空間的所有一階和二階的組合，得到了五個維度；如果原始空間是三維，那么我們會得到 19 維的新空間，這個數目是呈爆炸性增長的，這給 ?(?) 的計算帶來了非常大的困難，而且如果遇到無窮維的情況，就根本無從計算了。所以就需要 Kernel 出馬了。 還是從最開始的簡單例子出發，設兩個向量和，而?(?)即是到前面2.2.1節說的五維空間的映射，因此映射過后的內積為：  （公式說明：上面的這兩個推導過程中，所說的前面的五維空間的映射，這里說的前面便是文中2.2.1節的所述的映射方式，仔細看下2.2.1節的映射規則，再看那第一個推導，其實就是計算x1，x2各自的內積，然后相乘相加即可，第二個推導則是直接平方，去掉括號，也很容易推出來） 另外，我們又注意到：  二者有很多相似的地方，實際上，我們只要把某幾個維度線性縮放一下，然后再加上一個常數維度，具體來說，上面這個式子的計算結果實際上和映射  之后的內積的結果是相等的，那么區別在于什么地方呢？ 一個是映射到高維空間中，然后再根據內積的公式進行計算； 而另一個則直接在原來的低維空間中進行計算，而不需要顯式地寫出映射后的結果。 （公式說明：上面之中，最后的兩個式子，第一個算式，是帶內積的完全平方式，可以拆開，然后，通過湊一個得到，第二個算式，也是根據第一個算式湊出來的） 回憶剛才提到的映射的維度爆炸，在前一種方法已經無法計算的情況下，后一種方法卻依舊能從容處理，甚至是無窮維度的情況也沒有問題。 我們把這里的計算兩個向量在隱式映射過后的空間中的內積的函數叫做核函數 (Kernel Function) ，例如，在剛才的例子中，我們的核函數為：  核函數能簡化映射空間中的內積運算——剛好“碰巧”的是，在我們的 SVM 里需要計算的地方數據向量總是以內積的形式出現的。對比剛才我們上面寫出來的式子，現在我們的分類函數為：  其中 由如下 dual 問題計算而得：  這樣一來計算的問題就算解決了，避開了直接在高維空間中進行計算，而結果卻是等價的。 ###2.3、使用松弛變量處理 outliers 方法 在本文第一節最開始討論支持向量機的時候，我們就假定，數據是線性可分的，亦即我們可以找到一個可行的超平面將數據完全分開。后來為了處理非線性數據，在上文2.2節使用 Kernel 方法對原來的線性 SVM 進行了推廣，使得非線性的的情況也能處理。雖然通過映射 ?(?) 將原始數據映射到高維空間之后，能夠線性分隔的概率大大增加，但是對于某些情況還是很難處理。 例如可能并不是因為數據本身是非線性結構的，而只是因為數據有噪音。對于這種偏離正常位置很遠的數據點，我們稱之為 outlier ，在我們原來的 SVM 模型里，outlier 的存在有可能造成很大的影響，因為超平面本身就是只有少數幾個 support vector 組成的，如果這些 support vector 里又存在 outlier 的話，其影響就很大了。例如下圖：  用黑圈圈起來的那個藍點是一個 outlier ，它偏離了自己原本所應該在的那個半空間，如果直接忽略掉它的話，原來的分隔超平面還是挺好的，但是由于這個 outlier 的出現，導致分隔超平面不得不被擠歪了，變成途中黑色虛線所示（這只是一個示意圖，并沒有嚴格計算精確坐標），同時 margin 也相應變小了。當然，更嚴重的情況是，如果這個 outlier 再往右上移動一些距離的話，我們將無法構造出能將數據分開的超平面來。 為了處理這種情況，SVM 允許數據點在一定程度上偏離一下超平面。例如上圖中，黑色實線所對應的距離，就是該 outlier 偏離的距離，如果把它移動回來，就剛好落在原來的超平面上，而不會使得超平面發生變形了。 我們原來的約束條件為：  現在考慮到outlier問題，約束條件變成了：  其中稱為松弛變量 (slack variable) ，對應數據點允許偏離的 functional margin 的量。當然，如果我們運行任意大的話，那任意的超平面都是符合條件的了。所以，我們在原來的目標函數后面加上一項，使得這些的總和也要最小：  其中 C 是一個參數，用于控制目標函數中兩項（“尋找 margin 最大的超平面”和“保證數據點偏差量最小”）之間的權重。注意，其中  是需要優化的變量（之一），而 C 是一個事先確定好的常量。完整地寫出來是這個樣子：  用之前的方法將限制或約束條件加入到目標函數中，得到新的拉格朗日函數，如下所示：  分析方法和前面一樣，轉換為另一個問題之后，我們先讓針對w、b和最小化：  將 w 帶回  并化簡，得到和原來一樣的目標函數：  不過，由于我們得到而又有ri >= 0（作為 Lagrange multiplier 的條件），因此有，所以整個 dual 問題現在寫作：  把前后的結果對比一下（錯誤修正：圖中的Dual formulation中的Minimize應為maxmize）：  可以看到唯一的區別就是現在 dual variable  多了一個上限 C 。而 Kernel 化的非線性形式也是一樣的，只要把換成即可。這樣一來，一個完整的，可以處理線性和非線性并能容忍噪音和 outliers 的支持向量機才終于介紹完畢了。 行文至此，可以做個小結，不準確的說，SVM它本質上即是一個分類方法，用w^T+b定義分類函數，于是求w、b，為尋最大間隔，引出1/2||w||^2，繼而引入拉格朗日因子，化為對拉格朗日乘子a的求解（求解過程中會涉及到一系列最優化或凸二次規劃等問題），如此，求w.b與求a等價，而a的求解可以用一種快速學習算法SMO，至于核函數，是為處理非線性情況，若直接映射到高維計算恐維度爆炸，故在低維計算，等效高維表現。 ##第三層、擴展SVM ###3.1、損失函數 在本文1.0節有這么一句話“支持向量機(SVM)是90年代中期發展起來的基于統計學習理論的一種機器學習方法，通過尋求結構化風險最小來提高學習機泛化能力，實現經驗風險和置信范圍的最小化，從而達到在統計樣本量較少的情況下，亦能獲得良好統計規律的目的。”但初次看到的讀者可能并不了解什么是結構化風險，什么又是經驗風險。要了解這兩個所謂的“風險”，還得又從監督學習說起。 監督學習實際上就是一個經驗風險或者結構風險函數的最優化問題。風險函數度量平均意義下模型預測的好壞，模型每一次預測的好壞用損失函數來度量。它從假設空間F中選擇模型f作為決策函數，對于給定的輸入X，由f(X)給出相應的輸出Y，這個輸出的預測值f(X)與真實值Y可能一致也可能不一致，用一個損失函數來度量預測錯誤的程度。損失函數記為L(Y, f(X))。 常用的損失函數有以下幾種（基本引用自《統計學習方法》）：   如此，SVM有第二種理解，即最優化+損失最小，或如@夏粉_百度所說“可從損失函數和優化算法角度看SVM，boosting，LR等算法，可能會有不同收獲”。 關于損失函數，還可以看看張潼的這篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各種算法中常用的損失函數基本都具有fisher一致性，優化這些損失函數得到的分類器可以看作是后驗概率的“代理”。 此外，他還有另外一篇論文《Statistical analysis of some multi-category large margin classification methods》，在多分類情況下margin loss的分析，這兩篇對Boosting和SVM使用的損失函數分析的很透徹。 ###3.2、SMO算法 在上文2.1.2節中，我們提到了求解對偶問題的序列最小最優化SMO算法，但并未提到其具體解法。 事實上，SMO算法是由Microsoft Research的John C. Platt在1998年發表的一篇[論文](http://research.microsoft.com/en-us/um/people/jplatt/smoTR.pdf)《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》中提出，它很快成為最快的二次規劃優化算法，特別針對線性SVM和數據稀疏時性能更優。 接下來，咱們便參考John C. Platt的[這篇](http://research.microsoft.com/en-us/um/people/jplatt/smoTR.pdf)文章來看看SMO的解法是怎樣的。 ####*3.2.1、SMO算法的解法* 咱們首先來定義特征到結果的輸出函數為  再三強調，這個u與我們之前定義的實質是一樣的。 接著，咱們重新定義咱們原始的優化問題，權當重新回顧，如下：  求導得到：  代入中，可得。 引入對偶因子后，得：  s.t：且 注：這里得到的min函數與我們之前的max函數實質也是一樣，因為把符號變下，即有min轉化為max的問題，且yi也與之前的等價，yj亦如此。 經過加入松弛變量后，模型修改為：   從而最終我們的問題變為：  繼而，根據KKT條件可以得出其中取值的意義為：  這里的還是拉格朗日乘子(問題通過拉格朗日乘法數來求解) 1. 對于第1種情況，表明是正常分類，在邊界內部（我們知道正確分類的點yi*f(xi)>=0）； 2. 對于第2種情況，表明了是支持向量，在邊界上； 3. 對于第3種情況，表明了是在兩條邊界之間； 而最優解需要滿足KKT條件，即上述3個條件都得滿足，以下幾種情況出現將會出現不滿足： <=1但是<C則是不滿足的,而原本=C >=1但是>0則是不滿足的而原本=0 =1但是=0或者=C則表明不滿足的，而原本應該是0<<C 所以要找出不滿足KKT條件的這些ai，并更新這些ai，但這些ai又受到另外一個約束，即  注：別忘了2.1.1節中，L對a、b求偏導，得到：  因此，我們通過另一個方法，即同時更新ai和aj，要求滿足以下等式：  就能保證和為0的約束。 利用yiai+yjaj=常數，消去ai，可得到一個關于單變量aj的一個凸二次規劃問題，不考慮其約束0<=aj<=C,可以得其解為：  這里，，表示舊值。 然后考慮約束0<=aj<=C可得到a的解析解為：  把SMO中對于兩個參數求解過程看成線性規劃來理解來理解的話，那么下圖所表達的便是約束條件：   根據yi和yj同號或異號，可得出兩個拉格朗日乘子的上下界分別為：  對于。 那么如何求得ai和aj呢？ * 對于ai，即第一個乘子，可以通過剛剛說的那3種不滿足KKT的條件來找； * 而對于第二個乘子aj可以找滿足條件 ：求得。 而b的更新則是：  在滿足下述條件：  下更新b，且每次更新完兩個乘子的優化后，都需要再重新計算b，及對應的Ei值。 最后更新所有ai，y和b，這樣模型就出來了，從而即可求出咱們開頭提出的分類函數  此外，這里也有一篇類似的文章，大家可以參考下。 #### *3.2.2、SMO算法的步驟* 這樣，SMO的主要步驟如下：  意思是， 第一步選取一對ai和aj，選取方法使用啟發式方法； 第二步，固定除ai和aj之外的其他參數，確定W極值條件下的ai，由aj表示ai。 假定在某一次迭代中，需要更新，對應的拉格朗日乘子，，那么這個小規模的二次規劃問題寫為：  那么在每次迭代中，如何更新乘子呢？引用[這里](http://staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf)的兩張PPT說明下：   知道了如何更新乘子，那么選取哪些乘子進行更新呢？具體選擇方法有以下兩個步驟： 1. 步驟1：先“掃描”所有乘子，把第一個違反KKT條件的作為更新對象，令為a2； 2. 步驟2：在所有不違反KKT條件的乘子中，選擇使|E1 ?E2|最大的a1（注：別忘了，其中，而，求出來的E代表函數ui對輸入xi的預測值與真實輸出類標記yi之差）。 值得一提的是，每次更新完兩個乘子的優化后，都需要再重新計算b，及對應的Ei值。 與此同時，乘子的選擇務必遵循兩個原則： * 使乘子能滿足KKT條件 * 對一個滿足KKT條件的乘子進行更新，應能最大限度增大目標函數的值（類似于[梯度](http://zh.wikipedia.org/zh-cn/%E6%A2%AF%E5%BA%A6)下降） 綜上，SMO算法的基本思想是將Vapnik在1982年提出的Chunking方法推到極致，SMO算法每次迭代只選出兩個分量ai和aj進行調整，其它分量則保持固定不變，在得到解ai和aj之后，再用ai和aj改進其它分量。與通常的分解算法比較，盡管它可能需要更多的迭代次數，但每次迭代的計算量比較小，所以該算法表現出整理的快速收斂性，且不需要存儲核矩陣，也沒有矩陣運算。 ####*3.5.3、SMO算法的實現* 行文至此，我相信，SVM理解到了一定程度后，是的確能在腦海里從頭至尾推導出相關公式的，最初分類函數，最大化分類間隔，max1/||w||，min1/2||w||^2，凸二次規劃，拉格朗日函數，轉化為對偶問題，SMO算法，都為尋找一個最優解，一個最優分類平面。一步步梳理下來，為什么這樣那樣，太多東西可以追究，最后實現。如下圖所示：  至于下文中將闡述的核函數則為是為了更好的處理非線性可分的情況，而松弛變量則是為了糾正或約束少量“不安分”或脫離集體不好歸類的因子。 臺灣的林智仁教授寫了一個封裝SVM算法的[libsvm](http://www.csie.ntu.edu.tw/~cjlin/libsvm/)庫，大家可以看看，此外[這里](http://www.pami.sjtu.edu.cn/people/gpliu/document/libsvm_src.pdf)還有一份libsvm的注釋文檔。 除了在這篇論文《fast training of support vector machines using sequential minimal optimization》中platt給出了SMO算法的邏輯代碼之外，[這里](http://blog.csdn.net/techq/article/details/6171688)也有一份SMO的實現代碼，大家可以看下。 ##讀者評論 本文發表后，[微博](http://weibo.com/julyweibo)上的很多朋友給了不少意見，以下是節選的一些精彩評論： 1. “壓力”陡增的評論→//@藏了個鋒：我是看著July大神的博文長大的啊//@zlkysl：就是看了最后那一篇才決定自己的研究方向為SVM的。-- <http://weibo.com/1580904460/zraWk0u6u?mod=weibotime>。 2. @張金輝：“SVM的三重境界，不得不轉的一篇。其實Coursera的課堂上Andrew Ng講過支持向量機，但顯然他沒有把這作為重點，加上Ng講支持向量機的方法我一時半會難以完全消化，所以聽的也是一知半解。真正開始了解支持向量機就是看的這篇“三重境界”，之后才對這個算法有了大概的概念，以至如何去使用，再到其中的原理為何，再到支持向量機的證明等。總之，這篇文章開啟了我長達數月的研究支持向量機階段，直到今日。”-- <http://zhan.renren.com/profile/249335584?from=template#!//tag/三重境界>。 3. @孤獨之守望者："最后，推出svm的cost function 是hinge loss，然后對比其他的方法的cost function，說明其實他們的目標函數很像，那么問題是svm為什么這么popular呢？您可以再加些VC dimension跟一些error bound的數學，點一下，提供一個思路和方向"。-- <http://weibo.com/1580904460/AiohoyDwq?mod=weibotime>。 4. @夏粉_百度：“在面試時，考察SVM可考察機器學習各方面能力：目標函數,優化過程,并行方法，算法收斂性,樣本復雜度，適用場景,調參經驗，不過個人認為考察boosting和LR也還不錯啊。此外，隨著統計機器學習不斷進步，SVM只被當成使用了一個替代01損失hinge研究，更通用的方法被提出，損失函數研究替代損失與貝葉斯損失關系，算法穩定性研究替代損失與推廣性能關系,凸優化研究如何求解凸目標函數，SVM,boosting等算法只是這些通用方法的一個具體組建而已。” 5. @居里猴姐：關于SVM損失函數的問題，可以看看張潼老師的這篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各種算法中常用的損失函數基本都具有fisher一致性，優化這些損失函數得到的分類器可以看作是后驗概率的“代理”。此外，張潼老師還有另外一篇論文《Statistical analysis of some multi-category large margin classification methods》，在多分類情況下margin loss的分析，這兩篇對Boosting和SVM使用的損失函數分析的很透徹。 6. @夏粉_百度：SVM用了hinge損失，hinge損失不可導，不如其它替代損失方便優化并且轉換概率麻煩。核函數也不太用，現在是大數據時代，樣本非常大，無法想象一個n^2的核矩陣如何存儲和計算。 而且，現在現在非線性一般靠深度學習了。//@Copper_PKU:請教svm在工業界的應用典型的有哪些？工業界如何選取核函數，經驗的方法？svm的訓練過程如何優化？ 7. @Copper_PKU：July的svm tutorial 我個人覺得還可以加入和修改如下部分：(1) 對于支持向量解釋，可以結合圖和拉格朗日參數來表達，松弛中sv沒有寫出來. (2) SMO算法部分，加入Joachims論文中提到的算法，以及SMO算法選取workset的方法，包括SMO算法的收斂判斷，還有之前共軛梯度求解方法，雖然是較早的算法，但是對于理解SMO算法有很好的效果。模型的優化和求解都是迭代的過程，加入歷史算法增強立體感。-- http://weibo.com/1580904460/Akw6dl3Yk#_rnd1385474436177。 8. //@廖臨川: 之所以sgd對大訓練集的效果更好，1.因為SGD優化每次迭代使用樣本子集，比使用訓練全集（尤其是百萬數量級）要快得多；2.如果目標函數是凸的或者偽凸的，SGD幾乎必然可以收斂到全局最優；否則，則收斂到局部最優；3.SGD一般不需要收斂到全局最優，只要得到足夠好的解，就可以立即停止。//@Copper_PKU：sgd的核心思想：是迭代訓練，每拿到一個樣本就算出基于當前w(t) 的loss function，t代表訓練第t次，然后進行下一w（t+1）的更新，w(t+1)=w(t)-(learning rate) * loss function的梯度，這個類比神經網絡中bp中的參數訓練方法。 sample by sample就是每次僅處理一個樣本 而不是一個batch。 9. //@Copper_PKU：從損失函數角度說：primal問題可以理解為正則化項+lossfunction，求解目標是在兩個中間取平衡 如果強調loss function最小則會overfitting，所以有C參數。 //@研究者July：SVM還真就是在一定限定條件下，即約束條件下求目標函數的最優值問題，同時，為減少誤判率，盡量讓損失最小。 10. ... ###參考文獻及推薦閱讀 1. 《支持向量機導論》，[美] Nello Cristianini / John Shawe-Taylor 著； 2. 支持向量機導論一書的支持網站：<http://www.support-vector.net/>； 3. 《數據挖掘導論》，[美] Pang-Ning Tan / Michael Steinbach / Vipin Kumar 著； 4. 《數據挖掘：概念與技術》，(加)Jiawei Han;Micheline Kamber 著； 5. 《數據挖掘中的新方法：支持向量機》，鄧乃揚 田英杰 著； 6. 《支持向量機--理論、算法和擴展》，鄧乃揚 田英杰 著； 7. 支持向量機系列，pluskid：<http://blog.pluskid.org/?page_id=683>； 8. <http://www.360doc.com/content/07/0716/23/11966_615252.shtml>； 9. 數據挖掘十大經典算法初探； 10. 《模式識別支持向量機指南》，C.J.C Burges 著； 11. 《統計學習方法》，李航著(第7章有不少內容參考自支持向量機導論一書，不過，可以翻翻看看)； 12. 《統計自然語言處理》，宗成慶編著，第十二章、文本分類； 13. SVM入門系列，Jasper：<http://www.blogjava.net/zhenandaci/category/31868.html>； 14. 最近鄰決策和SVM數字識別的實現和比較，作者不詳； 15. 斯坦福大學機器學習課程原始講義：<http://www.cnblogs.com/jerrylead/archive/2012/05/08/2489725.html>； 16. 斯坦福機器學習課程筆記：<http://www.cnblogs.com/jerrylead/tag/Machine%20Learning/>； 17. <http://www.cnblogs.com/jerrylead/archive/2011/03/13/1982639.html>； 18. SMO算法的數學推導：<http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html>； 19. 數據挖掘掘中所需的概率論與數理統計知識、上； 20. 關于機器學習方面的文章，可以讀讀：<http://www.cnblogs.com/vivounicorn/category/289453.html>； 21. 數學系教材推薦：<http://blog.sina.com.cn/s/blog_5e638d950100dswh.html>； 22. 《神經網絡與機器學習(原書第三版)》，[加] Simon Haykin 著； 23. 正態分布的前世今生：<http://t.cn/zlH3Ygc>； 24. 《數理統計學簡史》，陳希孺院士著； 25. 《最優化理論與算法(第2版)》，陳寶林編著； 26. A Gentle Introduction to Support Vector Machines in Biomedicine：<http://www.nyuinformatics.org/downloads/supplements/SVM_Tutorial_2010/Final_WB.pdf>，此PPT很贊，除了對引入拉格朗日對偶變量后的凸二次規劃問題的深入度不夠之外，其它都挺好，配圖很精彩，本文有幾張圖便引自此PPT中； 27. 來自卡內基梅隆大學carnegie mellon university(CMU)的講解SVM的PPT：<http://www.autonlab.org/tutorials/svm15.pdf>； 28. 發明libsvm的臺灣林智仁教授06年的機器學習講義SVM：<http://wenku.baidu.com/link?url=PWTGMYNb4HGUrUQUZwTH2B4r8pIMgLMiWIK1ymVORrds_11VOkHwp-JWab7IALDiors64JW_6mD93dtuWHwFWxsAk6p0rzchR8Qh5_4jWHC>； 29. <http://staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf>； 30. Introduction to Support Vector Machines (SVM)，By Debprakash Patnai M.E (SSA)，<https://www.google.com.hk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCwQFjAA&url=http%3a%2f%2fwww%2epws%2estu%2eedu%2etw%2fccfang%2findex%2efiles%2fAI%2fAI%26ML-Support%2520Vector%2520Machine-1%2eppt&ei=JRR6UqT5C-iyiQfWyIDgCg&usg=AFQjCNGw1fTbpH4ltQjjmx1d25ZqbCN9nA>； 31. 多人推薦過的libsvm：<http://www.csie.ntu.edu.tw/~cjlin/libsvm/>； 32. 《machine learning in action》，中文版為《機器學習實戰》； 33. SMO算法的提出：Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines：<http://research.microsoft.com/en-us/um/people/jplatt/smoTR.pdf>； 34. 《統計學習理論的本質》，[美] Vladimir N. Vapnik著，非常晦澀，不做過多推薦； 35. 張兆翔，機器學習第五講之支持向量機<http://irip.buaa.edu.cn/~zxzhang/courses/MachineLearning/5.pdf>； 36. VC維的理論解釋：<http://www.svms.org/vc-dimension/>，中文VC維解釋<http://xiaoxia001.iteye.com/blog/1163338>； 37. 來自NEC Labs America的Jason Weston關于SVM的講義<http://www.cs.columbia.edu/~kathy/cs4701/documents/jason_svm_tutorial.pdf>； 38. 來自MIT的SVM講義：<http://www.mit.edu/~9.520/spring11/slides/class06-svm.pdf>； 39. PAC問題：<http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf>； 40. 百度張潼老師的兩篇論文：《Statistical behavior and consistency of classification methods based on convex risk minimization》http://home.olemiss.edu/~xdang/676/Consistency_of_Classification_Convex_Risk_Minimization.pdf，《Statistical analysis of some multi-category large margin classification methods》； 41. <http://jacoxu.com/?p=39>； 42. 《矩陣分析與應用》，清華張賢達著； 43. SMO算法的實現：<http://blog.csdn.net/techq/article/details/6171688>； 44. 常見面試之機器學習算法思想簡單梳理：<http://www.cnblogs.com/tornadomeet/p/3395593.html>； 45. 矩陣的wikipedia頁面：<http://zh.wikipedia.org/wiki/%E7%9F%A9%E9%98%B5>； 46. 最小二乘法及其實現：<http://blog.csdn.net/qll125596718/article/details/8248249>； 47. 統計學習方法概論：<http://blog.csdn.net/qll125596718/article/details/8351337>； 48. <http://www.csdn.net/article/2012-12-28/2813275-Support-Vector-Machine>； 49. A Tutorial on Support Vector Regression：<http://alex.smola.org/papers/2003/SmoSch03b.pdf>；SVR簡明版：<http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/tutorials/SVR.pdf>。 50. SVM Org：<http://www.support-vector-machines.org/>； 51. R. Collobert. Large Scale Machine Learning. Université Paris VI phd thesis. 2004：<http://ronan.collobert.com/pub/matos/2004_phdthesis_lip6.pdf>； 52. Making Large-Scale SVM Learning Practical：<http://www.cs.cornell.edu/people/tj/publications/joachims_99a.pdf>； 53. 文本分類與SVM：<http://blog.csdn.net/zhzhl202/article/details/8197109>； 54. Working Set Selection Using Second Order Information for Training Support Vector Machines：<http://www.csie.ntu.edu.tw/~cjlin/papers/quadworkset.pdf>； 55. SVM Optimization: Inverse Dependence on Training Set Size：<http://icml2008.cs.helsinki.fi/papers/266.pdf>； 56. Large-Scale Support Vector Machines: Algorithms and Theory：<http://cseweb.ucsd.edu/~akmenon/ResearchExam.pdf>； 57. 凸優化的概念：<http://cs229.stanford.edu/section/cs229-cvxopt.pdf>； 58. 《凸優化》，作者: Stephen Boyd / Lieven Vandenberghe，原作名: Convex Optimization； 59. Large-scale Non-linear Classification: Algorithms and Evaluations，Zhuang Wang，講了很多SVM算法的新進展：<http://ijcai13.org/files/tutorial_slides/te2.pdf>；