SVM（支持向量機）—— 原理

代碼請移步：SVM-SMO —— 代碼

線性可分

首先對於線性可分的數據必然存在一個分離超平面能夠把數據完全正確的分開，我們的目標就是要求該分離超平面的形式。前面的感知器通過最小化分錯的點到超平面的距離

$egin{split} & underset{w,b}{min} - sum_{x_iin M}frac{y_i(wcdot x_i+b)}{|w|} \ = & underset{w,b}{min} -sum_{x_iin M}y_i(wcdot x_i + b) end{split}$ 為所有被分離超平面錯誤分類的點的集合。上式中個人感覺因為上面的式子不好算所以用了下面的式子來代替，然後用迭代的方法更新，但這時得到的解不是唯一的，有無窮多個，線性可分的SVM用間隔最大化來求解分離超平面，相當於在原始感知器的基礎上加了一個間隔最大化的條件，使解是唯一的

對於超平面樣本點的函數間隔為

$hat{gamma}_i = y_i(wcdot x_i + b)$ 但對於函數間隔來說，當等比例變化時表示的該超平面不變，但函數間隔變為原來的倍，故不能直接用函數間隔來表示

現有間隔表示幾何上點到超平面的距離

$egin{split} gamma_i & = frac{y_i(wcdot x_i + b)}{|w|} \ & = frac{hat{gamma_i}}{|w|} end{split}$ 相當於在函數間隔上對超平面加了一個約束。

由此SVM表示為了最大化樣本點中最小的幾何間隔

$egin{split} & underset{w,b}{max} left{ underset{i}{min}frac{y_i(wcdot x_i+b)}{|w|} ight} \ = & underset{w,b}{max}left{ frac{1}{|w|}underset{i}{min} y_i(wcdot x_i + b) ight} = & underset{w,b}{max}left{ underset{i}{min} gamma_i ight} \ = & underset{w,b}{max}left{frac{1}{|w|} underset{i}{min} hat{gamma}_i ight} end{split}$ 由於當成比例的變化時函數距離 $hat{gamma}_i = lambda hat{gamma}_i$ 也成比例變化，但該超平面不變，幾何間隔也不變，故此時的函數間隔 $hat{gamma}_i$ 可取任意值，現取 $underset{i}{min}hat{gamma}_i=1$ ，也就是說樣本點到超平面的最小函數距離設為，故此時的優化問題變為 $egin{split} & underset{w,b}{max} frac{1}{|w|} \ & s.t. quad y_i(wcdot x_i + b) geq 1 quad ext{//保證最小函數間隔為1} end{split}$ 該優化問題等價於

$egin{split} & underset{w,b}{min} frac{1}{2}|w|^2 \ & s.t. quad y_i(wcdot x_i + b) geq 1 end{split}$ 這樣就消去了上面的最小化間隔形式中的，轉變成了一個單純的二次優化問題，該優化問題存在不等式約束故需要用KKT條件，現插播一下KKT條件

KKT條件 —— 鬆弛變數法

KKT條件使用鬆弛變數法推出來的，現有優化問題

$egin{split} underset{x}{min}& f(x) \ &s.t. left{egin{matrix} h_i(x) = 0 & i = 1,cdots,N_h \ g_i(x) le 0 & i = 1,cdots, N_g end{matrix} ight. end{split}$ 用鬆弛變數使不等式約束轉變為等式約束

然後根據拉格朗日乘子法得到

$egin{split} L(x, alpha, eta, a) = f(x) + sum_{i=1}^{N_h}alpha_ih_i(x) + sum_{i=1}^{N_g}eta_i(g_i(x)+a_i^2) end{split}$ 然後求偏導 $egin{split} frac{partial L}{partial x} & = abla f + sum_{i=1}^{N_h}alpha_i abla h_i + sum_{i=1}^{N_g}eta_i abla_i g_i = 0 \ frac{partial L}{partial a_i} & = 2eta_ia_i = 0 end{split}$ 得到，現在可分為兩種情況

：此時不等式約束不起作用
：此時不等式約束退化為等式約束

所以等價於或者也就消去了鬆弛變數故此時有

$egin{split} L(x,alpha,eta) & = f(x) + sum_{i=1}^{N_h}alpha_ih_i(x) + sum_{i=1}^{N_g}eta_ig_i(x) end{split}$ 並且對應的KKT條件為

$left{egin{split} & abla f + sum_{i=1}^{N_h} alpha_i abla h_i + sum_{i=1}^{N_g}eta_ig_i = 0 \ & h_i(x) = 0 \ & g_i(x) le 0 \ & eta_i g_i(x) = 0 \ & alpha_i geq 0 \ & eta_i geq 0 end{split} ight.$

對偶

由上一節可以得到

$L(w,b,alpha) = frac{1}{2}|w|^2 - sum_{i=1}^Nalpha_iy_i(wcdot x_i+b) + sum_{i=1}^N alpha_i$ 並且對應的KKT條件為

$left{egin{split} & frac{partial L}{partial w} = w - sum_{i=1}^N alpha_iy_ix_i = 0 \ & frac{partial L}{partial b} = - sum_{i=1}^N alpha_iy_i = 0 \ & alpha_i(y_i(wcdot x_i+b) - 1) = 0 \ & y_i(wcdot x_i +b) geq 1 \ & alpha_i geq 0 end{split} ight.$ 故現在優化問題變為一個極小極大問題

其與一個極大極小問題對應

由上面的KKT條件可以消去裡面的 $w = sum_{i=1}^N alpha_iy_ix_i,b$

$egin{split} L(alpha) & = frac{1}{2}|w|^2 - sum_{i=1}^N alpha_iy_i(wcdot x_i + b) + sum_{i=1}^N alpha_i \ & = frac{1}{2}sum_{i=1}^Nsum_{j=1}^N alpha_ialpha_jy_iy_j(x_icdot x_j) - sum_{i=1}^Nsum_{j=1}^N alpha_ialpha_jy_iy_j(x_icdot x_j) - bsum_{i=1}^Nalpha_iy_i + sum_{i=1}^N alpha_i \ & = -frac{1}{2}sum_{i=1}^Nsum_{j=1}^Nalpha_ialpha_jy_iy_j(x_icdot x_j) + sum_{i=1}^Nalpha_i end{split}$ 故現在優化問題變為

$egin{split} & underset{alpha}{max} L(alpha) = \ & underset{alpha}{min}-L(alpha) = \ & underset{alpha}{min} frac{1}{2} sum_{i=1}^Nsum_{j=1}^Nalpha_ialpha_jy_iy_j(x_icdot x_j) - sum_{i=1}^N alpha_i \ & s.t. left{egin{split} & sum_{i=1}^N alpha_iy_i = 0 \ & alpha_i geq 0 end{split} ight. end{split}$

支持向量

關於支持向量的圖示網上有很多這裡就不再畫一個了，只說下在優化的角度支持向量的解釋

支持向量是那些在分割帶邊緣的點，也即滿足最小化間隔的點，在上述的優化問題中就是滿足的點，支持向量有一個性質，SVM的解只與支持向量有關，而非支持向量的變化不改變SVM求解的超平面，再由前面的KKT條件的得到，支持向量需滿足，這時改點構成的約束起作用，並且該約束退化為等式約束也同樣表示了在分隔帶邊緣的點，而其他點滿足約束而，此時對應的約束失效，同樣表示為非支持變數的變化不影響最終優化的解