支持向量機SMO算法

1、支持向量機SMO算法 1 簡介支持向量機基本上是最好的有監(jiān)督學習算法了。最開始接觸SVM是去年暑假的時候，老師要求交統(tǒng)計學習理論的報告，那時去網(wǎng)上下了一份入門教程，里面講的很通俗，當時只是大致了解了一些相關概念。這次斯坦福提供的學習材料，讓我重新學習了一些SVM知識。我看很多正統(tǒng)的講法都是從VC 維理論和結構風險最小原理出發(fā)，然后引出SVM什么的，還有些資料上來就講分類超平面什么的。這份材料從前幾節(jié)講的logistic回歸出發(fā)，引出了SVM，既揭示了模型間的聯(lián)系，也讓人覺得過渡更自然。 2 重新審視logistic回歸Logistic回歸目的是從特征學習出一個0/1分類模型，而這個模型是將特性

2、的線性組合作為自變量，由于自變量的取值范圍是負無窮到正無窮。因此，使用logistic函數(shù)（或稱作sigmoid函數(shù)）將自變量映射到(0,1)上，映射后的值被認為是屬于y=1的概率。 形式化表示就是 假設函數(shù) 其中x是n維特征向量，函數(shù)g就是logistic函數(shù)。 的圖像是 可以看到，將無窮映射到了(0,1)。 而假設函數(shù)就是特征屬于y=1的概率。 當我們要判別一個新來的特征屬于哪個類時，只需求，若大于0.5就是y=1的類，反之屬于y=0類。 再審視一下，發(fā)現(xiàn)只和有關，>0，那么，g(z)只不過是用來映射，真實的類別決定權還在。還有當時，=1，反之=0。如果我們只從出發(fā)，希望模型達到的目

3、標無非就是讓訓練數(shù)據(jù)中y=1的特征，而是y=0的特征。Logistic回歸就是要學習得到，使得正例的特征遠大于0，負例的特征遠小于0，強調(diào)在全部訓練實例上達到這個目標。 圖形化表示如下： 中間那條線是，logistic回顧強調(diào)所有點盡可能地遠離中間那條線。學習出的結果也就中間那條線?？紤]上面3個點A、B和C。從圖中我們可以確定A是×類別的，然而C我們是不太確定的，B還算能夠確定。這樣我們可以得出結論，我們更應該關心靠近中間分割線的點，讓他們盡可能地遠離中間線，而不是在所有點上達到最優(yōu)。因為那樣的話，要使得一部分點靠近中間線來換取另外一部分點更加遠離中間線。我想這就是支持向量機的思路和

4、logistic回歸的不同點，一個考慮局部（不關心已經(jīng)確定遠離的點），一個考慮全局（已經(jīng)遠離的點可能通過調(diào)整中間線使其能夠更加遠離）。這是我的個人直觀理解。 3 形式化表示我們這次使用的結果標簽是y=-1,y=1，替換在logistic回歸中使用的y=0和y=1。同時將替換成w和b。以前的，其中認為?，F(xiàn)在我們替換為b，后面替換為（即）。這樣，我們讓，進一步。也就是說除了y由y=0變?yōu)閥=-1，只是標記不同外，與logistic回歸的形式化表示沒區(qū)別。再明確下假設函數(shù) 上一節(jié)提到過我們只需考慮的正負問題，而不用關心g(z)，因此我們這里將g(z)做一個簡化，將其簡單映射到y(tǒng)=-1和y=1上。映射

5、關系如下： 4 函數(shù)間隔（functional margin）和幾何間隔（geometric margin）給定一個訓練樣本，x是特征，y是結果標簽。i表示第i個樣本。我們定義函數(shù)間隔如下： 可想而知，當時，在我們的g(z)定義中，的值實際上就是。反之亦然。為了使函數(shù)間隔最大（更大的信心確定該例是正例還是反例），當時，應該是個大正數(shù)，反之是個大負數(shù)。因此函數(shù)間隔代表了我們認為特征是正例還是反例的確信度。 繼續(xù)考慮w和b，如果同時加大w和b，比如在前面乘個系數(shù)比如2，那么所有點的函數(shù)間隔都會增大二倍，這個對求解問題來說不應該有影響，因為我們要求解的是，同時擴大w和b對結果是無影響的。這樣，我們?yōu)?/p>

