機器學習筆記（三）支持向量機原型、對偶問題

05-11

零、摘要

本篇文章講述支持向量機的原型與他的拉格朗日對偶問題。

主要參考資料：

斯坦福大學 CS229 筆記吳恩達
《機器學習》周志華
《機器學習實戰》peter Harrington
《高等數學》同濟大學
《微積分學教程》【俄】菲赫金格爾茨
維基百科支持向量機

一、原型

支持向量機（support vector machine）處理的是分類問題。首先，我們考慮這樣一個問題，二維平面上有兩個點集，要畫一條一維直線把他們分開。

如圖，A是給定的點集，B，C，D分別嘗試用一條直線分開。直觀來看，D中的直線比B，C中的要更合理一些。支持向量機演算法就是要求得這一最為合理的直線。點集中距離這條直線最近的那些點被稱作支持向量

這裡，我們的輸入屬性值共有兩種（二維點集），我們可以將分割的概念推廣到高維空間中去。已知二維的點集可以用一維的直線分開（假定點集是線性可分的），那麼在同樣的假定下，三維空間中的點集可以用二維的平面分開，n維空間中的點集可以用n-1維的「平面」分開。由於人類無法直觀感受到三維以上的空間，我么這些情形，統一把這「平面」稱作超平面。

在n維空間中，要描述這樣一個超平面，我們可以寫： $w^T x + b=0$ ,其中法向量 $w=(w_1;w_2;.......:w_n)$ 。我們對於一個樣本點x，當 $w^T x + b>0$ 時，就預測他為正類， $w^T x + b<0$ 時，就預測他為反類（這裡只討論二元分類）。同時，我們有m個訓練樣本，對應於上圖中的m個點。m個點中第i個點有屬性 $y_i$ ，即該點是方塊還是圓圈。

有了這些符號的定義，我們可以寫出支持向量機的原型/基本型： $min _w,_b 1/2||w||^2 \s.t. y_i(w^T x_i+b) ge 1，i=1,2,...,m$

即在對於每一個樣本點滿足條件 $y(w^T x+b)ge 1$ 的情況下，通過最小化 $1/2||w||^2$ 來求得參數w,b。下面我們將從零開始推導這兩行的問題原型。

首先，我們考慮什麼樣的超平面分割效果最好？

我們看到，D中直線和兩個類別的點集的輪廓接近平行，換句話說，它離各個屬性點集的最小距離最大。推廣到高維空間就是最佳超平面與各個屬性點集的最小距離最大。這樣的超平面產生的分類結果是最為魯棒的，對未見樣本的泛化性能更強。那麼現在，事情就轉化成了，先求處最小距離表達式，再求這式取最大值時w,b的值。

我們先求任意點到超平面距離的表達式。

我們有這張示意圖，即在二維空間中的情形（我么可以毫不費力地將下面的結果推廣到高維空間）。注意兩坐標軸都標為x，這是因為豎軸也是用來表示樣本點坐標，而在這個問題中我們用y來表示樣本點的屬性（上圖中就有y=紅色或y=綠色）。

同樣在上圖中，我們用A來標記某一個（任意一個）樣本點 $x_i$ ，而B點是通過A點向超平面作垂線與超平面的交點。我們還有超平面的法向量w，因此，w/||w||就是法向量方向上的單位向量。我們令， $|AB| = gamma ^i$ ，可以得到B點坐標為 $x_i - gamma^i w/||w||$ ，同時，點B在超平面上，滿足超平面方程 $w^T x + b=0$ ，將點B坐標帶入超平面方程，移項，解得 $|AB|=gamma^i= |w^T x_i + b|/||w||$ 。

但存在一個問題，對於上圖中的A我們得到的距離是正值，然而對於綠色的點，距離就變成了負值。回想我們的目的是要對這些距離的值進行計算，這符號相異的情形令人十分煩躁。於是我們將兩個屬性的點的y值分別標記為1和-1，然後在進行距離計算之後，所得距離乘以這個y值，即 $gamma^i= yi |w^T xi + b|/||w||$ 。這時，我們就有了任意樣本點與超平面幾何距離的一般表達式。

