第八章支撐向量機目錄1.支持向量機的引入2.線性可分支持向量機的學習3.線性支持向量機的學習4.非線性支持向量機的學習5.SMO算法間隔的概念在正式介紹支持向量機模型及其學習算法之前，本節我們先對其涉及到的一些基本概念進行闡述。對于給定的訓練數據集其中，，，.這里稱的樣例為正例，反之為負例。數據集的線性可分性

給出的訓練數據集，存在法向量位移項，使得超平面能夠將數據集

中的不同類別的樣例正確地劃分開，即：

則稱該數據集為線性可分數據集，否則稱該數據線性不可分?，F要找出一個線性分類器將兩種類別的樣本（假定它們是線性可分的）分開，即在n維的樣本空間中找到一個劃分超平面“分隔”兩種類別的樣本.劃分超平面對應于下面的方程:其中是法向量，b是位移項。劃分超平面由這兩個參數唯一確定.劃分超平面將特征空間分為兩個部分.超平面

特征空間的任一點x到超平面的距離定義為：由上述公式，和確定，則超平面確定，此時可以衡量點到超平面的距離.對樣本來說，通過觀察與的符號是否一致判斷分類是否正。因此，可以通過的符號來判斷分類結果是否正確。由此，我們引出間隔的概念。超平面給定一個訓練樣本，定義單個樣本的函數間隔為：當時，，的值為；當時，，的值為。當時，我們希望是一個大的正數，反之應該是一個大的負數.因此函數間隔代表了我們認為特征是正例還是負例的確信度。函數間隔上面定義了單個樣本的間隔，現在給出關于訓練數據集的函數間隔的定義：也就是說，全局樣本的函數間隔指的是在訓練數據集上最小的那個函數間隔。函數間隔上面定義了單個樣本的間隔，現在給出關于訓練數據集的函數間隔的定義：也就是說，全局樣本的函數間隔指的是在訓練數據集上最小的那個函數間隔。不難發現，這樣定義的函數間隔是有問題的。當和成比例變化時（例如同時變成原來的3倍），超平面并不會發生改變，但函數間隔卻變成了原來的3倍。函數間隔上面定義了單個樣本的間隔，現在給出關于訓練數據集的函數間隔的定義：也就是說，全局樣本的函數間隔指的是在訓練數據集上最小的那個函數間隔。不難發現，這樣定義的函數間隔是有問題的。當和成比例變化時（例如同時變成原來的3倍），超平面并不會發生改變，但函數間隔卻變成了原來的3倍。事實上，我們可以對法向量加些約束條件來解決這個問題。從而引出了真正定義點到超平面的距離——幾何間隔（GeometricalMargin）的概念。函數間隔如圖所示，給定超平面，設A為任一個樣本（不妨設其在超平面劃分空間的正面），B點為其在超平面的投影，則BA的方向為。設B到該超平面的距離為，那么我們很容易知道B點可以表示為

將其帶入到超平面中得到：由此推出：這里的實際上就是點到平面距離.幾何間隔當點位于超平面的另一側時，寫作：即當樣本被正確分類時，到劃分超平面的距離是：對于給定的訓練集，稱：

為超平面關于單個樣本點的幾何間隔，同樣定義為全局樣本的幾何間隔。可以發現，時，幾何間隔其實就是函數間隔。并且，有下式成立：幾何間隔支持向量機是定義在特征空間上的間隔最大的線性分類器，它的學習思想是找到能夠正確劃分訓練數據集并且使得幾何間隔最大的分離超平面。最大幾何間隔分離超平面的求解可以表述為下面的帶約束最優化問題：由幾何間隔與函數間隔的關系，上式可以寫作：最大間隔分離超平面

支撐矢量機學習算法根據訓練數據是否線性可分，支持向量機方法可分為三種模型：線性可分支持向量機線性支持向量機非線性向量機線性可分支持向量機對于給定的線性可分的訓練數據集，通過間隔最大化或等價地求解相應的凸二次規劃問題學習得到的分離超平面為以及相應的分類決策函數稱為線性可分支持向量機。線性可分支持向量機對于給定的線性可分的訓練數據集，通過間隔最大化或等價地求解相應的凸二次規劃問題學習得到的分離超平面為以及相應的分類決策函數稱為線性可分支持向量機。

對于線性可分數據集，由于函數間隔的改變對上述最優化問題沒有影響，我們可以取。即我們將全局的函數間隔定義為1，也即是定義離超平面最近的點的距離為。對目標函數進行改寫后，得到如下的優化問題：

