MLIA/第六章：支持向量機/上

08-10

MLIA/第六章：支持向量機/上

來自專欄 changDA8 人贊了文章

本文作者：知乎用戶：@A Chang，點擊進入知乎主頁；本文首發於知乎。

在閱讀本文前，請先了解以下幾個約定。一旦你決定閱讀，即意味著你默認遵守與本文作者（即我）的這些約定。

著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。
本文不保證內容無誤，請不要以本文內容作為你的參考依據。如發現其中錯誤，懇請指正。
本文僅系本人閱讀書籍的讀書筆記及資料補充，對於非本人創作的內容（包括但不限於：文字，代碼），將會儘力指出原作者與出處。假如侵權請聯繫我刪改。

若對本文有指出意見或疑問，請盡量在評論下回復；私信不能或不能及時回復，請見諒。

一.前言

這是我閱讀《MachineLearningInAction》（中文譯名：《機器學習實戰》，以下簡稱MLIA）的第六章：支持向量（以下簡稱為SVM）的總結筆記。因我數學基礎不充分，故盡量以感性的方式來描寫具體的內容。凡涉及到數學推導的過程，將盡量保持簡單。

以英文版原書為準。你可以順著這篇文章來閱讀原書，因為原書的某些思路不夠具體。

本文不提供書本以及數據的下載，請在網上自行搜索。

支持向量機（Support vector machine）是利用一個分割超平面（ hyperplane）切割兩種類型數據的分布空間，再將未分類的數據放入模型當中判別從屬於哪一片空間以分類。基礎型僅應用於因變數是二分類（例如：0與1，是與否，男與女等）的分類情況。此外支持向量機必須應用在線性可分的數據集中。

我很喜歡知乎的一個回答，簡單道明了SVM的特性。

SVM是樣本稀疏（選幾個樣本作為support vector），LASSO是變數稀疏（選幾個變數作為重要的變數）。
by：@William Who

支持向量機(SVM)是什麼意思？?

www.zhihu.com

二.SVM概念

循序漸進講幾個概念：

分割超平面/不考慮間隔
最大分割超平面/線性SVM/硬間隔
最大分割超平面/非線性SVM/軟間隔

1.分割超平面/不考慮間隔

1.1線性可分

先來講講什麼叫做線性可分：

線性可分本質上就是指能用線性函數將兩類樣本完全分開。

當兩類樣本線性不可分的時候，不可以使用支持向量機；遇到了線性不可分的數據卻仍然想要使用支持向量機，可以利用軟間隔與核技巧的方式來突破這個限制，其中前者相當於給了一個容忍錯誤的界限，後者則是通過把數據投射到高維空間以達到線性可分。

參考鏈接：

線性可分與線性不可分 - Amazing_Man - 博客園?

www.cnblogs.com如何理解在二維空間內線性不可分的數據，可以在五維空間內線性可分？?

www.zhihu.com

1.2分割超平面

為了搞懂這個分割超平面，先搞懂下面幾個問題：

Q：什麼叫分割
A：顧名思義，就是給你一盤混合起來的紅豆綠豆，找到把他們分開的分割依據之後分割它。

Q：什麼叫超平面
A：這個超平面即之前提到的分割依據。之所以要叫」超平面「，這個」超「的意思就代表概念的超越。假設是一個二維空間（譬如一張紙），我們分割他只需要一維」平面「（一條線）；假設是一個三維空間（譬如一塊雪糕），我們分割他需要的是二維平面（就是一刀劈開兩面，一個平面）。如此類推假如我們要分割一個n維空間，我們需要一個n-1維」平面「。這個時候我們僅是借用了」平面「的概念（一維或三維的東西能叫做平面嗎？），所以要賦予它一個名字：超平面。

觀察上圖，這是一個自變數為二維的情況（算上因變數類別實際上是三維）。毋庸置疑這就是線性可分的情況，而且圖上已經花了很多條可以把兩個樣本所屬區域完美的切開的直線了（許多條藍色與一條紅色的直線），我們可以把這些直線都稱作分割超平面。

我們可以把這些平面定義為：

$hp(x,y):w^Tx+b=0$

這裡以w指代超平面參數/係數，x指代自變數，b表示截距，y指代因變數。若無特殊說明，以下公式表述一樣。

之後要討論的是y。一般而言，在其他的分類模型的數學表達中，二分類往往會被表示為1與0。但是在SVM中，我們會把它表示為1與-1，目的是為了方便之後的運算。這是一個關鍵點，在代碼的實現務必考慮到這一點。

這個線性可分的數據集規定為具有這個特性，我們也稱它為分割超平面的約束：

$hp(x,y):w^Tx+b=0$

這是高中數學的內容，無需證明，可以自己找些數據比劃（其實y的取值可以反過來，這取決於你的w的正負，因此我把這個過程叫做規定）。這個特性實際上可表示為：

