零基礎學SVM—Support Vector Machine系列之二

本文原作者耳東陳，本文原載於作者的知乎文章。AI 研習社已獲得轉載授權。有約束最優化問題的數學模型就像我們在第二部分結尾時提到的，SVM問題是一個不等式約束條件下的優化問題。絕大多數模式識別教材在討論這個問題時都會在附錄中加上優化演算法的簡介，雖然有些寫得未免太簡略，但看總比不看強，所以這時候如果你手頭有一本模式識別教材，不妨翻到後面找找看。結合附錄看我下面寫的內容，也許會有幫助。我們先解釋一下我們下面講解的思路以及重點關注哪些問題：1）有約束優化問題的幾何意象：閉上眼睛你看到什麼？2）拉格朗日乘子法：約束條件怎麼跑到目標函數裡面去了？3）KKT條件：約束條件是不等式該怎麼辦？4）拉格朗日對偶：最小化問題怎麼變成了最大化問題？5）實例演示：拉格朗日對偶函數到底啥樣子？6）SVM優化演算法的實現：數學講了辣么多，到底要怎麼用啊？3.1 有約束優化問題的幾何意象約束條件一般分為等式約束和不等式約束兩種，前者表示為（注意這裡的X跟第二章裡面的樣本x沒有任何關係，只是一種通用的表示)；後者表示為（你可能會問為什麼不是,別著急，到KKT那裡你就明白了）。假設（就是這個向量一共有d個標量組成），則的幾何意象就是d維空間中的d-1維曲面，如果函數是線性的，則是個d-1維的超平面。那麼有約束優化問題就要求在這個d-1維的曲面或者超平面上找到能使得目標函數最小的點，這個d-1維的曲面就是「可行解區域」。對於不等式約束條件，，則可行解區域從d-1維曲面擴展成為d維空間的一個子集。我們可以從d=2的二維空間進行對比理解。等式約束對應的可行解空間就是一條線；不等式約束對應的則是這條線以及線的某一側對應的區域，就像下面這幅圖的樣子（圖中的目標函數等高線其實就是等值線，在同一條等值線上的點對應的目標函數值相同）。

圖3 有約束優化問題的幾何意象圖

3.2 拉格朗日乘子法

儘管在3.1節我們已經想像出有約束優化問題的幾何意象。可是如何利用代數方法找到這個被約束了的最優解呢？這就需要用到拉格朗日乘子法。

首先定義原始目標函數，拉格朗日乘子法的基本思想是把約束條件轉化為新的目標函數的一部分(關於λ的意義我們一會兒再解釋)，從而使有約束優化問題變成我們習慣的無約束優化問題。那麼該如何去改造原來的目標函數使得新的目標函數的最優解恰好就在可行解區域中呢？這需要我們去分析可行解區域中最優解的特點。

1）最優解的特點分析

這裡比較有代表性的是等式約束條件（不等式約束條件的情況我們在KKT條件里再講）。我們觀察一下圖3中的紅色虛線（可行解空間）和藍色虛線（目標函數的等值線），發現這個被約束的最優解恰好在二者相切的位置。這是個偶然嗎？我可以負責任地說：「NO！它們溫柔的相遇，是三生的宿命。」為了解釋這個相遇，我們先介紹梯度的概念。梯度可以直觀的認為是函數的變化量，可以描述為包含變化方向和變化幅度的一個向量。然後我們給出一個推論：

推論1：「在那個宿命的相遇點（也就是等式約束條件下的優化問題的最優解），原始目標函數的梯度向量必然與約束條件的切線方向垂直。」

關於推論1的粗淺的論證如下：

如果梯度矢量不垂直於在點的切線方向，就會在的切線方向上存在不等於0的分量，也就是說在相遇點附近，還在沿著變化。這意味在上這一點的附近一定有一個點的函數值比更小，那麼就不會是那個約束條件下的最優解了。所以，梯度向量必然與約束條件的切線方向垂直。

推論2：「函數的梯度方向也必然與函數自身等值線切線方向垂直。」