式（1）線性可分SVM的學習算法——最大間隔法輸入：線性可分的訓練數據集，其中，，。通過求解上式（1）的約束最優化問題得到最優解，和，從而得到最大間隔分離超平面和分類決策函數。輸出：最大間隔劃分超平面和分類決策函數。對線性可分的數據集，特征空間中存在無數的劃分超平面將兩類數據正確分離開。但由上述的最大間隔法求得的劃分超平面是存在且唯一的。支持向量在線性可分的前提下，使得上式（1）中約束中等號成立的點（即滿足的點）稱為支持向量。線性可分SVM的對偶學習考慮式（1）的求解問題，根據拉格朗日函數的對偶性，可以通過求解其對偶問題得到該問題的解。我們將約束條件改寫為：在這里，每一個約束都表示一個訓練樣本。構造拉格朗日函數為

式（2）

這里引入了拉格朗日乘子根據拉格朗日函數的對偶性，將原始問題轉化為其對偶問題：首先，我們固定求的極小值，對和分別求偏導數并令其等于0，即：

式（3）得到:

式（4）將式（3）代入式（2）拉格朗日函數表達式，又由式（4），，代入上式即得：由此就求出了，接著求解關于的極大化，也就是：上式又與下面的最優化問題等價：式（5）如果是式（5）最優化問題的解，則一定存在和成為原始最優化問題的解，這里

式（6）式（7）因此我們可以得到分離超平面為，以及分類決策函數。這就是線性可分支持向量機的對偶學習算法。對線性可分數據集，通過構造并求解約束優化問題（5）得到最優解，選擇的一個正分量，然后根據（6）式和（7）式得到最優解，。從而求出了具有最大間隔的劃分超平面與分類決策函數。對于給定數據集，其中，，。若此時數據集中存在一些特異點（outlier），將這些特異點除去后，剩下大部分的樣本點組成的集合是線性可分的。顯然此時由于某些樣本點無法再滿足函數間隔大于的條件，我們不能再用上節的線性可分問題的支持向量機學習方法求解線性SVM的學習線性不可分的線性支持向量機的學習問題是如下的凸二次規劃問題：

式（8）這里引入了松弛變量，目標函數增加相應的代價，為懲罰參數。最小化目標函數，即在最大化間隔的同時，使得誤分類點的數量盡量小。支持向量機的對偶學習式（8）中的凸二次規劃問題解存在。唯一，而的解存在于一個區間。設解為，，由此得到分離超平面及分類決策函數，即得到了訓練樣本線性不可分時的線性支持向量機，簡稱為線性支持向量機。事實上，線性可分支持向量機也是線性支持向量機的一種情形。式（8）的拉格朗日函數為：

這里，。與上節對偶問題的推導過程類似，由拉格朗日的對偶性，原問題的對偶問題是極大極小問題，可以得到（8）式的對偶問題是：

式（9）對比式（5）和式（9）發現，線性可分支持向量與線性支持向量機的對偶問題的唯一差別就是對偶變量的約束不一樣：線性可分支持向量機要求，線性支持向量機要求。通過求解對偶問題可以得到原始問題的解。設對偶問題的一個解為，

則原始問題（8）的解為：從而得到了分離超平面和分類決策函數。至此我們也得出了線性支持向量機的學習算法。數據線性不可分時，將對偶問題（9）的解中對應于的樣本點的樣本點稱為軟間隔的支持向量。當，，此時支持向量恰好落在間隔邊界上；若，，則分類正確，支持向量在間隔邊界與分離超平面之間；若，，支持向量在分離超平面上；若，，則支持向量位于分離超平面誤分的一側。軟間隔支持向量數據線性不可分時，將對偶問題（9）的解中對應于的樣本點的樣本點稱為軟間隔的支持向量。軟間隔支撐向量具有如下性質：當，，此時支持向量恰好落在間隔邊界上；若，，則分類正確，支持向量在間隔邊界與分離超平面之間；若，，支持向量在分離超平面上；若，，則支持向量位于分離超平面誤分的一側。軟間隔支持向量線性分類支持向量機可以有效求解線性分類問題。然而，對于非線性分類問題的求解，則需要應用本節介紹的非線性支持向量機方法。我們通過一個小例子引入本節要討論的問題?，F有一個房屋銷售數據如下表所示：假設特征是房子的面積x,房子的價格是結果y。非線性支持向量機的學習面積（m^2）銷售價格（萬元）12325015032087160102220…………線性分類支持向量機可以有效求解線性分類問題。然而，對于非線性分類問題的求解，則需要應用本節介紹的非線性支持向量機方法。我們通過一個小例子引入本節要討論的問題?，F有一個房屋銷售數據如下表所示：假設特征是房子的面積x,房子的價格是結果y。若我們從樣本點的分布中發現x和y的值近似符合三次曲線，即我們可以使用x的三次多項式來逼近這些樣本點。我們將特征x擴展為三維，然后尋找特征與結果之間的模型。這種特征變換稱為特征映射，記映射函數為,這個例子中。非線性支持向量機的學習面積（m^2）銷售價格（萬元）12325015032087160102220…………我們將映射后的特征用于支持向量機分類，而不使用原來的特征。我們將超平面公式中公式中的內積從映射到。使用映射后的特征而不使用原始特征是因為映射特征不僅能夠更好的擬合數據，并且對于低維空間中的不可分數據，將特征映射到高維空間中往往就可分了。非線性問題很難求解，所以我們希望可以將非線性問題轉化為線性問題，然后用解線性分類問題的方法解決這個問題。由上例我們發現，我們可以采用非線性變換，將非線性問題轉化為線性問題，這樣我們就可以先解決變換后的線性問題，進而求解原來的非線性問題。核技巧就是采用這樣的方法。核技巧的基本思想是通過一個非線性變換將輸入空間（歐式空間或者離散集合）映射到一個特征空間（希爾伯特空間）。使得在輸入空間中的超曲面模型對應于特征空間中的超平面模型。從而通過在特征空間中求解先行支持向量機就可以進行分類。設是輸入空間（歐式空間的子集或離散集合），是特征空間（希爾伯特空間），如果存在一個到的映射：

