SVM 和最優化

1 前言

講解支援向量機(SVM)的文章數不勝數，不過大多缺乏中間很多推導細節。

相比其他經典機器學習算法，SVM裡面有更多的數學推導，用到拉格朗日乘子法，KKT條件，線性和非線性的核函數，這些都對非數學專業的入門者造成一定門檻。

不過挑戰意味着機遇，完全打通這些知識，可能會助你提升一個台階，盡管當下SVM用的可能沒有之前火爆，但SVM作為在深度學習模型之前應用最廣泛的模型之一，仍然有必要研究推導，尤其是如果想繼續深造，讀博、做科研的。

這篇文章是我之前寫的SVM數學推導部分，用的方法比較直白，自信這個推導方法大家都能看明白。

SVM 直接從目标函數和限制部分開始。

2 拉格朗日乘子法

SVM經過拉格朗日乘子法，引入了 m 個系數，目标函數的形式如下：

變量含義和相關假設如下：

• 設 w 向量次元是 m,

  

• a 的次元是 m (特征個數)，
• 樣本(X,Y)的第一次元代表樣本個數，設為n; 第二次元是特征次元m，如第 i 個樣本的向量表示為：

  

• b是标量

是以，下式可以化簡為：

為了更好地了解，先對w向量的第一個分量w1求偏導，和w1無關的分量全部消除，式子立即化簡為如下：

這些隻涉及到最簡單的求導公式，求出偏導：

這樣對w1的求導完畢，然後對整個的 w 向量求導：

已經求得L對w1的偏導，w1,w2,…,wn的地位是相同的，是以依次帶入即可，上式可以化簡為如下：

下面再利用一些基本的線性代數中行列式的一些知識，就可以轉化為向量的表達，具體操作如下：

回到文章開始對w向量和xi向量的定義，得到如下向量表達：

是以，對w向量的偏導求解完畢，結果如下：

下面再對b求導，b是标量，直接一步可以得到結果：

根據拉格朗日乘子法的理論，令L對w偏導等于0，得到關系式：

同理，令L對b偏導等于0，得到關系式：

3 化簡L

接下來，将得到2個關系式代入到L中，化簡L.

為了更好了解，仍然采用更直覺地表達方式，将向量完全展開，

将上面關系式代入到L之前，我們先展開這個式子，

仍然還是先抽出w的第一個分量w1，因為L完全展開中涉及到其平方，

是以，先化簡w1的平方這一步。因為w1可以進一步展開成如下形式：

w1的平方，是以可以展成如下形式：

上面這個式子就是基本的多項式求和，w1的平方進一步濃縮下：

至此，w1的平法化簡完畢，再整合所有其他w分量并求和，如下，整個推導過程依然相清晰，如下：

再對上式拆分成兩個向量，如下：

再寫成濃縮式子：

至此，代入w後化簡中的第一項已經完畢。

再化簡第二塊：

對上式展開，并利用條件：

，化簡如下：

代入w滿足的等式

後，

提取出公因子後變為如下：

将上式寫為向量形式：

因為都是向量，是以轉置相等，故，

至此，第一二項求解完畢，整理後得到：

目标函數終于變為系數的函數，接下來使用KKT求解上式的最優解。關于 KKT 的了解，可以先嘗試了解拉格朗日乘子法，而它的推導可借助下面這些圖更加容易了解

4 拉格朗日乘子法

機器學習是一個目标函數優化問題，給定目标函數f，限制條件會有一般包括以下三類：

1. 僅含等式限制
2. 僅含不等式限制
3. 等式和不等式限制混合型

當然還有一類沒有任何限制條件的最優化問題

關于最優化問題，大都令人比較頭疼，首先大多教材講解通篇都是公式，各種符号表達，各種梯度，叫人看的雲裡霧裡。

有沒有結合幾何圖形闡述以上問題的？很慶幸，還真有這麼好的講解材料，圖文并茂，邏輯推導嚴謹，更容易叫我們了解

拉格朗日乘數法

、

KKT條件

為什麼就能求出極值。

1 僅含等式限制

假定目标函數是連續可導函數，問題定義如下：

然後，

通過以上方法求解此類問題，但是為什麼它能求出極值呢？

下面解釋為什麼這種方法就能求出極值。

2 找找 sense

大家時間都有限，隻列出最核心的邏輯，找找sense, 如有興趣可回去下載下傳PPT仔細體會。

此解釋中對此類問題的定義：

為了更好的闡述，給定一個具體例子，鎖定：

是以，f(x)的一系列取值包括0,1,100,10000等任意實數：

但是，限制條件

h(x)

注定會限制

f(x)

不會等于100，不會等于10000...

一個可行點：

3 梯度下降

我們想要尋找一個移動

x

的規則，使得移動後

f(x+delta_x)

變小，當然必須滿足限制

h(x+delta_x)=0

使得

f(x

)減小最快的方向就是它的梯度反方向，即

是以，要想f(x+delta_x) 變小，通過圖形可以看出，隻要保持和梯度反方向夾角小于90，也就是保持大概一個方向，

f(x+delta_x)

就會變小，轉化為公式就是：

如下所示的一個

delta_x

就是一個會使得f(x)減小的方向，但是這種移動将會破壞等式限制: 

h(x)=0

，關于準确的移動方向下面第四小節會講到

4 限制面的法向

限制面的外法向：

限制面的内法向：

綠圈表示法向的

正交

方向

x沿着綠圈内的方向移動，将會使得f(x)減小，同時滿足等式限制h(x) = 0

5 提出猜想

我們不妨大膽假設，如果滿足下面的條件：

根據第四小節講述，

delta_x

必須正交于

h(x)

，是以：

是以：

至此，我們就找到

f(x)

偏導數等于0的點，就是下圖所示的兩個關鍵點（它們也是f(x)與h(x)的臨界點）。且必須滿足以下條件，也就是兩個向量必須是平行的：

6 完全解碼拉格朗日乘數法

至此，已經完全解碼拉格朗日乘數法，拉格朗日巧妙的構造出下面這個式子：

還有取得極值的的三個條件，都是對以上五個小節中涉及到的條件的編碼