支援向量機SVM：原理講解+手寫公式推導+疑惑分析

本文是需要一定基礎才可以看懂的，建議先看看參考部落格，一些疑惑會在文中直接提出，大家有額外的疑惑可以直接評論，有問題請直接提出，互相交流。

SVM-統計學習基礎

一開始講解了

最小間距超平面：所有樣本到平面的距離最小

。而距離度量有了函數間隔和幾何間隔，函數間隔與法向量 w w w和 b b b有關， w w w變為 2 w 2w 2w則函數間距變大了，于是提出了幾何距離，就是對 w w w處理，除以 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣，除以向量長度，進而讓幾何距離不受影響。

但是支援向量機提出了最大間隔分離超平面，這似乎與上面的分析相反，其實這個最大間隔是個什麼概念呢？通過公式來分析一下，正常我們假設超平面公式是：

w T x + b = 0 / / 超 平 面 w^{T}x+b=0 // 超平面 wTx+b=0//超平面

max ⁡ w , b γ s . t . y i ( w ∣ ∣ w ∣ ∣ x i + b ∣ ∣ w ∣ ∣ ) ≥ γ \max \limits_{w,b} \quad \gamma \\ s.t. \quad y_i(\frac{w}{||w||}x_i+\frac{b}{||w||}) \ge \gamma w,bmax​γs.t.yi​(∣∣w∣∣w​xi​+∣∣w∣∣b​)≥γ

也就是說對于所有的樣本到超平面距離 都大于 γ \gamma γ，那這個 γ \gamma γ如何求解，文中約定了概念支援向量：正負樣本最近的兩個點，這兩個點之間的距離就是 γ \gamma γ，那麼問題來了，這中間的超平面有無數個，如何确定這個超平面呢？于是我們可以限制這個超平面到兩個最近的點的距離是一樣的。

上圖中兩個紅色菱形點與一個藍色實心圓點就是支援向量，通過這個求解目标，以及限制條件來求解這個超平面。書中有完整的公式裝換以及證明這個超平面的唯一性。

這裡要講解一個樣本點到直線的距離，

正常我們可能難以了解公式裡 y y y去哪裡了，拿二維空間做例子，正常我們說一個線性方程都是 y = a x + b y=ax+b y=ax+b，其中a和b都是常量，這個線性方程中有兩個變量 x x x和 y y y，轉換公式就是 y − a x − b = 0 y-ax-b=0 y−ax−b=0，從線性矩陣的角度來思考問題就是 y y y是 x 1 x_1 x1​， x x x是 x 2 x_2 x2​，用一個 w T w^T wT來表示這兩者的系數，用 b b b代替 − b -b −b，是以公式就變為了：

w T x + b = 0 w^{T}x+b=0 wTx+b=0

于是任意一個樣本點到超平面的距離是：

r = ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ r = \frac{|w^{T}x+b|}{||w||} r=∣∣w∣∣∣wTx+b∣​

也就是說限制條件中要求 > γ >\gamma >γ，其實就是大于支援向量到超平面的距離。

通過一個例子來看看：

這裡例子中有 w 1 , w 2 w_1,w_2 w1​,w2​，這是因為坐标點是二維的，相當于樣本特征是兩個，分類的結果是這兩個特征的結果标簽，是以這裡的 w w w就是一個二維的，說明在具體的應用裡需要根據特征來确定 w w w的次元。

問題轉換：拉格朗日對偶

其實原始問題是這樣的：

max ⁡ w , b γ s . t . y i ( w ∣ ∣ w ∣ ∣ x i + b ∣ ∣ w ∣ ∣ ) ≥ γ \max \limits_{w,b} \quad \gamma \\ s.t. \quad y_i(\frac{w}{||w||}x_i+\frac{b}{||w||}) \ge \gamma w,bmax​γs.t.yi​(∣∣w∣∣w​xi​+∣∣w∣∣b​)≥γ

利用幾何距離與函數距離的關系 γ = γ ^ ∣ ∣ w ∣ ∣ \gamma = \frac{\hat{ \gamma}}{||w||} γ=∣∣w∣∣γ^​​将公式改為：