回想我們是想要最小距離最大化，那麼現在我們可以直接寫: $\arg max _w,_b {min_n gamma^i} = arg max_w,_b {min_n y_i |w^T x_i + b|/||w||}$ 或者，等價地： $max_gamma,_w,_b (gamma) \s.t. y_i(|w^T x_i + b|/||w||) ge gamma，i=1,2,...,m$ 即在確定gamma是最小值的情況下（第二行），求他的最大值。我們看到，這時我們得到的就與原型至少在結構上很接近了： $min_w,_b 1/2||w||^2\s.t. y_i(w^T x_i+b)ge1，i=1,2,...,m$

但是直接求解我們得到的問題相當困難（非凸優化），我們需要對這個問題進行最後的等價轉換，使他稱為相對更容易求解的原型。

回想，對於一個樣本點x，當 $min_w,_b 1/2||w||^2\s.t. y_i(w^T x_i+b)ge1，i=1,2,...,m$ $w^T x + b>0$ 時，就預測他為+1， $w^T x + b<0$ 時，就預測他為-1(躍遷函數)。那麼當w和b同時乘以一個大於零的乘數因子時，預測結果不會改變。所以說我們有自由縮放w，b的權利，因此我們不妨限制整個樣本集中與超平面距離最小的距離為 $gamma=1$ 。我們由此得到： $max_gamma,_w,_b (gamma) \s.t. y_i(w^T x_i + b) ge 1，i=1,2,...,m$

第二行已經於原型完全相同，我們再來關注第一行。回想我們對 $gamma$ 的定義 $gamma= y |w^T xi + b|/||w||$ ，最大化 $gamma$ 等價於最小化||w||等價於最小化 $||w||^2$ 。為了求導方便，我們增加1/2的乘積因子。所以我們最終得到了支持向量機的原型：

第二行求出所有距離中的最小值，第一行求他的最大值，我們想獲得取最大值時參數w和b的值。

二、條件極值與拉格朗日對偶問題

1.二元函數的情形

我們發現，我們剛剛得到的支持向量機的原型問題是一個凸二次規劃問題，能直接用現成的優化計算包來求解，但我們可以導出更加高效的方法。即將原型轉化為拉格朗日對偶問題求解。

我們看到，我們的原型屬於一個條件極值問題，即在 $y_i(w^T x_i+b)ge1$ 的條件下，求 $1/2||w||^2$ 的極值，現在我們來研究這種問題的解決方法。

我們考慮這樣一個問題：尋求函數 $z=f(x1,x2) (1.1)$ 在滿足條件 $phi(x1,x2) (1.2)$ 時的極值點。

首先，假設函數(1.1)在(x1^0,x2^0)取得極值，那麼顯然這點需要滿足條件(1.2)，即有 $\phi(x1^0,x2^0)=0 (1.3)$

接下來，為了使用隱函數存在定理，我們做如下假定：

在 $(x_1^0,x_2^0)$ 的某一鄰域內 $f(x_1,x_2)、phi(x_1,x_2)$ 都有連續的一階偏導數
$phi{x_2}(x_1^0,x_2^0)$ 即該函數關於x_2的偏導數不為零

則由隱函數存在定理：

設函數 $phi (x_1,x_2)$ 在點 $(x_1^0,x_2^0)$ 的某一鄰域內具有連續的偏導數，
且 $phi (x1^0,x2^0)=0，phi {x2}(x1^0,x2^0) eq 0，$
則方程 $phi (x_1,x_2)=0$ 在點 $(x_1^0,x_2^0)$ 的某一鄰域內恆能唯一確定一個連續且具有連續導數的函數 $x_2=g(x_1)$ ，它滿足條件 $x_2^0 = g(x_1^0)$ ，
並有 $d x_2/d x_1 = -phi {x_1}/phi {x_2}$ 。

可知，方程(1.2)確定了一個連續且具有連續導數的函數 $x_2=g(x_1)$ （注意，我們只利用了隱函數的存在性，而並不強求他能被顯化），把它帶入(1.1)式，結果得到了一個只關於 $x_1$ 的函數 $\z=f(x_1, g(x_1)) (1.4)$

