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

給出的訓(xùn)練數(shù)據(jù)集，存在法向量位移項(xiàng)，使得超平面能夠?qū)?shù)據(jù)集

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

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

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

將其帶入到超平面中得到：由此推出：這里的實(shí)際上就是點(diǎn)到平面距離.幾何間隔當(dāng)點(diǎn)位于超平面的另一側(cè)時(shí)，寫作：即當(dāng)樣本被正確分類時(shí)，到劃分超平面的距離是：對(duì)于給定的訓(xùn)練集，稱：

為超平面關(guān)于單個(gè)樣本點(diǎn)的幾何間隔，同樣定義為全局樣本的幾何間隔?？梢园l(fā)現(xiàn)，時(shí)，幾何間隔其實(shí)就是函數(shù)間隔。并且，有下式成立：幾何間隔支持向量機(jī)是定義在特征空間上的間隔最大的線性分類器，它的學(xué)習(xí)思想是找到能夠正確劃分訓(xùn)練數(shù)據(jù)集并且使得幾何間隔最大的分離超平面。最大幾何間隔分離超平面的求解可以表述為下面的帶約束最優(yōu)化問題：由幾何間隔與函數(shù)間隔的關(guān)系，上式可以寫作：最大間隔分離超平面

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

對(duì)于線性可分?jǐn)?shù)據(jù)集，由于函數(shù)間隔的改變對(duì)上述最優(yōu)化問題沒有影響，我們可以取。即我們將全局的函數(shù)間隔定義為1，也即是定義離超平面最近的點(diǎn)的距離為。對(duì)目標(biāo)函數(shù)進(jìn)行改寫后，得到如下的優(yōu)化問題：

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

式（2）

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

式（3）得到:

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

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

式（8）這里引入了松弛變量，目標(biāo)函數(shù)增加相應(yīng)的代價(jià)，為懲罰參數(shù)。最小化目標(biāo)函數(shù)，即在最大化間隔的同時(shí)，使得誤分類點(diǎn)的數(shù)量盡量小。支持向量機(jī)的對(duì)偶學(xué)習(xí)式（8）中的凸二次規(guī)劃問題解存在。唯一，而的解存在于一個(gè)區(qū)間。設(shè)解為，，由此得到分離超平面及分類決策函數(shù)，即得到了訓(xùn)練樣本線性不可分時(shí)的線性支持向量機(jī)，簡(jiǎn)稱為線性支持向量機(jī)。事實(shí)上，線性可分支持向量機(jī)也是線性支持向量機(jī)的一種情形。式（8）的拉格朗日函數(shù)為：

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

式（9）對(duì)比式（5）和式（9）發(fā)現(xiàn)，線性可分支持向量與線性支持向量機(jī)的對(duì)偶問題的唯一差別就是對(duì)偶變量的約束不一樣：線性可分支持向量機(jī)要求，線性支持向量機(jī)要求。通過求解對(duì)偶問題可以得到原始問題的解。設(shè)對(duì)偶問題的一個(gè)解為，

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

:

使得對(duì)所有的，函數(shù)滿足條件：那么稱為核函數(shù)，為映射函數(shù)。核技巧并不顯式地定義映射函數(shù)，它通過在學(xué)習(xí)和預(yù)測(cè)中定義核函數(shù)。特征空間的維度往往很高，甚至是無(wú)窮維的.并且對(duì)于給定的核函數(shù)，特征空間與映射函數(shù)的取法不唯一核函數(shù)的定義對(duì)于線性支持向量機(jī)的對(duì)偶問題，目標(biāo)函數(shù)和決策函數(shù)都只涉及到了輸入實(shí)例間的內(nèi)積。我們用核函數(shù)來代替目標(biāo)函數(shù)中的內(nèi)積，這時(shí)對(duì)偶問題的目標(biāo)函數(shù)為：同樣可以得到分類決策函數(shù)的表達(dá)式：在核函數(shù)給定時(shí)，我們?cè)谛碌奶卣骺臻g中用解線性分類問題的方法學(xué)習(xí)得到一個(gè)線性支持向量機(jī)，若映射函數(shù)為非線性函數(shù)，得到的含有核函數(shù)的支持向量機(jī)是非線性的分類模型。由于學(xué)習(xí)是隱式地在特征空間進(jìn)行的，不需要顯式地定義特征空間以及映射函數(shù)，這樣的技巧稱為核技巧。核技巧巧妙地利用了線性分類學(xué)習(xí)方法與核函數(shù)來解決非線性問題。核函數(shù)的選擇對(duì)于分類問題意義重大，現(xiàn)實(shí)生活中往往通過實(shí)驗(yàn)驗(yàn)證核函數(shù)的有效性。在核函數(shù)給定時(shí)，我們?cè)谛碌奶卣骺臻g中用解線性分類問題的方法學(xué)習(xí)得到一個(gè)線性支持向量機(jī)，若映射函數(shù)為非線性函數(shù)，得到的含有核函數(shù)的支持向量機(jī)是非線性的分類模型。

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

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

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

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

（18）