本章涉及到的知識(shí)點(diǎn)清單：

1、決策面方程

2、函數(shù)間隔和幾何間隔

3、不等式約束條件

4介评、SVM最優(yōu)化模型的數(shù)學(xué)描述（凸二次規(guī)劃）

5、引入拉格朗日函數(shù)

6爬舰、KKT條件的描述

7们陆、目標(biāo)函數(shù)的等高線與約束條件的最優(yōu)值分析

8、分類討論約束條件和拉格朗日乘子的組合

9情屹、求解對(duì)偶問(wèn)題

10棒掠、引入松弛變量

11、討論拉格朗乘子的取值意義和其值域

12屁商、SMO算法的思想

13烟很、多元函數(shù)推導(dǎo)為二元函數(shù)

14、二元函數(shù)推導(dǎo)為一元函數(shù)

15蜡镶、求解一元函數(shù)的偏導(dǎo)數(shù)雾袱，推導(dǎo)出第一個(gè)拉格朗乘子的遞推關(guān)系

16、由約束條件官还，推導(dǎo)出第二個(gè)拉格朗乘子的遞推關(guān)系

17芹橡、由支持向量方程，推導(dǎo)出偏置項(xiàng)的遞推關(guān)系

18望伦、 優(yōu)化SMO算法—啟發(fā)式規(guī)則下選擇兩個(gè)拉格朗乘子

19林说、編程實(shí)現(xiàn)SMO算法的步驟

20、非線性數(shù)據(jù)下的數(shù)據(jù)維度討論分析

21屯伞、核技巧與核函數(shù)

22腿箩、幾個(gè)常用的核函數(shù)

一、決策面方程

以二維空間為例劣摇，二維空間中任意一條直線方程可以寫(xiě)為

二維空間直線方程

我們將其向量化珠移，可以得到

向量化直線方程

設(shè)用向量w代表矩陣a1和a2，用向量x代表矩陣x1和x2末融，標(biāo)量γ代表b钧惧，則方程可化表示為

n維空間超平面方程

從方程可知，一個(gè)n維空間的超平面在二維空間上的表現(xiàn)勾习，可以是一條直線浓瞪，或者一個(gè)曲線（二維空間中只能看到這個(gè)n維超平面穿過(guò)而無(wú)法看到其模樣），超平面方程即是我們的決策面方程

二巧婶、函數(shù)間隔和幾何間隔

在SVM監(jiān)督學(xué)習(xí)中乾颁，我們規(guī)定標(biāo)簽數(shù)據(jù)為+1和-1兩個(gè)值涂乌，這么做的目的，可以計(jì)算出任意一個(gè)樣本點(diǎn)在超平面方程上的表現(xiàn)結(jié)果的符號(hào)钮孵，與標(biāo)簽符號(hào)是否一致來(lái)判斷分類的正確性，為此我們可以引入函數(shù)間隔的概念

函數(shù)間隔

但是當(dāng)我們成比例的縮放w和γ眼滤，函數(shù)間隔的值也將成比例的變化巴席，可是超平面的位置并沒(méi)有發(fā)生任何變化，所以函數(shù)間隔并不是我們想要的分類間隔诅需，為此漾唉，我們需要引入幾何間隔的概念

還是以二維空間出發(fā)，任意一點(diǎn)到直線的距離可以寫(xiě)成

二維空間中點(diǎn)到直線的距離

我們將其拓展到n維空間堰塌，直線方程即是我們的超平面方程赵刑，則n維空間中任何一點(diǎn)到超平面的距離可以寫(xiě)成

n維空間距離

為此，我們引入幾何間隔概念场刑，其中||w||表示向量w的二范數(shù)

幾何間隔

從幾何間隔可以看出般此，就算等比例縮放w和γ，由于除上了||w||使得幾何間隔的值不會(huì)改變牵现，它只隨著超平面位置的變化而變化铐懊，因此，我們要尋找的分類間隔是幾何間隔

三瞎疼、不等式約束條件

SVM算法的目的是找到一個(gè)將分類效果達(dá)到最合理化的超平面科乎，這個(gè)超平面即是分類器。而評(píng)估分類器的好壞的標(biāo)準(zhǔn)就是分類間隔的大小

我們定義分類間隔的距離為d贼急，好的分類器應(yīng)該讓所有樣本點(diǎn)到?jīng)Q策面的幾何間隔都大于等于d

樣本點(diǎn)到分類器的距離

化簡(jiǎn)上式茅茂，不等式兩邊同時(shí)除以d可得

不等式兩邊同時(shí)除以d

由于||w||和d都是標(biāo)量，可定義

定義向量的標(biāo)量

則上式可化簡(jiǎn)為

不同類別樣本點(diǎn)滿足的約束條件

在不等式兩邊同時(shí)乘以yi太抓，即將兩個(gè)式子化簡(jiǎn)為一個(gè)式子（這里體現(xiàn)了正是因?yàn)闃?biāo)簽數(shù)據(jù)為+1和-1空闲，才方便將約束條件變成一個(gè)約束方程）

所有樣本點(diǎn)滿足的約束方程

這個(gè)約束方程的意義即是任何樣本點(diǎn)到超平面（分類器）的幾何間隔都大于等于分類間隔

四、SVM最優(yōu)化模型的數(shù)學(xué)描述

評(píng)估分類器的優(yōu)劣是分類間隔的大小走敌，且對(duì)于任意樣本點(diǎn)都滿足約束方程

由約束方程可知进副，當(dāng)樣本點(diǎn)落在支持向量邊界上有如下關(guān)系

支持向量上的樣本點(diǎn)滿足約束

則分類間隔d可以表示為支持向量點(diǎn)到超平面的幾何間隔

支持向量的幾何間隔

要讓任何樣本點(diǎn)都在d之外，即求分類間隔d的最大值悔常，則目標(biāo)函數(shù)可以寫(xiě)成

目標(biāo)函數(shù)

為了方便在后續(xù)最優(yōu)化處理中對(duì)目標(biāo)函數(shù)的求導(dǎo)影斑，我們將目標(biāo)函數(shù)做等效變化

