機器學習，詳解SVM軟間隔與對偶問題

今天是機器學習專題的第34篇文章，我們繼續來聊聊SVM模型。

我們在上一篇文章當中推導了SVM模型在硬間隔的原理以及公式，最後我們消去了所有的變量，只剩下了$\alpha$。在硬間隔模型當中，樣本是線性可分的，也就是說-1和1的類別可以找到一個平面將它完美分開。但是在實際當中，這樣的情況幾乎是不存在的。道理也很簡單，完美是不存在的，總有些樣本會出錯。

那針對這樣的問題我們應該怎麼解決呢？

軟間隔

在上文當中我們說了，在實際的場景當中，數據不可能是百分百線性可分的，即使真的能硬生生地找到這樣的一個分隔平面區分開樣本，那麼也很有可能陷入過擬合當中，也是不值得追求的。

因此，我們需要對分類器的標準稍稍放鬆，允許部分樣本出錯。但是這就帶來了一個問題，在硬間隔的場景當中，間隔就等於距離分隔平面最近的支持向量到分隔平面的距離。那麼，在允許出錯的情況下，這個間隔又該怎麼算呢？

為了解決這個問題，我們需要對原本的公式進行變形，引入一個新的變量叫做鬆弛變量。鬆弛變量我們用希臘字母$\xi$來表示，這個鬆弛變量允許我們適當放鬆$y_i(\omega^T x_i + b) \ge 1 $這個限制條件，我們將它變成$y_i(\omega^T x_i + b) \ge 1-\xi_i $。

也就是說對於每一條樣本我們都會有一個對應的鬆弛變量$\xi_i$，它一共有幾種情況。

$\xi=0$，表示樣本能夠正確分類
$0 < \xi < 1$，表示樣本在分割平面和支持向量之間
$\xi = 1$，表示樣本在分割平面上
$\xi \ge 1$，表示樣本異常

我們可以結合下面這張圖來理解一下，會容易一些：

鬆弛變量雖然可以讓我們表示那些被錯誤分類的樣本，但是我們當然不希望它隨意鬆弛，這樣模型的效果就不能保證了。所以我們把它加入損失函數當中，希望在鬆弛得盡量少的前提下保證模型儘可能劃分正確。這樣我們可以重寫模型的學習條件：

\[\begin{align*}
&\min\quad \frac{1}{2}||\omega||^2 + C\sum_{i=1}^m\xi_i\\
& \begin{array}{r@{\quad}r@{}l@{\quad}l}
s.t.&y_i(\omega^Tx_i+b)\geq1-\xi_i, &i=1,2,3\ldots,n\\
&\xi_i \geq 0,&i=1,2,3\ldots,n\\
\end{array}
\end{align*}\]

這裡的C是一個常數，可以理解成懲罰參數。我們希望$||\omega||^2$盡量小，也希望$\sum \xi_i$盡量小，這個參數C就是用來協調兩者的。C越大代表我們對模型的分類要求越嚴格，越不希望出現錯誤分類的情況，C越小代表我們對鬆弛變量的要求越低。

從形式上來看模型的學習目標函數和之前的硬間隔差別並不大，只是多了一個變量而已。這也是我們希望的，在改動盡量小的前提下讓模型支持分隔錯誤的情況。

模型推導

對於上面的式子我們同樣使用拉格朗日公式進行化簡，將它轉化成沒有約束的問題。

首先，我們確定幾個值。第一個是我們要優化的目標：$f(x)=\min_{\omega, b, \xi}\frac{1}{2}||\omega||^2 + C\sum_{i=1}^m \xi_i$

第二個是不等式約束，拉格朗日乘子法當中限定不等式必須都是小於等於0的形式，所以我們要將原式中的式子做一個簡單的轉化：

\[\begin{aligned}
g(x) = 1 – \xi_i – y_i(\omega^Tx_i + b) \leq 0 \\
h(x) = -\xi_i \le 0
\end{aligned}
\]

最後是引入拉格朗日乘子: $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_m), \beta = (\beta_1, \beta_2, \cdots, \beta_m)$

我們寫出廣義拉格朗日函數：$L(\omega, b, \xi, \alpha, \beta) = \frac{1}{2}||\omega||^2 + C\sum_{i=1}^m \xi_i, + \sum_{i=1}^m \alpha_i(1 – \xi_i – y_i(\omega^Tx_i + b)) -\sum_{i=1}^m \beta_i\xi_i$

我們要求的是這個函數的最值，也就是$\min_{\omega, b, \xi}\max_{\alpha \ge 0, \beta\ge 0}L(\omega, b, \xi, \alpha, \beta)$。