6、了限制w和b，可能需要加入歸一化條件，畢竟求解的目標是確定唯一一個w和b，而不是多組線性相關的向量。這個歸一化一會再考慮。 剛剛我們定義的函數(shù)間隔是針對某一個樣本的，現(xiàn)在我們定義全局樣本上的函數(shù)間隔 說白了就是在訓練樣本上分類正例和負例確信度最小那個函數(shù)間隔。 接下來定義幾何間隔，先看圖 假設我們有了B點所在的分割面。任何其他一點，比如A到該面的距離以表示，假設B就是A在分割面上的投影。我們知道向量BA的方向是（分割面的梯度），單位向量是。A點是，所以B點是x=（利用初中的幾何知識），帶入得， 進一步得到 實際上就是點到平面距離。 再換種更加優(yōu)雅的寫法： 當時，不就是函數(shù)間隔嗎？是的，前面提到

7、的函數(shù)間隔歸一化結果就是幾何間隔。他們?yōu)槭裁磿粯幽兀恳驗楹瘮?shù)間隔是我們定義的，在定義的時候就有幾何間隔的色彩。同樣，同時擴大w和b，w擴大幾倍，就擴大幾倍，結果無影響。同樣定義全局的幾何間隔 5 最優(yōu)間隔分類器（optimal margin classifier）回想前面我們提到我們的目標是尋找一個超平面，使得離超平面比較近的點能有更大的間距。也就是我們不考慮所有的點都必須遠離超平面，我們關心求得的超平面能夠讓所有點中離它最近的點具有最大間距。形象的說，我們將上面的圖看作是一張紙，我們要找一條折線，按照這條折線折疊后，離折線最近的點的間距比其他折線都要大。形式化表示為： 這里用=1規(guī)約w，使

8、得是幾何間隔。 到此，我們已經(jīng)將模型定義出來了。如果求得了w和b，那么來一個特征x，我們就能夠分類了，稱為最優(yōu)間隔分類器。接下的問題就是如何求解w和b的問題了。 由于不是凸函數(shù)，我們想先處理轉化一下，考慮幾何間隔和函數(shù)間隔的關系，我們改寫一下上面的式子： 這時候其實我們求的最大值仍然是幾何間隔，只不過此時的w不受的約束了。然而這個時候目標函數(shù)仍然不是凸函數(shù)，沒法直接代入優(yōu)化軟件里計算。我們還要改寫。前面說到同時擴大w和b對結果沒有影響，但我們最后要求的仍然是w和b的確定值，不是他們的一組倍數(shù)值，因此，我們需要對做一些限制，以保證我們解是唯一的。這里為了簡便我們?nèi)?。這樣的意義是將全局的函數(shù)間隔定

9、義為1，也即是將離超平面最近的點的距離定義為。由于求的最大值相當于求的最小值，因此改寫后結果為： 這下好了，只有線性約束了，而且是個典型的二次規(guī)劃問題（目標函數(shù)是自變量的二次函數(shù)）。代入優(yōu)化軟件可解。 到這里發(fā)現(xiàn)，這個講義雖然沒有像其他講義一樣先畫好圖，畫好分類超平面，在圖上標示出間隔那么直觀，但每一步推導有理有據(jù)，依靠思路的流暢性來推導出目標函數(shù)和約束。 接下來介紹的是手工求解的方法了，一種更優(yōu)的求解方法。6 拉格朗日對偶（Lagrange duality）     先拋開上面的二次規(guī)劃問題，先來看看存在等式約束的極值問題求法，比如下面的最優(yōu)化問題：

10、             目標函數(shù)是f(w)，下面是等式約束。通常解法是引入拉格朗日算子，這里使用來表示算子，得到拉格朗日公式為              L是等式約束的個數(shù)。     然后分別對w和求偏導，使得偏導數(shù)等于0，然后解出w和。至于為什么引入拉格朗日算子可以求出極值，原因是f(w)的dw變化方向受其他不等式的約束，dw的變化方向與f(w)的梯度垂直時才能獲