等效變換目標(biāo)函數(shù)

由目標(biāo)函數(shù)是二次的，而約束條件是線性的机打，則SVM的數(shù)學(xué)模型即是：不等式約束條件下的二次型函數(shù)優(yōu)化矫户，而求解這一類優(yōu)化問(wèn)題，接下來(lái)我們需要構(gòu)造拉格朗乘子函數(shù)

五残邀、引入拉格朗函數(shù)

目標(biāo)函數(shù)是求解在約束條件g(x)下的二次型函數(shù)f(x)的最小值皆辽，直觀上我們希望構(gòu)造一個(gè)函數(shù)L(x)柑蛇，使得L(x)在f(x)的可行解區(qū)域內(nèi)的求出的值和f(x)求出的值完全一樣，而在f(x)的可行解區(qū)域外驱闷，L(x)的值又接近無(wú)窮大耻台，這么做的目的，使得我們可以用一個(gè)函數(shù)L(x)來(lái)等效表示原問(wèn)題的g(x)和f(x)

拉格朗函數(shù)的目的空另，就是將約束條件融合到目標(biāo)函數(shù)中盆耽，構(gòu)造一個(gè)新函數(shù)來(lái)表示目標(biāo)函數(shù)，將有約束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束的優(yōu)化問(wèn)題

下面扼菠，我們構(gòu)造拉格朗函數(shù)來(lái)表示目標(biāo)函數(shù)

構(gòu)造拉格朗函數(shù)來(lái)表示目標(biāo)函數(shù)

其中αi是拉格朗日乘子摄杂，每一個(gè)約束條件對(duì)應(yīng)一個(gè)拉格朗日乘子，其中αi大于等于0

則原優(yōu)化問(wèn)題可以轉(zhuǎn)化為

求拉格朗函數(shù)的最大值

討論如下條件(1)(2)：

(1) 當(dāng)樣本點(diǎn)不滿足約束條件時(shí)循榆，即說(shuō)明在可行解區(qū)域外

可行解區(qū)域外

此時(shí)將αi置為正無(wú)窮大析恢，那么θ(w)顯然也是正無(wú)窮大

(2) 當(dāng)樣本點(diǎn)滿足約束條件時(shí)，即說(shuō)明在可行解區(qū)域內(nèi)

可行解區(qū)域內(nèi)

此時(shí)θ(w)的最小值就是原目標(biāo)函數(shù)秧饮，于是綜上所述映挂，引入拉格朗乘子函數(shù)后，可以得到新的目標(biāo)函數(shù)

新目標(biāo)函數(shù)

我們用p*表示優(yōu)化目標(biāo)函數(shù)后的最優(yōu)解盗尸，且與最初的目標(biāo)函數(shù)等價(jià)

觀察新的目標(biāo)函數(shù)袖肥，如果直接求偏導(dǎo)數(shù)求解，那么一上來(lái)將面對(duì)w和b兩個(gè)未知參數(shù)振劳，而αi又是不等式約束椎组，求解過(guò)程將非常復(fù)雜。換一個(gè)角度思考历恐，如果將max和min的位置對(duì)調(diào)寸癌，變成如下新的目標(biāo)函數(shù)

拉格朗函數(shù)的對(duì)偶性

上式變化使用了拉格朗日函數(shù)的對(duì)偶性，交換后的新問(wèn)題即是原目標(biāo)函數(shù)的對(duì)偶問(wèn)題弱贼，我們用d*來(lái)表示對(duì)偶目標(biāo)函數(shù)的最優(yōu)解蒸苇，可見(jiàn)d*的求導(dǎo)過(guò)程比p*相對(duì)容易，且d*<=p*吮旅，而當(dāng)滿足下列條件時(shí)溪烤，d*= p*

(1) 優(yōu)化問(wèn)題是凸優(yōu)化問(wèn)題

(2) 最優(yōu)值滿足KKT條件

因?yàn)槟繕?biāo)函數(shù)本身已經(jīng)是一個(gè)凸函數(shù)，而優(yōu)化問(wèn)題又是求解最小值庇勃，所以目標(biāo)函數(shù)的最優(yōu)化問(wèn)題就是凸優(yōu)化問(wèn)題檬嘀，則接下來(lái)就要重點(diǎn)討論KKT條件

六、KKT條件的描述

一個(gè)最優(yōu)化模型能夠表示成下列標(biāo)準(zhǔn)形式

最優(yōu)化模型的標(biāo)準(zhǔn)形式

其中f(x)是需要最小化的函數(shù)责嚷，h(x)是等式約束鸳兽，g(x)是不等式約束，m和n分別是等式約束和不等式約束的數(shù)量

KKT條件即是規(guī)定f(x)的最優(yōu)值必須滿足以下(1)(2)(3)條件罕拂，只有滿足KKT條件揍异，目標(biāo)函數(shù)的最優(yōu)化問(wèn)題依然可以用拉格朗日乘子法解決

條件一：目標(biāo)函數(shù)（拉格朗函數(shù)）對(duì)x的導(dǎo)數(shù)為0（這里x代表參數(shù)向量）

條件二：h(x) = 0

條件三：∑α*g(x) = 0

很明顯全陨，我們需要優(yōu)化的目標(biāo)函數(shù)屬于帶有不等式約束函數(shù)g(x)，所以條件二顯然滿足衷掷，下面我們來(lái)分析條件一和條件三的理論

七辱姨、目標(biāo)函數(shù)的等高線與約束條件的最優(yōu)值分析（條件一）

對(duì)于KKT條件一的分析，我們假設(shè)目標(biāo)函數(shù)是f(x1,x2)的二元函數(shù)戚嗅，它的圖像在三維空間里是一個(gè)曲面雨涛，準(zhǔn)確的來(lái)說(shuō)是一個(gè)凸曲面

目標(biāo)函數(shù)與約束方程的幾何關(guān)系

