機器學習：SVM（一）——線性可分支援向量機原理與公式推導

摘要： 原理 SVM基本模型是定義在特徵空間上的二分類線性分類器（可推廣為多分類），學習策略為間隔最大化，可形式化為一個求解凸二次規劃問題，也等價於正則化的合頁損失函式的最小化問題。求解演算法為序列最小最優化演算法（SMO） 當資料集線性可分時，通過硬間隔最大化，學習一個線性分類...

原理

• SVM基本模型是定義在特徵空間上的二分類線性分類器（可推廣為多分類），學習策略為間隔最大化，可形式化為一個求解凸二次規劃問題，也等價於正則化的合頁損失函式的最小化問題。求解演算法為序列最小最優化演算法（SMO）
• 當資料集線性可分時，通過硬間隔最大化，學習一個線性分類器；資料集近似線性可分時，即存在一小部分outlier，除這些點外，其他的樣本線性可分，此時通過軟間隔最大化，學習一個線性分類器；當資料集線性不可分時，將輸入對映到高維空間使得線性可分，利用原本空間中的核函式表示特徵向量對映到高維空間之後的內積，這種方法稱為核技巧，此時學習到非線性支援向量機。
• 函式間隔與幾何間隔
  一個點距離超平面遠近可以表示分類預測的確信程度，在超平面\(w \cdot x + b = 0\;({w^T}x + b = 0)\) 確定的情況下，\(|{w^T}x + b|\) 能夠相對錶示距離超平面的遠近，取正例\(y=+1\) ，負例\(y=-1\) ,則\(y({w^T}x + b)\) 可以表示分類正確性以及確信度。大小表示遠近，正負表示分類正確與否。
  超平面關於某個樣本點\((x_i,y_i)\) 的函式間隔為\[{\hat \gamma _i} = {y_i}(w \cdot {x_i} + b)\] 超平面關於訓練集的函式間隔為\[\hat \gamma= \mathop {\min {{\hat \gamma }_i}}\limits_{i = 1,2,...,N} \]
  在成比例改變\(w,b\) 時，函式間隔會變大，但此時超平面並沒有改變。因此需對法向量施加約束，從而有了幾何間隔。
  超平面關於某個樣本點\((x_i,y_i)\) 的幾何間隔為\[{\gamma _i} = {y_i}(\frac{{w \cdot x_i + b}}{{||w||}})\] 超平面關於訓練集的幾何間隔為\[ {\gamma } = \mathop {\min {\gamma _i}}\limits_{i = 1,2,..,N} \]
• 線性可分支援向量機選擇一個超平面將空間分成兩部分，一部分全部為正例，一部分全部為負例，要求幾何間隔最大。感知機的策略是誤分類數最小，因此滿足條件的超平面不唯一，有無窮多。而線性可分支援向量機基於幾何間隔最大的超平面唯一。
• 演算法描述
  輸入：線性可分訓練集\(T = \{ ({x_1},{y_1}),({x_2},{y_2}),...,({x_N},{y_N})\} ,{y_i} \in \{ + 1, - 1\} ,i = 1,2,..,N\)
  輸出：分離超平面和分類決策函式
  (1).構造並求解約束最優化問題\[\begin{array}{l} \mathop {\min }\limits_\alpha\;\;\;\;\;\frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i} \cdot {x_j}) - \sum\limits_{i = 1}^N {{\alpha _i}} } } \\ s.t.\;\;\;\;\;\;\;\sum\limits_{i = 1}^N {{\alpha _i}{y_i}}= 0\\ \;\;\;\;\;\;\;\;\;\;\;{\alpha _i} \ge \;0\;\;\;\;\;\;i = 1,2,...,N \end{array}\] 求得最優解\({\alpha ^*} = {(\alpha _1^*,\alpha _2^*,...,\alpha _N^*)^T}\)
  (2).計算\[{w^*} = \sum\limits_{i = 1}^N {\alpha _i^*{y_i}} {x_i}\] 並選擇一個\(\alpha _j^* > 0\) ，計算\[{b^*} = {y_i} - \sum\limits_{i = 1}^N {\alpha _i^*{y_i}({x_i}}\cdot {x_j})\]
  (3).求得分離超平面\[{w^*} \cdot x + {b^*} = 0\] 分類決策函式：\[f(x) = sign({w^*} \cdot x + {b^*})\]