推論2的粗淺論證：與推論1 的論證基本相同，如果的梯度方向不垂直於該點等值線的切線方向，就會在等值線上有變化，這條線也就不能稱之為等值線了。

根據推論1和推論2，函數的梯度方向在點同時垂直於約束條件和自身的等值線的切線方向，也就是說函數的等值線與約束條件曲在點具有相同（或相反）的法線方向，所以它們在該點也必然相切。

讓我們再進一步，約束條件也可以被視為函數的一條等值線。按照推論2中「函數的梯度方向必然與自身的等值線切線方向垂直」的說法，函數在點的梯度矢量也與的切線方向垂直。

到此我們可以將目標函數和約束條件視為兩個具有平等地位的函數，並得到推論3：

推論3：「函數與函數的等值線在最優解點處相切，即兩者在點的梯度方向相同或相反」，

於是我們可以寫出公式(3.1)，用來描述最優解的一個特性：

這裡增加了一個新變數,用來描述兩個梯度矢量的長度比例。那麼是不是有了公式（3.1）就能確定的具體數值了呢？顯然不行！從代數解方程的角度看，公式（3.1）相當於d個方程（假設是d維向量，函數的梯度就是d個偏導數組成的向量，所以公式(2.15)實際上是1個d維矢量方程，等價於d個標量方程），而未知數除了的d個分量以外，還有1個。所以相當於用d個方程求解d+1個未知量，應有無窮多組解；從幾何角度看，在任意曲線（k為值域範圍內的任意實數）上都能至少找到一個滿足公式(3.1)的點，也就是可以找到無窮多個這樣的相切點。所以我們還需要增加一點限制，使得無窮多個解變成一個解。好在這個限制是現成的，那就是：

把公式(3.1)和(3.2)放在一起，我們有d+1個方程，解d+1個未知數，方程有唯一解，這樣就能找到這個最優點了。

2）構造拉格朗日函數

雖然根據公式(3.1)和(3.2),已經可以求出等式約束條件下的最優解了，但為了在數學上更加便捷和優雅一點，我們按照本節初提到的思想，構造一個拉格朗日函數，將有約束優化問題轉為無約束優化問題。拉格朗日函數具體形式如下：

新的拉格朗日目標函數有兩個自變數，根據我們熟悉的求解無約束優化問題的思路，將公式(3.3)分別對求導，令結果等於零，就可以建立兩個方程。同學們可以自己試一下，很容易就能發現這兩個由導數等於0構造出來的方程正好就是公式(3.1)和(3.2)。說明新構造的拉格朗日目標函數的優化問題完全等價於原來的等式約束條件下的優化問題。

至此，我們說明白了「為什麼構造拉格朗日目標函數可以實現等式約束條件下的目標優化問題的求解」。可是，我們回頭看一下公式(2.14)，也就是我們的SVM優化問題的數學表達。囧，約束條件是不等式啊！怎麼辦呢？

3.3 KKT條件

對於不等式約束條件的情況，如圖4所示，最優解所在的位置有兩種可能，或者在邊界曲線上或者在可行解區域內部滿足不等式的地方。

第一種情況：最優解在邊界上，就相當於約束條件就是。參考圖4，注意此時目標函數的最優解在可行解區域外面，所以函數在最優解附近的變化趨勢是「在可行解區域內側較大而在區域外側較小」，與之對應的是函數在可行解區域內小於0，在區域外大於零，所以在最優解附近的變化趨勢是內部較小而外部較大。這意味著目標函數的梯度方向與約束條件函數的梯度方向相反。因此根據公式(3.1)，可以推斷出參數。

圖4：不等式約束條件下最優解位置分布的兩種情況

第二種情況：如果在區域內，則相當於約束條件沒有起作用，因此公式(3.3)的拉格朗日函數中的參數。整合這兩種情況，可以寫出一個約束條件的統一表達，如公式(3.4)所示。

其中第一個式子是約束條件本身。第二個式子是對拉格朗日乘子的描述。第三個式子是第一種情況和第二種情況的整合：在第一種情況里，，；在第二種情況下，，。所以無論哪一種情況都有。公式(3.4)就稱為Karush-Kuhn-Tucker條件，簡稱KKT條件。