其中g(shù)(x1,x2)是約束方程，要求目標(biāo)函數(shù)f(x1,x2)的最小值渡处，即轉(zhuǎn)化為求g(x1,x2)=c這條曲線上的一點(diǎn)镜悉，使得f(x1,x2)取得最小值祟辟，換個(gè)比喻医瘫，就是在山上（目標(biāo)函數(shù)曲面）尋找一條山路（約束條件曲線）的最低點(diǎn)

我們畫(huà)出目標(biāo)函數(shù)的等高線，來(lái)分析目標(biāo)函數(shù)最優(yōu)值和約束條件的關(guān)系

目標(biāo)函數(shù)登高線與約束曲線的幾何關(guān)系

對(duì)于研究目標(biāo)函數(shù)z=f(x1,x2)旧困，當(dāng)z取不同的值醇份，即將曲線z投影在(x1,x2)組成的空間中（這里指的是二維空間），也就是曲面的等高線吼具，上圖中d1和d2即是兩條目標(biāo)函數(shù)的等高線僚纷，可以看出，當(dāng)約束函數(shù)g(x1,x2)與目標(biāo)函數(shù)的等高線有共同的交點(diǎn)拗盒，即證明這組值同時(shí)滿足在目標(biāo)函數(shù)的可行域中怖竭，也符合約束條件的約束關(guān)系

如果等高線與g(x1,x2)相交，則是一組目標(biāo)函數(shù)的解陡蝇，但是這個(gè)解一定不是最優(yōu)解痊臭，因?yàn)橄嘟灰馕吨隙ù嬖谄渌雀呔€在該條等高線的內(nèi)部或者外部，可能會(huì)使得新的等高線與g(x1,x2)的交點(diǎn)更大或者更小登夫，這就意味著只有當(dāng)?shù)雀呔€與g(x1,x2)相切广匙，才可能得到最優(yōu)解（切線可能多條）

所以最優(yōu)解必須滿足：目標(biāo)函數(shù)的負(fù)梯度方向與約束函數(shù)的梯度方向一致

約束函數(shù)和目標(biāo)函數(shù)的梯度關(guān)秀

而上式恒成立的條件就是：拉格朗日乘子α >= 0，且這個(gè)式子就是目標(biāo)函數(shù)對(duì)各個(gè)參數(shù)求偏導(dǎo)數(shù)的結(jié)果恼策，即KKT的第一個(gè)條件：目標(biāo)函數(shù)對(duì)各個(gè)參數(shù)的導(dǎo)數(shù)為0

八鸦致、分類討論約束條件和拉格朗日乘子的組合（條件三）

對(duì)于KKT條件三，可以看出涣楷，因?yàn)樗械募s束函數(shù)gi(x)<=0分唾，所有的拉格朗日乘子αi>=0，要使得求和后結(jié)果為0狮斗，要么某個(gè)約束函數(shù)gi(x)=0鳍寂，要么其對(duì)應(yīng)的αi=0

從一個(gè)案例出發(fā)來(lái)分析KKT條件三的邏輯，假設(shè)目標(biāo)函數(shù)和約束函數(shù)是

案例研究KKT條件三

將不等式約束構(gòu)造出拉格朗日函數(shù)情龄，并分別對(duì)x1和x2求偏導(dǎo)數(shù)

案例研究KKT條件三

而KKT的條件三要求最優(yōu)解滿足?∑α*g(x) = 0迄汛，在這個(gè)案例里α和g(x)只有一個(gè)捍壤，結(jié)合條件一，可以得到

案例研究KKT條件三

根據(jù)之前的分析鞍爱，最優(yōu)值滿足條件三的話鹃觉，要么α=0，要么g(x)=0

（i）：如果α=0睹逃，則x1=1盗扇，x2=-2，代入g(x1,x2) =10-1-10*(-2)=29>0沉填，發(fā)現(xiàn)這組解違背了約束函數(shù)g(x)<0疗隶，則舍棄這組解

（ii）: 如果g(x1,x2)=0，則代入x1和x2的表達(dá)式到g(x)中翼闹，解出α=58/101>0斑鼻，發(fā)現(xiàn)這組解不違背約束函數(shù)，則代入α解出x1=130/101猎荠，x2=88/101坚弱，則這組解有可能是最優(yōu)解

綜上(i)(ii)討論，目標(biāo)函數(shù)的最優(yōu)值符合KKT條件三关摇，也說(shuō)明了滿足強(qiáng)對(duì)偶條件的優(yōu)化問(wèn)題的最優(yōu)值必須滿足KKT條件

九荒叶、求解對(duì)偶問(wèn)題

上面分析了目標(biāo)函數(shù)滿足凸優(yōu)化和KKT條件，則問(wèn)題轉(zhuǎn)化為求解原問(wèn)題的對(duì)偶問(wèn)題（即p*=d*）

目標(biāo)函數(shù)（對(duì)偶）

根據(jù)對(duì)偶問(wèn)題描述输虱，先要求內(nèi)側(cè)w和b關(guān)于L(w,b,α)的最小化值些楣，即求L對(duì)w和b的偏導(dǎo)數(shù)

拉格朗函數(shù)L對(duì)w的偏導(dǎo)數(shù)

拉格朗函數(shù)L對(duì)b的偏導(dǎo)數(shù)

將w和b的偏導(dǎo)數(shù)帶入拉格朗函數(shù)化簡(jiǎn)得

帶入w和b化簡(jiǎn)拉格朗函數(shù)L

整理一下最終化簡(jiǎn)結(jié)果為

拉格朗函數(shù)L的化簡(jiǎn)結(jié)果

從上述結(jié)果可以看出，樣本的x和y是已知的宪睹，此時(shí)的L(w,b,α)函數(shù)只有一個(gè)變量愁茁，即αi

我們歸納一下現(xiàn)在的目標(biāo)函數(shù)為

新的目標(biāo)函數(shù)

現(xiàn)在目標(biāo)函數(shù)變成了如上形式，其中αi>=0横堡，這里隱含著一個(gè)假設(shè)埋市，即數(shù)據(jù)100%線性可分，但是現(xiàn)實(shí)生活中命贴，數(shù)據(jù)往往是不會(huì)那么規(guī)則的線性化道宅，為此我們需要引入松弛變量