max ⁡ w , b γ ^ ∣ ∣ w ∣ ∣ s . t . y i ( w x i + b ) ≥ γ ^ \max \limits_{w,b} \quad \frac{\hat{ \gamma}}{||w||} \\ s.t. \quad y_i(wx_i+b) \ge \hat{\gamma} w,bmax​∣∣w∣∣γ^​​s.t.yi​(wxi​+b)≥γ^​

函數間隔是會随着 w 與 b w與b w與b的變化而變化，同時将 w 與 b w與b w與b變成 λ w 與 λ b \lambda w與\lambda b λw與λb，則函數間隔也會變成 λ γ \lambda \gamma λγ，是以書中直接将 γ = 1 \gamma=1 γ=1來轉換問題。同樣的問題又改為：

max ⁡ w , b 1 ∣ ∣ w ∣ ∣ s . t . y i ( w x i + b ) ≥ 1 \max \limits_{w,b} \quad \frac{1}{||w||} \\ s.t. \quad y_i(wx_i+b) \ge1 w,bmax​∣∣w∣∣1​s.t.yi​(wxi​+b)≥1

求解最大值改為另一個問題，求解最小值：

min ⁡ 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w x i + b ) ≥ 1 \min \quad \frac{1}{2} ||w||^2 \\ s.t. \quad y_i(wx_i+b) \ge1 min21​∣∣w∣∣2s.t.yi​(wxi​+b)≥1

這就是一個對偶問題的例子，也是書中支援向量機模型的一個目标函數轉換的過程，大家可以看看了解一下這個思路。其實書中利用拉格朗日乘子來求解條件極值，這一塊在

高等數學中多元函數的極值及求解方法

中有提到。

為了加深記憶，手寫了後面的推導過程：

關于拉格朗日對偶的證明：

1、拉格朗日乘子法

m i n L ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i = 1 m a i [ y i ( w t x i + b ) − 1 ] s . t . y i ( w x i + b ) ≥ 1 a i ≥ 0 min \quad L(w,b,a) = \frac{1}{2} ||w||^2 -\sum_{i=1}^{m}a_i[y^i(w^tx^i+b)-1] \\ s.t. \quad y_i(wx_i+b) \ge 1\\ a^i\ge0 minL(w,b,a)=21​∣∣w∣∣2−i=1∑m​ai​[yi(wtxi+b)−1]s.t.yi​(wxi​+b)≥1ai≥0

一般我們會最大化 m a x a max_{a} maxa​，得到

m i n w , b m a x a L ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i = 1 m a i [ y i ( w t x i + b ) − 1 ] s . t . y i ( w x i + b ) ≥ 1 a i ≥ 0 min_{w,b} \quad max_{a} \quad L(w,b,a) = \frac{1}{2} ||w||^2 -\sum_{i=1}^{m}a_i[y^i(w^tx^i+b)-1] \\ s.t. \quad y_i(wx_i+b) \ge 1\\ a^i\ge0 minw,b​maxa​L(w,b,a)=21​∣∣w∣∣2−i=1∑m​ai​[yi(wtxi+b)−1]s.t.yi​(wxi​+b)≥1ai≥0

其實滿足限制條件下可以證明：

m i n w , b m a x a L ( w , b , a ) = m i n w , b L ( w , b , a ) min_{w,b} \quad max_{a} \quad L(w,b,a) = min_{w,b} \quad L(w,b,a) minw,b​maxa​L(w,b,a)=minw,b​L(w,b,a)

證明可以參考上面的圖寫，也可以參考部落格機器學習數學：拉格朗日對偶問題，問題來了，明明一樣為什麼這麼寫？這麼寫的形式可以幫助我們來從對偶的角度來轉換問題，對偶形式是将 m i n min min和 m a x max max 對換：

m a x a m i n w , b L ( w , b , a ) max_{a} \quad min_{w,b} \quad L(w,b,a) maxa​minw,b​L(w,b,a)

證明：假設滿足條件下有極值點： w ∗ w^* w∗，則

g ( b , a ) = min ⁡ L ( w ∗ , b , a ) ≤ 1 2 ∣ ∣ w ∗ ∣ ∣ 2 ≤ min ⁡ 1 2 ∣ ∣ w ∣ ∣ 2 g(b,a)=\min \quad L(w^*,b,a) \le \quad \frac{1}{2} ||w^*||^2 \le \min \quad \frac{1}{2} ||w||^2 g(b,a)=minL(w∗,b,a)≤21​∣∣w∗∣∣2≤min21​∣∣w∣∣2

