SVM推導筆記（一）

04-03

第一部分只記錄在線性可分情況下涉及的一些問題

線性可分是指可以用一條線或一個平面或一個超平面將數據分成兩部分，相反，如果不可以，則線性不可分。這樣的直線或（超）平面可以用下式表示

$w_{1} cdot x_{1}+w_{2}cdot x_{2}+cdotcdotcdot+w_{n}cdot x_{n}+b=0$ 向量表示為： $w^{T} cdot x+ b=0$

上圖中黃色的線將圓圈和三角分成兩部分，是線性可分情況。SVM在這種情況下的目的是：找到一條直線，使得【離這條直線最近的兩個點】的【點到直線距離】相等且最大。也就是上圖中用紅色和黃色分別圈起來的兩個點，這兩個點離紅色線的距離相等且最大。最終找出的直線就是上圖中紅色這條線。

樣本空間中任意點到直線的距離公式為：

$frac{|w_{1} cdot x_{1} + w_{2} cdot x_{2} +cdotcdotcdot +w_{n} cdot x_{n} +b|} {sqrt{w_{1}^{2}+w_{2}^{2}+cdotcdotcdot+w_{n}^{2}}}$

用向量表示則為： $frac{|w^{T} cdot x+ b|}{||w||}$

設 $x_{circ}$ 為圓圈類中離直線最近的點（黃色圈起來的點）， $x_{ riangle}$ 為圓圈類中離直線最近的點（紅色圈起來的點），對於黃色直線來說，它的參數 $w,b$ 可以將數據正確分類，那麼可以同時調整 $w,b$ （這個調整方式就是同時乘或除以某個數），在直線不變的情況下，使得 $|w^{T} cdot x_{circ}+ b|=1$ ，這樣變換的目的在於將 $|w^{T} cdot x+ b|$ 這個式子從距離公式中消去，更方便計算，此時 $x_{circ}$ 距離黃色線的距離變為 $frac{1}{||w||}$ ，可以理解為距離直線最近的點的距離變為 $frac{1}{||w||}$ 。

那麼對與圓圈類中任意點，存在 $|w^{T} cdot x+ b|geq1$ 。對於三角類來說， $x_{ riangle}$ 距離黃色直線更遠，所以對於所有的三角類來說，同樣滿足 $|w^{T} cdot x+ b|geq1$ 。為了方便計算，把絕對值消去，假設圓圈類為-1類，三角類為+1類（也就是對於所有圓圈數據，y=-1，對於所有三角數據，y=+1），再次調整 $w,b$ 使得 $w^{T} cdot x_{circ}+ bleq-1$ （這個調整方式就是如果 $w,b$ 不滿足 $w^{T} cdot x_{circ}+ bleq-1$ 則 $w,b$ 同時乘-1，其實這個調整就是當直線的一側大於0，另一側小於0時，同乘-1可以反轉過來）那麼在三角類中 $w^{T} cdot x_{ riangle}+ bgeq+1$ ，這時對y的假設就派上用場了，在所有數據中 $y cdot (w^{T} cdot x+ b)geq1$ 成立。

總結一下，對於所有能將數據正確分類的，且離最近點距離為1的直線來說，統統滿足 $y cdot (w^{T} cdot x+ b)geq1$ ，但為了使最近距離最大，使 $frac{1}{||w||}$ 最大就好了。所以此問題可以描述為：

$max frac{1}{||w||}$

$s.t. y_{i}(w^{T}x_{i}+b) geq1$ $,i=1,2,...,m$

其中 $max frac{1}{||w||}$ 可變為 $minfrac{1}{2}||w||^{2}$ 使問題不變，此變化為了方便求導和求解。上述問題可歸為凸二次規劃（convex quadratic programming）問題，可以通過現成的計算包求解，但我們可以用拉格朗日乘子法得到其「對偶問題」。要注意一點，這裡的拉格朗日乘子法和我們高中所學到的不太一樣，高中所學的拉格朗日乘子法的約束條件為等式 $h_{i}(x)=0$ ,這裡的約束條件為不等式，但仍然可以用拉格朗日函數將約束條件和目標函數融合在一起。這裡寫下構造後的拉格朗日函數：

$L(w,b,alpha)=frac{1}{2}||w||^2+Sigma_{i=1}^{m}alpha_{i}(1-y_{i}(w^{T}x_{i}+b))$ 其中 $alpha_igeq0$

再構造 $E(w) = max L(w,b,alpha)$ ，這個函數的意思是通過調整 $alpha$ 的大小，使 $L$ 最大。當不滿足約束條件時，令 $alpha=infty$ 則可以使 $E(w)=infty$ ；當滿足約束條件時， $1-y_{i}(w^{T}x_{i}+b)$ 總是小於或等於0，這時想要使 $L$ 最大，則可以令 $alpha=0$ ，得 $E(w) = frac{1}{2}||w||^2$ 。那麼我們的目標函數也因此變為:

$minE(w)=minmaxL(w,b,alpha)=p^*$

為了方便求解，這個問題可以變換為對偶問題 $d^*=maxminL(w,b,alpha)$ ，在滿足一定條件的情況下（KKT & slater）， $p^*=d^*$ ，可以先對 $w,b$ 求 $L$ 的極小，然後再對 $alpha$ 求 $L$ 的極大。

首先，固定 $alpha$ ，對 $w,b$ 求偏導數，並領其為0。這裡 $w$ 是個向量，對其求偏導應是對其各個分量分別求偏導。 $frac{1}{2}||w||^2=frac{1}{2}w_1^2+frac{1}{2}w_2^2+...+frac{1}{2}w_n^2$ , 分別對 $w_1,w_2,...,w_n$ 求偏導可得 $(w_1,w_2,...,w_n) = w$ 。可以得到