十、引入松弛變量

由于現(xiàn)實(shí)世界中的數(shù)據(jù)都是帶有噪音的胸蛛，也就是數(shù)據(jù)可能出偏離其正常的位置很遠(yuǎn)污茵，而出現(xiàn)這種極端現(xiàn)象后往往會(huì)影響超平面的選擇，也許將無(wú)法構(gòu)造出將數(shù)據(jù)徹底分開(kāi)的超平面出來(lái)

所以對(duì)于處理這種情況葬项，SVM需要允許（妥協(xié)）出某些噪音很大的數(shù)據(jù)點(diǎn)能夠偏離超平面泞当，即允許其出現(xiàn)在超平面的錯(cuò)誤的一側(cè)，為此我們引入松弛變量C民珍，這樣我們的目標(biāo)函數(shù)又變?yōu)?/p>

帶有松弛變量的新目標(biāo)函數(shù)

接下來(lái)為了研究討論αi的取值范圍襟士，我們加上一個(gè)負(fù)號(hào)將目標(biāo)函數(shù)等價(jià)轉(zhuǎn)化為

新目標(biāo)函數(shù)等價(jià)

十一盗飒、討論拉格朗乘子的取值意義和其值域

回顧一下最初的約束條件為

所有樣本點(diǎn)滿足的約束方程

設(shè)ui為該約束條件，可以歸納出αi關(guān)于約束函數(shù)的取值意義

αi關(guān)于約束函數(shù)的取值意義

上述關(guān)系可以描述為：

當(dāng)αi=0時(shí)陋桂，樣本點(diǎn)屬于正常分類逆趣，即在兩條邊界之外或者邊界上

當(dāng)0<αi<C時(shí)，樣本點(diǎn)屬于支持向量嗜历，即只在兩條邊界上

當(dāng)αi=C時(shí)宣渗，樣本點(diǎn)在兩條邊界之間

αi只有滿足上述3種情況，才能求出最優(yōu)解梨州，所以當(dāng)αi與約束條件ui沖突的時(shí)候痕囱，需要更新這些αi，這也就是滿足目標(biāo)函數(shù)的第一個(gè)約束限制暴匠，即0<=αi<=C

而同時(shí)目標(biāo)函數(shù)還受到第二個(gè)約束條件的限制鞍恢，即

目標(biāo)函數(shù)的第二個(gè)約束限制

所以不能只更新一個(gè)αi因子，需要同時(shí)再次更新第二個(gè)αj因子巷查，也就是α因子總是成對(duì)的更新（αi對(duì)總是和αj配對(duì)）有序，一增一減抹腿，此消彼長(zhǎng)岛请，才能保證加權(quán)和為0的約束，同時(shí)這也就是下面提及SMO算法的思想和多元函數(shù)化簡(jiǎn)為二元函數(shù)警绩，在從二元函數(shù)化簡(jiǎn)為一元函數(shù)的難點(diǎn)

根據(jù)這個(gè)約束和α因子需要成對(duì)更新崇败，假設(shè)我們選取的兩個(gè)拉格朗乘子為α1和α2，則更新之前是old肩祥，更新之后是new后室，且更新前后需要滿足和為0的約束

α1和α2的更新前后關(guān)系

兩個(gè)因子同時(shí)更新顯然非常困難，所以需要先求出第一個(gè)αj的解混狠，再用αj的解去表示更新第二個(gè)αi的解岸霹，后文的SMO算法會(huì)闡述這一點(diǎn)。因此需要先確定αj的取值范圍将饺，假設(shè)L和H分別為它的下界和上界贡避，結(jié)合目標(biāo)函數(shù)的約束限制來(lái)綜合討論L和H的取值關(guān)系

綜合討論L和H的取值

（i）：當(dāng)y1和y2異號(hào)時(shí)，可以得到

y1和y2異號(hào)時(shí)

移項(xiàng)可得a2 = a1 - A予弧，此時(shí)α的取值范圍如下圖所示

y1和y2異號(hào)時(shí)刮吧， α因子的上下界限制

所以此時(shí)α的上下界H和L為

α的上下界關(guān)系

（ii）：當(dāng)y1和y2同號(hào)時(shí)，可以得到

y1和y2同號(hào)時(shí)

移項(xiàng)可得a2 = -a1 + A掖蛤，此時(shí)α的取值范圍如下圖所示

y1和y2異號(hào)時(shí)杀捻，?α因子的上下界限制

所以此時(shí)α的上下界H和L為

α的上下界關(guān)系

綜上(i)(ii)的討論，通過(guò)y1和y2的異號(hào)或者同號(hào)蚓庭，可以推導(dǎo)出α更新后的上下界分別為

α更新后的上下界

這個(gè)公式顯得非常的重要致讥，它將α因子限制在有效的矩形范圍內(nèi)仅仆，在SMO算法中，當(dāng)我們更新完α后垢袱，由于α可能會(huì)被更新得很大或很小蝇恶，因此需要經(jīng)過(guò)裁剪來(lái)保證α的在約束條件內(nèi)

12、SMO算法的思想

回顧之前第九惶桐，第十撮弧，第十一步的分析，目標(biāo)函數(shù)為

目標(biāo)函數(shù)

目標(biāo)函數(shù)只包含n個(gè)變量α的多元函數(shù)姚糊，且?guī)в袃蓚€(gè)約束條件飞涂，我們的目的是求出目標(biāo)函數(shù)的最小值，即找到一組α的組合肩碟，使得目標(biāo)函數(shù)取得最小值

由第十一步的分析纳决，我們需要不斷更新這n個(gè)α因子，通過(guò)迭代來(lái)逼近函數(shù)達(dá)到最小值肠槽，但是如果一次性更新n個(gè)參數(shù)擎淤，將會(huì)有n!種組合，那么時(shí)間復(fù)雜度將會(huì)非常高秸仙，為此我們首先想到坐標(biāo)上升（下降）法