於是所求極值轉化為了(1.4)在 $x_1=x_1^0$ 時的值（因為我們之前曾假定函數(1)在 $(x_1^0,x_2^0)$ 取得極值）。這一元函數取得極值的條件便是關於自變數的導數為零，即當 $x_1 = x_1^0$ 時，有： $\dz/d x_1 = f{x_1}(x_1^0,x_2^0)+f{x_2}(x_1^0,x_2^0)d x_2/d x_1 = 0$ 注意其中使用了複合函數求導的鏈式法則。

由之前隱函數存在性定理中提到的求導公式，可以知道當 $x_1 = x_1^0$ 時， $d x_2/d x_1 = -phi {x_1}/phi {x_2}$ ，代入上式，得到 $\f{x_1}(x_1^0,x_2^0)-f{x_2}(x_1^0,x_2^0)phi {x_1}/phi {x_2} = 0$

於是，這式與之前的(1.3)式 $phi(x_1^0,x_2^0)=0$ 就是所求極值的條件。

其實到此為止我們已經完成目的了，但為了方便記憶，我們設 $f{x_2}(x_1^0,x_2^0)/phi {x_2}(x_1^0,x_2^0)=-lambda$ ，則上述條件可以等價地改寫為

· $f_{x_1}(x_1^0,x_2^0) + lambda phi _{x_1}(x_1^0,x_2^0)=0$

· $f_{x_2}(x_1^0,x_2^0) + lambda phi _{x_2}(x_1^0,x_2^0)=0$

· $phi(x_1^0,x_2^0)=0$

引進輔助函數 $L(x_1,x_2)=f(x_1,x_2) +lambda phi(x_1,x_2)$ ，則對這函數分別關於 $x_1，x_2$ 求偏導數，就得到了上面第一、二個式子。

在這個輔助函數裡面， $L(x_1,x_2)$ 被稱作拉格朗日函數， $lambda$ 被稱作拉格朗日乘子，這一方法也被稱作拉格朗日乘數法。

2.多元函數的情形

我們只討論了二元函數的條件極值，但回想我們要轉化的原型： $\min_w,_b 1/2||w||^2\s.t. y_i(w^T x_i+b)ge1，i=1,2,...,m$ 這裡要求的極值是關於w的函數，而回想關於超平面的定義： $w^T x + b=0$ ，其中法向量 $w=(w_1;w_2;.......:w_n)$ 是n維的，我們還需要研究當n大於二時如何導出拉格朗日乘數法。

為了推廣拉格朗日乘數法，我們考慮這樣一個問題：求n+m個變元的函數 $\z=f(x_1,x_2,x3...,x{n+m}) (2.1)$ 假定這些變元滿足m個條件： $\phi_i(x_1,x_2,x3...,x_{x+m})=0 (i=1,2,...,m) (2.2)$ 時的極值點。

首先，假設函數(2.1)在 $(x_1^0,x_2^0,.....,x_{n+m}^0)$ 取得極值，那麼顯然這點需要滿足條件(2.2)，即有 $\phi_i(x_1^0,x_2^0....,x_{n+m}^0)=0 (2.3)$

接下來，類似於為了使用隱函數存在定理，我們做如下假定：

· 函數 f 即 $phi_i$ 在點 $(x_1^0,x_2^0,.....,x_{n+m}^0)$ 的某一鄰域內存在關於所有變元的連續偏導數

· 從偏導數組成的雅可比矩陣內取出的m階行列式中至少有一個在點 $(x_1^0,x_2^0,.....,x_{n+m}^0)$ 處不為零

則由定理：

假定：
1)一切函數F1,F2,...Fm在以點 $(x_1^0, x_2^0...x_n^0,y_1^0,y_2^0,...y_m^0)$ 為中心的某鄰域內有定義且連續
2)在定義域中這些函數關於一切變元的偏導數存在且連續
3)點 $(x_1^0, x_2^0...x_n^0,y_1^0,y_2^0,...y_m^0)$ 滿足方程組 $F_i(x_1^0, x_2^0...x_n^0,y_1^0,y_2^0,...y_m^0)=0 i=1,2...,m$
4)雅可比式在此處異於零
則：
1)在點 $(x_1^0, x_2^0...x_n^0,y_1^0,y_2^0,...y_m^0)$ 的某鄰域內確定 $y_1,y_2,...y_m$ 為 $x_1,x_2...,x_n$ 的單值函數