${displaystyle hp_s(x,y;w,b)={egin{cases}w^T+b>0,&y=1,\w^T+b<0,&y=-1end{cases}}}$

因此，當你求得一個決策邊界擁有這個特性的時候，這個決策邊界即這個數據集的分割超平面。

由於一個數據集可能擁有無數個類似的分割超平面（其中肯定會有一個超平面在大多數情況下都表現最好），因此沒必要深究如何求得這個分割超平面，進入下一節：帶硬間隔的最大分割超平面。

1.3比例放縮問題

考慮一個高中數學問題。

考慮兩條直線的區別：

$y=2x+4-2\ y=x+2-1$

沒錯，他們並沒有任何區別，僅僅是寫法不一樣而已。這個問題已經表達了本節的主題：假如不指定係數範圍，將會出現無數組符合最大分割超平面的係數組合（其實他們都是等比例的）。因此我們有必要歸一化係數，以得到唯一的最大分割超平面的係數。

有兩種固定比例的方法：

第一種：

規定||w||=1，即把它轉化單位向量。

單位向量_百度百科?

baike.baidu.com

第二種：

將係數除以自己的模。這時候我們將把這個係數叫做幾何間隔（原係數叫做函數間隔）。

$hp(x;w,b):frac{w^T}{||w||_2}x+frac{b}{||w||_2}=0$

當||w||=1的時候，幾何間隔即等於函數間隔（故兩種方法實質上等價）。

2.最大分割超平面/硬間隔

2.1硬間隔

前面講到，某個線性可分的數據集可能會擁有無數個分割超平面，我們的目標應該由尋找分割超平面轉為尋找最優分割超平面，而這個最優分割超平面，很有可能就是最大分割超平面。這個最大分割超平面，相比一般的分割超平面，它擁有一個最大的間隔（margin）（maximum margin），而且是硬間隔。正是因為具有這個間隔，最大分割超平面是離訓練觀測最遠的分割超平面。

我們來看看這個間隔是什麼東西，繼續看回上圖：圖中Margin的所標註的地方即為間隔。

可理解為：一個自變數為n維的數據集，那麼他的分割超平面應該表示為n-1維，而這個分割超平面的間隔應該表示為n維。對於圖中自變數為2維的情況來說，這塊間隔也是一塊2維的空間，樣本點僅存在於這塊空間之外，這即是所謂的硬間隔，而且這是最大的間隔。而構成這塊空間的，即是樣本集中的某幾個點，這幾個點是它們各自所屬樣本中距離最大分割超平面最近的點，我們稱這些點為支持向量（Support vectors）。這些點支持著這個最大分割超平面（及其間隔）的存在。

間隔具有兩個特性：

這個最大分割超平面的存在與除了支持向量點之外的樣本點無關，這些樣本點改變不會導致最大分割超平面改變。
間隔的邊緣與最大分割超平面平行。而最大分割超平面到這間隔的兩邊距離應該相等。這很好理解，最大分割超平面無非是間隔這塊空間的中軸。這設置有一個意義：兩個不同類型的樣本集到最分割超平面的最短距離應該是相等的。

之後引入一個高中數學知識：點到超平面的距離公式。

2.2點到超平面（直線/平面等）距離公式

這裡的距離公式基於歐幾里得距離（l2範數）。這是我們最常用的。

$r=frac{|w^Tx+b|}{sqrt{w^Tw}}$

也有不少資料會表示為這樣：

$r=frac{|w^Tx+b|}{||w||_2}$

這個||w||2的符號即表示l2範數（歐幾里得範數），類似的|w|（或||w||1）即表示為l1範數（絕對值範數）。

講到這裡，不妨把兩個平行的超平面到超平面的距離公式也講講，其實兩個平行的平面w是一樣的，b不一樣而已：

$m=frac{|b_1-b_2|}{||w||_2}=frac{|b_1-b_2|}{sqrt{w^Tw}}$

有了這個這兩條公式，我們即可表示出間隔與支持向量的距離關係了。

顯然最大分割超平面的間隔大小是兩個超平面的距離M，而兩個不同類別的支持向量到超平面的距離分別為r甲、r乙且r甲=r乙（前面講到了），以下將r甲與r乙統一稱為R。他們的關係如下：

$M=r_甲+r_乙\R=r_甲=r_乙$

參考鏈接：

https://zh.wikipedia.org/wiki/%E8%8C%83%E6%95%B0?

zh.wikipedia.org

2.4數學表示

顯然，最大分割超平面作為分割超平面的一種，他們的數學表達在形式上應該是十分相似的。

最大分割超平面的數學表示：

$hp(x,y):w^Tx+b=0 ag{最大分割超平面}$

最大分割超平面的約束：

$hp_s(x,y;w,b)=y(w^Tx+b)>0 ag{最大分割超平面的約束}$

間隔的數學表示：

