Learn R | SVM of Data Mining（二）

01-24

在上一文中，我們闡述了支持向量機的基本思想，並從線性可分支持向量機開始學習。簡單回顧一下，當已知數據空間為 $n$ 維時，我們需要尋找一個 $n-1$ 維的超平面，並使這個超平面之間的間隔達到最大。出於這個目的，我們引入了函數間隔和幾何間隔的概念，並選擇幾何間隔最大的超平面定義為最大間隔分類器。

如此定義的最大間隔分類器，數學表達式為： $min~frac{1}{2}left | w ight |^2,s.t.y_i(w^Tx_i+b)geq 1,i=1,2,...,n$

要求解這個式子，我們可以通過求解對偶問題得到最優解，這就是線性可分支持向量機的對偶演算法，這樣做的優點在於：

一者對偶問題往往更容易求解；
二者可以自然的引入核函數，進而推廣到非線性分類問題。

接下來我們進行具體的推導求解。

一、拉格朗日乘數法

簡單回顧下拉格朗日乘數法，假設我們要求 $f(x)$ 的最小值，約束條件為 $h(x)=0$ ，即：

$min~f(x),s.t.h_i(x)=0,i=1,2,...,n$

那麼我們可以引入拉格朗日運算元 $alpha$ ，構造拉格朗日函數為： $F(x,alpha )=f(x)-sum_{i=1}^{n}{alpha h_i(x)}$

接著分別對 $x$ 和 $alpha$ 求偏導，使偏導數等於 $0$ ，然後解出 $x$ 和 $alpha$ 。

這就是拉格朗日乘數法的基本流程，但最大間隔分類器的約束條件是一個不等式，那麼我們應該如何處理這個問題呢？

實際上，我們仍可以通過拉格朗日函數將約束條件融合到目標函數里去。首先，構造拉格朗日函數： $F(w,b,alpha )=frac{1}{2}left | w ight |^2-sum_{i=1}^{n}{alpha _i}cdot left[ y_i(w^Tx_i+b)- 1 ight]$

接著，令 $C(w)=max_{alpha _i>0}F(w,b,alpha )$ ，所構建的這個函數意味著：

通過調整 $alpha$ 的大小，我們可以使 $F(w,b,alpha )$ 函數達到最大；
當約束條件不滿足時（例如 $y_i(w^Tx_i+b)<1$ ），一定可以調整 $alpha$ 使得 $C(w)$ 無限大（令 $alpha$ 等於正無窮即可）；
當約束條件滿足時，當 $F(w,b,alpha )$ 函數達到最大時，就有 $C(w)=frac{1}{2}left | w ight |^2$

因此，原命題就等價於： $min_{w,b}C(w)=min_{w,b}max_{alpha _i>0}F(w,b,alpha )=p^{ast }$

二、拉格朗日對偶

儘管我們將約束條件下的不等式轉化為一個求 $p^*$ 的問題，先求約束條件下的不等式最大值，在此基礎上求關於 $w$ 的最小值，但實際上這仍然是一個難以求解的問題。有沒有更好的辦法用於求解呢？如果我們能夠把順序調換一下，先求解關於 $w$ 的最小值，再解決約束條件下的最大值，即： $max_{alpha _i>0}min_{w,b}F(w,b,alpha )=d^{ast }$

$d^{ast }$ 就是 $p^{ast }$ 的對偶形式，但可惜的是，對偶歸對偶，兩者卻未必相等，在拉格朗日對偶性中，有以下定理：若原始問題和對偶問題都有最優值，那麼就有：

$d^{ast }=max_{alpha _i>0}min_{w,b}F(w,b,alpha ) leq min_{w,b}max_{alpha _i>0}F(w,b,alpha )=p^{ast }$

這就是該不等式的弱對偶性質（Week Duality）。直觀上其實也非常好理解：最大值中最小的一個，必然要大於等於最小值中最大的一個。

由於不等式的存在，我們就得到了一個對偶間隙，即 $p^*-d^*$ ，這樣我們的求解進一步明朗，只要我們找到能夠使該不等式恰好取到等號的條件，那麼對偶間隙也就自然而然的消失了，接下來我們學習一些相關定理，這些定理將幫助我們實現對偶間隙的消失。

三、Slater定理與KKT條件

1. Slater定理

在凸優化理論中，若凸優化問題存在嚴格可行解，即存在一個點 $x_i$ ，使得所有的等式約束條件都成立，並且所有的不等式約束條件都嚴格成立（取到嚴格不等號），數學表述為：

$f_i(x)<0,i=1,2,...,m;AX=b$

那麼，所對應的優化問題則具有強對偶性，此時就滿足 $p^*=d^*$ 。

Slater定理其實很好理解：存在一點 $x_i$ ，使得不等式約束中的「小於等於號」要嚴格取到「小於號」，這樣對偶間隙就會消失。

2. KKT條件

OK，假設現在Slater定理得到了滿足，實現了 $p^*=d^*$ ，但不能忽略的是， $p^*$ 和 $d^*$ 都有可能存在不止一個解，而我們需要確保 $p^*=d^*$ 的解為最優解，這樣接下來的求解才有實際意義。因此，進一步引入KKT條件的相關知識，它將幫助我們保證 $p^*=d^*$ 的解為最優解。

