機器學習——支援向量機（SVM）複講

之前做了支援向量機的筆記，過了這幾天，覺得又有點忘了，重新拿起來複習一遍，然後作了一個更加精簡的筆記，應該會更容易懂。

支援向量機在解決什麼問題：

支援向量機和很多機器學習的算法一樣，是針對分類的一種算法，最簡單的了解就是線性二分類，如下圖：

這副圖其實就很概括性地了解了支援向量機的分類原理，什麼樣的分類間隔面才是合理并且最優的呢？顯然是與兩堆類别間隔最大的分隔面，說到底，SVM的原理就是一直在求、并且推導怎麼得到這個最大間隔的分類面的參數，在這裡，我們首先了解線性分類的參數，因為它是我們上手的基礎。

間隔表示

為了最小化這個間隔，我們根據空間矢量的距離公式可以得到我們的目标函數（就是距離公式，不要說高中的距離公式都不會吧？可以看我上一篇具體有公式），然後由上圖可以知道 ( w T x i + b ) = 1 (w^Tx_i+b)=1 (wTxi​+b)=1，支援向量上的點滿足圖上表示的公式，代入其實就是最小化 ω \omega ω，沒錯，就是這麼簡單的目标，線性可分的支援向量機目标就是最小化這個 ω \omega ω。

當然我們還有限制條件，就是分類正确（如上圖所示），應該滿足：

s . t . y i ( w T x i + b ) ≥ 1 s.t.y_i(w^Tx_i+b)\geq1 s.t.yi​(wTxi​+b)≥1

怎麼會有這個公式？看圖！分類正确就是滿足這個公式，這個很好了解。

明顯上面提供了兩個條件，一個式子要最小化，一個限制條件，那麼我們就遇到優化問題了。很好，拉格朗日函數來了。

拉格朗日函數優化：

之前看這個的時候，看到一篇寫得很簡單但很透徹的文章：

https://www.jianshu.com/p/47986a0b1bf1

它講拉格朗日式子為什麼要這麼構造講得很好，其實懂了這個你根本不要看我上一篇列的式子，因為你根據上面的目标和限制條件，任何人都能構造出我們所要得到的函數，然後它也說到對偶性這個東西，我們就是根據這個轉化這個式子，然後應該滿足KKT條件，這個可以看我的上一篇具體講述。

總之你隻要懂得我們根據限制條件和目标函數列出拉格朗日函數，進行對偶、滿足KKT、求導為零得到了：

∂ L ∂ w = 0 → w = ∑ 1 n α i y i x i ∂ L ∂ b = 0 → ∑ 1 n α i y i = 0 \frac{\partial L}{\partial w}=0\rightarrow w=\sum_1^n\alpha_iy_ix_i \\ \frac{\partial L}{\partial b}=0\rightarrow\sum_1^n\alpha_iy_i=0 ∂w∂L​=0→w=1∑n​αi​yi​xi​∂b∂L​=0→1∑n​αi​yi​=0

代入目标函數：

max ⁡ α ∑ 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j x i T x j s . t . α i ≥ 0 , i = 1 , 2 , . . . n ∑ 1 n α i y i = 0 \max_\alpha\sum_1^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \\ s.t.\alpha_i\geq0,i=1,2,...n \\ \sum_1^n\alpha_iy_i=0 αmax​1∑n​αi​−21​i,j=1∑n​αi​αj​yi​yj​xiT​xj​s.t.αi​≥0,i=1,2,...n1∑n​αi​yi​=0

沒錯，還是這麼簡單，就是求了導的含限制條件的目标函數，我們就是要進行alpha的求解。

SMO算法：

其實SMO算是比較複雜的一步了，因為前面都是簡單的一步步順承下來的，接下來是通過不斷更新alpha來得到最後的結果。

接下來，因為我們通過兩個alpha值來不斷更新，是以把原來的目标函數進行拆分，然後化成最後的更新公式（這其中的都是簡單的的換元推導）：

α 2 n e w = α 2 o l d + y 2 ( E 1 − E 2 ) η E i = f ( x i ) − y i η = x 1 T x 1 + x 2 T x 2 − 2 x 1 T x 2 \alpha2^{new}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}\\ E_i=f(x_i)-y_i \\ \eta=x_1^Tx_1+x_2^Tx_2-2x_1^Tx_2 α2new=α2old​+ηy2​(E1​−E2​)​Ei​=f(xi​)−yi​η=x1T​x1​+x2T​x2​−2x1T​x2​

也就是說我們首先需要得到誤差E，得到學習率eta，然後進行更新第二個參數，因為我們考慮了軟判決（我們對分類給了一個可浮動的判決空間），是以添加了備援量，使得我們需要對這個參數有一個上下限的修正，然後根據第二個參數更新第一個參數：

α 1 n e w = α 1 o l d + y 1 y 2 ( α 2 o l d − α 2 n e w , c l i p p e d ) \alpha_1^{new}=\alpha_1^{old}+y_1y_2(\alpha_2old-\alpha_2^{new,clipped}) α1new​=α1old​+y1​y2​(α2​old−α2new,clipped​)

得到這兩個參數後，我們就可以得到b：

$$

b=\begin{cases}

b_1 && 0<\alpha_1^{new}<C

\

b_2 && 0<\alpha_2^{new}<C

\

(b_1+b_2)/2 &&otherwise\end{cases}

$$

這就完成了！根據b算出w，ok！

具體推導參見我的github：

https://github.com/Brian-Liew/Machine-Learning