來(lái)通過(guò)一個(gè)例子來(lái)說(shuō)明坐標(biāo)上升法的思路

案例研究坐標(biāo)上升法

可知案例中要求一個(gè)三元函數(shù)的最大值嘴拢，算法的思想是每次迭代時(shí)只更新一個(gè)維度，通過(guò)多次迭代直到收斂來(lái)優(yōu)化函數(shù)的最值寂纪，求出三個(gè)變量的偏導(dǎo)數(shù)推出其關(guān)系

案例研究坐標(biāo)上升法

通過(guò)迭代即就可以求出其最值

案例研究坐標(biāo)上升法

SMO算法借鑒了坐標(biāo)上升（下降）法的思想來(lái)優(yōu)化α因子組合席吴，但是由于目標(biāo)函數(shù)的第二個(gè)約束條件有加權(quán)和為0的限制，導(dǎo)致每次迭代時(shí)候不能只更新一個(gè)因子αi捞蛋，必須同時(shí)更新與之配對(duì)的另一個(gè)因子αj孝冒，此消彼長(zhǎng)才能保證加權(quán)和為0（第十一步中已提及）

所以SMO算法思想是將原始問(wèn)題中，求解n個(gè)參數(shù)的二次規(guī)劃問(wèn)題拟杉，分解成了多個(gè)子二次規(guī)劃問(wèn)題來(lái)分別求解庄涡，每一個(gè)子問(wèn)題只需要求解2個(gè)參數(shù)，即將多元函數(shù)推導(dǎo)為二元函數(shù)搬设，再將二元函數(shù)推導(dǎo)為一元函數(shù)

13穴店、多元函數(shù)推導(dǎo)為二元函數(shù)

目標(biāo)函數(shù)是關(guān)于α的N元函數(shù)，通過(guò)SMO的算法思想焕梅，假設(shè)每次迭代更新迹鹅，選取一對(duì)α1和α2的組合，其余的乘子不變贞言，首先需要將α1和α2從目標(biāo)函數(shù)中分離出來(lái)斜棚，也就是將多元函數(shù)推導(dǎo)為二元函數(shù)

N元目標(biāo)函數(shù)

從N元函數(shù)中分離出α1和α2因子

N元函數(shù)化簡(jiǎn)為二元函數(shù)—1

N元函數(shù)化簡(jiǎn)為二元函數(shù)—2

由于上式推導(dǎo)結(jié)果過(guò)于復(fù)雜，我們定義2個(gè)表達(dá)式來(lái)表示上式常量部分，用來(lái)簡(jiǎn)化上式

N元函數(shù)化簡(jiǎn)為二元函數(shù)—3

又由于單獨(dú)存下的常數(shù)項(xiàng)對(duì)以后的求導(dǎo)沒(méi)有貢獻(xiàn)弟蚀，所以我們提出單獨(dú)的常數(shù)項(xiàng)定義為Constant

N元函數(shù)化簡(jiǎn)為二元函數(shù)—4

帶入vi和Constant表達(dá)式蚤霞，則結(jié)果化簡(jiǎn)為

N元函數(shù)化簡(jiǎn)為二元函數(shù)—5

至此，我們將多元函數(shù)推導(dǎo)為含有α1和α2變量的二元函數(shù)义钉，接下來(lái)將這個(gè)二元函數(shù)推導(dǎo)為一元函數(shù)

14昧绣、二元函數(shù)推導(dǎo)為一元函數(shù)

我們需要推導(dǎo)出α1和α2的關(guān)系，然后用α2來(lái)表示α1帶入二元函數(shù)捶闸，就可以推導(dǎo)出關(guān)于α2的一元函數(shù)了

由目標(biāo)函數(shù)的第二個(gè)約束條件

目標(biāo)函數(shù)的第二個(gè)約束限制

同理根據(jù)SMO算法思想夜畴，從約束條件中分離出α1和α2

分離出α1和α2

將等式兩邊同時(shí)乘以y1，可推導(dǎo)出α1和α2的關(guān)系

α1和α2的關(guān)系

同理删壮，我們定義兩個(gè)表達(dá)式r和s來(lái)表示上式的常量部分贪绘，用來(lái)簡(jiǎn)化上式關(guān)系

定義常量化簡(jiǎn)用來(lái)α1和α2的關(guān)系

帶入r和s后，α1和α2的關(guān)系推導(dǎo)為

α1和α2的關(guān)系

下面將α1帶入我們的二元函數(shù)中央碟，可得

二元函數(shù)化簡(jiǎn)為一元函數(shù)

至此税灌，我們將二元函數(shù)推導(dǎo)為只含有一個(gè)變量α2的一元函數(shù)，接下來(lái)終于可以對(duì)目標(biāo)函數(shù)求導(dǎo)了

15亿虽、求解一元函數(shù)的偏導(dǎo)數(shù)菱涤，推導(dǎo)出第一個(gè)拉格朗乘子的遞推關(guān)系

我們對(duì)一元函數(shù)求α2的偏導(dǎo)數(shù)為0

α2關(guān)于W的偏導(dǎo)數(shù)

帶入s=y1*y2和y2*y2=1，整理上式可求出α2

α2的表達(dá)式

同理洛勉，由于上式推導(dǎo)結(jié)果過(guò)于復(fù)雜粘秆，我們定義2個(gè)表達(dá)式來(lái)表示上式常量部分，用來(lái)簡(jiǎn)化上式

定義兩個(gè)表達(dá)式用于化簡(jiǎn)α2

帶入vi和r的表達(dá)式

vi和r的表達(dá)式

將Ei坯认，η翻擒，vi氓涣，r的表達(dá)式帶入α2表達(dá)式中繼續(xù)化簡(jiǎn)牛哺，可得

帶入Ei，η劳吠，vi引润，r化簡(jiǎn)α2表達(dá)式

整理消去同類項(xiàng)，可得

整理推導(dǎo)出α2的遞推式