:

使得對所有的，函數滿足條件：那么稱為核函數，為映射函數。核技巧并不顯式地定義映射函數，它通過在學習和預測中定義核函數。特征空間的維度往往很高，甚至是無窮維的.并且對于給定的核函數，特征空間與映射函數的取法不唯一核函數的定義對于線性支持向量機的對偶問題，目標函數和決策函數都只涉及到了輸入實例間的內積。我們用核函數來代替目標函數中的內積，這時對偶問題的目標函數為：同樣可以得到分類決策函數的表達式：在核函數給定時，我們在新的特征空間中用解線性分類問題的方法學習得到一個線性支持向量機，若映射函數為非線性函數，得到的含有核函數的支持向量機是非線性的分類模型。由于學習是隱式地在特征空間進行的，不需要顯式地定義特征空間以及映射函數，這樣的技巧稱為核技巧。核技巧巧妙地利用了線性分類學習方法與核函數來解決非線性問題。核函數的選擇對于分類問題意義重大，現實生活中往往通過實驗驗證核函數的有效性。在核函數給定時，我們在新的特征空間中用解線性分類問題的方法學習得到一個線性支持向量機，若映射函數為非線性函數，得到的含有核函數的支持向量機是非線性的分類模型。

由于學習是隱式地在特征空間進行的，不需要顯式地定義特征空間以及映射函數，這樣的技巧稱為核技巧。核技巧巧妙地利用了線性分類學習方法與核函數來解決非線性問題。核函數的選擇對于分類問題意義重大，現實生活中往往通過實驗驗證核函數的有效性。圖例：樣本空間經過核映射后的特征空間對于給定的訓練數據集，每一個對應于一個特征向量，我們將任意兩個向量和代入核函數中，得到，因此我們可以得到一個的核函數矩陣，我們用表示。若是有效的核函數，那么根據核函數的定義：即一定是一個對稱矩陣，令表示映射函數的第維屬性值，則對于任意的向量,有即如果是有效的核函數（即和等價），那么在訓練集上得到的核函數矩陣應該是半正定的。核函數有效性判定設函數是一個上的映射。如果是一個有效的核函數，也稱為Mercer核函數，那么當且僅當對于訓練樣本，其對應的核函數矩陣是對稱半正定的。Mercer定理確保核函數總可以用高維空間中的兩個輸入向量的點積表示。定理表明為了證明是有效的核函數，我們不需要尋找，只需要在訓練樣本集上求出核函數矩陣，然后判斷其是否正定即可。Mercer定理線性核函數多項式核函數高斯核函數線性核主要用于線性可分的情形，參數少，速度快，對于一般的訓練數據，分類效果已經很理想了。高斯核應用最廣，主要用于線性不可分的情形，參數多，在實際應用中常常通過訓練數據的交叉驗證尋找合適的參數,最終要選取哪種核，要根據具體問題分析，目前并沒有一種準則幫助我們確定哪種核函數是最優的。常用的核函數對于給定的訓練數據集，其中，，，。通過選取適當的核函數和適當的參數，構造并求解最優化問題：得到最優解，再選擇的一個正分量，計算：構造決策函數從而輸出分類決策函數，這就是非線性支持向量機的學習算法。非線性支持向量機的學習我們在前幾小節的內容中已經詳細介紹了SVM的原理，在求解的時候，我們將原始的最優化問題轉化為其對偶問題。SVM的對偶問題是一個凸二次規劃問題，并且這樣的凸二次規劃問題具有全局最優解。盡管在SMO算法出現之前就已經出現了很多算法應用到了SVM問題的求解上,但這些算法都具有計算量過于龐大、不適用于小樣本的通病。1988年，MicrosoftResearch的JohnC.Platt提出SMO(Sequentialminimaloptimization)算法用于訓練SVM。它是一種快速的二次規劃優化算法，基本思路是在一次迭代中只優化兩個變量而固定其他變量，從而將一個大的優化問題分解為若干個小的優化問題進行求解。這種方法類似于坐標上升法。SMO算法特別針對線性SVM和數據稀疏時性能更優。SMO算法回顧前面我們得到的SVM的最優化問題的對偶問題：（10）其中是訓練樣本數據，是訓練樣本特征，是樣本標簽，是懲罰系數。在這個問題中，和都是已知量，懲罰系數C由我們預先設定，也是已知量，未知參數只有拉格朗日乘子。由于一個變量對應一個樣本點，因此參數的個數等于訓練樣本的個數m。SMO算法是一種啟發式算法，如果所有變量的解都滿足此最優化問題的KKT條件，那么這個最優化問題的解就得到了。因為KKT條件是該最優化問題的充分必要條件。否則，選擇兩個變量，固定其他變量，針對這兩個變量構建一個二次規劃問題。這個二次規劃問題關于這兩個變量的解應該更接近原始二次規劃問題的解，因為這會使得原始二次規劃問題的目標函數值變得更小。同時，由于此時子問題可以通過解析的方法進行求解，算法的計算速度大大提升。子問題有兩個變量，一個是違反KKT條件最嚴重的那一個，另一個由約束條件自動確定。SMO算法就是將原問題不斷分解為子問題然后對子問題進行求解，進而達到求解原問題的目的。雖然我們選取了兩個變量構建二次規劃，但是兩個變量中只有一個變量是自由變量。由等式約束可知，若對任意兩個變量，，固定這兩個變量以外的其他變量，那么由等式約束可知：即只要確定了，那么也就隨之確定了，因此子問題同時更新兩個變量。SMO算法的主要步驟如下：第一步選取一對和，選取方法使用啟發式方法。第二步固定和之外的其他參數，確定W極值條件下的，由表示。接下來討論具體的操作方法假設我們選取了初始值滿足了問題中的約束條件。接下來，我們固定，在略去了不影響目標函數最優化求解的函數項后，（10）的最優化問題的子問題就可以寫成：