在處理硬間隔的時候，我們講過對偶問題，對於軟間隔也是一樣。我們求L函數的對偶函數的極值。

對偶問題

原函數的對偶問題是$\max_{\alpha \ge0, \beta \ge 0}\min_{\omega, b, \xi}L(\omega, b, \xi, \alpha, \beta)$，這個對偶問題要成立需要滿足KKT條件。

我們先把這個KKT條件放一放，先來看一下對偶問題當中的內部的極小值。這個極小值沒有任何約束條件，所以我們可以放心大膽地通過求導來來計算極值。這個同樣是高中數學的內容，我們分別計算$\frac{\partial L}{\partial \omega}$，$\frac{\partial L}{\partial b}$和$\frac{\partial L}{\partial \xi}$。

求導之後，我們可以得到：

\[\begin{aligned}
\frac{\partial L}{\partial \omega} = 0 &\rightarrow \omega = \sum_{i=1}^m \alpha_i y_i x_i \\
\frac{\partial L}{\partial b} = 0 &\rightarrow \sum_{i=1}^m \alpha_i y_i = 0 \\
\frac{\partial L}{\partial \xi} = 0 &\rightarrow \beta_i = C – \alpha_i
\end{aligned}
\]

我們把這三個式子帶入對偶函數可以得到：

\[\begin{aligned}
L(\omega, b, \xi, \alpha,\beta) &= \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_iy_jx_i^Tx_j + C\sum_{i=1}^m \xi_i + \sum_{i=1}^m \alpha_i (1 – \xi_i) – \sum_{i=1}^m (C – \alpha_i) \xi_i \\
&= \sum_{i=1}^m\alpha_i – \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_iy_jx_i^Tx_j
\end{aligned}
\]

由於$\beta_i \ge 0$，所以我們可以得到$0 \le \alpha_i \le C$，所以最後我們可以把式子化簡成：

\[\begin{align*}
&\max_{\alpha} \sum_{i=1}^m\alpha_i – \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_iy_jx_i^Tx_j\\
& \begin{array}{r@{\quad}r@{}l@{\quad}l}
s.t.& \sum_{i=1}^m \alpha_i y_i = 0 \\
& 0 \le \alpha_i \le C,&i=1,2,3\ldots,m\\
\end{array}
\end{align*}\]

將原始化簡了之後，我們再回過頭來看KKT條件。KKT條件單獨理解看起來有點亂，其實我們可以分成三個部分，分別是原始問題可行：

\[\begin{aligned}
1 – \xi_i – y_i(\omega^Tx_i + b) \le 0 \\
-\xi_i \le 0
\end{aligned}
\]

對偶問題可行：

\[\begin{aligned}
\alpha_i \ge 0 \\
\beta_i = C – \alpha_i
\end{aligned}
\]

以及鬆弛可行：

\[\begin{aligned}
\alpha_i (1 – \xi – y_i(\omega^Tx_i + b)) = 0 \\
\beta_i \xi_i = 0
\end{aligned}
\]

我們觀察一下倒數第二個條件：$\alpha_i (1 – \xi – y_i(\omega^Tx_i + b)) = 0$。

這是兩個式子相乘並且等於0，無非兩種情況，要麼$\alpha_i = 0$，要麼後面那串等於0。我們分情況討論。

如果$\alpha_i = 0$，那麼$y_i(\omega^Tx_i + b) – 1 \ge 0$，樣本分類正確，不會對模型產生影響。
如果$\alpha_i > 0$，那麼$y_i(\omega^Tx_i + b) = 1 – \xi_i$，則樣本是支持向量。由於$C = \alpha_i + \beta_i$ ，並且$\beta_i \xi_i= 0$。我們又可以分情況：
1. $\alpha_i < C$，那麼$\beta_i > 0$，所以$\xi_i = 0$，那麼樣本在邊界上
2. 如果$\alpha_i = C$，那麼$\beta_i = 0$，如果此時$\xi \le 1$，那麼樣本被正確分類，否則樣本被錯誤分類

經過了化簡之後，式子當中只剩下了變量$\alpha$，我們要做的就是找到滿足約束條件並且使得式子取極值時的$\alpha$，這個$\alpha$要怎麼求呢？我們這裡先放一放，將在下一篇文章當中詳解講解。

今天的文章到這裡就結束了，如果喜歡本文的話，請來一波素質三連，給我一點支持吧（關注、轉發、點贊）。

原文鏈接，求個關注

Tags: SVM 機器學習機器學習基礎機器學習模型