11、得極值，而且在極值處，f(w)的梯度與其他等式梯度的線性組合平行，因此他們之間存在線性關系。（參考最優(yōu)化與KKT條件） 然后我們探討有不等式約束的極值問題求法，問題如下：              我們定義一般化的拉格朗日公式     這里的和都是拉格朗日算子。如果按這個公式求解，會出現(xiàn)問題，因為我們求解的是最小值，而這里的已經(jīng)不是0了，我們可以將調(diào)整成很大的正值，來使最后的函數(shù)結果是負無窮。因此我們需要排除這種情況，我們定義下面的函數(shù)：   &

12、#160;     這里的P代表primal。假設或者，那么我們總是可以調(diào)整和來使得有最大值為正無窮。而只有g和h滿足約束時，為f(w)。這個函數(shù)的精妙之處在于，而且求極大值。     因此我們可以寫作         這樣我們原來要求的min f(w)可以轉換成求了。             我們使用來表示。如果直接求解，首先面對的是兩個參數(shù)，而也是不等式約束，然后再在w上求最小值。這

13、個過程不容易做，那么怎么辦呢？     我們先考慮另外一個問題     D的意思是對偶，將問題轉化為先求拉格朗日關于w的最小值，將和看作是固定值。之后在求最大值的話：     這個問題是原問題的對偶問題，相對于原問題只是更換了min和max的順序，而一般更換順序的結果是Max Min(X) <= MinMax(X)。然而在這里兩者相等。用來表示對偶問題如下：         下面解釋在什么條件下兩者會等價。假設f和g都是凸函數(shù)，h是仿射的（

14、affine，）。并且存在w使得對于所有的i，。在這種假設下，一定存在使得是原問題的解，是對偶問題的解。還有另外，滿足庫恩-塔克條件（Karush-Kuhn-Tucker, KKT condition），該條件如下：         所以如果滿足了庫恩-塔克條件，那么他們就是原問題和對偶問題的解。讓我們再次審視公式（5），這個條件稱作是KKT dual complementarity條件。這個條件隱含了如果，那么。也就是說，時，w處于可行域的邊界上，這時才是起作用的約束。而其他位于可行域內(nèi)部（的）點都是不起作用的約束，其。這個KKT雙

15、重補足條件會用來解釋支持向量和SMO的收斂測試。     這部分內(nèi)容思路比較凌亂，還需要先研究下非線性規(guī)劃中的約束極值問題，再回頭看看。KKT的總體思想是將極值會在可行域邊界上取得，也就是不等式為0或等式約束里取得，而最優(yōu)下降方向一般是這些等式的線性組合，其中每個元素要么是不等式為0的約束，要么是等式約束。對于在可行域邊界內(nèi)的點，對最優(yōu)解不起作用，因此前面的系數(shù)為0。 7 最優(yōu)間隔分類器（optimal margin classifier）    重新回到SVM的優(yōu)化問題：       

16、;  我們將約束條件改寫為：         從KKT條件得知只有函數(shù)間隔是1（離超平面最近的點）的線性約束式前面的系數(shù)，也就是說這些約束式，對于其他的不在線上的點()，極值不會在他們所在的范圍內(nèi)取得，因此前面的系數(shù).注意每一個約束式實際就是一個訓練樣本。     看下面的圖：         實線是最大間隔超平面，假設×號的是正例，圓圈的是負例。在虛線上的點就是函數(shù)間隔是1的點，那么他們前面的系數(shù)，其他點都是。這三個點稱作支

17、持向量。構造拉格朗日函數(shù)如下：             注意到這里只有沒有是因為原問題中沒有等式約束，只有不等式約束。     下面我們按照對偶問題的求解步驟來一步步進行，         首先求解的最小值，對于固定的，的最小值只與w和b有關。對w和b分別求偏導數(shù)。             并得到   