公式推導

預備知識

• 拉格朗日函式與求解約束最優化問題。假設\(f(x),c_i(x),h_j(x)\) 是定義在\(R^n\) 上的連續可微函式，對於約束最優化問題\[\begin{array}{l} \mathop {\min }\limits_x f(x)\\ s.t.\;\;{c_i}(x) \le 0,\;\;i = 1,2,...,k\\ \;\;\;\;\;\;{h_j}(x) = 0,\;\;j = 1,2,...l \end{array}\] 首先引入拉格朗日函式\[L(x,\alpha ,\beta ) = f(x) + \sum\limits_{i = 1}^k {{\alpha _i}} {c_i}(x) + \sum\limits_{j = 1}^l {{\beta _j}} {h_j}(x),\;\;\;\;\;{\alpha _i} \ge0\] 則在\(x\) 滿足約束條件下\[\mathop {\min }\limits_x f(x) = \mathop {\min }\limits_x \;\mathop {\max }\limits_{\alpha ,\beta } L(x,\alpha ,\beta ),\;\;\;\;{\alpha _i} \ge 0\] 這樣一來，就把原始問題表示為廣義拉格朗日函式的極小極大問題。
• 對偶問題。記極小極大問題為原始問題，則其對偶問題為\(\mathop {\max }\limits_{\alpha ,\beta } \;\mathop {\min }\limits_x L(x,\alpha ,\beta )\) ，稱為廣義拉格朗日函式的極大極小問題。假設原始問題與極大極小問題函式都有最優值，兩者關係為前者最優值大於等於後者最優值。對應於最優值，存在可行解。當最優值相等時，兩個問題的可行解即為兩個問題的最優解。
• KKT條件。由上我們可以得出思路，當原始問題與對偶問題的最優值相等時，可行解為最優解，可用解對偶問題替代解原始問題。假設\(f(x),c_i(x)\) 為凸函式，\(h_j(x)\) 為仿射函式，並且不等式約束是嚴格可行的，則此時\(x^*\) 和\({\alpha ^*},{\beta ^{^*}}\) 分別是原始問題和最偶問題的充要條件是滿足KKT條件：\[\begin{array}{l} {\nabla _x}L({x^*},{\alpha ^*},{\beta ^*}) = 0\\ {\nabla _\alpha }L({x^*},{\alpha ^*},{\beta ^*}) = 0\\ {\nabla _\beta }L({x^*},{\alpha ^*},{\beta ^*}) = 0\\ {\alpha _i} \ge 0\\ {c_i}({x^*}) \le 0\\ {\alpha _i}{c_i}({x^*}) = 0\;\;\;\;\;\;\;i = 1,2,...,k\\ {h_j}({x^*}) = 0\;\;\;\;\;\;\;\;j = 1,2,...,l \end{array}\] 第五式為對偶互補條件！其中一個因子必為0。以線性可分支援向量機來看，第一個因子為零，樣本不會在求和中出現。第二個因子為零，樣本在間隔邊界上，此時為支援向量。同時保證了二式。

具體推導

在上面演算法描述中我們知道，要求出超平面只需要解決演算法描述中的(1)，後面超平面問題即可迎刃而解。關鍵是（1）怎麼得到的，下面推導為過程，其中用到了預備知識。