至此痒玩，通過(guò)繁復(fù)的化簡(jiǎn)推導(dǎo)淳附，我們終于推導(dǎo)出第一個(gè)拉格朗乘子α2的遞推公式了，也就是SMO算法更新的第一個(gè)拉格朗乘子的方式蠢古，但是奴曙，此時(shí)更新后的α2還沒(méi)有經(jīng)過(guò)裁剪，記得我們?cè)诘谑徊接懻摰年P(guān)于拉格朗乘子的取值意義和其值域吧草讶，我們需要將更新后的α2裁剪到它的值域范圍內(nèi)洽糟，于是有

裁剪α2在其值域內(nèi)有效

其中H和L是α2的上下界，在第十一步中我們已經(jīng)求出

α因子的值域

因子SMO算法需要同時(shí)更新一對(duì)α因子，于是接下來(lái)需要推導(dǎo)出第二個(gè)拉格朗乘子的遞推關(guān)系

十六坤溃、由約束條件拍霜，即可推導(dǎo)出第二個(gè)拉格朗乘子的遞推關(guān)系

我們已知裁剪后α2因子的遞推式，由之前的約束條件中α1和α2的關(guān)系式

α1和α2的關(guān)系式

帶入未更新的α1薪介、α2和更新裁剪后的α1祠饺、α2可以得到如下兩式

更新前后α1和α2的關(guān)系

由上面兩式消去r表達(dá)式，帶入s=y1*y2可以得到

整理推導(dǎo)出α1的遞推式

上式即是第二個(gè)拉格朗乘子α1的遞推式汁政，可以看到其只與更新前的α1和α2道偷，以及更新裁剪后的α2有關(guān)。

而我們的分類函數(shù)是

分類函數(shù)

其中w向量我們通過(guò)拉格朗乘子α來(lái)計(jì)算出來(lái)记劈，還剩下偏置項(xiàng)b试疙，為此需要在SMO算法更新完一對(duì)α因子后重新計(jì)算更新偏置項(xiàng)b

17、由支持向量方程抠蚣，推導(dǎo)出偏置項(xiàng)的遞推關(guān)系

我們知道當(dāng)樣本點(diǎn)屬于支持向量時(shí)祝旷，滿足下式

xi屬于支持向量

而w向量的表達(dá)式是之前w對(duì)拉格朗函數(shù)的偏導(dǎo)數(shù)已經(jīng)求出

w向量的表達(dá)式

帶入w整理得

偏置項(xiàng)b的表達(dá)式

由于我們是根據(jù)SMO算法更新的α1和α2去計(jì)算偏置項(xiàng)b，則需要從上式中單獨(dú)提出i=1和i=2的兩項(xiàng)嘶窄，我們先推導(dǎo)α1對(duì)應(yīng)的偏置項(xiàng)b1的遞推式

偏置項(xiàng)b的遞推式推導(dǎo)_1

我們通過(guò)f(xi)和Ei的表達(dá)式用來(lái)化簡(jiǎn)上式

f(xi)和Ei的表達(dá)式

但是上式?jīng)]有出現(xiàn)f(x)的結(jié)構(gòu)怀跛，所以我們需要用加一項(xiàng)減一項(xiàng)的方法手動(dòng)構(gòu)造出f(x)的結(jié)構(gòu)

偏置項(xiàng)b的遞推式推導(dǎo)_2（ 加一項(xiàng)減一項(xiàng) ）

帶入f(xi)和Ei化簡(jiǎn)上式可以得到b1的遞推式

偏置項(xiàng)b的遞推式推導(dǎo)_3

同理b2的遞推式為

α2對(duì)應(yīng)的b2的遞推式

可以從偏置項(xiàng)b的遞推式看出b只與更新前后的α和Ei有關(guān)，考慮α的值域柄冲，我們可以歸納出更新后的b的表達(dá)式為

偏置項(xiàng)b的更新表達(dá)式

至此吻谋，我們通過(guò)SMO算法的思想，經(jīng)過(guò)一個(gè)又一個(gè)的數(shù)學(xué)推導(dǎo)现横，推導(dǎo)出了在每一次迭代過(guò)程中α1漓拾、α2、偏置項(xiàng)b的遞推更新式戒祠，通過(guò)不斷的迭代這些參數(shù)來(lái)優(yōu)化模型的目標(biāo)函數(shù)骇两，最后計(jì)算出目標(biāo)函數(shù)的最優(yōu)解參數(shù)α和b，從而求出我們的分類函數(shù)來(lái)做預(yù)測(cè)

18姜盈、優(yōu)化SMO算法—啟發(fā)式規(guī)則選擇兩個(gè)拉格朗乘子

推導(dǎo)完SMO算法的幾個(gè)遞推更新式用來(lái)優(yōu)化目標(biāo)函數(shù)低千，我們來(lái)討論如何優(yōu)化SMO算法

SMO是一個(gè)啟發(fā)式算法，它將原始問(wèn)題分解為多個(gè)二次規(guī)劃子問(wèn)題馏颂，通過(guò)求解一對(duì)拉格朗乘子（α1和α2）的解示血，使得目標(biāo)函數(shù)的值變得更小，從而不斷逼近原始問(wèn)題的解救拉，由此可見(jiàn)需要啟發(fā)式的選取一對(duì)拉格朗乘子來(lái)做優(yōu)化

第一個(gè)因子的遞推式

由第一個(gè)因子的遞推式分析可知难审，要使得新的因子得到足夠大的變化，而yi和η是常量亿絮，則只要讓

兩對(duì)誤差最大化

讓變化足夠大的α因子使得目標(biāo)函數(shù)有足夠大的下降告喊，所以我們可以在編程過(guò)程中用一個(gè)列表保存每一個(gè)Ei拂铡，并且在更新完兩個(gè)α因子后更新維護(hù)這個(gè)列表，整個(gè)SMO算法是一個(gè)雙重循環(huán)過(guò)程

至此我們整理出了優(yōu)化SMO算法的思路：

1葱绒、在外層循環(huán)中感帅，從樣本集里選擇任意一個(gè)違反KKT條件的乘子，作為SMO算法需要優(yōu)化的第一個(gè)αi