說明 g ( b , a ) g(b,a) g(b,a)是 min ⁡ 1 2 ∣ ∣ w ∣ ∣ 2 \min \quad \frac{1}{2} ||w||^2 min21​∣∣w∣∣2的一個下限，那麼我們可以最大化這個下限，于是就可以：

max ⁡ a min ⁡ w , b L ( w , b , a ) \max_{a}\min_{w,b}L(w,b,a) amax​w,bmin​L(w,b,a)

軟間隔

硬間隔是友善用來分隔線性可分的資料，如果樣本中的資料是線性不可分的呢？也就是如圖所示：

有一部分紅色點在綠色點那邊，綠色點也有一部分在紅色點那邊，是以就不滿足上述的限制條件： s . t . y i ( x i + b ) > 1 s.t. \quad y_i(x_i+b) >1 s.t.yi​(xi​+b)>1，軟間隔的最基本含義同硬間隔比較差別在于允許某些樣本點不滿足原限制，從直覺上來說，也就是“包容”了那些不滿足原限制的點。軟間隔對限制條件進行改造，迫使某些不滿足限制條件的點作為損失函數，如圖所示：

這裡要差別非線性情況，非線性的意思就是一個圓圈，圓圈裡是一個分類結果，圓圈外是一個分類結果。這就是非線性的情況。

其中當樣本點不滿足限制條件時，損失是有的，但是滿足條件的樣本都會被置為0，這是因為加入了轉換函數，使得求解min的條件會專注在不符合條件的樣本節點上。

但截圖中的損失函數非凸、非連續，數學性質不好，不易直接求解，我們用其他一些函數來代替它，叫做替代損失函數（surrogate loss）。後面采取了松弛變量的方式，來使得某些樣本可以不滿足限制條件。

這裡思考一個問題：既然是線性不可分，難道最後求出來的支援向量就不是直線？某種意義上的直線？

其實還是直線，不滿足條件的節點也被錯誤的配置設定了，隻是盡可能的求解最大間隔，

核函數

引入核函數可以解決非線性的情況：将樣本從原始空間映射到一個更高為的特征空間，使得樣本在這個特征空間内線性可分。圖檔所示：

粉紅色平面就是超平面，橢圓形空間曲面就是映射到高維空間後的樣本分布情況，為了将樣本轉換空間或者映射到高維空間，我們可以引用一個映射函數，将樣本點映射後再得到超平面。這個技巧不僅用在SVM中，也可以用到其他統計任務。

但映射函數并不是最重要的，核函數是重要的，看到《統計學習方法》中提到的概念：

其中映射函數與核函數之間有函數關系，一般我們顯示的定義核函數，而不顯示的定義映射函數，一方面是因為計算核函數比映射函數簡單，我們對一個二維空間做映射，選擇的新空間是原始空間的所有一階和二階的組合，得到了五個次元；如果原始空間是三維，那麼我們會得到 19 維的新空間，這個數目是呈爆炸性增長的，這給 的計算帶來了非常大的困難，而且如果遇到無窮維的情況，就根本無從計算了。是以就需要 Kernel 出馬了。這樣，一個确定的核函數，都不能确定特征空間和映射函數，同樣确定了一個特征空間，其映射函數也可能是不一樣的。舉個例子：

上述例子很好說明了核函數和映射函數之間的關系。這就是核技巧，将原本需要确定映射函數的問題轉換為了另一個問題，進而減少了計算量，也達到了線性可分的目的，

原始方法：  樣本X   ---->  特征空間Z  ---- >   内積求解超平面
核函數：    樣本X   ---- >   核函數 求解超平面
           

但是我一直很疑惑，為什麼這個核函數就正好是映射函數的内積？他為什麼就可以生效？核函數的參數是哪裡來的？就是樣本中的兩個樣本點 ?

檢視了一些部落格之後，慢慢了解，得到以下的内容。

這也說明核函數是作用在兩個樣本點上的，以下來自如某一篇部落格裡：