推導除了KKT條件，感覺有點奇怪。因為本來問題的約束條件就是一個，怎麼這個KKT條件又多弄出來兩條，這不是讓問題變得更複雜了嗎？這裡我們要適當的解釋一下：

1）KKT條件是對最優解的約束，而原始問題中的約束條件是對可行解的約束。

2）KKT條件的推導對於後面馬上要介紹的拉格朗日對偶問題的推導很重要。

3.4 拉格朗日對偶

接下來讓我們進入重頭戲——拉格朗日對偶。很多教材到這裡自然而然的就開始介紹「對偶問題」的概念，這實際上是一種「先知式」的教學方式，對於學生研究問題的思路開拓有害無益。所以，在介紹這個知識點之前，我們先要從宏觀的視野上了解一下拉格朗日對偶問題出現的原因和背景。

按照前面等式約束條件下的優化問題的求解思路，構造拉格朗日方程的目的是將約束條件放到目標函數中，從而將有約束優化問題轉換為無約束優化問題。我們仍然秉承這一思路去解決不等式約束條件下的優化問題，那麼如何針對不等式約束條件下的優化問題構建拉格朗日函數呢？

因為我們要求解的是最小化問題，所以一個直觀的想法是如果我能夠構造一個函數，使得該函數在可行解區域內與原目標函數完全一致，而在可行解區域外的數值非常大，甚至是無窮大，那麼這個沒有約束條件的新目標函數的優化問題就與原來有約束條件的原始目標函數的優化是等價的問題。

拉格朗日對偶問題其實就是沿著這一思路往下走的過程中，為了方便求解而使用的一種技巧。於是在這裡出現了三個問題：1）有約束的原始目標函數優化問題；2）新構造的拉格朗日目標函數優化問題；3）拉格朗日對偶函數的優化問題。我們希望的是這三個問題具有完全相同的最優解，而在數學技巧上通常第三個問題——拉格朗日對偶優化問題——最好解決。所以拉格朗日對偶不是必須的，只是一條捷徑。

1）原始目標函數（有約束條件）

為了接下來的討論，更具有一般性，我們把等式約束條件也放進來，進而有約束的原始目標函數優化問題重新給出統一的描述：

公式(3.5)表示m個等式約束條件和n個不等式約束條件下的目標函數的最小化問題。

2）新構造的目標函數（沒有約束條件）

接下來我們構造一個基於廣義拉格朗日函數的新目標函數，記為：

其中為廣義拉格朗日函數，定義為：

這裡，，是我們在構造新目標函數時加入的係數變數，同時也是公式(3.6)中最大化問題的自變數。將公式(3.7)帶入公式(3.6)有：

我們對比公式(3.5)中的約束條件，將論域範圍分為可行解區域和可行解區域外兩個部分對公式（3.8）的取值進行分析，將可行解區域記為，當時有：

可行解區域內：由於，且係數，, 所以有：

可行解區域外：代表公式(3.5)中至少有一組約束條件沒有得到滿足。如果，則調整係數就可以使；如果，則調整係數就可以使；如果，調整係數就可以使。這意味著，此時有

把公式(3.8),(3.9)和(3.10)結合在一起就得到我們新構造的目標函數的取值分布情況：

此時我們回想最初構造新目標函數的初衷，就是為了建立一個在可行解區域內與原目標函數相同，在可行解區域外函數值趨近於無窮大的新函數。看看公式（3.11）,yeah,我們做到了。

現在約束條件已經沒了，接下來我們就可以求解公式(3.12)的問題

這個問題的解就等價於有約束條件下的原始目標函數最小化問題（公式3.5）的解。

3）對偶問題

儘管公式(3.12)描述的無約束優化問題看起來很美好，但一旦你嘗試著手處理這個問題，就會發現一個麻煩。什麼麻煩呢？那就是我們很難建立的顯示錶達式。如果再直白一點，我們很難直接從公式(3.8)裡面把這兩組參數拿掉，這樣我們就沒法通過令的方法求解出最優解。

