支援向量機（Support Vector Machine，簡稱 SVM）于 1995 年正式發表，由于其在文本分類任務中的卓越性能，很快就成為機器學習的主流技術。盡管現在 Deep Learning 很流行，SVM 仍然是一種很有的機器學習算法，在資料集小的情況下能比 Deep Learning 取得更好的結果。本文主要讨論線性 SVM，kernel 部分沒有涉及。
支援向量機（Support Vector Machine，簡稱 SVM）于 1995 年正式發表，由于其在文本分類任務中的卓越性能，很快就成為機器學習的主流技術。盡管現在 Deep Learning 很流行，SVM 仍然是一種很有的機器學習算法，在資料集小的情況下能比 Deep Learning 取得更好的結果。
本文将詳細介紹線性 SVM，非線性 SVM 涉及到的 kernel，本文中沒有介紹。我将從以下兩個方面展開介紹線性 SVM：
- 間隔和支援向量
- 對偶問題
1. 間隔和支援向量
給定一個訓練集 \(D= \{( \boldsymbol{x}_1, y_1), (\boldsymbol{x}_2, y_2),..., (\boldsymbol{x}_m, y_m)\}, y \in \{ -1, +1\}\)，我們想要找一個超平面對其進行劃分，可以有多種選擇，如下圖所示：
圖 1 存在多個超平面可以将訓練集劃分開
憑直覺，我們會選擇最中間的那個超平面（也就是圖 1 中最粗的那條，注：在 2 維情況下，超平面就是一條直線），為什麼？因為更 robust，測試集中的點一般沒有在訓練集中出現過，這個時候難免會有些點會偏向分類的超平面，要是該分類超平面離訓練資料點近了，這些偏向超平面的資料點豈不是直接分錯了。這個時候最中間的那條線受到的影響最小，是以最優。
在樣本空間中，劃分超平面可以通過以下線性方程來描述：
\begin{equation}
\boldsymbol{w}^T \boldsymbol{x} + b = 0
\end{equation}
其中 \(\boldsymbol{w} = [w_1; w_2; ...; w_d]\)（注：\(\boldsymbol{w}\) 是列向量）為法向量，決定了超平面的方向；\(b\) 是位移，決定了超平面和原定之間的距離。知道 \(\boldsymbol{w}\) 和 \(b\)，我們也就能确定該超平面的位置。樣本空間中任一點 \(\boldsymbol{x}\) 到超平面 \(\boldsymbol{w}^T \boldsymbol{x} + b = 0\) 的距離可以記為：
r = \frac{ |\boldsymbol{w}^T \boldsymbol{x} + b |}{ \Vert \boldsymbol{w} \Vert }
假設超平面 \(\boldsymbol{w}^T \boldsymbol{x} + b = 0\) 能夠将訓練集 \(D\) 完全正确分類，即對于 \(D\) 中任一樣本 \(( \boldsymbol{x}_i, y_i)\)，若 $y_i = +1 $，則 \(\boldsymbol{w}^T \boldsymbol{x}_i + b > 0\)；若 $y_i = -1 $，則 \(\boldsymbol{w}^T \boldsymbol{x}_i + b < 0\)。我們再假設訓練集 \(D\) 的兩個類别中，離超平面最近的點到超平面的距離都是 \(r^*(r^* > 0 )\)（兩個類别離超平面最近的點到超平面的距離是一樣的，不然超平面就不在“最中間”，該超平面肯定不是最優的，可以對其平移滿足這個條件）。此時所有訓練集 \(D\) 中點都滿足以下方程：
\begin{cases}
\boldsymbol{w}^T \boldsymbol{x}_i + b \ge +r^, & y_i = +1 \cr
\boldsymbol{w}^T \boldsymbol{x}_i + b \le -r^, & y_i = -1
\end{cases}
此時我們對公式（3）做一個變換，不等式兩邊都除以 \(r^*\) 可以得到：
\frac{ \boldsymbol{w} T}{r*} \boldsymbol{x}_i + \frac{b}{r^*} \ge +1, & y_i = +1 \cr
\frac{ \boldsymbol{w} T}{r*} \boldsymbol{x}_i + \frac{b}{r^*} \le -1, & y_i = -1
對于公式（4）中的 \(\frac{ \boldsymbol{w} ^T}{r^*}\) 和 \(\frac{b}{r^*}\)，我們令其分别為新的 \(\boldsymbol{w}^T\) 和 \(b\)，這樣做隻是對原超平面 \(\boldsymbol{w}^T \boldsymbol{x} + b = 0\) 的法向量和位移項進行了縮放，實際上并沒有改變超平面的位置。（對位移項和法向量同時進行縮放，不會改變原點到超平面的距離，可以代入公式（2）進行檢驗。同樣地，該變換也不會改變樣本點和分類超平面之間的距離。）故而，公式（4）可以寫成如下最常見的形式：
\boldsymbol{w}^T \boldsymbol{x}_i + b \ge +1, & y_i = +1 \cr
\boldsymbol{w}^T \boldsymbol{x}_i + b \le -1, & y_i = -1
如圖 2 所示，距離超平面最近的這幾個訓練樣本點使式（5）的等号成立，它們被稱為“支援向量”（support vector），兩個類别的支援向量到超平面的距離之和為：
\gamma = \frac{2}{\Vert \boldsymbol{w} \Vert}
其中，\(\gamma\) 被稱為“間隔”（margin）。
圖 2 支援向量和間隔
式（5）中兩個不等式可以合成一個統一的形式，如下所示：（這也是為什麼類别 \(y_i\) 的取值為 -1 和 1 的原因，友善将兩個不等式統一形式）
\[\quad y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1, \quad i = 1,2,...m.
\]
欲找到具有“最大間隔”（maximum margin）的劃分超平面，也就是要找到能滿足式（5）中限制的參數 \(\boldsymbol{w}^T\) 和 \(b\)，使得 \(\gamma\) 最大，即
\begin{split}
& \max_{\boldsymbol{w}, b} \frac{2}{\Vert \boldsymbol{w} \Vert } \quad \
& s.t. \quad y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1, \quad i = 1,2,...m.
\end{split}
為了最大化間隔，隻需要式（7）中分母最小即可，即最小化 \(\Vert \boldsymbol{w} \Vert\)，等價于最小化 \(\Vert \boldsymbol{w} \Vert^2\)，式（7）可重新寫為：
& \min_{\boldsymbol{w}, b} \frac{1}{2}\Vert \boldsymbol{w} \Vert^2 \quad \
式（8）就是支援向量機想要優化的目标函數。
2. 對偶問題
我們希望求解式（8）來得到最大間隔劃分超平面所對應的模型：
f(\boldsymbol{x} ) = \boldsymbol{w}^T \boldsymbol{x} + b
其中 \(\boldsymbol{w}^T\) 和 \(b\) 是模型參數，式（8）本身是一個凸二次規劃（convex quadratic programming）問題，能直接用現成的優化計算包求解，但我們可以有更高效的辦法，即使用拉格朗日乘子法求其“對偶問題”（dual problem）。下面我們先來了解最優化問題可以分為哪幾類，什麼是拉格朗日乘子法，什麼又是對偶問題。
2.1 最優化問題分類
通常，我們需要求解的最優化問題有如下幾類：（注：2.1 小節的 \(f(\boldsymbol{x})\) 和公式（9）沒有關系）
（i）無限制優化問題：
\[\min_{\boldsymbol{x}} f(\boldsymbol{x})
（ii）有等式限制的優化問題：
\[\begin{split}
& \min_{\boldsymbol{x}} f(\boldsymbol{x}) \\
s.t. \quad & h_i(\boldsymbol{x}) = 0, \quad i = 1,2,\dots,n.
（iii）有不等于限制的優化問題：
s.t. \quad & h_i(\boldsymbol{x}) = 0, \quad i = 1,2,\dots,n; \\
& g_j(\boldsymbol{x}) \le 0, \quad j = 1,2,\dots, m.
對于第（i）類的優化問題，嘗試使用的方法就是費馬大定理(Fermat)，即使用求取函數 $ f(\boldsymbol{x}) $ 的導數，然後令其為零，可以求得候選最優值，再在這些候選值中驗證；如果是凸函數，可以保證是最優解。這也就是我們高中經常使用的求函數的極值的方法。
對于第（ii）類的優化問題，常常使用的方法就是拉格朗日乘子法（Lagrange Multiplier) ，即把等式限制 $ h_i(\boldsymbol{x}) = 0$ 用一個系數與 $ f(\boldsymbol{x}) $ 寫為一個式子，稱為拉格朗日函數，而系數稱為拉格朗日乘子。通過拉格朗日函數對各個變量求導，令其為零，可以求得候選值集合，然後驗證求得最優值。
對于第（iii）類的優化問題，常常使用的方法就是KKT條件。同樣地，我們把所有的等式、不等式限制與 $ f(\boldsymbol{x}) $ 寫為一個式子，也叫拉格朗日函數，系數也稱拉格朗日乘子，通過一些條件，可以求出最優值的必要條件，這個條件稱為KKT條件。（注：若事件 B 是事件 A 的必要條件，則從事件 A 可以推出事件 B）
SVM 的優化問題屬于第（iii）類。
2.2 拉格朗日乘子法
拉格朗日乘子法（Lagrange multipliers）是一種尋找多元函數在一組限制下的極值的方法。通過引入拉格朗日乘子，可以将有 \(d\) 個變量和 \(k\) 個限制條件的最優化問題轉化為具有 \(d+k\) 個變量的無限制優化問題求解。
為什麼需要拉格朗日乘子法？當然是因為無限制的問題比有限制的問題更好求解。
“我們知道我們要求解的是最小化問題，是以一個直覺的想法是如果我能夠構造一個函數，使得該函數在可行解區域内與原目标函數完全一緻，而在可行解區域外的數值非常大，甚至是無窮大，那麼這個沒有限制條件的新目标函數的優化問題就與原來有限制條件的原始目标函數的優化問題是等價的問題。這就是使用拉格朗日方程的目的，它将限制條件放到目标函數中，進而将有限制優化問題轉換為無限制優化問題。”
随後，人們又發現，使用拉格朗日獲得的函數，使用求導的方法求解依然困難。進而，需要對問題再進行一次轉換，即使用一個數學技巧：拉格朗日對偶。
是以，在拉格朗日優化的問題上，我們需要進行下面二個步驟：
- 将有限制的原始目标函數轉換為無限制的新構造的拉格朗日目标函數
- 使用拉格朗日對偶性，将不易求解的優化問題轉化為易求解的優化
下面首先将有限制的 SVM 目标函數式（8）轉化為無限制的拉格朗日函數：
式（8）中隻有不等式限制 \(g_i(w, b) \le 0\) (即 \(1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \le 0, \quad i = 1,2,...m.\))，是以這裡不考慮等式限制的情況。式（8）轉化的無限制的拉格朗日函數如下所示：
L(\boldsymbol{w}, b, \boldsymbol{\alpha} ) = \frac{1}{2}\Vert \boldsymbol{w} \Vert^2 +\sum_{i = 1}^{m} \alpha_i (1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) )
其中 \(\boldsymbol{\alpha} = [\alpha_1, \alpha_2, ..., \alpha_m]^T\) 為拉格朗日乘子，且 \(\alpha_i \ge 0, i = 1,2,..., m\)。然後，我們令
\theta(\boldsymbol{w}) = \max_{\alpha_i \ge 0} L(\boldsymbol{w}, b, \boldsymbol{\alpha} )
當樣本點不滿足限制條件時，即在可行解區域外：
y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) < 1
此時我們将 \(\alpha_i\) 設定為正無窮，此時 $\theta(\boldsymbol{w}) $ 顯然也是正無窮。
當樣本點滿足限制條件時，即在可行解區域内：
y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1
此時，\(\alpha_i (1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) ) \le 0\)，想要最大化 $\theta(\boldsymbol{w}) $，這一項為 0 即可，即此時 $\theta(\boldsymbol{w}) = \frac{1}{2}\Vert \boldsymbol{w} \Vert^2 $。是以 $\theta(\boldsymbol{w}) $ 可以寫成如下形式：
\theta(\boldsymbol{w}) =
\frac{1}{2}\Vert \boldsymbol{w} \Vert^2, & \boldsymbol{x}_i \in 可行域; \cr
+\infty, & \boldsymbol{x}_i \in 不可行域, \quad i = 1,2,...m.
自此，我們建立了一個在可行域内和原目标函數相同，在可行域外函數值趨近無窮大的新函數。
現在我們的問題變成了求新函數的最小值：
\min_{\boldsymbol{w}, b} \theta(\boldsymbol{w}) =\min_{\boldsymbol{w}, b} \max_{\alpha_i \ge 0} L(\boldsymbol{w}, b, \boldsymbol{\alpha} ) = p^*
這裡的 \(p^*\) 表示這個問題的最優值，和原目标函數的最優值是一樣的。
2.3 拉格朗日對偶
在式（15）中，我們先求最大值，再求最小值，在求最大值面臨的是含有未知參數 \(\boldsymbol{w}, b\) 的，而且 \(\alpha_i \ge 0\) 又是不等式限制，如果此時我們要對 \(\alpha_i\) 求偏導，那麼有多少個樣本就要求多少個偏導，這個求解過程不好做。是以，我們需要使用拉格朗日函數對偶性，将最小和最大的位置交換一下，這樣就變成了：
\max_{\alpha_i \ge 0} \min_{\boldsymbol{w}, b} L(\boldsymbol{w}, b, \boldsymbol{\alpha} ) = d^*
式（16）是式（15）的對偶問題，這個新問題的最優值用 \(d^*\) 表示。顯然有 \(d^* \le p^*\)，這稱為“弱對偶性”成立；若 \(d^* = p^*\)，則稱為“強對偶性”成立，此時由對偶問題能獲得主問題的最優下界。對于一般的優化問題，強對偶性通常不成立。但是若主問題是凸優化問題，如式（8）中 $\frac{1}{2} \Vert \boldsymbol{w} \Vert^2 $ 和 $1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) $ 均為凸函數，且其可行域中至少有一個點使不等式限制嚴格成立（即至少存在一個 \(\boldsymbol{w}, b\)，使得 \(1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) < 0\) 成立），則此時強對偶性成立。
令 \(L(\boldsymbol{w}, b, \boldsymbol{\alpha} )\) 對 \(\boldsymbol{w}\) 和 \(b\) 分别求偏導可得：
\boldsymbol{w} = \sum_{i = 1}^m \alpha_i y_i \boldsymbol{x}_i
0 = \sum_{i = 1}^m \alpha_i y_i
将公式（17）代入公式（10），即可将 \(L(\boldsymbol{w}, b, \boldsymbol{\alpha} )\) 中的 \(\boldsymbol{w}\) 和 \(b\) 消去，再考慮式（18）的限制，就得到式（8）的拉格朗日對偶問題：
& \max_{\boldsymbol{\alpha}} & \sum_{i = 1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j = 1}^m \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j \\
& s.t. & \sum_{i = 1}^m \alpha_i y_i = 0 , \\
& & \alpha_i \ge 0, \quad i = 1,2, \dots, m.
\end{split}\tag{19}
現在我們的優化問題如公式（19）所示，我們隻需要求出 \(\alpha_i\)，然後将其代入公式（17）求出 \(\boldsymbol{w}\)，然後找個支援向量帶入公式（9）算出 \(b\)。（支援向量代入公式（9）會得到 \(f(\boldsymbol{x} ) = \pm1\)，此時随便一個支援向量 \(\boldsymbol{x}^*\) 都能解出 $b = f(\boldsymbol{x}^* ) - \boldsymbol{w}^T \boldsymbol{x}^* = \pm1 - \boldsymbol{w}^T \boldsymbol{x}^* $。）而求解 \(\alpha_i\)，一般會用 SMO 算法。（這裡不再展開）
最後得到的 SVM 判别函數為：
f(\boldsymbol{x} ) & = \boldsymbol{w}^T \boldsymbol{x} + b \\
& = \sum_{i = 1}^m \alpha_i y_i \boldsymbol{x}_i^T \boldsymbol{x}_i +b
\end{split}\tag{20}
這就結束了嗎？還沒有，注意到公式（8）中有不等式限制，是以上述過程需滿足 KKT（Karush-Kuhn-Tucker）條件，即要求
\[\begin{cases}
\alpha_i \ge 0; \cr
1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \le 0; \cr
\alpha_i (1 - y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) = 0 .
\end{cases}\tag{21}
具體 KKT 條件的由來這裡不做論述，但需要明白，如果目标函數求得了最優解，則 KKT 條件一定會滿足，即 KKT 條件是最優解的必要條件。
于是，對于任意的訓練樣本 \((\boldsymbol{x}_i, b_i)\)，總有 \(\alpha_i = 0\) 或者 $y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) = 1 $。若 \(\alpha_i = 0\)，則該樣本将不會出現在式（20）的求和中出現，也就不會對 \(f(\boldsymbol{x} )\) 有任何影響；若 \(\alpha_i > 0\)，則必有 $y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) = 1 $，所對應的樣本點在位于最大間隔邊界上，是一個支援向量。這裡顯示出 SVM 的一個重要性質：訓練完成後，大部分的訓練樣本都不需要保留，最終模型僅與支援向量有關。
References
《機器學習》周志華
機器學習實戰教程（八）：支援向量機原理篇之手撕線性SVM -- Jack Cui
深入了解拉格朗日乘子法（Lagrange Multiplier) 和KKT條件 -- xianlingmao
支援向量機（SVM）必備知識(KKT、slater、對偶）-- feilong_csdn
作者：wuliytTaotao
出處：https://www.cnblogs.com/wuliytTaotao/
本作品采用知識共享署名-非商業性使用-相同方式共享 4.0 國際許可協定進行許可，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接。