KKT條件是指在滿足一些有規則的條件下，一個非線性規劃(Nonlinear Programming)問題能有最優化解法的一個必要和充分條件。這是一個廣義化拉格朗日乘數的成果。

首先，一個最優化問題具有如下的基本形式：

$egin{eqnarray*}&&minf(x) \&&s.t.g_i(x)leq 0,i=1,2,...,p \&&h_i(x)=0,i=1,2,...,qend{eqnarray*}$ ， $g_i(x)$ 和 $h_i(x)$ 分別代表不等式約束和等式約束

一般地，一個最優化數學模型在滿足Slater定理的前提下，且 $F(w,b,alpha )$ 對 $w$ 和 $b$ 都可微時，所謂的Karush-Kuhn-Tucker最優化條件，就是指上式的最優點 $x_i$ 必須滿足下面的條件：

$frac{partial }{partial w_i} F(w,b,alpha )=0,i=1,2,...,n\frac{partial }{partial b_i}F(w,b,alpha )=0,i=1,2,...,m\alpha _ig_i(w_i)=0,i=1,2,...,k\g_i(w_i)leq 0,i=1,2,...,k\alpha _igeq 0,i=1,2,...,k$

為了突出重點，我們這裡不對KKT條件詳細展開探討，只需要知道KKT的內容對我們最優解的求解起著決定作用就可以了，有興趣者可自行查閱文末的相關參考文檔。

此時，若找到參數值 $w^*,b^*,alpha ^*$ 滿足了KKT條件的話，我們就使得 $p^*=d^*$ ，並且得到解為最優解。換句話來講，我們只需要拋開 $p^*$ ，專心求解 $d^*$ 就可以了。

四、對偶問題的具體求解

首先， $max_{alpha _i>0}min_{w,b}F(w,b,alpha )=d^{ast }$

固定參數 $alpha$ ，讓 $F(w,b,alpha )$ 分別關於 $w$ 和 $b$ 最小化（求偏導），得：

$egin{eqnarray*}&&frac{partial F}{partial w}=0Rightarrow w=sum_{i=1}^{n}alpha _iy_ix_i \&&frac{partial F}{partial b}=0Rightarrow sum_{i=1}^{n}alpha _iy_i=0 \end{eqnarray*}$

然後帶入到 $F(w,b,alpha )$ 中：

$egin{align}F(w,b,alpha )&=frac{1}{2}left | w ight |^2-sum_{i=1}^{n}{alpha _i}cdot left[ y_i(w^Tx_i+b)- 1 ight]\&=frac{1}{2} w^Tw-w^Tsum_{i=1}^{n}{alpha_iy_ix_i-bsum_{i=1}^{n}{alpha _iy_i}+sum_{i=1}^{n}{alpha _i} }\&=frac{1}{2} w^Tsum_{i=1}^{n}{alpha _iy_ix_i}-w^Tsum_{i=1}^{n}{alpha_iy_ix_i}+sum_{i=1}^{n}{alpha _i}\&=-frac{1}{2}( sum_{i=1}^{n}{alpha _iy_ix_i})^Tsum_{i=1}^{n}{alpha _iy_ix_i}+sum_{i=1}^{n}alpha_i\&=sum_{i=1}^{n}alpha_i- frac{1}{2}sum_{i=1}^{n}sum_{j=1}^{n}alpha _ialpha _jx_i^Tx_jy_iy_j end{align}$

從上面最後一個式子中，我們可以看到此時的 $F(w,b,alpha )$ 只包含一個變數 $alpha _i$ ，只要能求出最大化的 $alpha _i$ ，根據已知的 $alpha$ 與 $w,b$ 之間的關係，我們就可以很輕易的得到 $w$ 和 $b$ 的具體值。這樣，分類函數（即最大間隔分類器）也就輕而易舉的得到了。

對求 $alpha$ 的極大值，數學語言表述為：

$egin{eqnarray*}&&max_{alpha}(sum_{i=1}^{n}alpha_i- frac{1}{2}sum_{i=1}^{n}sum_{j=1}^{n}alpha _ialpha _jx_i^Tx_jy_iy_j) \&&s.t.sum_{i=1}^{n}{alpha _iy_i=0},alpha _igeq 0,i=1,2,...,nend{eqnarray*}$

那麼接下來該如何求解呢？在後面的學習中，我們將接觸到SMO高效優化演算法，它將幫助我們求解對偶問題中的這個拉格朗日乘子 $alpha$ 。

未完待續

References：

統計學習方法 (豆瓣)
機器學習 (豆瓣)
支持向量機 - Wikipedia
支持向量機 | 數據挖掘十大演算法詳解
支持向量機: Support Vector
支持向量機通俗導論 - 結構之法演算法之道 - CSDN.NET
統計學習精要(The Elements of Statistical Learning)課堂筆記（二十）：SVM
KKT條件介紹 - johnnyconstantine - CSDN.NET
最優化理論與KKT條件 | 刻骨銘心