${displaystyle ma(x,y)={egin{cases}w^T+b=r,&y=1,\w^T+b=-r,&y=-1end{cases}}} ag{間隔}$

間隔的約束：

$ma_s(x,y;w,b)=y(w^Tx+b)geq{r} ag{間隔的約束}$

為了推導公式方便，不妨規定間隔為：

${displaystyle ma(x,y)={egin{cases}w^T+b=1,&y=1,\w^T+b=-1,&y=-1end{cases}}} ag{間隔2}$

不要產生疑問，w和b本身就可以變的。

這個時候根據前述平行平面到平面的距離公式可得間隔大小（這一步相當於處理了比例縮放的問題）：

$M=frac{2}{||w||} ag{間隔大小}$

間隔的約束轉化為：

$ma_s(x,y;w,b)=y(w^Tx+b)geq{1} ag{間隔的約束2}$

由於我們要求的是最大分割超平面，它具有最大間隔，因此我們要求得Max（M），該問題已經轉化為一個最優化問題（這裡m或l代表樣本數，以i或j來特指；以下n代表維度數，以k來特指；若無特殊說明，不做變動）：

$max(M)=max_{w,b}frac{2}{||w||}\ s.t.quad y_i(w^Tx_i+b)geq{1},space i=1,2,cdots,m;quad$

最大化||w||^(-1)，等價於最小化||w||^2。故該問題等價於：

$min_{w,b}frac{||w||^2}{2}\ s.t.quad y_i(w^Tx_i+b)geq{1},space i=1,2,cdots,m$

至此，已經把基礎型的SVM求解問題用數學語言表示出來。之後就是如何求解這個問題。這個問題本身是凸優化問題（鬼知道這是什麼？），能直接求解，但是代價太大。因此應該使用一個更加高效的求解方法。這也是2.5章主講的話題。

2.5求解帶約束的多元函數極值

這裡已經不是我能夠為大家講解的地方了，我只能夠通過閱讀資料嘗試把我能理解的部分整理出來給大家分享。假如有錯誤，懇請指正。

對於我而言，目標不在於徹底搞懂數學推導，只要能夠找到一條能夠直接轉換為計算機代碼的求解公式即可。

再此之前我們先引入一個概念：拉格朗日乘數法。

2.5.1（廣義）拉格朗日乘數法part1

請注意小標題包含了廣義兩字，這在之後會解釋為什麼。

先來看看維基百科：

在數學中的最優化問題中，拉格朗日乘數法（以數學家約瑟夫·拉格朗日命名）是一種尋找多元函數在其變數受到一個或多個條件的約束時的極值的方法。這種方法可以將一個有n個變數與k個約束條件的最優化問題轉換為一個解有n + k個變數的方程組的解的問題。這種方法中引入了一個或一組新的未知數，即拉格朗日乘數，又稱拉格朗日乘子，或拉氏乘子，它們是在轉換後的方程，即約束方程中作為梯度（gradient）的線性組合中各個向量的係數。

參考鏈接：

https://zh.wikipedia.org/wiki/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0?

zh.wikipedia.org

說得這麼多，無非就是想表達這樣一個意思：拉格朗日乘數法是用來解帶有一個或多個約束條件的多元函數的極值的方法；同時這個過程還會引入一些叫做拉格朗日乘子的未知數。約束符號為s.t.或subject to。

↓↓↓以下為通用例子↓↓↓

假設某個問題形式如下：

$min_{x}space f(x)\ s.t.quad egin{aligned} g_i(x)leq0,i=1,2,cdots,mquad不等式約束\ h_j(x)=0,j=1,2,cdots,ellquad等式約束 end{aligned}$

則該問題的拉格朗日函數形式為：

$L(x,alpha_{i},eta)=f(x)+sum_{i=1}^{m}alpha_ig_i(x)+sum_{j=1}^{ell}eta_jh_j(x)$

更具體的知識點請看這些老哥的講解：

簡易解說拉格朗日對偶（Lagrange duality）?

www.cnblogs.comhttps://www.douban.com/group/topic/22833507?

www.douban.com

↑↑↑以上為通用例子↑↑↑

回到SVM：

對比觀察我們需要求解的問題，他確實符合這樣的形式：

$min_{w,b}frac{||w||^2}{2}\ s.t.quad 1-y_i(w^Tx_i+b)leq{0},space i=1,2,cdots,m\原問題$

不要只看這裡約束只有一個式子，實際上是有m（樣本數）個，因為你要保證每個樣本都得符合約束。

轉換為拉格朗日函數，為了下一步計算方便，設置運算元α>=0（KKT條件）：

$L(w,b,alpha)=frac{1}{2}||w||^2+sum_{i=1}^{m}alpha_i(1-y_i(w^Tx_i+b))\ s.t. quad alpha_i geq0\ 新問題$

2.5.2（廣義）拉格朗日乘數法part2

那麼，我們得到了這個拉格朗日函數，接下來該怎麼做？