要解決這個問題，就得用一點數學技巧了，這個技巧就是對偶問題。我們先把公式(3.6)和公式(3.12)放在一起，得到關於新構造的目標函數的無約束優化的一種表達：

然後我們再構造另一個函數，叫做，然後給出另外一個優化問題的描述：

對比公式(3.13)和(3.14)，發現兩者之間存在一種對稱的美感。所以我們就把(3.14)稱作是(3.13)的對偶問題。現在我們可以解釋一下中的P是原始問題Primary的縮寫，中的D是對偶問題Dual的縮寫。如果我們能夠想辦法證明(3.14)和(3.13)存在相同的解，那我們就可以在對偶問題中選擇比較簡單的一個來求解。

4）對偶問題同解的證明

對偶問題和原始問題到底有沒有相同的最優解呢？關於這個問題的根本性證明其實沒有在這裡給出，而且在幾乎我看到的所有有關SVM的資料里都沒有給出。但我比較厚道的地方是我至少可以告訴你哪裡能找到這個證明。在給出證明的鏈接地址之前，我們先給一個定理，幫助大家做一點準備，同時也減少一點看那些更簡略的資料時的困惑。

定理一：對於任意α，β和χ有：

定理一的證明：

即

所以

即：

這裡的,分別是對偶問題和原始問題的最優值。

定理一既引入了,的概念，同時也描述了兩者之間的關係。我們可以在這個基礎上再給一個推論：如果能夠找到一組使得，那麼就應該有：

這個推論實際上已經涉及了原始問題與對偶問題的「強對偶性」。當時，我們稱原始問題與對偶問題之間「弱對偶性」成立；若，則稱「強對偶性」成立。

如果我們希望能夠使用拉格朗日對偶問題替換原始問題進行求解，則需要「強對偶性」作為前提條件。於是我們的問題變成了什麼情況下，強對偶性才能夠在SVM問題中成立。關於這個問題我們給出定理二：

定理二：對於原始問題和對偶問題，假設函數和不等式約束條件,

為凸函數，等式約束條件中的為仿射函數（即由一階多項式構成的函數，均為列向量，為標量）；並且至少存在一個X使所有不等式約束條件嚴格成立，即，則存在使得是原始問題的最優解，是對偶問題的最優解且有：，並其充分必要條件如下：

再次強調一下，公式(3.15)是使為原始問題的最優解，為對偶問題的最優解，且的充分必要條件。公式(3.15)中的(1)~(3)，是為了求解最優化要求目標函數相對於三個變數的梯度為0；(4)~(6)為KKT條件（見公式3.4(3)），這也是我們為什麼要在3.3節先介紹KKT條件的原因；(7)為等式約束條件。

定理二的證明詳見 《Convex Optimization》， by Boyd and Vandenberghe. Page-234, 5.3.2節。（http://dwz.cn/6P8gpT）

關於拉格朗日對偶的一些參考資料：

1. 簡易解說拉格朗日對偶（Lagrange duality）（http://dwz.cn/6P8k8s），這一篇對對偶問題的來龍去脈說的比較清楚，但是在強對偶性證明方面只給出了定理，沒有給出證明過程，同時也缺少幾何解釋。

2.優化問題中的對偶性理論（http://xiaoyc.com/duality-theory-for-optimization/），這一篇比較專業，關於對偶理論的概念，條件和證明都比較完整，在數學專業文獻里屬於容易懂的，但在我們這種科普文中屬於不太好懂的，另外就是論述過程基本跟SVM沒啥關係。

3.5 拉格朗日對偶函數示例

儘管上述介紹在代數層面已經比較淺顯了，但是沒有可視化案例仍然不容易建立起直觀的印象。所以我儘可能的在這裡給出一個相對簡單但是有代表性的可視化案例。

圖5：有約束條件下的最優化問題可視化案例

圖5中的優化問題可以寫作：

