AI面試之SVM推導

SVM現在主流的有兩個方法。一個是傳統的推導，計算支援向量求解的方法，一個是近幾年興起的梯度下降的方法。 梯度下降方法的核心是使用了hinge loss作為損失函數，是以最近也有人提出的深度SVM其實就是使用hinge loss的神經網絡。

本文的目的是講解傳統的推導。

SVM的超平面

SVM模型的基本原理，就是尋找一個合适的超平面，把兩類的樣本正确分開。單個SVM隻能處理二分類，多分類需要多個SVM。

【什麼是超平面？】

超平面就是n次元空間的n-1次元的子空間。換成人話就是2維空間中的1次元的線，三維立體空間的二維平面。

圖中總共有5個超平面，那麼哪一個是最好的呢？我們認為中間的那個是最好的。因為他對兩側的間隔較大。

SVM基本型

超平面我們可以用這個方程來表示：

\(\bm{w^Tx}+b=0\)

空間中任意一個點x到這個超平面的垂直距離為：

\(d = \frac{|\bm{w^Tx}+b|}{||\bm{w}||}\)

這裡不得不提到一下邏輯回歸，對于邏輯回歸來說：

就是在超平面一側的樣本，邏輯回歸給出的預測類别是1，另外一側就是0.

但是SVM覺得這樣有一些過于絕對了，是以：

不僅僅要一個樣本在平面的一側，還要在平面的這一側足夠遠的地方，才能算作某一類的樣本。

從圖中可以看到，兩條虛線之外的點，才是SVM能确定是正樣本還是負樣本的點。

【什麼是支援向量？】

圖中距離超平面最近的幾個訓練樣本，并且這幾個訓練樣本可以讓上式的等号成立。這個點就是支援向量。

【什麼是SVM的間隔】

兩個不同類别的支援向量到超平面的最小距離之和。其實也就是\(\frac{2}{||w||}\)

到這裡，我們可以隐隐約約的發現，尋找最優的超平面其實等價于尋找一個最大的間隔，或者說讓間隔最大化。是以可以得到：

\(\max_{w,b} \frac{2}{||\bm{w}||}\)

這個的限制條件就是：讓SVM給正樣本的打分大于1，給負樣本的打分小于-1,也就是：

簡化一下這個限制條件，可以得到：

\(y_i(\bm{w^Tx_i}+b)>=1\)

一般我們都是求取最小化問題，是以把最大化max問題取倒數，變成最小化問題：

\(\min_{w,b} \frac{||\bm{w}||}{2}\)

這裡為了後續的計算友善，最小化\(||w||\)等價于最小化\(||w||^2\),是以得到：

\(\min_{w,b} \frac{||\bm{w}||^2}{2}\)

總之SVM的基本型就是:

SVM求解

現在求得了基本型。現在可以來進一步優化這個最小化問題。但是首當其沖的問題便是，如何處理這個限制條件。這裡用到的方法是拉格朗日乘子法。将限制條件以\(\alpha_i\)的權重加入到優化問題中，是以可以得到：

\(Loss(\bm{w},b,\bm{\alpha})=\frac{1}{2}||w||^2+\sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b))\)

• 這裡的loss就是我們要最小化的對象；
• 這裡的m就是支援向量的數量。

為了最小化這個問題，對w和b求偏導數，可以得到：

\(w = \sum^m_{i=1}{\alpha_iy_ix_i}\)

\(0 = \sum^m_{i=1}{\alpha_iy_i}\)

然後把這兩個公式代入到：

\(Loss(\bm{w},b,\bm{\alpha})=\frac{1}{2}||w||^2+\sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b))\)

可以消掉w和b，得到：

限制條件為：

進而根據這個計算出\(\alpha_i\)的取值，然後得到w和b的取值。

【到底如何求解\(\alpha\)?】

上面說的最後一部求解alpha，都是理論可以求解，但是實際中如何做到呢？其實這裡如何求解\(\alpha\)要用到另外一個條件。

就是上述過程要滿足一個叫做KKT的條件（KKT具體是什麼有點複雜，就不多說了）：

• 想要第三個公式成立，要麼\(\alpha_i\)等于0，要麼\(y_if(x_i)-1=0\).如果alpha=0，那麼意味着這個樣本不是支援向量，不應該對SVM超平面起到任何影響，是以是不可能的。是以隻有\(y_if(x_i)-1=0\)。

加上了這個條件，我們可以求解出來\(\alpha_i\)的具體數值，然後求解w和b的數值。

假設有3個支援向量，那麼就會有三個\(\alpha_1, \alpha_2, \alpha_3\) ,然後根據\(y_if(x_i)-1=0\)可以列出3個關于\(\alpha_1,\alpha_2,\alpha_3\)的三元一次方程組，然後得到唯一解。