（11）其中。此時就是和的函數，并且滿足下述條件：由于都是已知量，為了方便，將等式右邊標記為實數值。則上式可以表示為：在等式兩邊同時乘上，得到：（12）將上式帶入（11）的等式中得到只關于參數的最優化問題：對上式關于求導并令其為0得到：（13）由（13）式求得了的解。帶回（12）式可得的解，分別記為，，將優化前的解記為，。在參數固定的前提條件下，由等式約束知有：

成立,即：（14）若SVM的超平面模型為，由前一節推出的的表達式知，，即為對樣本的預測值，定義為對輸入的預測值與真實值之差，即，由于.故（15）（16）將（14），（15），（16）代入（13）中求解，由于此時求解出的并沒有考慮約束條件，這里記為，得到：上式代入（14）式，并記得：

這里求出的沒有考慮約束條件。由不等式約束，由于未知參數只有兩個，又因為和均只有和兩種取值。和異號時，兩個參數可以表示為一條斜率為的直線，如下圖所示：橫軸和縱軸的最大值均為，即和不僅要在直線上，還要在矩形框內，因此我們最終求得的目標函數值的最優值位于矩形框內平行于對角線的線段上。下面我們考慮當和異號時的取值范圍。設,由不等式約束條件知，其中，。同理可以求出和同號時，,。于是經過上述約束的修剪，得到的最優解為：由于其他個變量是固定的，因此，代入，得到的表達式：上述的分析都是基于從m個變量中選擇兩個變量進行優化的方法，并且要求其中一個標量是違反KKT條件的，下面我們給出如何高效的選擇兩個變量進行優化，使得目標函數的下降速度最快。第一個變量的選擇：在SMO算法中，稱第1個變量的選擇過程為外層循環。首先遍歷所有的樣本點，選取違反KKT條件最嚴重的樣本點作為第一個變量。檢驗過程中外層循環首先遍歷所有滿足條件的樣本點，檢驗它們是否滿足KKT條件，如果這些樣本點都滿足KKT條件，那么遍歷整個訓練樣本集，檢驗它們是否滿足KKT條件。我們在循環過程中需要檢驗訓練樣本點是否滿足KKT條件：（17）

（18）