2)當 $x_1=x_1^0, ...x_n=x_n^0$ 時，這些函數的函數值為 $y_1=y_1^0,....y_m = y_m^0$ 這些函數連續且有關於一切變元的偏導數

可知，（2.2）中 $x_{n+1},x_{n+2},.....,x_{n+m}$ 就可以寫成關於 $x_1,x_2,....x_n$ 的函數了，即 $\x_{n+i}=g_i(x_1,x_2,...x_n) i=1,2,.......,m (2.5)$ （注意，我們只利用了這些函數的存在性，而並不強求他能被顯化），把它帶入(2.1)式，結果得到了一個只關於 $x_1,x_2,...,x_n$ 的函數 $\z=f(x_1, x_2,....x_n,g_1(x_1,x_2,...,x_n),g_2(x_1,x_2,...x_n),....g_m(x_1,x_2,...,x_n)) (2.4)$ 於是這就轉化為了普通極值（而非條件極值）的問題了。

注意到我們得到的函數（2.4）中後面的變數與前面的變數有關，並不是所有變數都能自由地變動的，所以並不能用一般的方法來求他的極值。於是我們還要進行如下一波騷操作：

不要忘記，我們之前已經有過假設：函數(2.1)在 $(x_1^0,x2^0,.....,x_{n+m}^0)$ 取得極值。

那麼，在該點的全微分： $\d f(x_1^0,x_2^0,.....,x_{n+m}^0)=f{x_1} d x_1+f{x_2} dx_2+...+f{x_{n+m}} d x_{n+m}=0$

先了解一下下面這個定理：

如果其中各個微分 $dx_1,dx_2,...,dx_{n+m}$ 是任意的，則各個偏導數 $f{x_1}，f{x_2} ,.....,f{x_{n+m}}$ 都等於零。

又由一階微分形式的不變性，這條件可以寫成 $\sum （partial f/partial x_j） d x_j=0 j=1,2,...n+m (2.6)$ 其中 $d x_{n+1},...d x_{n+m}$ 要理解為（2.5）的微分。

但是我們不能斷定各個偏導數 $f{x_1}，f{x_2} ,.....,f{x_{n+m}}$ 都等於零。因為各個微分 $dx_1,dx_2,...,dx_{n+m}$ 不是任意的（回想剛才了解的定理和之前說過的：並不是所有變數都能自由地變動的）。

這樣的情形同樣令人十分煩躁。所以我們要試圖使問題只涉及可以任意選取的微分，即前n個微分。

回想我們有m個條件方程（2.2） $\phi_i(x_1,x_2,x_3...,x_{x+m})=0 (i=1,2,...,m)$ ：顯然這些恆等於零的函數的全微分也恆等於零。我們取這m個方程的全微分，並令他們為零： $\sum （partial phi_i/partial x_j） d x_j=0 （i=1,2,....m；j=1,2,...n+m） (2.7)$

回想很久之前我們做過這樣一個假定：從偏導數組成的雅可比矩陣內取出的m階行列式中至少有一個在點 $(x_1^0,x_2^0,.....,x_{n+m}^0)$ 處不為零。因此，從（2.7）中我們可以將 $d x_{n+1},...d x_{n+m}$ 用 $dx_1,dx_2,...,dx_n$ 表達。把這些表達式代入(2.6)： $\sum （partial f/partial x_j） d x_j=0 j=1,2,...n+m$ 得到了等式形如： $\A_1 d x_1+...+A_n d x_n = 0$ 我們知道這裡的n個微分是任意的，回想之前了解的但不能使用的那個定理，他在這時終於啟用處了。我們得到： $A_i = 0 i=1,2,...n$ 這n個方程加上m個條件方程一共有n+m個方程，可以解出n+m個未知量。 $x_1,x_2,x_3...,x_{n+m}$ 。

但非常容易能夠知道，上述方法會導致非常非常複雜的計算。偉大的拉格朗日提出了解決方法：把（2.7）中的各個等式 $\sum （partial phi_i/partial x_j） d x_j=0 （i=1,2,....m；j=1,2,...n+m）$ 依次乘以（不定的）乘數 $lambda_i (i=1,2,...,m)$ ，然後將所得結果與（2.6） $\sum （partial f/partial x_j） d x_j=0 (j=1,2,...n+m)$ 相加。得到等式： $\sum (partial f/partial x_j +sumlambda_ipartial phi_i/partial x_j ) d x_j=0 (i=1,2,...m；j=1,2,....,n+m) (2.8)$