18、60;     將上式帶回到拉格朗日函數(shù)中得到，此時得到的是該函數(shù)的最小值（目標函數(shù)是凸函數(shù)）     代入后，化簡過程如下：     最后得到     由于最后一項是0，因此簡化為         這里我們將向量內(nèi)積表示為     此時的拉格朗日函數(shù)只包含了變量。然而我們求出了才能得到w和b。     接著是極大化的過程，  

19、   前面提到過對偶問題和原問題滿足的幾個條件，首先由于目標函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對于所有的i，。因此，一定存在使得是原問題的解，是對偶問題的解。在這里，求就是求了。     如果求出了，根據(jù)即可求出w（也是，原問題的解）。然后         即可求出b。即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負的函數(shù)間隔。     關于上面的對偶問題如何求解，將留給下一篇中的SMO算法來闡明。   &

20、#160; 這里考慮另外一個問題，由于前面求解中得到         我們通篇考慮問題的出發(fā)點是，根據(jù)求解得到的，我們代入前式得到         也就是說，以前新來的要分類的樣本首先根據(jù)w和b做一次線性運算，然后看求的結果是大于0還是小于0,來判斷正例還是負例?，F(xiàn)在有了，我們不需要求出w，只需將新來的樣本和訓練數(shù)據(jù)中的所有樣本做內(nèi)積和即可。那有人會說，與前面所有的樣本都做運算是不是太耗時了？其實不然，我們從KKT條件中得到，只有支持向量的，其他情況。因此，我們只需求新來的樣

21、本和支持向量的內(nèi)積，然后運算即可。這種寫法為下面要提到的核函數(shù)（kernel）做了很好的鋪墊。這是上篇，先寫這么多了。支持向量機（三）核函數(shù) 7 核函數(shù)（Kernels） 考慮我們最初在“線性回歸”中提出的問題，特征是房子的面積x，這里的x是實數(shù)，結果y是房子的價格。假設我們從樣本點的分布中看到x和y符合3次曲線，那么我們希望使用x的三次多項式來逼近這些樣本點。那么首先需要將特征x擴展到三維，然后尋找特征和結果之間的模型。我們將這種特征變換稱作特征映射（feature mapping）。映射函數(shù)稱作，在這個例子中 我們希望將得到的特征映射后的特征應用于SVM分類，而不是最初的特征。這樣，我們需

22、要將前面公式中的內(nèi)積從，映射到。 至于為什么需要映射后的特征而不是最初的特征來參與計算，上面提到的（為了更好地擬合）是其中一個原因，另外的一個重要原因是樣例可能存在線性不可分的情況，而將特征映射到高維空間后，往往就可分了。（在數(shù)據(jù)挖掘導論Pang-Ning Tan等人著的支持向量機那一章有個很好的例子說明） 將核函數(shù)形式化定義，如果原始特征內(nèi)積是，映射后為，那么定義核函數(shù)（Kernel）為 到這里，我們可以得出結論，如果要實現(xiàn)該節(jié)開頭的效果，只需先計算，然后計算即可，然而這種計算方式是非常低效的。比如最初的特征是n維的，我們將其映射到維，然后再計算，這樣需要的時間。那么我們能不能想辦法減少計算

23、時間呢？ 先看一個例子，假設x和z都是n維的， 展開后，得 這個時候發(fā)現(xiàn)我們可以只計算原始特征x和z內(nèi)積的平方（時間復雜度是O(n)），就等價與計算映射后特征的內(nèi)積。也就是說我們不需要花時間了。 現(xiàn)在看一下映射函數(shù)（n=3時），根據(jù)上面的公式，得到 也就是說核函數(shù)只能在選擇這樣的作為映射函數(shù)時才能夠等價于映射后特征的內(nèi)積。 再看一個核函數(shù) 對應的映射函數(shù)（n=3時）是 更一般地，核函數(shù)對應的映射后特征維度為。（求解方法參見 由于計算的是內(nèi)積，我們可以想到IR中的余弦相似度，如果x和z向量夾角越小，那么核函數(shù)值越大，反之，越小。因此，核函數(shù)值是和的相似度。 再看另外一個核函數(shù) 這時，如果x和z很

24、相近（），那么核函數(shù)值為1，如果x和z相差很大（），那么核函數(shù)值約等于0。由于這個函數(shù)類似于高斯分布，因此稱為高斯核函數(shù)，也叫做徑向基函數(shù)(Radial Basis Function 簡稱RBF)。它能夠把原始特征映射到無窮維。 既然高斯核函數(shù)能夠比較x和z的相似度，并映射到0到1，回想logistic回歸，sigmoid函數(shù)可以，因此還有sigmoid核函數(shù)等等。 下面有張圖說明在低維線性不可分時，映射到高維后就可分了，使用高斯核函數(shù)。 來自Eric Xing的slides 注意，使用核函數(shù)后，怎么分類新來的樣本呢？線性的時候我們使用SVM學習出w和b，新來樣本x的話，我們使用來判斷，如果值

25、大于等于1，那么是正類，小于等于是負類。在兩者之間，認為無法確定。如果使用了核函數(shù)后，就變成了，是否先要找到，然后再預測？答案肯定不是了，找很麻煩，回想我們之前說過的 只需將替換成，然后值的判斷同上。 8 核函數(shù)有效性判定 問題：給定一個函數(shù)K，我們能否使用K來替代計算，也就說，是否能夠找出一個，使得對于所有的x和z，都有？ 比如給出了，是否能夠認為K是一個有效的核函數(shù)。 下面來解決這個問題，給定m個訓練樣本，每一個對應一個特征向量。那么，我們可以將任意兩個和帶入K中，計算得到。I可以從1到m，j可以從1到m，這樣可以計算出m*m的核函數(shù)矩陣（Kernel Matrix）。為了方便，我們將核函

26、數(shù)矩陣和都使用K來表示。 如果假設K是有效地核函數(shù)，那么根據(jù)核函數(shù)定義 可見，矩陣K應該是個對稱陣。讓我們得出一個更強的結論，首先使用符號來表示映射函數(shù)的第k維屬性值。那么對于任意向量z，得 最后一步和前面計算時類似。從這個公式我們可以看出，如果K是個有效的核函數(shù)（即和等價），那么，在訓練集上得到的核函數(shù)矩陣K應該是半正定的（） 這樣我們得到一個核函數(shù)的必要條件： K是有效的核函數(shù) => 核函數(shù)矩陣K是對稱半正定的。 可幸的是，這個條件也是充分的，由Mercer定理來表達。 Mercer定理： 如果函數(shù)K是上的映射（也就是從兩個n維向量映射到實數(shù)域）。那么如果K是一個有效核函數(shù)（也稱為M

27、ercer核函數(shù)），那么當且僅當對于訓練樣例，其相應的核函數(shù)矩陣是對稱半正定的。Mercer定理表明為了證明K是有效的核函數(shù)，那么我們不用去尋找，而只需要在訓練集上求出各個，然后判斷矩陣K是否是半正定（使用左上角主子式大于等于零等方法）即可。 許多其他的教科書在Mercer定理證明過程中使用了范數(shù)和再生希爾伯特空間等概念，但在特征是n維的情況下，這里給出的證明是等價的。 核函數(shù)不僅僅用在SVM上，但凡在一個模型后算法中出現(xiàn)了，我們都可以常使用去替換，這可能能夠很好地改善我們的算法。9 規(guī)則化和不可分情況處理（Regularization and the non-separable case）

28、我們之前討論的情況都是建立在樣例線性可分的假設上，當樣例線性不可分時，我們可以嘗試使用核函數(shù)來將特征映射到高維，這樣很可能就可分了。然而，映射后我們也不能100%保證可分。那怎么辦呢，我們需要將模型進行調(diào)整，以保證在不可分的情況下，也能夠盡可能地找出分隔超平面。 看下面兩張圖： 可以看到一個離群點（可能是噪聲）可以造成超平面的移動，間隔縮小，可見以前的模型對噪聲非常敏感。再有甚者，如果離群點在另外一個類中，那么這時候就是線性不可分了。 這時候我們應該允許一些點游離并在在模型中違背限制條件（函數(shù)間隔大于1）。我們設計得到新的模型如下（也稱軟間隔）： 引入非負參數(shù)后（稱為松弛變量），就允許某些樣本

29、點的函數(shù)間隔小于1，即在最大間隔區(qū)間里面，或者函數(shù)間隔是負數(shù)，即樣本點在對方的區(qū)域中。而放松限制條件后，我們需要重新調(diào)整目標函數(shù)，以對離群點進行處罰，目標函數(shù)后面加上的就表示離群點越多，目標函數(shù)值越大，而我們要求的是盡可能小的目標函數(shù)值。這里的C是離群點的權重，C越大表明離群點對目標函數(shù)影響越大，也就是越不希望看到離群點。我們看到，目標函數(shù)控制了離群點的數(shù)目和程度，使大部分樣本點仍然遵守限制條件。 模型修改后，拉格朗日公式也要修改如下： 這里的和都是拉格朗日乘子，回想我們在拉格朗日對偶中提到的求法，先寫出拉格朗日公式（如上），然后將其看作是變量w和b的函數(shù)，分別對其求偏導，得到w和b的表達式。

30、然后代入公式中，求帶入后公式的極大值。整個推導過程類似以前的模型，這里只寫出最后結果如下： 此時，我們發(fā)現(xiàn)沒有了參數(shù)，與之前模型唯一不同在于又多了的限制條件。需要提醒的是，b的求值公式也發(fā)生了改變，改變結果在SMO算法里面介紹。先看看KKT條件的變化： 第一個式子表明在兩條間隔線外的樣本點前面的系數(shù)為0，離群樣本點前面的系數(shù)為C，而支持向量（也就是在超平面兩邊的最大間隔線上）的樣本點前面系數(shù)在(0,C)上。通過KKT條件可知，某些在最大間隔線上的樣本點也不是支持向量，相反也可能是離群點。 10 坐標上升法（Coordinate ascent） 在最后討論的求解之前，我們先看看坐標上升法的基本原

31、理。假設要求解下面的優(yōu)化問題： 這里W是向量的函數(shù)。之前我們在回歸中提到過兩種求最優(yōu)解的方法，一種是梯度下降法，另外一種是牛頓法。現(xiàn)在我們再講一種方法稱為坐標上升法（求解最小值問題時，稱作坐標下降法，原理一樣）。 方法過程： 最里面語句的意思是固定除之外的所有，這時W可看作只是關于的函數(shù)，那么直接對求導優(yōu)化即可。這里我們進行最大化求導的順序i是從1到m，可以通過更改優(yōu)化順序來使W能夠更快地增加并收斂。如果W在內(nèi)循環(huán)中能夠很快地達到最優(yōu)，那么坐標上升法會是一個很高效的求極值方法。 下面通過一張圖來展示： 橢圓代表了二次函數(shù)的各個等高線，變量數(shù)為2，起始坐標是(2,-2)。圖中的直線式迭代優(yōu)化的路

32、徑，可以看到每一步都會向最優(yōu)值前進一步，而且前進路線是平行于坐標軸的，因為每一步只優(yōu)化一個變量。11 SMO優(yōu)化算法（Sequential minimal optimization） SMO算法由Microsoft Research的John C. Platt在1998年提出，并成為最快的二次規(guī)劃優(yōu)化算法，特別針對線性SVM和數(shù)據(jù)稀疏時性能更優(yōu)。關于SMO最好的資料就是他本人寫的Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines了。 我拜讀了一下，下面先說講義上對此方法的總結

33、。 首先回到我們前面一直懸而未解的問題，對偶函數(shù)最后的優(yōu)化問題： 要解決的是在參數(shù)上求最大值W的問題，至于和都是已知數(shù)。C由我們預先設定，也是已知數(shù)。 按照坐標上升的思路，我們首先固定除以外的所有參數(shù)，然后在上求極值。等一下，這個思路有問題，因為如果固定以外的所有參數(shù)，那么將不再是變量（可以由其他值推出），因為問題中規(guī)定了 因此，我們需要一次選取兩個參數(shù)做優(yōu)化，比如和，此時可以由和其他參數(shù)表示出來。這樣回帶到W中，W就只是關于的函數(shù)了，可解。 這樣，SMO的主要步驟如下： 意思是，第一步選取一對和，選取方法使用啟發(fā)式方法（后面講）。第二步，固定除和之外的其他參數(shù)，確定W極值條件下的，由表示。