之所以說這個案例比較典型是因為它與線性SVM的數學模型非常相似，且包含了等式和不等式兩種不同的約束條件。更重要的是，這兩個約束條件在優化問題中都起到了作用。如圖5所示，如果沒有任何約束條件，最優解在坐標原點(0, 0)處（青色X）；如果只有不等式約束條件，最優解在坐標(1,0)處（紅色X）；如果只有等式約束條件，最優解在坐標(1,-1)處（綠色+）；如果兩個約束條件都有，最優解在處(黃色O)。

針對這一問題，我們可以設計拉格朗日函數如下：

根據公式（3.11），函數只在綠色直線在紅色圓圈內的部分——也就是直線在圓上的弦——與原目標函數取相同的值，而在其他地方均有，如圖6所示。

圖6：（除了圖中綠色虛線部分，其他部分的函數值均為無窮大）

（需要注意的是，此處不能使用對求導等於0的方式消掉，因為函數

在X為確定值時，是的線性函數，其極大值並不在梯度為0的地方）。由於函數在沒有約束條件下的最優解並不在這條弦上，所以顯然對求導等於零的方法是找不到最優解的。但是對於這個簡單的問題，還是能夠從圖中看到最優解應該在 ：

由於該最優解是在和的交點處，所以可以很容易地理解：當時，無論取什麼值都可以使函數達到最小值。

然而這個最優解是依靠幾何推理的方式找到的，對於複雜的問題，這種方法似乎不具有可推廣性。

那麼，我們不妨嘗試一下，用拉格朗日對偶的方式看看這個問題。我們將視為常數，這時就只是X的函數。我們可以通過求導等於零的方式尋找其最小值，即。我們對公式(3.17)對

分別求偏導，令其等於0，有：

可以解得:

將(3.19)帶入(3.17)可以得到:

考慮到（3.15）中的條件（5），我們將函數(3.20)在的論域畫出來，如圖7所示。可以通過對求導等於0的方式解出最優解，將其帶入公式（3.19）可以得到

最後通過對比，我們看到拉格朗日原始問題和對偶問題得到了相同的最優解（原始問題的最優解中可以是任何值）。

最後，我來解釋一下鞍點的問題。鞍點的概念大家可以去網上找，形態上顧名思義，就是馬鞍的中心點，在一個方向上局部極大值，在另一個方向上局部極小值。這件事跟我們的拉格朗日函數有什麼關係呢？由於這個例子中的拉格朗日函數包含，四個自變數，無法直接顯示。為了更好的可視化，我們固定住其中兩個變數，令。此時拉格朗日函數就變成一個可以可視化的二元函數，我們把它的曲面畫出來。

圖8：可視化效果

圖8(a)中的最優點可以能夠兩個角度去定義，如圖8(b)所示。(為加以區別二維和四維的情況，我們將四維情況對應的 大寫的下角標P和D改寫為小寫的p和d)。

第一種定義：沿著與軸平行的方向將曲面切成無數條曲線（紅色虛線），在每條紅色虛線上找到最大值（綠色圓點），即，然後在所有的中找到最小的那個（藍色圓點），即。

第二種定義：沿著與軸平行的方向將曲面切成無數條曲線（綠色虛線），在每條綠色虛線上找到最小值（紅色圓點），即，然後在所有的中找到最大的那個（藍色圓點），即。

從圖8的二維情況思考神秘的四維空間中的拉格朗日函數，就變成了，，如圖8(b)所示。其實四元函數就是一個定義在4維空間上的鞍形函數，這個從兩種思路共同得到的藍色點就是函數的鞍點，也就是我們要找的最優解。在這個二元化的圖中，拉格朗日對偶問題和拉格朗日原始問題的差別就是：原始問題採用第一種定義去求解鞍點，對偶問題採用第二種方法去求解鞍點。

至此，我們比較形象地描述了一個有約束條件下的函數優化問題的拉格朗日對偶問題求解過程以及相應的幾何解釋。

新人福利

關注 AI 研習社（okweiwu），回復1領取

【超過 1000G 神經網路 / AI / 大數據，教程，論文】

零基礎學SVM—Support Vector Machine系列之一

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！

請您繼續閱讀更多來自 AI研習社 的精彩文章: