這是關於SVM的第二篇文章，主要解決有約束條件下的優化問題。

關於SVM基本型等基礎講解可參看第一部分，鏈接如下：

木小易：Support Vector Machines(SVMs-P1)?

zhuanlan.zhihu.com圖標

目前已知SVM基本型的表達式為：

Min ||oldsymbol{w}|| s.t. oldsymbol{y}_{mathbf{i}}（oldsymbol{w}^{mathrm{T}} oldsymbol{x}{mathbf{i}}+b） geq 1

我們不妨先來討論一下約束條件，它分為等式約束和不等式約束，標準的拉格朗日乘子法其實只能解決等式約束的問題，那麼我們先來通過等式約束認識一下拉式乘子法的強大作用，之後再進一步解決不等式約束的問題。

1.等式約束

先給出等式約束的基本形式： underset{oldsymbol{x}}{operatorname{minimize}} f(x) s.t. oldsymbol{h}_{mathbf{i}}(x)= C (i=1,2,...,k)

underset{oldsymbol{x}}{operatorname{minimize}} f(x) 指尋找可以使 f(x) 最小的 oldsymbol{x} 的值，值得注意的是 oldsymbol{x} 在這裡是矢量，即可以表示多個自變數。

我們觀察到上式有 k 個等式約束，為了簡便，我們假設只有一個等式約束，即 oldsymbol{h}(x)= C

下面我們引入拉格朗日乘子法，

「基本的拉格朗日乘子法就是求函數f(x1,x2,...)在約束條件g(x1,x2,...)=0下的極值的方法。其主要思想是將約束條件函數與原函數聯立，從而求出使原函數取得極值的各個變數的解。」（百度百科）

根據百度百科的定義，不難看出拉格朗日乘子法是通過將約束條件函數與原函數結合起來構造出一個函數，從而整體上來求解優化問題。

那麼等式約束的函數與需要優化的函數之間存在怎樣的關係呢？在滿足約束函數的約束下，原函數何時才能取得最小值呢？答案是兩個函數的梯度平行的時候，原函數可以取得最大或者最小值，這就是拉格朗日發現的奧秘。

如何理解拉格朗日給出的答案呢？

限於篇幅原因，不再提供對梯度進行詳細講解。

以下只給出梯度的3點重要性質：

1.梯度是矢量，每個元素是函數在某點對某個自變數的偏導數值

2.梯度方向指向函數增長最快的方向

3.梯度垂直於函數等高線

那麼為何函數的梯度平行時原函數取到極值點呢？

我們不妨舉個例子直觀的理解這個問題，請參看下圖：

圖中黑色的兩個圓為原函數在二維平面上的等高線的一部分（實際上有無數個同心圓），藍色的曲線為等式約束函數的等高線，我們總能找到兩個函數的相切點O，此時O點就是拉格朗日認為的極值點。原因在於，梯度方向指向函數增長最快的方向，假設向量 oldsymbol{u} 為原函數在O點的梯度，由小圓指向大圓，那麼我們知道在該圖中，半徑小的圓上函數的值一定比大圓上的函數值小，如果取約束函數與原函數等高線另外兩個交點，原函數的取值一定要大於兩函數相切時的點對應的原函數的值。

下面我們用數學形式來描述這一條件，即： abla f(oldsymbol{x})=alpha abla (h(oldsymbol{x})-C)

結合上述的等式約束函數，我們可以寫出一個綜合了兩個條件的複合型函數：

L(x, alpha)=f(mathbf{x})- alpha (h(x)-C)

寫到這裡，可能還是看不出為什麼 L(x, alpha) 包含了上述兩個條件，我們令 abla L(x, alpha)=0

則 egin{cases} abla_x L(x, alpha)=0\ abla_alpha L(x, alpha)=0end{cases}

解得 abla f(oldsymbol{x})=alpha abla (h(oldsymbol{x})-C) 和 oldsymbol{h}(x)= C

我們發現 abla L(x, alpha)=0 是和上述兩個條件等價的，因此可以通過求解 abla L(x, alpha)=0 來解決等式約束下原函數取得最優解的問題。

2.不等式約束

先來寫出不等式約束的基本形式： underset{oldsymbol{x}}{operatorname{minimize}} f(x) s.t. egin{cases}oldsymbol{h}{mathbf{i}}(x)= 0 (i=1,2,...,k)\ oldsymbol{g}{mathbf{i}} (x)leq 0(i=1,2,...,k)end{cases}

我們觀察到上式有 k+k 個等式約束，為了簡便，我們假設只有一個不等式約束，即 oldsymbol{g}(x)leq 0

我們此時仍然想引入拉格朗日乘子法： L(x, alpha)=f(mathbf{x})- alpha g(x) 但顯然此時再令 abla L(x, alpha)=0 求出的條件已經不滿足不等式約束，因此我們要對拉格朗日乘子法進行一些條件限定，使得通過某種限定後我們依然可以在不等式約束的情況下繼續使用拉式乘子法。