• 基於最大幾何間隔分離超平面可表示為\[\begin{array}{l} \mathop {\max }\limits_{w,b} \gamma \\ s.t.\;\;\;{y_i}(\frac{{w \cdot x + b}}{{\left\| w \right\|}}) \ge \gamma ,\;\;\;i = 1,2,..,N \end{array}\]
• 考慮到幾何間隔與函式間隔的關係，可將問題改寫為\[\begin{array}{l} \mathop {\max }\limits_{w,b} \frac{{\hat \gamma }}{{\left\| w \right\|}}\\ s.t.\;\;\;{y_i}(w \cdot x + b) \ge \hat \gamma ,\;\;\;i = 1,2,..,N \end{array}\]
• 函式間隔取值對最優化問題求解不影響，因此可取1，顛倒分子分母后，最大化與最小化等價，於是得到如下最優化問題\[\begin{array}{l} \mathop {\min }\limits_{w,b} \;\;\frac{1}{2}{\left\| w \right\|^2}\\ s.t.\;\;\;{y_i}(w \cdot x + b) - 1 \ge 0,\;\;\;i = 1,2,..,N \end{array}\]
• 構造拉格朗日函式\[L(w,b,\alpha ) = \frac{1}{2}{\left\| w \right\|^2} + \sum\limits_{i = 1}^N {{\alpha _i}} [1 - {y_i}(w \cdot {x_i} + b)] = \frac{1}{2}{\left\| w \right\|^2} - \sum\limits_{i = 1}^N {{\alpha _i}} {y_i}(w \cdot {x_i} + b) + \sum\limits_{i = 1}^N {{\alpha _i}}，{\alpha _i} \ge 0 \] 此時，在約束條件下\[\mathop {\min }\limits_{w,b} \;\;\frac{1}{2}{\left\| w \right\|^2} = \mathop {\min }\limits_{w,b} \;\mathop {\max }\limits_\alphaL(w,b,\alpha ),{\alpha _i} \ge 0\] ，為極小極大問題。
• 對偶問題為極大極小問題\(\mathop {\max }\limits_\alpha \mathop {\min }\limits_{w,b} L(w,b,\alpha ),{\alpha _i} \ge 0\) ,我們知道普通條件下原問題是不能利用對偶條件來求解的，需要某些條件進行限定，即\(KKT\) 條件。因此我們給出限定約束如下：\[\begin{array}{l} {\nabla _w}L = 0\\ {\nabla _b}L = 0\\ {\alpha _i} \ge 0\\ {y_i}(w \cdot {x_i} + b) - 1 \ge 0\\ {\alpha _i}{y_i}(w \cdot {x_i} + b) = 0 \end{array}\]
• 此時我們只需求解對偶問題\[\mathop {\max }\limits_\alpha\mathop {\min }\limits_{w,b} L(w,b,\alpha ),{\alpha _i} \ge 0\] 即可。我們需要先求極小，將解帶入得到極小的函式值，再求極大。
  1.將拉格朗日求偏導並令其等於0\[\begin{array}{l} {\nabla _w}L = w - \sum\limits_{i = 1}^N {{\alpha _i}} {y_i}{x_i} = 0\\ {\nabla _b}L = \sum\limits_{i = 1}^N {{\alpha _i}{y_i} = } 0\\ \\ w = \sum\limits_{i = 1}^N {{\alpha _i}} {y_i}{x_i}\\ \sum\limits_{i = 1}^N {{\alpha _i}{y_i} = } 0 \end{array}\]
  2.帶入拉格朗日函式，可得\[\begin{array}{l} L = \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}} } {y_i}{y_j}({x_i} \cdot {x_j}) - \sum\limits_{i = 1}^N {{\alpha _i}} {y_i}[(\sum\limits_{j = 1}^N {{\alpha _j}} {y_j}{x_j}) \cdot {x_i} + b] + \sum\limits_{i = 1}^N {{\alpha _i}} \\ \;\;\; =- \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}} } {y_i}{y_j}({x_i} \cdot {x_j}) + \sum\limits_{i = 1}^N {{\alpha _i}} \end{array}\] ，即\[\;\;\min L\; =- \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}} } {y_i}{y_j}({x_i} \cdot {x_j}) + \sum\limits_{i = 1}^N {{\alpha _i}} \]
  3.對上式求極大，相當於加符號求極小，從而得到最終形式\[\begin{array}{l} \mathop {\min }\limits_\alpha\;\;\;\;\;\frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}} } {y_i}{y_j}({x_i} \cdot {x_j}) - \sum\limits_{i = 1}^N {{\alpha _i}} \\ s.t.\;\;\;\;\;\;\sum\limits_{i = 1}^N {{\alpha _i}{y_i} = } 0\\ \;\;\;\;\;\;\;\;\;\;{\alpha _i} \ge 0,\;\;\;\;\;i = 1,2,...,N \end{array}\]
  因此我們只需考慮求解上面的最終形式，從而進一步求得\(w,b\) 即可得線性可分支援向量機。這也是一個約束最優化問題，利用序列最小最優化演算法（SMO）即可求解。

總結

• 求解線性可分支援向量機，即利用SMO求解最終形式最優化問題，得到\(\alpha\) ,進一步求得\(w,b\) ，從而得到分離超平面和分類決策函式。其中的推導過程需要理解明白，單純記住一個最終模型沒有意義。