2地淀、進(jìn)入內(nèi)層循環(huán)失球，在非邊界乘子中尋找讓|Ei - Ej|誤差最大的樣本其對(duì)應(yīng)的乘子，作為SMO算法需要優(yōu)化的第二個(gè)αj

3帮毁、如果沒(méi)有找到实苞，就在整個(gè)樣本集里隨機(jī)的選取一個(gè)乘子，作為SMO算法需要優(yōu)化的第二個(gè)αj

4烈疚、如果更新前后的αj變化太小黔牵，則放棄這輪選擇，重新進(jìn)入外層循環(huán)再次重新選擇第一個(gè)αi

19爷肝、編程實(shí)現(xiàn)SMO算法的步驟

現(xiàn)在猾浦，我們梳理SMO算法的編程步驟如下

1、計(jì)算誤差灯抛，并維護(hù)進(jìn)入誤差列表

2金赦、在外層循環(huán)中選擇任意一個(gè)不滿足KKT條件的樣本作為第一個(gè)待更新的拉格朗乘子αi

3、在內(nèi)層循環(huán)中对嚼，根據(jù)SMO的優(yōu)化思想選擇出第二個(gè)待更新的拉格朗乘子αj

4夹抗、計(jì)算αj的值域（上下界）

5、計(jì)算學(xué)習(xí)率η

6纵竖、由αj的遞推式更新αj

7漠烧、由αj的值域裁剪αj

8、由αi的遞推式更新αi

9靡砌、在誤差列表中維護(hù)更新后Ei和Ej

10已脓、根據(jù)bi和bj的遞推式，更新bi和bj乏奥，從而更新原始截距參數(shù)b

下面為SMO算法的部分截圖

SMO算法部分截圖-1

SMO算法部分截圖-2

程序運(yùn)行結(jié)果

線性數(shù)據(jù)程序運(yùn)行結(jié)果-1

線性數(shù)據(jù)程序運(yùn)行結(jié)果-2

從程序的運(yùn)行結(jié)果中來(lái)看摆舟，藍(lán)色的線即是超平面，空心圈的點(diǎn)即是支持向量點(diǎn)邓了，可以看到分類效果完全正確，錯(cuò)誤率為0媳瞪，同時(shí)也可以看到SVM本質(zhì)上就是一個(gè)二分類器

但是骗炉，以上的分類實(shí)例屬于數(shù)據(jù)線性可分，當(dāng)數(shù)據(jù)完全不能線性可分蛇受，又該怎么去尋找其超平面完成分類呢句葵？這也就是SVM模型最厲害也是最神奇的地方，它可以有效的處理非線性數(shù)據(jù)的分類問(wèn)題

20、非線性數(shù)據(jù)下的數(shù)據(jù)維度討論分析

當(dāng)訓(xùn)練數(shù)據(jù)線性不可分乍丈，如果我們停留在這些非線性數(shù)據(jù)本身所處的世界上觀察剂碴，顯然無(wú)法存在一個(gè)超平面將數(shù)據(jù)區(qū)分開(kāi)來(lái)，例如以下數(shù)據(jù)集

非線性數(shù)據(jù)

我們就用以上這個(gè)數(shù)據(jù)集案例說(shuō)明如何面對(duì)非線性數(shù)據(jù)

設(shè)X1轻专，X2來(lái)表示這個(gè)二維平面上的數(shù)據(jù)點(diǎn)忆矛，我們寫(xiě)出一般化的二次曲線方程（圓形是二次曲線的特殊情況）

二次曲線方程（?二維空間 ）

從方程上可以看出，此時(shí)數(shù)據(jù)所處的空間是一個(gè)二維空間

如果我們替換其中的維度X1和X2请垛，令Z1=X1催训，Z2=X1*X1，Z3=X2宗收，Z4=X2*X2漫拭，Z5=X1*X2，那么我們就構(gòu)造了一個(gè)新的五維空間混稽，將原始數(shù)據(jù)拉到了這個(gè)五維空間中采驻，那么此時(shí)二次曲線的方程在新的世界里可以寫(xiě)為

二次曲線方程（ 五維空間 ）

此時(shí)，我們就做了一個(gè)映射?匈勋，將X按照一定的規(guī)則映射為Z挑宠，即將數(shù)據(jù)集映射到一個(gè)新空間里

二維空間映射為五維空間

當(dāng)然，你我不可能畫(huà)出五維空間颓影，但是如果只考慮三維空間各淀，即修改映射規(guī)則為Z1=X1*X1，Z2=X2*X2诡挂，Z3=X2碎浇，那么此時(shí)二次曲線的方程在新的世界（三維空間）里可以寫(xiě)為

二次曲線方程（ 三維空間?）

我們畫(huà)出這個(gè)三維空間

數(shù)據(jù)在三維空間上表現(xiàn)

可以看出在這個(gè)世界里，數(shù)據(jù)是可以通過(guò)一個(gè)超平面來(lái)區(qū)分的璃俗，為此我們得出一個(gè)重要的推論：將非線性數(shù)據(jù)從它本身的世界映射到N維世界后奴璃，數(shù)據(jù)在新的世界里將變得線性可分

因此，我們定義映射?城豁，用來(lái)將數(shù)據(jù)映射到高維空間苟穆，則我們需要修改原分類函數(shù)的表現(xiàn)

原來(lái)的分類函數(shù)

帶入映射?，將xi和xj映射到高維空間

映射后的分類函數(shù)

分析到這里可以看到當(dāng)拿到一個(gè)非線性數(shù)據(jù)唱星，我們就需要找到一個(gè)?來(lái)映射數(shù)據(jù)到高維空間雳旅，然后在高維空間里做SMO算法即可，即原始問(wèn)題為：低維空間里解決非線性問(wèn)題间聊，而做映射后等價(jià)于：高維空間里解決線性問(wèn)題

但是攒盈，事情顯然不會(huì)那么順利，需要考慮一個(gè)問(wèn)題—維度爆炸