最理想的情況下，我們希望知道資料的具體形狀和分布，進而得到一個剛好可以将資料映射成線性可分的 ϕ(⋅) ，然後通過這個 ϕ(⋅) 得出對應的 κ(⋅,⋅) 進行内積計算。然而，第二步通常是非常困難甚至完全沒法做的。不過，由于第一步也是幾乎無法做到，因為對于任意的資料分析其形狀找到合适的映射本身就不是什麼容易的事情，是以，人們通常都是“胡亂”選擇映射的，是以，根本沒有必要精确地找出對應于映射的那個核函數，而隻需要“胡亂”選擇一個核函數即可——我們知道它對應了某個映射，雖然我們不知道這個映射具體是什麼。由于我們的計算隻需要核函數即可，是以我們也并不關心也沒有必要求出所對應的映射的具體形式。

常用的核函數及對比：

• Linear Kernel 線性核

  k ( x i , x j ) = x i T x j k(x_i,x_j)=x_i^{T}x_j k(xi​,xj​)=xiT​xj​

  線性核函數是最簡單的核函數，主要用于線性可分，它在原始空間中尋找最優線性分類器，具有參數少速度快的優勢。 如果我們将線性核函數應用在KPCA中，我們會發現，推導之後和原始PCA算法一模一樣，這隻是線性核函數偶爾會出現等價的形式罷了。

• Polynomial Kernel 多項式核

  k ( x i , y j ) = ( x i T x j ) d k(x_i,y_j)=(x_i^{T}x_j)^d k(xi​,yj​)=(xiT​xj​)d

  也有複雜的形式：

  k ( x i , x j ) = ( a x i T x j + b ) d k(x_i,x_j)=(ax_i^{T}x_j+b)^d k(xi​,xj​)=(axiT​xj​+b)d

  其中 d ≥ 1 d\ge1 d≥1為多項式次數，參數就變多了，多項式核實一種非标準核函數，它非常适合于正交歸一化後的資料，多項式核函數屬于全局核函數，可以實作低維的輸入空間映射到高維的特征空間。其中參數d越大，映射的次元越高，和矩陣的元素值越大。故易出現過拟合現象。

• 徑向基函數 高斯核函數 Radial Basis Function（RBF）

k ( x i , x j ) = e x p ( − ∣ ∣ x i − x j ∣ ∣ 2 2 σ 2 ) k(x_i,x_j)=exp(-\frac{||x_i-x_j||^2}{2\sigma^2}) k(xi​,xj​)=exp(−2σ2∣∣xi​−xj​∣∣2​)

σ > 0 \sigma>0 σ>0是高斯核帶寬，這是一種經典的魯棒徑向基核，即高斯核函數，魯棒徑向基核對于資料中的噪音有着較好的抗幹擾能力，其參數決定了函數作用範圍，超過了這個範圍，資料的作用就“基本消失”。高斯核函數是這一族核函數的優秀代表，也是必須嘗試的核函數。對于大樣本和小樣本都具有比較好的性能，是以在多數情況下不知道使用什麼核函數，優先選擇徑向基核函數。

• Laplacian Kernel 拉普拉斯核

  k ( x i , x j ) = e x p ( − ∣ ∣ x i − x j ∣ ∣ σ ) k(x_i,x_j)=exp(-\frac{||x_i-x_j||}{\sigma}) k(xi​,xj​)=exp(−σ∣∣xi​−xj​∣∣​)

• Sigmoid Kernel Sigmoid核

  k ( x i , x j ) = t a n h ( α x T x j + c ) k(x_i,x_j)=tanh(\alpha x^Tx_j+c) k(xi​,xj​)=tanh(αxTxj​+c)

  采用Sigmoid核函數，支援向量機實作的就是一種多層感覺器神經網絡。

其實還有很多核函數，在參考部落格裡大家都可以看到這些核函數，對于核函數如何選擇的問題，吳恩達教授是這麼說的：

• 如果Feature的數量很大，跟樣本數量差不多，這時候選用LR或者是Linear Kernel的SVM
• 如果Feature的數量比較小，樣本數量一般，不算大也不算小，選用SVM+Gaussian Kernel
• 如果Feature的數量比較小，而樣本數量很多，需要手工添加一些feature變成第一種情況

參考部落格

重點推薦：SVM系列文章

【直覺詳解】支援向量機SVM

支援向量機擴充

SVM-非線性可分情況-可視化展示-視訊

機器學習----SVM（2）從原始問題到對偶問題的轉換

總結一下遇到的各種核函數~

攀登傳統機器學習的珠峰-SVM (上)

SVM smo算法

統計方法學習之：svm超平面存在唯一性證明過程