↓↓↓以下為通用例子↓↓↓

回到例子：

$min_{x}space f(x)\ s.t.quad egin{aligned} g_i(x)leq0,i=1,2,cdots,m quad不等式約束 \ h_j(x)=0,j=1,2,cdots,n quad等式約束 end{aligned}\原問題$

我們認為其等價於求解（我們把這個問題叫做主問題）：

$min_xspace max_{alpha,eta}space L(x,alpha,eta)\主問題$

證明如下：

首先我們要解構拉格朗日函數的各組成部分（x遵守約束的前提下）：

$L(x,alpha,eta)=underbrace{f(x)}_{我們要求解的原問題}+sum_{i=1}^{m}underbrace{alpha_i}_{拉格朗日乘數}spaceunderbrace{g_i(x)}_{這東西小於等於0}+sum_{j=1}^{ell}underbrace{eta_i}_{拉格朗日乘數}space underbrace{h_i(x)}_{這東西等於0}\拉格朗日函數$

因此：

$egin{align} max_{alpha,eta} space L(x,alpha,eta)&=max_{alpha,eta} space f(x)+sum_{i=1}^{m}alpha_ig_i(x)+sum_{j=1}^{ell}eta_jh_j(x)\ &=f(x)+max_{alpha,eta}space(sum_{i=1}^{m}alpha_ig_i(x)+sum_{j=1}^{ell}eta_jh_j(x))\ &=f(x)+egin{cases}0,&x遵守約束\+inf,&x不遵守約束 end{cases} end{align}$

為什麼這樣？x遵守約束的時候自不必講；x不遵守約束的時候，假如gi(x)>0或hi(x)=0，完全可以透過設置α和β的值使得max L得到正無限。所以當x遵守約束的時候，我們可以認為max L(x,α,β)=f(x)，而min max L(x,α,β)=min f(x)。

↑↑↑以上為通用例子↑↑↑

回到SVM：

$min_{w,b}space max_{alpha}space L(w,b,alpha)=underbrace{frac{1}{2}||w||^2}_{我們要求的原問題}+sum_{i=1}^{m}underbrace{alpha_i}_{這東西大於等於0}underbrace{(1-y_i(w^Tx_i+b))}_{這東西小於等於0}\ SVM主問題$

相似的：只要w符合約束條件，那麼可以認為求解min max L(w,α,β)即為求解min 1/2*||w||^2。

2.5.3對偶問題/對偶性/Slater條件

我們不糾纏於背景知識，直接進入例子。

↓↓↓以下為通用例子↓↓↓

現在我們要求解的問題：

$min_xspace f(x) = min_{x} space max_{α,β} space L(x,alpha,eta)\ s.t.quad egin{aligned} g_i(x)leq0,i=1,2,cdots,m \ h_j(x)=0,j=1,2,cdots,n end{aligned}\ 主問題$

我們定義這個問題的對偶問題是：

$max_{alpha,eta} space min_{x} L(x,alpha,eta)\對偶問題$

顧名思義，之所以叫做對偶問題，就是因為兩個問題呈現出對偶的特點（求最小值轉化為最大值，求最大值轉化為求最小值）。接下來有這樣一個性質（弱對偶性）：

若主問題與對偶問題都有最優值，則對偶問題是主問題的下界。

即：

$max_{alpha,eta}space min_x space L(x,alpha,eta)leq min_xspace max_{alpha,eta}space L(x,alpha,eta)$

證明：

$egin{align} & min_x space L(x,alpha,eta) leq L(x,alpha,eta)\ & ightarrow max_{alpha,eta}space min_x space L(x,alpha,eta) leq L(x,alpha,eta)\ & ightarrow max_{alpha,eta}space min_x space L(x,alpha,eta) leq max_{alpha,eta}space L(x,alpha,eta)\ & ightarrow max_{alpha,eta}space min_x space L(x,alpha,eta) leq min_x space max_{alpha,eta}space L(x,alpha,eta) end{align}$

以上這種性質我們叫做對偶問題的弱對偶性。我們之所以千辛萬苦求得原問題的對偶問題，就是想通過求解更簡單的對偶問題來替代求解複雜的原問題。但是弱對偶性仍然不滿足這個過程的前提，我們需要的是強對偶性，只有達到強對偶性，才能使得對偶問題的最優值等於原問題的最優值。

為了滿足強對偶性，這時候需要保證滿足Slaters condition(slater條件)。具體數學含義不詳述（我也沒能力詳述），具體參考維基條目。值得一提的是維基百科的這句話：

In words, Slaters condition implies that strong duality holds if there exists an x* is feasible (i.e. all constraints are satisfied and x* is in the domain of all of the fi), and all the nonlinear constraints are slack.

它的意思就是：