(1) abla_x L(x, alpha)=0 的改寫

首先，由 abla_x L(x, alpha)=0 可得出： abla f(oldsymbol{x})=alpha abla g(oldsymbol{x}) s.t. alpha leq 0

在不等式約束中，乘子 alpha 相對於等式約束的情況多了一個約束條件。

下面我們來具體解釋為什麼這裡必須加上 alpha leq 0 的約束條件。

不難發現， oldsymbol{g}（x)leq 0 代表著一個區域，相對於等式約束中藍色的曲線而言，現在的 oldsymbol{g}（x)leq 0 可以理解為下圖中藍色曲線加黃色的區域。

如圖，可以看到原函數取得極值的點位於 oldsymbol{g}(x)leq 0 內，這意味 oldsymbol{g}(x)leq 0 著這一約束條件不起作用，此時 abla f(oldsymbol{x})=0 ，而 abla f(oldsymbol{x})=alpha abla g(oldsymbol{x}) ，所以此時 alpha 必須為0才能使上式成立。

接下來，讀者可能已經發現，還存在一種情況，即下圖：

此時， abla f(oldsymbol{x})=alpha abla g(oldsymbol{x}) ,而我們注意到O點處 abla g(oldsymbol{x}) 的方向一定是指向曲線包裹區域外的，因為我們知道曲線區域內 oldsymbol{g}(x)leq 0 ，可知區域外方向為 g(oldsymbol{x}) 增大的方向，而 abla f(oldsymbol{x}) 一定是指向區域內的，因為如果指向區域外，說明我們可以在 oldsymbol{g}(x)leq 0 的區域內找到一個點，在該點處可以讓原函數取得更小的值,這就又回到了第一種情況。

因此， abla f(oldsymbol{x})=alpha abla g(oldsymbol{x}) 中， abla f(oldsymbol{x}) 與 abla g(oldsymbol{x}) 方向必然相反，再結合上一種情況，可得， alpha leq 0

(2)由 abla_alpha L(x, alpha)=0 不滿足約束條件引發的改寫

那麼接下來，令 abla_alpha L(x, alpha)=0 ，得 g(x)= 0 ,這顯然不對。因此我們不得不換一種方式來理解 abla_alpha L(x, alpha)=0 ，在等式約束中是為了表示 g(x)= 0 這個等式約束，那麼在不等式約束中，我們應該如何表示呢？

我們先來改寫一下等式約束的形式，即改寫 L(x, alpha)=f(mathbf{x})- alpha g(x)

改寫為： underset{oldsymbol{x}}{operatorname{min}}underset{oldsymbol{alpha}}{operatorname{max}} L(x,alpha)

這裡讀者或許會存在疑惑，因此我們首先證明改寫前後的兩個形式是否等價。

此時， oldsymbol{g}(x)= 0 ，故 underset{oldsymbol{x}}{operatorname{min}}underset{oldsymbol{alpha}}{operatorname{max}} L(x,alpha)=underset{oldsymbol{x}}{operatorname{min}} f(x)

那麼當不等式約束的情況下，即 oldsymbol{g}(x)leq 0

若 oldsymbol{g}(x)<0 ,則 alpha=0 時，有 underset{oldsymbol{alpha}}{operatorname{max}} L(x,alpha)=0 ， underset{oldsymbol{x}}{operatorname{min}}underset{oldsymbol{alpha}}{operatorname{max}} L(x,alpha)=underset{oldsymbol{x}}{operatorname{min}} f(x)

oldsymbol{g}(x)= 0 ，則 alpha< 0 時， underset{oldsymbol{alpha}}{operatorname{max}} L(x,alpha)=0 ， underset{oldsymbol{x}}{operatorname{min}}underset{oldsymbol{alpha}}{operatorname{max}} L(x,alpha)=underset{oldsymbol{x}}{operatorname{min}} f(x)

oldsymbol{g}(x)> 0 ，則 alpha 取負無窮時， underset{oldsymbol{alpha}}{operatorname{max}} L(x,alpha) 趨向於正無窮， underset{oldsymbol{x}}{operatorname{min}}underset{oldsymbol{alpha}}{operatorname{max}} L(x,alpha) 無解。

此時，也可以得出 oldsymbol{g}(x)leq 0 時， alphaleq0

(3)小結

由上述的討論，我們總結出在不等式約束的情況下，要想使用 L(x, alpha)=f(mathbf{x})- alpha g(x) 的形式來求解，必須滿足一下條件，即 egin{cases}oldsymbol{g}(x)leq 0\ alphaleq0\ abla_x L(x, alpha)=0\ alpha g(x)=0end{cases} ，這組條件我們稱之為KKT條件。

[1]svm-tutorial.com/

[2]周志華. 機器學習. 清華大學出版社. 2016


推薦閱讀：
相关文章