matlabsmo演算法

1. 支持向量機原理講解（一）

支持向量機(Support Vector Machine,以下簡稱SVM)，作為傳統機器學習的一個非常重要的分類演算法，它是一種通用的前饋網路類型，最早是由Vladimir N.Vapnik 和 Alexey Ya.Chervonenkis在1963年提出，目前的版本（soft margin）是Corinna Cortes 和 Vapnik在1993年提出，1995年發表。深度學習（2012）出現之前，如果不考慮集成學習的演算法，不考慮特定的訓練數據集，在分類演算法中的表現SVM說是排第一估計是沒有什麼異議的。

SVM本來是一種線性分類和非線性分類都支持的二元分類演算法，但經過演變，現在也支持多分類問題，也能應用到了回歸問題。本篇文章重點講解線性支持向量機的模型原理和目標函數優化原理。

在講解SVM模型之前，我們可以先簡單了解感知機模型的原理，因為這兩個模型有一些相同的地方。在二維平面中，感知機模型是去找到一條直線，盡可能地將兩個不同類別的樣本點分開。同理，在三維甚至更高維空間中，就是要去找到一個超平面。定義這個超平面為wTx+b=0（在二維平面中，就相當於直線w_1 x+w_1 y+b=0），而在超平面上方的點，定義為y=1，在超平面下方的點，定義為y=-1。而這樣的超平面可能是不唯一的，那麼感知機是怎麼定期最優超平面呢？從感知機模型的目標函數中，我們了解到它是希望讓所有誤分類的點(定義為M)到超平面的距離和最小。其目標函數如下：

(註：加入 是因為點若在超平面下， 為負數，需要乘上對應的 )

當w和b成比例增加了之後，比如都擴大N倍，會發現，分子和分母都會同時擴大N倍，這對目標函數並不影響。因此，當我們將W擴大或縮小一定倍數使得，||w||=1，分子也會相應的擴大或縮小，這樣，目標函數就能簡化成以下形式：

這個思想將會應用到支持向量機的目標函數優化上，後文將會詳細講解。

正如上文所說，線性支持向量機的思想跟感知機的思想很相似。其思想也是對給定的訓練樣本，找到一個超平面去盡可能的分隔更多正反例。不同的是其選擇最優的超平面是基於正反例離這個超平面盡可能遠。

從上圖可以發現，其實只要我們能保證距離超平面最近的那些點離超平面盡可能遠，就能保證所有的正反例離這個超平面盡可能的遠。因此，我們定義這些距離超平面最近的點為支持向量（如上圖中虛線所穿過的點）。並且定義正負支持向量的距離為Margin。

對SVM思想有一定理解之後，設超平面為 。我們講解一下函數間隔和幾何間隔的區別。

給定一個樣本 ， 表示點x到超平面的距離。通過觀察 和 是否同號，我們判斷分類是否正確。所以函數間隔定義 為：

而函數間隔不能正常反應點到超平面的距離，因為當我們等比例擴大 和 的時候，函數間隔也會擴大相應的倍數。因此，我們引入幾何間隔。

幾何間隔就是在函數間隔的基礎下，在分母上對 加上約束（這個約束有點像歸一化），定義為 ：

其實參考點到直線的距離，我們可以發現幾何間隔就是高維空間中點到超平面的距離，才能真正反映點到超平面的距離。

根據SVM的思想，我們可以知道是要取最大化支持向量到超平面的幾何間隔，所以目標函數可以表示為：

在感知機模型最後，我們知道當同時擴大w和b，分子分母都會同樣擴大，對目標函數不影響，所以在這里我們將分子(支持向量到超平面的函數間隔)擴大或壓縮等於1，則目標函數可以轉化為：

但是上式並不是凸函數，不好求解，再進一步轉化為：

上式就是一個凸函數，並且不等式約束為仿射函數，因此可以使用拉格朗日對偶去求解該問題。

根據拉格朗日乘子法，引入拉格朗日乘子α，且α≥0我們可以知道，先不考慮min，(2)問題等價於：

然後再考慮min，則有：

應用拉格朗日對偶性，通過求解對偶問題得到最優解，則對偶問題的目標函數為：

這就是線性可分條件下支持向量機的對偶演算法。這樣做的優點在於：一是原問題的對偶問題往往更容易求解，二者可以自然的引入核函數，進而推廣到非線性分類問題。

從(4)中，我們可以先求目標函數對於 和 的極小值，再求拉格朗日乘子 的極大值。

首先，分別對 和 分別求偏導數，並令為0：

得：

將(5)和(6)代入(4)得到：

對(7)取反得到：

只要我們可以求出(8)中極小化的 向量，那麼我們就可以對應的得到 和 ，而求解 需要使用SMO演算法，由於該演算法比較復雜，我們將在下一篇文章專門講解。假設我們現在已經使用SMO演算法得到了最優的 值，記為

再求 ：

對於任一樣本 有：

注意到任一樣本都有 ，則將右式的1用 代：

將(9)代入上式，可以得到：

這樣，我們就能夠求解得到線性支持向量機的目標函數的各個參數，進而得到最優的超平面，將正負樣本分隔開。但是在上文中我們沒有講解求 向量的SMO演算法，在下篇文章，將會詳細講解SMO演算法，歡迎繼續關注。

2. SVM演算法，包括演算法原理、演算法實現、核函數參數的選取、優化、系數調整，能通俗地說明下嗎謝謝

SVM 原理，在一個超空間找一個 切分的超平面，
SVM 演算法實現，主要是解決SVM公式對偶問題，常用的是SMO，
SVM 核參數，隱含的將特徵映射到高維空間，有興趣可學習 learn with kernel.
SVM 參數調整分兩部分，1 參數調整，用上述SMO演算法，2 模型選擇。

太累，不想寫太多

3. 機器學習實戰 SMO演算法是否寫錯了

我確定，里頭的完整版SMO演算法是寫錯了。在尋找第二個變數時，每次只找了一個，優化失敗後就放棄了，重新挑選第一個變數。這樣最後演算法結束後，還有不少變數不滿足KKT條件。我一度以為這個演算法不能收斂到全局最優。而且每次運行結果都不一樣。後來，我把代碼改了一下，在尋找第二個變數時，把所有可能符合條件的變數都嘗試一遍。這樣，演算法就能收斂了。運行結束後，所有變數都能滿足KKT條件。

4. 支持向量機（SVM）

        支持向量機（support vector machine），故一般簡稱SVM，通俗來講，它是一種二分類模型，其基本模型定義為特徵空間上的間隔最大的線性分類器，這族分類器的特點是他們能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機也被稱為最大邊緣區分類器。其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。SVM在很多諸如文本分類，圖像分類，生物序列分析和生物數據挖掘，手寫字元識別等領域有很多的應用。

        支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面，分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。

        假設給定一些分屬於兩類的2維點，這些點可以通過直線分割， 我們要找到一條最優的分割線，如何來界定一個超平面是不是最優的呢?

        如圖：

        在上面的圖中，a和b都可以作為分類超平面，但最優超平面只有一個，最優分類平面使間隔最大化。 那是不是某條直線比其他的更加合適呢? 我們可以憑直覺來定義一條評價直線好壞的標准:

        距離樣本太近的直線不是最優的，因為這樣的直線對雜訊敏感度高，泛化性較差。 因此我們的目標是找到一條直線（圖中的最優超平面），離所有點的距離最遠。 由此， SVM演算法的實質是找出一個能夠將某個值最大化的超平面，這個值就是超平面離所有訓練樣本的最小距離。這個最小距離用SVM術語來說叫做間隔(margin) 。

        描述：給定一些數據點，它們分別屬於兩個不同的類，現在要找到一個線性分類器把這些數據分成兩類。如果用x表示數據點，用y表示類別（y可以取1或者-1，分別代表兩個不同的類），一個線性分類器的學習目標便是要在n維的數據空間中找到一個超平面（hyper plane），這個超平面的方程可以表示為（ wT中的T代表轉置）：

        例如：現在有一個二維平面，平面上有兩種不同的數據，分別用圈和叉表示。由於這些數據是線性可分的，所以可以用一條直線將這兩類數據分開，這條直線就相當於一個超平面，超平面一邊的數據點所對應的y全是-1 ，另一邊所對應的y全是1。

        我們令分類函數為：

        當f(x) 等於0的時候，x便是位於超平面上的點，而f(x)大於0的點對應 y=1 的數據點，f(x)小於0的點對應y=-1的點，如下圖所示：

        一個點距離超平面的遠近可以表示分類預測的確信或准確程度，如何確定這個超平面呢？從直觀上而言，這個超平面應該是最適合分開兩類數據的直線。而判定「最適合」的標准就是這條直線離直線兩邊的數據的間隔最大。所以，得尋找有著最大間隔的超平面。

補充知識點： 點到平面的距離

        支持向量機學習的基本想法是求解能夠正確劃分訓練數據集並且幾何間隔最大的分離超平面.。對線性可分的訓練數據集而言，線性可分分離超平面有無窮多個(等價於感知機)，但是幾何間隔最大的分離超平面是唯一的。這里的間隔最大化又稱為硬間隔最大化。

        間隔最大化的直觀解釋是:對訓練數據集找到幾何間隔最大的超平面意味著以充分大的確信度對訓練數據進行分類。也就是說，不僅將正負實例點分開，而且對最難分的實例點(離超平面最近的點)也有足夠大的確信度將它們分開。這樣的超平面應該對未知的新實例有很好的分類預測能力。

      按照我們前面的分析，對一個數據點進行分類， 當它的margin越大的時候，分類的confidence越大。 對於一個包含n個點的數據集，我們可以很自然地定義它的margin為所有這n個點的margin值中最小的那個。於是，為了使得分類的confidence高，我們希望所選擇的超平面hyper plane能夠最大化這個margin值。讓所選擇的超平面能夠最大化這個「間隔」值，這個間隔就是下圖中的Gap的一半：

為什麼用幾何間隔求最大的分離超平面而不用函數間隔？

例題：

我們構造了約束最優化問題，就是下面這個：

        此外，由於這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變數 (al variable) 的優化問題，即通過求解與原問題等價的對偶問題（al problem）得到原始問題的最優解，這就是線性可分條件下支持向量機的對偶演算法，這樣做的優點在於：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。

補充知識點： 拉格朗日乘子法學習

                     拉格朗日KKT條件

                     KKT條件介紹

                     拉格朗日對偶

         通過給每一個約束條件加上一個拉格朗日乘子（Lagrange multiplier）α，定義拉格朗日函數（通過拉格朗日函數將約束條件融合到目標函數里去，從而只用一個函數表達式便能清楚的表達出我們的問題）：

 求解這個式子的過程需要拉格朗日對偶性的相關知識。

例題：

         接下來談談線性不可分的情況，因為 線性可分這種假設實在是太有局限性 了。下圖就是一個典型的線性不可分的分類圖，我們沒有辦法用一條直線去將其分成兩個區域，每個區域只包含一種顏色的點。

         要想在這種情況下的分類器，有兩種方式， 一種是用曲線 去將其完全分開，曲線就是一種 非線性 的情況，跟之後將談到的 核函數 有一定的關系：

         另外一種還是用直線，不過不用去保證可分性 ，就是包容那些分錯的情況，不過我們得加入懲罰函數，使得點分錯的情況越合理越好。其實在很多時候，不是在訓練的時候分類函數越完美越好，因為訓練函數中有些數據本來就是雜訊，可能就是在人工加上分類標簽的時候加錯了，如果我們在訓練（學習）的時候把這些錯誤的點學習到了，那麼模型在下次碰到這些錯誤情況的時候就難免出錯了。這種學習的時候學到了「雜訊」的過程就是一個過擬合（over-fitting），這在機器學習中是一個大忌。

我們可以為分錯的點加上一點懲罰，對一個分錯的點的 懲罰函數 就是 這個點到其正確位置的距離：

        對於線性不可分的情況，我們可以用核函數讓空間從原本的線性空間變成一個更高維的空間 ， 在這個高維的線性空間下，再用一個超平面進行劃分 。 這兒舉個例子，來理解一下如何利用空間的維度變得更高來幫助我們分類的：

        上圖是一個線性不可分的圖，當我們把這兩個類似於橢圓形的點映射到一個高維空間後，映射函數為：

        用這個函數可以將上圖的平面中的點映射到一個三維空間（z1,z2,z3)，並且對映射後的坐標加以旋轉之後就可以得到一個線性可分的點集了。

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

核函數定義：

核技巧在支持向量機中的應用：

常用核函數：

