1.線性可分SVM

感知機(jī)找出將線性可分?jǐn)?shù)據(jù)劃分開的超平面，線性可分SVM是在尋找最優(yōu)的那一條！

1.1 幾何角度看線性可分SVM

對(duì)與如圖2所示的線性可分?jǐn)?shù)據(jù)集，我們需要找一條可以將數(shù)據(jù)分開的直線，這樣的直線有很多。那么如何找到最優(yōu)的那一條呢？

圖2

圖2所示的兩個(gè)超平面都可以將訓(xùn)練數(shù)據(jù)劃分開，但是如果測(cè)試數(shù)據(jù)上出現(xiàn)了圖3的情況，綠線所示的超平面依然可以將數(shù)據(jù)劃分開，但是黑線所示的超平面的測(cè)試誤差就沒(méi)那么好了。

圖3

1.2 轉(zhuǎn)化為數(shù)學(xué)優(yōu)化問(wèn)題

我們通常使用硬間隔最大化的策略，下面我們進(jìn)行推導(dǎo)：
設(shè)訓(xùn)練集為 $(x_i,y_i)\in D$ ,超平面為 $w^Tx_i + b = 0$ 我們的目的就是找到最優(yōu)的 $w^T$ 和 $b$ 。
首先該超平面需要滿足條件：
$\begin{align} w^Tx_i +b>0,y_i&=+1 \\ w^Tx_i +b<0,y&=-1 \end{align} \rightarrow y_i (w^Tx_i+b)>0$
設(shè)： $\exists \alpha >0 \ s.t \ y_i (w^Tx_i+b)\ge \alpha$

則： $\frac {1}{\alpha}y_i (w^Tx_i+b)\ge \frac {\alpha}{\alpha}$

即： $y_i (\frac {1}{\alpha}w^Tx_i+\frac {1}{\alpha}b)\ge+1$

令： $\frac {1}{\alpha}w^T= w^T, \frac {1}{\alpha}b =b$

得： $y_i (w^Tx_i+b)\ge +1$ .........公式(1)

$d$ = $\frac {1}{||w||}|w^Tx_i+b|$ 為點(diǎn)到超平面的距離，距離超平面最近的點(diǎn)使得上式(1)等號(hào)成立。這些點(diǎn)稱為支持向量，兩個(gè)異類到超平面的距離的和為 $\frac {2}{||w||}$ 我們稱他為間隔。所以最大間隔策略可以表示為 $Max\frac {2}{||w||}$ 等價(jià)于 $Min{||w||} \rightarrow Min(ww^T )$ 所以優(yōu)化問(wèn)題轉(zhuǎn)化為：
$Min(ww^T )\ s.t \ y_i (w^Tx_i+b)\ge1$