當主問題及約束函數均是凸函數（條件1）時，假如滿足slater條件即：在f(x)的可行域中存在特定的x*使得原問題的所有約束成立（條件2）；對於不等式約束：線性約束要小於等於0，非線性約束要小於0（條件3）。這時候可以認為強對偶性存在。

而在更普遍的不等式約束情況下：更是要求所有的約束都要嚴格小於0（不能有等於0的情況出現）。

↑↑↑以上為通用例子↑↑↑

回到SVM：

SVM中原問題及約束均是凸函數（不證明）；而假如數據是線性可分的（SVM適用的條件），w,b的定義域中必然存在一個最優w*,b*（最大分割超平面）（要是不存在你為什麼要求它？？）。

PS：這部分存疑。對於SVM來說，毫無疑問要求約束：1-yi(w^T*xi+b)<=0。但是slater條件(在一般化的不等式約束中，SVM的約束正是如此）要求嚴格取小於0，我無法解釋這部分？？？？請有能力解釋這個問題的朋友指正一下。

因此在SVM中，slater條件是成立的。我們可以通過求解SVM的對偶問題來求解這個最優w*,b*。

參考鏈接：

https://en.wikipedia.org/wiki/Slaters_condition?

en.wikipedia.org

2.5.4KKT條件

還記得前面的標題提及到要留意（廣義）拉格朗日乘數法的廣義這兩字嗎？這一小節將就這一個問題擴展。

先回憶2.5.1小節介紹的拉格朗日乘數法的通用例子：

↓↓↓以下為通用例子↓↓↓

原問題：

$min_{x}space f(x)\ s.t.quad egin{aligned} g_i(x)leq0,i=1,2,cdots,mquad不等式約束\ h_j(x)=0,j=1,2,cdots,nquad等式約束 end{aligned}\原問題$

主問題（拉格朗日函數）：

$min_xspace max_{alpha,eta}space L(x,alpha,eta)=f(x)+sum_{i=1}^{m}alpha_ig_i(x)+sum_{j=1}^{ell}eta_jh_j(x)\主問題$

其實在這種情況下，拉格朗日乘數法是不適用的。為什麼？因為裡面除了包含了等式約束之外，還包含了不等式約束。而（狹義）拉格朗日乘數法是不應該出現不等式約束的。為了能讓拉格朗日乘數法適用於這種情況，必須要對其進行推廣，這時候你已經可以把它叫做KKT乘數法了。

而使用KTT乘數法需要遵循以下的條件：

必要條件（x*代表最優值）：

平穩性(Stationarity)：
$For maximizing space f(x): {displaystyle abla f(x^{*})=sum _{i=1}^{m}alpha_{i} abla g_{i}(x^{*})+sum _{j=1}^{ell }eta_{i} abla h_{j}(x^{*}),}\ For minimizing space f(x): {displaystyle - abla f(x^{*})=sum _{i=1}^{m}alpha_{i} abla g_{i}(x^{*})+sum _{j=1}^{ell }eta_{i} abla h_{j}(x^{*})}$
主問題可行(Primal feasibility)：
${displaystyle g_{i}(x^{*})leq 0,{ ext{ for }}i=1,ldots ,m} \ {displaystyle h_{j}(x^{*})=0,{ ext{ for }}j=1,ldots ,ell ,!}$
對偶可行(Dual feasibility)：
${displaystyle alpha _{i}geq 0,{ ext{ for }}i=1,ldots ,m}$
這就是為什麼我會在前面要求SVM中設置拉格朗日運算元α>=0的原因。
PS：我看到有一些資料要求等式約束的拉格朗日運算元β=0的，但是維基百科並沒有收錄，故備註。希望有讀者能分享相關資料。
互補鬆弛(Complementary slackness)：
${displaystyle alpha _{i}g_{i}(x^{*})=0,{ ext{ for }};i=1,ldots ,m}$
這是一個額外的約束，理由不詳。但是這個約束對於SVM的特性的表示十分重要。之後詳細解釋。

充分條件：

主問題及其約束是凸函數，且是連續可微的（要是不連續可微，你怎麼求上一步的偏導數呢，滿足平穩性這個條件呢？）。

↑↑↑以上為通用例子↑↑↑

當滿足上述條件，你即可以得到KKT乘數法的充分必要條件，這時候已經足以進入下一步的公示表示中去了。

回到SVM：

SVM滿足KKT的充分必要條件。

總結SVM中需要顯式註明的KKT條件（其他的在SVM中已經內含了）：

主問題可行：
$1-y_i(w^Tx_i+b)leq{0},space i=1,2,cdots,m$
對偶可行：
${displaystyle alpha _{i}geq 0,{ ext{ for }}i=1,ldots ,m}$
互補鬆弛：
${displaystyle alpha _{i}*(1-y_i(w^Tx_i+b))=0,{ ext{ for }};i=1,ldots ,m}$

第一、二個約束一開始已經聲明。剩下第三個約束需要詳細講述他在SVM中的實際意義。

回憶SVM的拉格朗日函數結構：

$L(w,b,alpha)=underbrace{frac{1}{2}||w||^2}_{我們要求的原問題}+sum_{i=1}^{m}underbrace{alpha_i}_{這東西大於等於0}underbrace{(1-y_i(w^Tx_i+b))}_{這東西小於等於0}\ SVM的拉格朗日函數$

根據這些條件，實際上我們可以得到兩種情況：

aigi(xi)=0，ai>0，gi(xi)=0；這個時候拉格朗日運算元α（也許該叫做KTT運算元了）大於0，而gi(x)等於0。毫無疑問，這代表的是樣本集中作為支持向量的樣本，因為他們距離間隔的距離為0，實際上承擔著維持間隔存在的作用。
aigi(xi)=0，ai=0，gi(xi)<0；這個時候α=0,而gi(x)小於0。即表明這些這些樣本是遠離間隔（乃至超平面），靠近兩端的一般樣本，這些樣本對於下一步的接下來的計算毫無意義。

2.5.5（廣義）拉格朗日乘數法part3

到了這一步，我們就差不多到達最後一步了。上兩小節的目的是為我們對SVM問題使用拉格朗日乘數法鋪墊好了理論依據（強對偶性、KKT條件），而這一節即將進入對SVM的拉格朗日函數求解的過程中。

回憶SVM的對偶問題：

$underbrace{max_{alpha}space underbrace{min_{w,b}space L(w,b,alpha)=frac{1}{2}||w||^2+sum_{i=1}^{m}alpha_i(1-y_i(w^Tx_i+b))}_{內層}}_{外層}\ s.t. quad {displaystyle alpha _{i}geq 0,{ ext{ for }}i=1,ldots ,m}\SVM對偶問題$

之所以要得到主問題的對偶問題，是因為求解對偶問題的最優值等價於求解主問題（而求解主問題又等價於求解原問題），並且求解難度更簡單。為什麼更簡單，因為在內層的部分即：

${min_{w,b}space L(w,b,alpha)=frac{1}{2}||w||^2+sum_{i=1}^{m}alpha_i(1-y_i(w^Tx_i+b))}$

我們對內層求w（w是n維的）與b的偏導數並置0（求極值），不需要考慮拉格朗日乘子α的約束：因為在內層這一步並不是求對偶函數本身，而是對偶函數內含的一個中間值（求外層即對偶函數才要求KTT條件），所以可以簡單把他視作無約束求極值問題（相比原問題簡單多了）；此外在內層求偏導的過程應把其他無關的未知數視作常量。

$frac{partial L(w,b,alpha)}{partial w_k}=w_k-sum_{i=1}^{m}alpha_iy_ix_i=0\ 沿著w_j方向求偏導數並置0$

我建議這一步你們都手動推演一下，提示：當你求wk偏導的時候，其他的w你自然要把它當做常數無視掉。觀察上式，實際上你會發現wk的偏導數和k並無關係。所以可以認為各個w的偏導是一樣的：

$frac{partial L(w,b,alpha)}{partial w}=w-sum_{i=1}^{m}alpha_iy_ix_i=0\ 沿著各w方向求偏導數並置0$

可得：

$w=sum_{i=1}^{m}alpha_iy_ix_i ag{1}$

之後對b方向求偏導：

$frac{partial L(w,b,alpha)}{partial b}=-sum_{i=1}^{m}alpha_iy_i=0\ 沿著b方向求偏導數並置0$

可得：

$sum_{i=1}^{m}alpha_iy_i=0 ag{2}$

折騰一番，把（1）式及（2）式代回對偶函數中，（並考慮KTT條件，）可得：

$underbrace{max_alphaspace L(w,b,alpha)=sum_{i=1}^{m}alpha_i-frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}alpha_ialpha_jy_iy_jx_i^Tx_j\}_{外層}\ s.t.space egin{align} & sum_{i=1}^{m}alpha_iy_i=0\ & 0leqalpha_i space,{ ext{ for }};i=1,ldots ,m end{align}$

