【轉載請注明出處】http://www.cnblogs.com/jerrylead
1 簡介
支援向量機基本上是最好的有監督學習算法了。最開始接觸SVM是去年暑假的時候，老師要求交《統計學習理論》的報告，那時去網上下了一份入門教程，裡面講的很通俗，當時隻是大緻了解了一些相關概念。這次斯坦福提供的學習材料，讓我重新學習了一些SVM知識。我看很多正統的講法都是從VC 維理論和結構風險最小原理出發，然後引出SVM什麼的，還有些資料上來就講分類超平面什麼的。這份材料從前幾節講的logistic回歸出發，引出了SVM，既揭示了模型間的聯系，也讓人覺得過渡更自然。
2 重新審視logistic回歸
Logistic回歸目的是從特征學習出一個0/1分類模型，而這個模型是将特性的線性組合作為自變量，由于自變量的取值範圍是負無窮到正無窮。是以，使用logistic函數（或稱作sigmoid函數）将自變量映射到(0,1)上，映射後的值被認為是屬于y=1的機率。
形式化表示就是
假設函數
其中x是n維特征向量，函數g就是logistic函數。
的圖像是
可以看到，将無窮映射到了(0,1)。
而假設函數就是特征屬于y=1的機率。
當我們要判别一個新來的特征屬于哪個類時，隻需求
，若大于0.5就是y=1的類，反之屬于y=0類。
再審視一下
，發現
隻和
有關，
>0，那麼
，g(z)隻不過是用來映射，真實的類别決定權還在
。還有當
時，
=1，反之
=0。如果我們隻從
出發，希望模型達到的目标無非就是讓訓練資料中y=1的特征
，而是y=0的特征
。Logistic回歸就是要學習得到
，使得正例的特征遠大于0，負例的特征遠小于0，強調在全部訓練執行個體上達到這個目标。
圖形化表示如下：
中間那條線是
，logistic回顧強調所有點盡可能地遠離中間那條線。學習出的結果也就中間那條線。考慮上面3個點A、B和C。從圖中我們可以确定A是×類别的，然而C我們是不太确定的，B還算能夠确定。這樣我們可以得出結論，我們更應該關心靠近中間分割線的點，讓他們盡可能地遠離中間線，而不是在所有點上達到最優。因為那樣的話，要使得一部分點靠近中間線來換取另外一部分點更加遠離中間線。我想這就是支援向量機的思路和logistic回歸的不同點，一個考慮局部（不關心已經确定遠離的點），一個考慮全局（已經遠離的點可能通過調整中間線使其能夠更加遠離）。這是我的個人直覺了解。
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上。映射關系如下：
4 函數間隔（functional margin）和幾何間隔（geometric margin）
給定一個訓練樣本
，x是特征，y是結果标簽。i表示第i個樣本。我們定義函數間隔如下：
可想而知，當
時，在我們的g(z)定義中，
，
的值實際上就是
。反之亦然。為了使函數間隔最大（更大的信心确定該例是正例還是反例），當
時，
應該是個大正數，反之是個大負數。是以函數間隔代表了我們認為特征是正例還是反例的确信度。
繼續考慮w和b，如果同時加大w和b，比如在
前面乘個系數比如2，那麼所有點的函數間隔都會增大二倍，這個對求解問題來說不應該有影響，因為我們要求解的是
，同時擴大w和b對結果是無影響的。這樣，我們為了限制w和b，可能需要加入歸一化條件，畢竟求解的目标是确定唯一一個w和b，而不是多組線性相關的向量。這個歸一化一會再考慮。
剛剛我們定義的函數間隔是針對某一個樣本的，現在我們定義全局樣本上的函數間隔
說白了就是在訓練樣本上分類正例和負例确信度最小那個函數間隔。
接下來定義幾何間隔，先看圖
假設我們有了B點所在的
分割面。任何其他一點，比如A到該面的距離以
表示，假設B就是A在分割面上的投影。我們知道向量BA的方向是
（分割面的梯度），機關向量是
。A點是
，是以B點是x=
（利用國中的幾何知識），帶入
得，
進一步得到
實際上就是點到平面距離。
再換種更加優雅的寫法：
當
時，不就是函數間隔嗎？是的，前面提到的函數間隔歸一化結果就是幾何間隔。他們為什麼會一樣呢？因為函數間隔是我們定義的，在定義的時候就有幾何間隔的色彩。同樣，同時擴大w和b，w擴大幾倍，
就擴大幾倍，結果無影響。同樣定義全局的幾何間隔
5 最優間隔分類器（optimal margin classifier）
回想前面我們提到我們的目标是尋找一個超平面，使得離超平面比較近的點能有更大的間距。也就是我們不考慮所有的點都必須遠離超平面，我們關心求得的超平面能夠讓所有點中離它最近的點具有最大間距。形象的說，我們将上面的圖看作是一張紙，我們要找一條折線，按照這條折線折疊後，離折線最近的點的間距比其他折線都要大。形式化表示為：
這裡用
=1規約w，使得
是幾何間隔。
到此，我們已經将模型定義出來了。如果求得了w和b，那麼來一個特征x，我們就能夠分類了，稱為最優間隔分類器。接下的問題就是如何求解w和b的問題了。
由于
不是凸函數，我們想先處理轉化一下，考慮幾何間隔和函數間隔的關系，
，我們改寫一下上面的式子：
這時候其實我們求的最大值仍然是幾何間隔，隻不過此時的w不受
的限制了。然而這個時候目标函數仍然不是凸函數，沒法直接代入優化軟體裡計算。我們還要改寫。前面說到同時擴大w和b對結果沒有影響，但我們最後要求的仍然是w和b的确定值，不是他們的一組倍數值，是以，我們需要對
做一些限制，以保證我們解是唯一的。這裡為了簡便我們取
。這樣的意義是将全局的函數間隔定義為1，也即是将離超平面最近的點的距離定義為
。由于求
的最大值相當于求
的最小值，是以改寫後結果為：
這下好了，隻有線性限制了，而且是個典型的二次規劃問題（目标函數是自變量的二次函數）。代入優化軟體可解。
到這裡發現，這個講義雖然沒有像其他講義一樣先畫好圖，畫好分類超平面，在圖上标示出間隔那麼直覺，但每一步推導有理有據，依靠思路的流暢性來推導出目标函數和限制。
接下來介紹的是手工求解的方法了，一種更優的求解方法。
6 拉格朗日對偶（Lagrange duality）
先抛開上面的二次規劃問題，先來看看存在等式限制的極值問題求法，比如下面的最優化問題：
目标函數是f(w)，下面是等式限制。通常解法是引入拉格朗日算子，這裡使用
來表示算子，得到拉格朗日公式為
L是等式限制的個數。
然後分别對w和
求偏導，使得偏導數等于0，然後解出w和
。至于為什麼引入拉格朗日算子可以求出極值，原因是f(w)的dw變化方向受其他不等式的限制，dw的變化方向與f(w)的梯度垂直時才能獲得極值，而且在極值處，f(w)的梯度與其他等式梯度的線性組合平行，是以他們之間存線上性關系。（參考《最優化與KKT條件》）
然後我們探讨有不等式限制的極值問題求法，問題如下：
我們定義一般化的拉格朗日公式
這裡的
和
都是拉格朗日算子。如果按這個公式求解，會出現問題，因為我們求解的是最小值，而這裡的
已經不是0了，我們可以将
調整成很大的正值，來使最後的函數結果是負無窮。是以我們需要排除這種情況，我們定義下面的函數：
這裡的P代表primal。假設
或者
，那麼我們總是可以調整
和
來使得
有最大值為正無窮。而隻有g和h滿足限制時，
為f(w)。這個函數的精妙之處在于
，而且求極大值。
是以我們可以寫作
這樣我們原來要求的min f(w)可以轉換成求
了。
我們使用
來表示
。如果直接求解，首先面對的是兩個參數，而
也是不等式限制，然後再在w上求最小值。這個過程不容易做，那麼怎麼辦呢？
我們先考慮另外一個問題
D的意思是對偶，
将問題轉化為先求拉格朗日關于w的最小值，将
和
看作是固定值。之後在
求最大值的話：
這個問題是原問題的對偶問題，相對于原問題隻是更換了min和max的順序，而一般更換順序的結果是Max Min(X) <= MinMax(X)。然而在這裡兩者相等。用
來表示對偶問題如下：
下面解釋在什麼條件下兩者會等價。假設f和g都是凸函數，h是仿射的（affine，
）。并且存在w使得對于所有的i，
。在這種假設下，一定存在
使得
是原問題的解，
是對偶問題的解。還有
另外，
滿足庫恩-塔克條件（Karush-Kuhn-Tucker, KKT condition），該條件如下：
是以如果
滿足了庫恩-塔克條件，那麼他們就是原問題和對偶問題的解。讓我們再次審視公式（5），這個條件稱作是KKT dual complementarity條件。這個條件隐含了如果
，那麼
。也就是說，
時，w處于可行域的邊界上，這時才是起作用的限制。而其他位于可行域内部（
的）點都是不起作用的限制，其
。這個KKT雙重補足條件會用來解釋支援向量和SMO的收斂測試。
這部分内容思路比較淩亂，還需要先研究下《非線性規劃》中的限制極值問題，再回頭看看。KKT的總體思想是将極值會在可行域邊界上取得，也就是不等式為0或等式限制裡取得，而最優下降方向一般是這些等式的線性組合，其中每個元素要麼是不等式為0的限制，要麼是等式限制。對于在可行域邊界内的點，對最優解不起作用，是以前面的系數為0。
7 最優間隔分類器（optimal margin classifier）
重新回到SVM的優化問題：
我們将限制條件改寫為：
從KKT條件得知隻有函數間隔是1（離超平面最近的點）的線性限制式前面的系數
，也就是說這些限制式
，對于其他的不線上上的點(
)，極值不會在他們所在的範圍内取得，是以前面的系數
.注意每一個限制式實際就是一個訓練樣本。
看下面的圖：
實線是最大間隔超平面，假設×号的是正例，圓圈的是負例。在虛線上的點就是函數間隔是1的點，那麼他們前面的系數
，其他點都是
。這三個點稱作支援向量。構造拉格朗日函數如下：
注意到這裡隻有
沒有
是因為原問題中沒有等式限制，隻有不等式限制。
下面我們按照對偶問題的求解步驟來一步步進行，
首先求解
的最小值，對于固定的
，
的最小值隻與w和b有關。對w和b分别求偏導數。
并得到
将上式帶回到拉格朗日函數中得到，此時得到的是該函數的最小值（目标函數是凸函數）
代入後，化簡過程如下：
最後得到
由于最後一項是0，是以簡化為
這裡我們将向量内積
表示為
此時的拉格朗日函數隻包含了變量
。然而我們求出了
才能得到w和b。
接着是極大化的過程
，
前面提到過對偶問題和原問題滿足的幾個條件，首先由于目标函數和線性限制都是凸函數，而且這裡不存在等式限制h。存在w使得對于所有的i，
。是以，一定存在
使得
是原問題的解，
是對偶問題的解。在這裡，求
就是求
了。
如果求出了
，根據
即可求出w（也是
，原問題的解）。然後
即可求出b。即離超平面最近的正的函數間隔要等于離超平面最近的負的函數間隔。
關于上面的對偶問題如何求解，将留給下一篇中的SMO算法來闡明。
這裡考慮另外一個問題，由于前面求解中得到
我們通篇考慮問題的出發點是
，根據求解得到的
，我們代入前式得到
也就是說，以前新來的要分類的樣本首先根據w和b做一次線性運算，然後看求的結果是大于0還是小于0,來判斷正例還是負例。現在有了
，我們不需要求出w，隻需将新來的樣本和訓練資料中的所有樣本做内積和即可。那有人會說，與前面所有的樣本都做運算是不是太耗時了？其實不然，我們從KKT條件中得到，隻有支援向量的
，其他情況
。是以，我們隻需求新來的樣本和支援向量的内積，然後運算即可。這種寫法為下面要提到的核函數（kernel）做了很好的鋪墊。這是上篇，先寫這麼多了。
7 核函數（Kernels）
考慮我們最初在“線性回歸”中提出的問題，特征是房子的面積x，這裡的x是實數，結果y是房子的價格。假設我們從樣本點的分布中看到x和y符合3次曲線，那麼我們希望使用x的三次多項式來逼近這些樣本點。那麼首先需要将特征x擴充到三維
，然後尋找特征和結果之間的模型。我們将這種特征變換稱作特征映射（feature mapping）。映射函數稱作
，在這個例子中
我們希望将得到的特征映射後的特征應用于SVM分類，而不是最初的特征。這樣，我們需要将前面
公式中的内積從
，映射到
。
至于為什麼需要映射後的特征而不是最初的特征來參與計算，上面提到的（為了更好地拟合）是其中一個原因，另外的一個重要原因是樣例可能存線上性不可分的情況，而将特征映射到高維空間後，往往就可分了。（在《資料挖掘導論》Pang-Ning Tan等人著的《支援向量機》那一章有個很好的例子說明）
将核函數形式化定義，如果原始特征内積是
，映射後為
，那麼定義核函數（Kernel）為
到這裡，我們可以得出結論，如果要實作該節開頭的效果，隻需先計算
，然後計算
即可，然而這種計算方式是非常低效的。比如最初的特征是n維的，我們将其映射到
維，然後再計算，這樣需要
的時間。那麼我們能不能想辦法減少計算時間呢？
先看一個例子，假設x和z都是n維的，
展開後，得
這個時候發現我們可以隻計算原始特征x和z内積的平方（時間複雜度是O(n)），就等價與計算映射後特征的内積。也就是說我們不需要花
時間了。
現在看一下映射函數（n=3時），根據上面的公式，得到
也就是說核函數
隻能在選擇這樣的
作為映射函數時才能夠等價于映射後特征的内積。
再看一個核函數
對應的映射函數（n=3時）是
更一般地，核函數
對應的映射後特征次元為
。（求解方法參見http://zhidao.baidu.com/question/16706714.html）。
由于計算的是内積，我們可以想到IR中的餘弦相似度，如果x和z向量夾角越小，那麼核函數值越大，反之，越小。是以，核函數值是
和
的相似度。
再看另外一個核函數
這時，如果x和z很相近（
），那麼核函數值為1，如果x和z相差很大（
），那麼核函數值約等于0。由于這個函數類似于高斯分布，是以稱為高斯核函數，也叫做徑向基函數(Radial Basis Function 簡稱RBF)。它能夠把原始特征映射到無窮維。
既然高斯核函數能夠比較x和z的相似度，并映射到0到1，回想logistic回歸，sigmoid函數可以，是以還有sigmoid核函數等等。
下面有張圖說明在低維線性不可分時，映射到高維後就可分了，使用高斯核函數。
來自Eric Xing的slides
注意，使用核函數後，怎麼分類新來的樣本呢？線性的時候我們使用SVM學習出w和b，新來樣本x的話，我們使用
來判斷，如果值大于等于1，那麼是正類，小于等于是負類。在兩者之間，認為無法确定。如果使用了核函數後，
就變成了
，是否先要找到
，然後再預測？答案肯定不是了，找
很麻煩，回想我們之前說過的
隻需将
替換成
，然後值的判斷同上。
8 核函數有效性判定
問題：給定一個函數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是 |
Mercer定理表明為了證明K是有效的核函數，那麼我們不用去尋找
，而隻需要在訓練集上求出各個
，然後判斷矩陣K是否是半正定（使用左上角主子式大于等于零等方法）即可。
許多其他的教科書在Mercer定理證明過程中使用了
範數和再生希爾伯特空間等概念，但在特征是n維的情況下，這裡給出的證明是等價的。
核函數不僅僅用在SVM上，但凡在一個模型後算法中出現了
，我們都可以常使用
去替換，這可能能夠很好地改善我們的算法。
9規則化和不可分情況處理（Regularizationand the non-separable case）
我們之前讨論的情況都是建立在樣例線性可分的假設上，當樣例線性不可分時，我們可以嘗試使用核函數來将特征映射到高維，這樣很可能就可分了。然而，映射後我們也不能100%保證可分。那怎麼辦呢，我們需要将模型進行調整，以保證在不可分的情況下，也能夠盡可能地找出分隔超平面。
看下面兩張圖：
可以看到一個離群點（可能是噪聲）可以造成超平面的移動，間隔縮小，可見以前的模型對噪聲非常敏感。再有甚者，如果離群點在另外一個類中，那麼這時候就是線性不可分了。
這時候我們應該允許一些點遊離并在在模型中違背限制條件（函數間隔大于1）。我們設計得到新的模型如下（也稱軟間隔）：
引入非負參數後（稱為松弛變量），就允許某些樣本點的函數間隔小于1，即在最大間隔區間裡面，或者函數間隔是負數，即樣本點在對方的區域中。而放松限制條件後，我們需要重新調整目标函數，以對離群點進行處罰，目标函數後面加上的就表示離群點越多，目标函數值越大，而我們要求的是盡可能小的目标函數值。這裡的C是離群點的權重，C越大表明離群點對目标函數影響越大，也就是越不希望看到離群點。我們看到，目标函數控制了離群點的數目和程度，使大部分樣本點仍然遵守限制條件。
模型修改後，拉格朗日公式也要修改如下：
這裡的和都是拉格朗日乘子，回想我們在拉格朗日對偶中提到的求法，先寫出拉格朗日公式（如上），然後将其看作是變量w和b的函數，分别對其求偏導，得到w和b的表達式。然後代入公式中，求帶入後公式的極大值。整個推導過程類似以前的模型，這裡隻寫出最後結果如下：
此時，我們發現沒有了參數，與之前模型唯一不同在于又多了的限制條件。需要提醒的是，b的求值公式也發生了改變，改變結果在SMO算法裡面介紹。先看看KKT條件的變化：
第一個式子表明在兩條間隔線外的樣本點前面的系數為0，離群樣本點前面的系數為C，而支援向量（也就是在超平面兩邊的最大間隔線上）的樣本點前面系數在(0,C)上。通過KKT條件可知，某些在最大間隔線上的樣本點也不是支援向量，相反也可能是離群點。
10坐标上升法（Coordinateascent）
在最後讨論的求解之前，我們先看看坐标上升法的基本原理。假設要求解下面的優化問題：
這裡W是向量的函數。之前我們在回歸中提到過兩種求最優解的方法，一種是梯度下降法，另外一種是牛頓法。現在我們再講一種方法稱為坐标上升法（求解最小值問題時，稱作坐标下降法，原理一樣）。
方法過程：
最裡面語句的意思是固定除之外的所有，這時W可看作隻是關于的函數，那麼直接對求導優化即可。這裡我們進行最大化求導的順序i是從1到m，可以通過更改優化順序來使W能夠更快地增加并收斂。如果W在内循環中能夠很快地達到最優，那麼坐标上升法會是一個很高效的求極值方法。
下面通過一張圖來展示：
橢圓代表了二次函數的各個等高線，變量數為2，起始坐标是(2,-2)。圖中的直線式疊代優化的路徑，可以看到每一步都會向最優值前進一步，而且前進路線是平行于坐标軸的，因為每一步隻優化一個變量。
11SMO優化算法（Sequentialminimal optimization）
SMO算法由MicrosoftResearch的JohnC.Platt在1998年提出，并成為最快的二次規劃優化算法，特别針對線性SVM和資料稀疏時性能更優。關于SMO最好的資料就是他本人寫的《SequentialMinimal Optimization A Fast Algorithm for Training Support VectorMachines》了。
我拜讀了一下，下面先說講義上對此方法的總結。
首先回到我們前面一直懸而未解的問題，對偶函數最後的優化問題：
要解決的是在參數上求最大值W的問題，至于和都是已知數。C由我們預先設定，也是已知數。
按照坐标上升的思路，我們首先固定除以外的所有參數，然後在上求極值。等一下，這個思路有問題，因為如果固定以外的所有參數，那麼将不再是變量（可以由其他值推出），因為問題中規定了
是以，我們需要一次選取兩個參數做優化，比如和，此時可以由和其他參數表示出來。這樣回帶到W中，W就隻是關于的函數了，可解。
這樣，SMO的主要步驟如下：
意思是，第一步選取一對和，選取方法使用啟發式方法（後面講）。第二步，固定除和之外的其他參數，确定W極值條件下的，由表示。
SMO之是以高效就是因為在固定其他參數後，對一個參數優化過程很高效。
下面讨論具體方法：
假設我們選取了初始值滿足了問題中的限制條件。接下來，我們固定，這樣W就是和的函數。并且和滿足條件：
由于都是已知固定值，是以為了方面，可将等式右邊标記成實數值。
當和異号時，也就是一個為1，一個為-1時，他們可以表示成一條直線，斜率為1。如下圖：
橫軸是，縱軸是，和既要在矩形方框内，也要在直線上，是以
，
同理，當和同号時，
，
然後我們打算将用表示：
然後反代入W中，得
展開後W可以表示成。其中a,b,c是固定值。這樣，通過對W進行求導可以得到，然而要保證滿足，我們使用表示求導求出來的，然而最後的，要根據下面情況得到：
這樣得到後，我們可以得到的新值。
下面進入Platt的文章，來找到啟發式搜尋的方法和求b值的公式。
這邊文章使用的符号表示有點不太一樣，不過實質是一樣的，先來熟悉一下文章中符号的表示。
文章中定義特征到結果的輸出函數為
與我們之前的實質是一緻的。
原始的優化問題為：
求導得到：
經過對偶後為：
s.t.
這裡與W函數是一樣的，隻是符号求反後，變成求最小值了。和是一樣的，都表示第i個樣本的輸出結果（1或-1）。
經過加入松弛變量後，模型修改為：
由公式（7）代入（1）中可知，
這個過程和之前對偶過程一樣。
重新整理我們要求的問題為：
與之對應的KKT條件為：
這個KKT條件說明，在兩條間隔線外面的點，對應前面的系數為0，在兩條間隔線裡面的對應為C，在兩條間隔線上的對應的系數在0和C之間。
将我們之前得到L和H重新拿過來：
之前我們将問題進行到這裡，然後說将用表示後代入W中，這裡将代入中，得
其中
這裡的和代表某次疊代前的原始值，是以是常數，而和是變量，待求。公式（24）中的最後一項是常數。
由于和滿足以下公式
因為的值是固定值，在疊代前後不會變。
那麼用s表示，上式兩邊乘以時，變為：
其中
代入（24）中，得
這時候隻有是變量了，求導
如果的二階導數大于0（凹函數），那麼一階導數為0時，就是極小值了。
假設其二階導數為0（一般成立），那麼上式化簡為：
将w和v代入後，繼續化簡推導，得（推導了六七行推出來了）
我們使用來表示：
通常情況下目标函數是正定的，也就是說，能夠在直線限制方向上求得最小值，并且。
那麼我們在（30）兩邊都除以可以得到
這裡我們使用表示優化後的值，是疊代前的值，。
與之前提到的一樣不是最終疊代後的值，需要進行限制：
那麼
在特殊情況下，可能不為正，如果核函數K不滿足Mercer定理，那麼目标函數可能變得非正定，可能出現負值。即使K是有效的核函數，如果訓練樣本中出現相同的特征x，那麼仍有可能為0。SMO算法在不為正值的情況下仍有效。為保證有效性，我們可以推導出就是的二階導數，，沒有極小值，最小值在邊緣處取到（類比），時更是單調函數了，最小值也在邊緣處取得，而的邊緣就是L和H。這樣将和分别代入中即可求得的最小值，相應的還是也可以知道了。具體計算公式如下：
至此，疊代關系式出了b的推導式以外，都已經推出。
b每一步都要更新，因為前面的KKT條件指出了和的關系，而和b有關，在每一步計算出後，根據KKT條件來調整b。
b的更新有幾種情況：
來自羅林開的ppt
這裡的界内指，界上就是等于0或者C了。
前面兩個的公式推導可以根據
和對于有的KKT條件推出。
這樣全部參數的更新公式都已經介紹完畢，附加一點，如果使用的是線性核函數，我們就可以繼續使用w了，這樣不用掃描整個樣本庫來作内積了。
w值的更新方法為：
根據前面的
公式推導出。
12SMO中拉格朗日乘子的啟發式選擇方法
終于到了最後一個問題了，所謂的啟發式選擇方法主要思想是每次選擇拉格朗日乘子的時候，優先選擇樣本前面系數的作優化（論文中稱為無界樣例），因為在界上（為0或C）的樣例對應的系數一般不會更改。
這條啟發式搜尋方法是選擇第一個拉格朗日乘子用的，比如前面的。那麼這樣選擇的話，是否最後會收斂。可幸的是Osuna定理告訴我們隻要選擇出來的兩個中有一個違背了KKT條件，那麼目标函數在一步疊代後值會減小。違背KKT條件不代表，在界上也有可能會違背。是的，是以在給定初始值=0後，先對所有樣例進行循環，循環中碰到違背KKT條件的（不管界上還是界内）都進行疊代更新。等這輪過後，如果沒有收斂，第二輪就隻針對的樣例進行疊代更新。
在第一個乘子選擇後，第二個乘子也使用啟發式方法選擇，第二個乘子的疊代步長大緻正比于，選擇第二個乘子能夠最大化。即當為正時選擇負的絕對值最大的，反之，選擇正值最大的。
最後的收斂條件是在界内（）的樣例都能夠遵循KKT條件，且其對應的隻在極小的範圍内變動。
至于如何寫具體的程式，請參考JohnC. Platt在論文中給出的僞代碼。
13總結
這份SVM的講義重點概括了SVM的基本概念和基本推導，中規中矩卻又讓人醍醐灌頂。起初讓我最頭疼的是拉格朗日對偶和SMO，後來逐漸明白拉格朗日對偶的重要作用是将w的計算提前并消除w，使得優化函數變為拉格朗日乘子的單一參數優化問題。而SMO裡面疊代公式的推導也着實讓我花費了不少時間。
對比這麼複雜的推導過程，SVM的思想确實那麼簡單。它不再像logistic回歸一樣企圖去拟合樣本點（中間加了一層sigmoid函數變換），而是就在樣本中去找分隔線，為了評判哪條分界線更好，引入了幾何間隔最大化的目标。
之後所有的推導都是去解決目标函數的最優化上了。在解決最優化的過程中，發現了w可以由特征向量内積來表示，進而發現了核函數，僅需要調整核函數就可以将特征進行低維到高維的變換，在低維上進行計算，實質結果表現在高維上。由于并不是所有的樣本都可分，為了保證SVM的通用性，進行了軟間隔的處理，導緻的結果就是将優化問題變得更加複雜，然而驚奇的是松弛變量沒有出現在最後的目标函數中。最後的優化求解問題，也被拉格朗日對偶和SMO算法化解，使SVM趨向于完美。
另外，其他很多議題如SVM背後的學習理論、參數選擇問題、二值分類到多值分類等等還沒有涉及到，以後有時間再學吧。其實樸素貝葉斯在分類二值分類問題時，如果使用對數比，那麼也算作線性分類器。