34、SMO之所以高效就是因為在固定其他參數(shù)后，對一個參數(shù)優(yōu)化過程很高效。 下面討論具體方法： 假設我們選取了初始值滿足了問題中的約束條件。接下來，我們固定，這樣W就是和的函數(shù)。并且和滿足條件： 由于都是已知固定值，因此為了方面，可將等式右邊標記成實數(shù)值。 當和異號時，也就是一個為1，一個為-1時，他們可以表示成一條直線，斜率為1。如下圖： 橫軸是，縱軸是，和既要在矩形方框內(nèi)，也要在直線上，因此 ， 同理，當和同號時， ， 然后我們打算將用表示： 然后反代入W中，得 展開后W可以表示成。其中a,b,c是固定值。這樣，通過對W進行求導可以得到，然而要保證滿足，我們使用表示求導求出來的，然而最后的，要根

35、據(jù)下面情況得到： 這樣得到后，我們可以得到的新值。 下面進入Platt的文章，來找到啟發(fā)式搜索的方法和求b值的公式。 這邊文章使用的符號表示有點不太一樣，不過實質(zhì)是一樣的，先來熟悉一下文章中符號的表示。 文章中定義特征到結果的輸出函數(shù)為 與我們之前的實質(zhì)是一致的。 原始的優(yōu)化問題為： 求導得到： 經(jīng)過對偶后為： s.t. 這里與W函數(shù)是一樣的，只是符號求反后，變成求最小值了。和是一樣的，都表示第i個樣本的輸出結果（1或-1）。 經(jīng)過加入松弛變量后，模型修改為： 由公式（7）代入（1）中可知， 這個過程和之前對偶過程一樣。 重新整理我們要求的問題為： 與之對應的KKT條件為： 這個KKT條件說明

36、，在兩條間隔線外面的點，對應前面的系數(shù)為0，在兩條間隔線里面的對應為C，在兩條間隔線上的對應的系數(shù)在0和C之間。 將我們之前得到L和H重新拿過來： 之前我們將問題進行到這里，然后說將用表示后代入W中，這里將代入中，得 其中 這里的和代表某次迭代前的原始值，因此是常數(shù)，而和是變量，待求。公式（24）中的最后一項是常數(shù)。 由于和滿足以下公式 因為的值是固定值，在迭代前后不會變。 那么用s表示，上式兩邊乘以時，變?yōu)椋?其中 代入（24）中，得 這時候只有是變量了，求導 如果的二階導數(shù)大于0（凹函數(shù)），那么一階導數(shù)為0時，就是極小值了。 假設其二階導數(shù)為0（一般成立），那么上式化簡為： 將w和v代入后

37、，繼續(xù)化簡推導，得（推導了六七行推出來了） 我們使用來表示： 通常情況下目標函數(shù)是正定的，也就是說，能夠在直線約束方向上求得最小值，并且。 那么我們在（30）兩邊都除以可以得到 這里我們使用表示優(yōu)化后的值，是迭代前的值，。 與之前提到的一樣不是最終迭代后的值，需要進行約束： 那么 在特殊情況下，可能不為正，如果核函數(shù)K不滿足Mercer定理，那么目標函數(shù)可能變得非正定，可能出現(xiàn)負值。即使K是有效的核函數(shù)，如果訓練樣本中出現(xiàn)相同的特征x，那么仍有可能為0。SMO算法在不為正值的情況下仍有效。為保證有效性，我們可以推導出就是的二階導數(shù)，沒有極小值，最小值在邊緣處取到（類比），時更是單調(diào)函數(shù)了，最小值也在邊緣處取得，而的邊緣就是L和H。這樣將和分別代入中即可求得的最小值，相應的還是也可以知道了。具體計算公式如下： 至此，迭代關系式出了b的推導式以外，都已經(jīng)推出。 b每一步都要更新，因為前面的KKT條件指出了和的關系，而和b