這個代入過程十分困難：涉及到各種亂七八糟的矩陣運算。因此在推導的過程中你不妨把x和w當做一維來嘗試推導（但是我也不建議你這麼做，沒有必要）。

到了這一步，只需要求得α這個問題就基本解決了。但是求解這個問題是十分困難的（這已經是第二次提到要求解困難的問題了)。而且求出α並不是終極目標，我們先討論如何得到終極目標，再來討論如何求解α的問題。

2.5.6求解w和b

Q：我們現在先假設我們已經求得α，但是我們的終極目標是什麼？
A：回到本源，我們的目的是為了求得參數w和b，因為只有求得這些參數我們才能確定最大分割超平面。拉格朗日乘子α只是我們為了求解這個問題的中間量而已（不要被一大堆未知數和min、max弄混了）。

在求解w和b之前，我們先來講講前面提及到的一個知識點：

樣本集中只有支持向量所對應的拉格朗日乘數α大於0。

因此我們不妨從樣本集中提出一個子集S代表僅包含支持向量的部分：

$S={i|alpha_i>0,i=1,2,cdots,m}$

假如你已經求得了α，根據之前求偏導並置0的結果你已得到了w：

$egin{align} w&=sum_{i=1}^{m}alpha_iy_ix_i\ &=sum_{i otin S}0*y_ix_i+sum_{iin S}alpha_iy_ix_i\ &=sum_{iin S}alpha_iy_ix_i end{align}$