回想一下在最初的例子里哎榴，我們將數(shù)據(jù)所在的原始空間型豁，也就是二維空間做了空間映射僵蛛，而選擇出的新空間是原始空間里所有維度的組合，也就得到了新的五維空間迎变；那么如果數(shù)據(jù)的原始空間是三維空間充尉，我們對(duì)三維空間做空間映射后，會(huì)得到一個(gè)新的19維空間衣形，發(fā)現(xiàn)每當(dāng)數(shù)據(jù)的原始空間多一個(gè)維度驼侠，那么映射后的新空間其維度呈指數(shù)級(jí)增長(zhǎng)，當(dāng)遇到無(wú)窮維的情況泵喘，此時(shí)根本無(wú)法計(jì)算分類函數(shù)里的其內(nèi)積

至此泪电，我們知道不能僅僅通過(guò)引入高維映射?來(lái)解決非線性問(wèn)題，我們需要另外的技巧

21纪铺、核技巧與核函數(shù)

數(shù)學(xué)家們喜歡成將輸入空間轉(zhuǎn)換為另一個(gè)特征空間稱之為從一個(gè)特征空間到另一個(gè)特征空間的映射相速，在一般情況下，這種映射會(huì)將低維空間映射到高維空間鲜锚，而為了防止維度爆炸的問(wèn)題突诬，我們通過(guò)核技巧來(lái)實(shí)現(xiàn)

觀察SVM的分類函數(shù)f(x)，發(fā)現(xiàn)所有的計(jì)算結(jié)果都可以寫(xiě)成內(nèi)積的形式芜繁，向量的內(nèi)積旺隙，即是指兩個(gè)向量相乘之后得到的單個(gè)標(biāo)量或者單個(gè)數(shù)值，這是我們推導(dǎo)出SVM的分類函數(shù)非常重要也是非常神奇的一點(diǎn)骏令，所謂的核技巧蔬捷，就是將這個(gè)內(nèi)積計(jì)算替換成核函數(shù)計(jì)算

我們從一個(gè)案例說(shuō)明什么是核函數(shù)

假設(shè)我們有一個(gè)從二維空間映射到五維空間的映射?，我們定義?為

案例核函數(shù)-1

現(xiàn)在有兩個(gè)二維向量a1=(x1榔袋，x2)和a2=(y1周拐，y2)要做點(diǎn)積計(jì)算，那么將會(huì)有如下兩種方法

（i）：先映射到五維空間凰兑，在做點(diǎn)積運(yùn)算

案例核函數(shù)-2

（ii）：找到一個(gè)函數(shù)K妥粟，直接將原始二維向量帶入該K，定義K=(<x1吏够，x2> + 1)^2

案例核函數(shù)-3

綜上（i）（ii）討論來(lái)看勾给，兩個(gè)式子的計(jì)算結(jié)果完全一樣，但是計(jì)算的過(guò)程區(qū)別很明顯锅知，（i）是先映射到高維播急，再計(jì)算內(nèi)積，而（ii）是直接在原來(lái)的低維空間進(jìn)行某個(gè)函數(shù)的計(jì)算喉镰，在計(jì)算出相同的結(jié)果的同時(shí)旅择，計(jì)算量比起（i）來(lái)說(shuō)小得多，顯然（ii）要比（i）優(yōu)秀得多

通過(guò)低維的函數(shù)計(jì)算得到了先映射再內(nèi)積的高維結(jié)果侣姆，這就是核函數(shù)生真。

可以分析出，核函數(shù)的引入能隱式的得到相同的高維計(jì)算結(jié)果捺宗，這樣可以有效的避免維度爆炸柱蟀，即避免了在高維空間中做內(nèi)積計(jì)算，我們定義核函數(shù)K蚜厉，則SVM的分類函數(shù)可以寫(xiě)為

引入核函數(shù)后的分類函數(shù)

至此长已，我們通過(guò)核技巧替換內(nèi)積計(jì)算為核函數(shù)，SVM模型就可以解決在低維空間里的非線性問(wèn)題（等價(jià)于解決在高維空間里的線性問(wèn)題）

22昼牛、幾個(gè)常用的核函數(shù)

在輸入空間轉(zhuǎn)換到特征空間的過(guò)程中术瓮，對(duì)于任意一個(gè)映射，要構(gòu)造出對(duì)應(yīng)的核函數(shù)顯得非常困難贰健，通常在實(shí)際應(yīng)用中胞四，我們會(huì)在一些常用的核函數(shù)中進(jìn)行選擇，這一點(diǎn)往往依賴特定的某些領(lǐng)域伶椿，而核函數(shù)選擇的有效性需要通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證

下面是一些常用的核函數(shù)

（1）：多項(xiàng)式核函數(shù)

多項(xiàng)式核函數(shù)

其對(duì)應(yīng)的SVM的分類函數(shù)辜伟，是一個(gè)p次多項(xiàng)式，選擇該核函數(shù)則完整的分類函數(shù)為

多項(xiàng)式核函數(shù)的分類函數(shù)

（2）：高斯核函數(shù)

高斯核函數(shù)

其對(duì)應(yīng)的SVM的分類函數(shù)脊另，是一個(gè)高斯徑向基函數(shù)导狡，選擇該核函數(shù)則完整的分類函數(shù)為

高斯核函數(shù)的分類函數(shù)

其中σ是用戶自定義的用于確定到達(dá)率或者說(shuō)函數(shù)值跌落到0的速度參數(shù)，可以通過(guò)調(diào)控σ來(lái)達(dá)到理想的分類效果偎痛，高斯核也是應(yīng)用最為廣泛的核函數(shù)之一

下圖是SVM應(yīng)用核函數(shù)后處理非線性數(shù)據(jù)的結(jié)果

應(yīng)用核函數(shù)完成內(nèi)積計(jì)算

非線性數(shù)據(jù)程序運(yùn)行結(jié)果-1

非線性數(shù)據(jù)程序運(yùn)行結(jié)果-2

可以看到引入核函數(shù)的SVM模型也可以高效的判斷出非線性數(shù)據(jù)樣本的正確分類

整個(gè)SVM的代碼見(jiàn)：SVM算法原理