非線性支持向量機學習演算法：

        支持向量機的學習問題可以形式化為求解凸二次規劃問題。這樣的凸二次規劃問題具有全局最優解，並且有許多最優化演算法可以用於這一一問題的求解。但是當訓練樣本容量很大時，這些演算法往往變得非常低效，以致無法使用。所以，如何高效地實現支持向量機學習就成為一一個重要的問題。目前人們已提出許多快速實現演算法.本節講述其中的序列最小最優化(sequential minimal optimization, SMO)演算法。

        上述問題是要求解N個參數(α1,α2,α3,...,αN)，其他參數均為已知，序列最小最優化演算法(SMO)可以高效的求解上述SVM問題，它把原始求解N個參數二次規劃問題分解成很多個子二次規劃問題分別求解，每個子問題只需要求解2個參數，方法類似於坐標上升，節省時間成本和降低了內存需求。每次啟發式選擇兩個變數進行優化，不斷循環，直到達到函數最優值。

        整個SMO演算法包括兩部分，求解兩個變數的 二次規劃 問題和選擇這兩個變數的 啟發式 方法。

 上面求得的(α1)new和(α2)new是在η>0的情況下求得的：

        當時為了推導公式我們直接默認它是大於0了，現在我們需要重新審視這一項（η）。這一項是原來關於的二次項的系數。我們可以分下面三種情況討論：

（1）當η>0時 ：這個二次函數開口向上，所以要求這個二次函數的最小值，如果說極值點不在計算出的可行域的范圍內，就要根據這個極值點和可行域邊界值的關系來得到取最小值的地方：

①如果這個極值點在可行域左邊，那麼我們可以得到這個可行域內二次函數一定在單增，所以此時L應該是那個取最小值的地方。就如大括弧的第三種情況。

②如果這個極值點在可行域右邊，那麼此時可行域內一定單減，所以此時H就是那個取最小值的地方，就是大括弧里的第一種情況。

（2）當η=0時： 這個二次函數就變成了一個一次函數，那麼不管這個一次函數的單調性怎樣，最小值一定是在邊界處取到。所以到時候計算可行域的兩個邊界的值，看哪個小就用哪個。

（3）當η<0時: 這個二次函數開口向下，那麼此時怎麼得到取最小值的點呢？很容易就能想到：最小值也是在可行域的邊界處取到。很容易理解，此時開口向下，當極值點在區間內時，最小值只能在端點處取，因為極值點處是最大的。而當極值點在區間外時，區間內一定是單調的，此時最小值也只能在端點處取。通過計算比較邊界處的目標函數值，哪個小取哪個。

通過以上判斷求出(α2)new以後，再根據公式求出(α1)new，然後帶入目標函數（1）中。即如下過程：

        上述分析是在從N個變數中已經選出兩個變數進行優化的方法，下面分析如何高效地選擇兩個變數進行優化，使得目標函數下降的最快。

5. 支持向量機基本原理 matlab程序及其應用

支持向量機
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 ality）
先拋開上面的二次規劃問題，先來看看存在等式約束的極值問題求法，比如下面的最優化問題：

目標函數是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 al 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時）是

更一般地，核函數 對應的映射後特徵維度為 。（這個我一直沒有理解）。
由於計算的是內積，我們可以想到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，那麼是正類，小於等於是負類。在兩者之間，認為無法確定。如果使用了核函數後， 就變成了 ，是否先要找到 ，然後再預測？答案肯定不是了，找 很麻煩，回想我們之前說過的

只需將 替換成 ，然後值的判斷同上。

6. 深度學習為什麼會出現局部最優問題

對於二次規劃的求解可採用SMO演算法。對於回歸問題，需要依靠不敏感損失函數。

SVM在解決小樣本、非線性及高維模式識別中表現出許多特有的優勢。

支持向量機方法是在機器學習理論指導下專門針對有限樣本設計的學習方法，不僅對於小樣本問題可以得到最優解，而且SVM模型具有很強的泛化能力。更
為突出的是SVM最終轉化為求解一個凸二次規劃問題，在理論上可以得到全局最優解，克服了一些傳統方法（如神經網路方法）可能陷入局部極值的不足。雖然
SVM與神經網路相比有明顯優勢，但在實際應用中還存在一些問題，比如對於大規模的數據集，由於SVM要解凸二次規劃而使演算法效率很低，甚至無法進
行；SVM對奇異值的穩健性不高；SVM的解不具有稀疏性，存在著大量冗餘支撐向量；其參數沒有好的選擇策略。