下一步是求b，這時候我們要藉助間隔公式：

$y_s(w^Tx_s+b)=1 \s.t. quad sin S$

之後：

$egin{align} &y_s(w^Tx_s+b)=1\ & ightarrow w^Tx_s+b=frac{1}{y_s}\ & ightarrow w^Tx_s+b=y_s \ &(支持向量中y_s=1|-1,所以 frac{1}{y_s}=y_s)\ & ightarrow b =y_s-w^Tx_s\ &(代入上面求解得到的w)\ & ightarrow b=y_s-sum_{iin S}alpha_iy_ix_i^Tx_s end{align}$

任意一組(ys,xs)都可以用來計算b，因此在實際操作中，我們一般會採取更具穩健性的取平均值：

$b=meanspacesum_{sin S}(y_s-sum_{iin S}alpha_iy_ix_i^Tx_s)$

至此w和b已求得，最大分割超平面已確定。

2.6預測

把預測樣本帶入到最大分割超平面的公式當中，以得到的結果的符號作為預測結果。

$y_{test}=sign(sum_{iin S}alpha_iy_ix_i^Tx_{test}+b) \預測公式$

3.最大分割超平面/軟間隔

3.1軟間隔

之前提到，SVM只能應用於數據集線性可分的場合，但是現實的數據往往是非線性可分的。這時候，為了保證能尋找到一個線性決策邊界，只能使模型允許盡量少的錯誤存在。軟間隔正是脫胎於這個概念。顧名思義，軟間隔相對於硬間隔，最重要的特點就在於他的間隔並不是絕對的，見下圖：

以紅點為例，可以看出圖上實際上分為了4類樣本（點）：

支持向量；
不是支持向量/被正確分類/在間隔之外/遠離最大分割超平面；
不是支持向量/被正確分類/在間隔之內/離最大分割超平面有一些距離；
不是支持向量/被錯誤分類/越過了最大分割超平面出現在錯誤的一側；

其中前兩種樣本是硬間隔SVM中就出現的。而後面兩種樣本是由於軟間隔SVM的特性而導致產生的。第三種雖然沒有分類錯誤，但是進入了間隔的區域；而第四種是分類錯誤。顯而易見，對於這兩種點來說：

$0<y_{type3}(w^Tx_{type3}+b)<1 ag{type3}$

$y_{type4}(w^Tx_{type4}+b)<0 ag{type4}$

這和第一第二種點的公式是相悖的：

$y(w^Tx+b)geq1 ag{type1|type2}$

為此，硬間隔的公式已經不足以表示這種情況，因此需要引入新的概念：損失函數。

3.2損失函數

損失函數的概念類似於在邏輯回歸提及的激活函數（其實還會遇到懲罰函數，約束函數的說法，意思也類似）。顧名思義，損失函數就是為了衡量損失程度的函數：衡量的是模型預測與實際觀察值之間的偏差（損失）的大小。在大部分機器學習的模型中，總是會引入類似的概念用來衡量模型的損失程度，損失程度自然是越小越好，使得模型更加貼切實際觀察值，但同時也要避免過擬合的情況發生。

這裡我們把引入損失函數l(z)的軟間隔SVM公式定義為：

$min_{w,b}spacefrac{||w||^2}{2}+Csum_{i=1}^{m}ell(z)\ s.t.quad egin{align} &y_i(w^Tx_i+b)geq{1-ell(z)},space i=1,2,cdots,m\ &z=y_i(w^Tx_i+b) end{align}$

觀察公式，可以發現引入一個新的未知數C，這個C代表的是懲罰係數。對C的取值能影響損失函數的錯誤允許的寬限程度：假如C取值為+inf，這時等價於硬間隔SVM（因為l(z)是一個大於等於0的數字，代表對實際觀察的偏差程度），這時候對於+inf取最小值是無意義的，因此必須要求l(z)=0（即要求分類完全準確）；假如C取值為有限值，這時允許部分樣本錯誤分類；當C取值為0，這時將代表允許所有樣本分類錯誤，模型沒有意義。

損失函數也有數種不同類型（以下z=yi(wTxxi+b)）：