回想我們之前使用過的那個假定：從偏導數組成的雅可比矩陣內取出的m階行列式中至少有一個在點 $(x_1^0,x_2^0,.....,x_{n+m}^0)$ 處不為零。

這假定使得下面的操作成為可能：

這樣選取乘數 $lambda_i (i=1,2,...m)$ 的值，使得（2.8）中微分 $d x_{n+1},...d x_{n+m}$ 前得係數剛好等於零： $\partial f/partial x_j +sumlambda_ipartial phi_i/partial x_j =0 (j=n+1, n+2,....,n+m) (2.9)$

這樣確定了乘數 $lambda _i (i=1,2,...m)$ 的值之後，之前的等式（2.8）就成為了 $\sum (partial f/partial x_j +sumlambda_i(partial phi_i/partial x_j ) d x_j=0 (i=1,2,...m；j=n+1,....,n+m)$

我們愉快地發現，這裡面只剩下前n個任意變換得微分了，這樣，他們之前得係數應都為零。這是因為之前的定理：

如果其中各個微分 $dx_1,dx_2,...,dx_{n+m}$ 是任意的，則各個偏導數 $f{x_1}，f{x_2} ,.....,f{x_{n+m}}$ 都等於零。

於是我們有了： $\sum (partial f/partial x_j +sumlambda_i(partial phi_i/partial x_j ) d x_j=0 (i=1,2,...m；j=1,2,....,n)$ 加上之前的，我們有了： $\sum (partial f/partial x_j +sumlambda_i(partial phi_i/partial x_j ) d x_j=0 (i=1,2,...m；j=1,2,....,n+m)$ （關注 j 的取值）

其實到此為止我們已經完成目的了，但為了方便記憶，與二元函數的情形類似地，我們引入輔助函數 $F=f+lambda_1 phi _1+...+lambda_m phi_m$ ，這樣，上面的方程就可以寫成 $\partial F/ partial x_j = 0 (j=1,2,...,n+m)$ 至此，我們終於完成了拉格朗日乘數法由二元向多元的推廣。

重述一遍多元函數的拉格朗日乘數法：

求n+m個變元的函數 $z=f(x_1,x_2,x_3...,x_{n+m})$ 假定這些變元滿足m個條件： $phi_i(x_1,x_2,x_3...,x_{n+m})=0 (i=1,2,...,m)$ 時的極值點。

我們的做法是：

引入拉格朗日函數 $F=f+lambda_1 phi _1+...+lambda_mphi_m$ 並令 $\partial F/ partial x_j = 0 (j=1,2,...,n+m)$ 從而解出所有的自變數 $x_1,x_2,...x_{n+m}$

3.廣義拉格朗日

再來回想我們的支持向量機原型： $\min_w,_b 1/2||w||^2\ s.t. y_i(w^T x_i+b)ge1，i=1,2,...,m$

注意到，這裡的條件是不等式。為了能將拉格朗日乘數法應用到這個問題上，我們需要再對它進行推廣。接下來，我們不再使用 $x_1,x_2,x_3...,x_{n+m}$ 做為自變數，轉而使用 $w=(w_1;w_2;.......;w_n)$ 。

我們把要討論的主問題記為： $min_w f(w)\ s.t. g_i(w)le 0，i=1,2,...,k \ h_i(w)=0， i=1,2,...l$ 即我們要最小化關於w的函數f（w），約束條件包括關於w的k個不等式和l個等式。

我們定義廣義拉格朗日函數： $L(w, a, b)=f(w)+sum a_i g_i(w)+sum b_i h_i(w)$ 其中各個a,b都是拉格朗日乘數。我們要求這一函數在 $a_i ge 0$ 時的最大值 $heta p(w)=max_{a_i>0}L(w, a, b)$ 其中腳標p代表主問題（primal）。

我們來思考為什麼這個取最大值的操作有意義呢？我們的限制條件是 $g_i(w)le 0$ ，假如有某一個 $g_i(w)ge 0$ ，我們又是要將整個函數最大化，這就迫使乘數 $a_i ge 0$ 越大越好，於是整個函數就趨向於無窮。反而如果所有條件都滿足 $g_i(w)le 0$ ，那麼無論乘數多大，這一項 $a_i g_i(w)$ 都不會出現在拉格朗日函數之中（對於 $h_i(w) eq 0$ 也是同樣的道理）。也就是說， $heta _p$ 有這樣的性質：

如果違背了任一條件，則它趨向於正無窮；如果所有條件都滿足，則它的值等於L(w,a,b)。

我們不希望違背條件，所以我們不希望 $heta p$ 趨向於正無窮，所以我們希望 $heta_p$ 趨向於零，所以我們希望最小化 $heta _p$ 。

設p為主問題的解，即 $p=min_w heta _p (w)=min_w max_{a_i>0}L(w, a, b)$

高潮來了，定義對偶問題： $heta_d=min_w L(w,a,b)$ ，其中 d 代表著「對偶」（dual）我們設d為對偶問題的解，下面這個式子： $d=max_{a_i>0} min_w L(w,a,b) le min_w max_{a_i>0}L(w, a, b) = p*$

當滿足KKT條件時等號成立。

我們一會再來說這莫名其妙的KKT條件。先觀察上面的式子，即一個函數最小值中的最大值le最大值中的最小值。

我們再列出KKT（Karush-Kuhn-Tucker）條件：

· $partial L/partial w_i = 0，i=1,2,...n$

· $a_i g_i(w) = 0，i=1,2,...k$

· $g_i(w)le 0，i=1,2,...,k$

· $a_ige 0，i=1,2,...k$

好的，再次回憶我們的原型（簡單地移項）： $min_w,_b 1/2||w||^2\ s.t. 1-y_i(w^T x_i+b)le0，i=1,2,...,m$

將 $1-y_i(w^Tx_i+b)$ 看作 $g_i(w)$ ，我們就有拉格朗日函數 $L(w,a,b)=1/2||w||^2+sum a_i(1-y_i(w^T x_i+b)) i=1,2,...m$

要注意，這裡L（w,a,b）中的b和之前的b是不同的概念。

我們令L（w,a,b）對w和b的偏導數為零得到

$w=sum a_i y_i x_i$ 和 $0=sum a_i y_i$

綜合上面幾個式子，我們終於得到關於支持向量機原型的對偶問題： $max_a sum a_i - 1/2 sum sum a_i a_j x_i^T x_j y_i y_j \ s.t. sum a_i y_i=0\ a_i le 0, \i=1,2,...m；j=1,2,..m$

在滿足KKT條件

· $a_ile 0$

· $1-y_i(w^T x_i+b) ge 0$

· $a_i(1-y_i(w^T x_i+b)) = 0$

的情形下，我們從上式中解出a，然後就能求出w和b，這樣就得到了所求的超平面 $w^T x + b$ 。

但是，同樣地，這是一個二次規劃問題，問題的規模正比於訓練樣本數。於是，人們提出了很多高效演算法，包括著名的SMO演算法。

三、總結與討論

本文花費了大量的篇幅講述支持向量機的原型與其拉格朗日對偶問題的推導過程。雖然說，明白了演算法的推導過程並不意味著能夠使用好，但是，如果只知道結論而對於結論的來歷完全不懂的話，不僅會在接下來的拓展學習中遭遇天花板，更會減少創新的能力。希望有科研志向的讀者能夠對於每一個演算法都不拘泥於僅僅學會使用。

本文關於拉格朗日對偶問題的推導，二元部分來自高等數學，多元推廣來自俄羅斯數學分析的教材。為了便於理解，我儘力將這些部分寫得儘可能的友善。但是由於這狗血問題本身的複雜性，我也是在反覆閱讀之後才明白作者的確切意思（當然現在我才大一，數學功底有限），如果讀者沒能在讀完第一遍的時候完全明白，也千萬不要灰心：)

至此本文更是超過一萬一千字，但也僅僅介紹了支持向量機演算法最基礎部分的一部分。在下一篇文章里，我們將繼續討論基於拉格朗日對偶問題的SMO演算法，核函數與核技巧等內容。

機器學習筆記（三） 支持向量機 原型、對偶問題