SVM 白板推導| 由最大間隔化目標演化的損失函數推導過程
SVM 英文名爲 Support Vector Machine，叫支持向量機，SVM 是一個二分類模型。算法
感知機學習算法會由於初始值不一樣而獲得不一樣的超平面，而 SVM 試圖尋找一個最佳超平面，來劃分數據，怎麼纔算最佳呢？咱們天然能想到，距離樣本點距離儘量的遠，模型的泛化性能和魯棒性更強爲最好，並且能夠找到一條惟一的超平面。函數
以下圖能夠看出，感知機的超平面能夠有無數條，SVM只要找到一條距離樣本點最大間隔的超平面便可。性能
SVM 目標
咱們知道，感知機是一個如今網上已經有不少最初被提出是爲了解決二分類問題，假設以下有正負樣本。學習
由此，咱們知道，SVM 的目標就是要找到一條間隔最大化的超平面，使得樣本點距離超平面儘量的遠，那麼，咱們如何找到間隔最大的超平面呢？優化
首先，咱們要先想到，間隔最大，便是求樣本點到超平面的距離。spa
而如今，咱們有 N 個樣本點，則咱們可能有 N 個距離，那咱們最終想要的就是，離超平面距離最小的樣本點的最大值。rem
既然是最大間隔分類器，咱們拆開來解釋：it
最大：找到距離樣本點最大的間隔class
間隔：N 個樣本點距離超平面的最小值變量
分類器：既然是二分類問題，那麼咱們的超平面就是要將樣本分開，對於超平面 $y=w^Tx+b$ 而言，咱們能夠假設有兩條超平面，一條是 $w^Tx+b>0$ 和 $w^Tx+b<0$，咱們能夠引入函數 $yi=\{_{-1}^{+1}$，將兩個超平面用一個函數表示，如圖。
如今就須要咱們想辦法計算樣本點到超平面的距離，以下圖，表示點 $(x_i,y_i)$ 到超平面 $y=w^Tx+b$ 的距離的計算，最終將目標轉化爲找到 N 個樣本點距離超平面的最小距離。
將 $min-distance(w,b,x)$ 代入 $max-margin(w,b)$，條件是 $y_i=w^Tx_i+b>0$，而且是恆大於0，由此，咱們能夠將下圖的式子轉換一下，將模去掉。
而且咱們還能看出，$\frac{1}{||w||}$ 與 $x_i$ 無關，咱們能夠將它提到前面去。
這樣一來，咱們的問題就轉化成求解一個帶約束的優化問題。對於條件 $y_i(w^Tx_i+b)>0$ 而言，必定存在一個 γ，使得 $min(y_i(w^Tx_i+b)>0)=γ$，爲了簡化計算，咱們能夠令 $y_i(w^Tx_i+b)=γ$。
假設令 γ=1，則咱們能夠獲得最終的式子只與 W 有關，咱們要求損失函數，則將其轉化成最小化問題。
可能有的人會疑惑，爲何 γ=1可行，咱們知道，$y=w^Tx+b$ 和$ y=2w^Tx+2b$ 表示的是同一個超平面，咱們若是將 2-範數 固定下來，這樣去指定 $y=w^Tx+b$ 的值是能夠肯定下來，不然有無窮多個，由於能夠隨機縮放，由於 γ > 0，因此不管 γ 等於多少，均可以任意比例縮放成 1，對整個等式無影響。
咱們能夠看到，目標函數是二次的，約束條件是線性的，因此它是一個帶約束的凸二次規劃問題，這個問題能夠用現成的 QP 優化包進行求解，一言以蔽之：在必定約束下，目標最優，損失最小。
引入拉格朗日乘子
經過拉格朗日乘子，咱們已經將帶約束的原問題轉化成了無約束的問題。
那麼什麼是拉格朗日對偶性呢？簡單來說，經過給每一個約束條件加上拉格朗日乘子 λ，定義拉格朗日函數 (經過拉格朗日函數將約束條件融合到目標函數中，從而只用一個函數表達式便能清楚的表達出咱們的問題)。
咱們能夠看到，原式子是一個關於 w 的凸二次函數，約束條件是 N 個關於 x 的不等式。經過引入拉格朗日乘子以後，咱們能夠將有約束問題轉化爲一個無約束的，只與 λ 有關的式子。
咱們能夠簡單的理解一下，爲何能夠這樣定義，假設以下是關於 w,b 的集合，咱們能夠將其表示爲兩個部分，一部分是 △>0，一部分是 △<=0。
當 △>0 時，即 $1-y_i(w^Tx_i+b)>0$，顯然 $maxL(w,b,λ)=\frac{1}{2}w^Tw+∞=∞$，此時，對於咱們求解無心義，咱們也得不到最小化的值。
當 △<=0 時，即 $1-y_i(w^Tx_i+b)<=0$，顯然 $maxL(w,b,λ)=\frac{1}{2}w^Tw+0=\frac{1}{2}w^Tw$，咱們能夠看到，與原問題相符。
因此，當咱們談到知足最優化的條件時，一般狀況都是 △<=0 的狀況。
此外，因爲這個問題的特殊結構，還能夠經過拉格朗日對偶性變換到對偶變量的優化問題，即經過求解與原問題等價的對偶問題獲得原始問題的最優解，這就是線性可分條件下支持向量機的對偶算法，這樣作的優勢在於：一是對偶問題每每更容易求解，二是能夠天然的引入核函數進而推廣到非線性分類問題。
對偶問題與原問題
這裏用 $p^*$ 表示原問題的最優解，且和最初的問題是等價的。若是直接求解，那麼一上來便得面對 $w,b$ 兩個參數，而 λ 又是不等式約束，這個求解過程很差作。不放把最小和最大的位置交換下。
交換之後的新問題是原問題的對偶問題，對偶問題的最優解用 $d^*$ 來表示，並且有 $d^* <= P^*$ ，在知足某些條件的狀況下，這二者相等，這個時候，口能夠經過求解對偶問題來間接求解原問題。
換言之，之因此從 $min$ $max$ 原始問題 $p^*$ 轉化爲 $max$ $min$ 的對偶問題 $d^*$，一者是由於 $d^*$ 是 $p^*$ 是近似解，兩者，轉化成對偶問題更容易求解。
下面能夠先求 $L$ 對 $w,b$ 的極小，再求 $L$ 對 λ 的極大。
KKT
上面提到 $d^* <= P^*$ 在知足某些條件的狀況下，二者相等，某些條件就是 KKT 條件。
對偶問題求解的 3 個步驟
1，固定 λ，讓 $L$ 關於 $w,b$ 最小化，對 $w,b$ 求偏導，令 $\frac{δL}{δw}=0$ 和 $\frac{δL}{δb}=0$。
將以上結果代入 L，最終結果咱們能夠看到，最終的結果只與 x 有關。
如何理解這一結果呢？咱們能夠看看 KKT 條件中的其中一個。
當 λ=0 時，此時的 L 只與 w 有關，對超平面無限制。
當 λ>0 時，此時 $1-y_i(w^Tx_i+b)=0$，由於 $yi=\{_{-1}^{+1}$，此時，L 與在邊界上的點有關，即只與支持向量有關。
2, 對 λ 求極大，便是關於對偶問題的最優化問題，通過上面的第一個步驟的求 w 和 b，獲得拉格朗日函數式子已經沒有了變量 w，b，只有 λ。
而且咱們也在以前求導過程當中求出了 w。
將上述式子代入 L 中，能夠求出 w 和 b
最終，咱們能夠獲得新的分類決策函數。
3, 在求得 $L(w,b,λ)$ 關於 $w$ 和 $b$ 最小化，以及對 $λ$ 極大以後，最後一步即是利用 SMO 算法求解對偶問題中的拉格朗日乘子 λ。
咱們的拉格朗日函數中，在 $λ_i={λ_1,λ_2,...,λ_n}$ 上求上述目標函數的最小值，爲了求解這些乘子，每次從中任意抽取兩個乘子 $λ_1,λ_2$，而後固定 $λ_1,λ_2$ 之外的乘子 $λ_i={λ_3,λ_4,...,λ_n}$，使得目標函數只關於 $λ_1,λ_2$ 的函數，這樣，不斷的從一堆乘子中任意抽取兩個求解，不斷的迭代求乘子問題，最終達到求解原問題的目的。
若是您以爲文章對你有幫助，歡迎點贊轉發關注。