01損失函數：與之前邏輯回歸提及的階躍函數等價，是一個非凸非連續的函數，數學性質不好。一般會以此為基礎選擇更平滑的函數來替代。在軟間隔SVM中：
$ell(z)= egin{cases} 1,1-z>0space即z<1,\ 0,1-zleq0space即zgeq1 end{cases}$
很好理解。當z<1即代表不符合硬間隔SVM的約束，所以對於模型來說是損失，這時候的損失值等於1。這裡的截斷點z=1，而在邏輯回歸中，截斷點等於0.5。
鉸鏈損失（hinge loss）：參見維基百科原話：「鉸鏈損失是使用於最大化最小間隔（即SVM的間隔：最大化間隔到兩類型樣本中的最短距離）」的損失函數。這是SVM中最常用的損失函數。公式如下：
$ell(z)=max(0,1-z)$
對率損失（logistic loss）：實際上與邏輯回歸中的Sigmoid等價，公式如下：
$l(z)=logspace ({1+e^{-x}})$

在之後會講到，使用特定的核函數的與對率損失函數的SVM，能被數學證明為與邏輯回歸等價

PS：我發現邏輯回歸中某個樣本的類別幾率有兩種表示方式，其中有一個表示方式是不能等價於SVM的。（請指正）。

我們以SVM最常用的鉸鏈損失為例，繼續介紹軟間隔SVM的公式。

之後我們以ξ作為鬆弛變數指代l(z)，並以hinge損失作為例子：

$min_{w,b}spacefrac{||w||^2}{2}+Csum_{i=1}^{m}xi_i\ s.t.quad egin{align} &y_i(w^Tx_i+b)geq{1-xi_i},space i=1,2,cdots,m\ &xigeq{0}\ end{align}$

3.3推導

類似地，我們將要對以上公式使用拉格朗日乘數法，使得問題轉化為更容易解答的形式。為避免篇幅過長，將不在具體推導，僅列舉公式：

軟間隔SVM的拉格朗日函數：

$L(w,b,alpha)=frac{1}{2}||w||^2+sum_{i=1}^{m}alpha_i(1-xi_i-y_i(w^Tx_i+b))+sum_{i=1}^{m}eta_i(-xi_i)\ s.t. quad egin{align} alpha_i geq0\ eta_i geq0 end{align} \軟間隔SVM的拉格朗日函數$

之後利用對偶問題的處理手法來轉換：

$max_{alpha,eta}space min_{w,b}L(w,b,alpha)=frac{1}{2}||w||^2+sum_{i=1}^{m}alpha_i(1-xi_i-y_i(w^Tx_i+b))+sum_{i=1}^{m}eta_i(-xi_i)\ s.t. quad egin{align} alpha_i geq0\ eta_i geq0 end{align} \軟間隔SVM的拉格朗日函數的對偶函數$

之後，對該問題的內層求w、b方向與C方向的偏導數：

$w=sum_{i=1}^{m}alpha_iy_ix_i ag{1}$

$sum_{i=1}^{m}alpha_iy_i=0 ag{2}$

$C=alpha_i+eta_i ag{3}$

第三條公式是軟間隔SVM所特有的。將其代入為原來的對偶公式的內層：

在考慮KTT條件：

主問題可行：
$1-xi-y_i(w^Tx_i+b)leq{0}$
對偶可行（僅指不等式約束的拉格朗日乘數項大於等於0，為表示方便，把a<=C也放入）：
$0leqalphaleq C,quad0leqeta$
互補鬆弛：
${displaystyle alpha _{i}*(1-xi-y_i(w^Tx_i+b))=0,{ ext{ for }};i=1,ldots ,m}$
${displaystyle eta _{i}*xi_i=0,{ ext{ for }};i=1,ldots ,m}$

以上即使得軟間隔SVM使用KTT乘數法的條件。根據對偶可行以及互補鬆弛條件，可描述三種情況：

ai=0，gi(xi)>=0，這時樣本xi是被正確分類且不是支持向量的樣本；
0<ai<C，gi(xi)=0，這時候樣本xi是被正確分類且是支持向量的樣本；
ai=C，gi(xi)=0，即bi=0。這時候ξi（就是那個代表單個樣本損失的希臘字母）取任何值都無意義（換言之取無限的損失也無所謂）。若ξi<=1，則代表樣本xi進入到兩間隔內部；若ξi>1，則代表樣本xi被錯分。

進行到這一步的時候，對於軟間隔SVM的公式推導也已經全部完結了，之後的問題就是如何實現解題過程了。所涉及的內容則是SMO演算法。篇幅有限，將在下一篇文章上講解（還值得一講的是核技巧/kernel tricks/核函數）。

三.總結

以上就是本文的知識脈絡圖。

這東西實在很繞，我花了2個星期才搞明白整個思路，而整理這篇文章也快花了2星期，算起來快1個月了。感謝群裡面以及知乎大佬的指導，沒有他們的講解我不能整理出清晰的脈絡。希望大家多多支持。本文篇幅過大，作者又不精於數學，若遇到錯誤，請多多包涵，歡迎指正。