摘要：簡(jiǎn)述在統(tǒng)計(jì)學(xué)習(xí)方法中，這樣描述支持向量機(jī)，是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，其學(xué)習(xí)策略便是間隔最大化，可形式化為一個(gè)凸二次規(guī)劃問(wèn)題的求解。求將拉格朗日函數(shù)分別對(duì)求偏導(dǎo)數(shù)并令其等于。

在《統(tǒng)計(jì)學(xué)習(xí)方法》中，這樣描述：

支持向量機(jī)（support vector machines，SVM）是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，其學(xué)習(xí)策略便是間隔最大化，可形式化為一個(gè)凸二次規(guī)劃（convex quadratic programming）問(wèn)題的求解。

函數(shù)間隔(function margin)定義：對(duì)于給定訓(xùn)練數(shù)據(jù)集T和超平面$(w, b)$,定義超平面$(w,b)$關(guān)于樣本點(diǎn)$(x_{i},y_{i})$的函數(shù)間隔為$$widehat{gamma _{i}}=y_{i}(wcdot x_{i}+b)$$
定義超平面$(w,b)$關(guān)于數(shù)據(jù)集T的幾何間隔為超平面$(w,b)$T中所有樣本點(diǎn)$(x_{i},y_{i})$的函數(shù)間隔之最小值，即$$widehat{gamma}=minwidehat{gamma _{i}}$$
幾何間隔(geimetric margin)定義：對(duì)于給定訓(xùn)練數(shù)據(jù)集T和超平面$(w, b)$,定義超平面$(w,b)$關(guān)于樣本點(diǎn)
$(x_{i},y_{i})$的幾何間隔為$$gamma _{i}=y_{i}(frac{w}{left | w ight |}cdot x_{i}+frac{left | w ight |})$$
定義超平面$(w,b)$關(guān)于數(shù)據(jù)集T的幾何間隔為超平面$(w,b)$T中所有樣本點(diǎn)$(x_{i},y_{i})$的函數(shù)間隔之最小值，即$$gamma=mingamma _{i}$$
因?yàn)槿绻矫鎱?shù)$w$和$b$成比例改變，雖然超平面不變，但是函數(shù)間隔離變了。因此使用幾何間隔，并且令$left | w ight |=1$，下圖為《機(jī)器學(xué)習(xí)》中的一張插圖。

得到的目標(biāo)函數(shù)如下
$$maxfrac{1}{left |w ight |} hspace{0.5cm} s.t., gamma_{i}(w^{T}+b)geq 1$$
$由于求frac{1}{left |w ight |}的最大值相當(dāng)于求frac{1}{2}left |w ight |^{2}的最小值，所以上面的目標(biāo)函數(shù)等價(jià)于$
$$minfrac{1}{2}left |w ight |^{2} hspace{0.5cm} s.t., gamma_{i}(w^{T}+b)geq 1$$

為了更好地理解接下來(lái)的內(nèi)容，這里插入一段有關(guān)對(duì)偶性(duality)的補(bǔ)充。詳情請(qǐng)見(jiàn)這篇文章，已經(jīng)清楚的伙伴可以跳過(guò)。

簡(jiǎn)單來(lái)說(shuō)，對(duì)于任意一個(gè)帶約束的優(yōu)化都可以寫(xiě)成這樣的形式：

$$ egin{aligned} min&f_0(x) s.t. &f_i(x)leq 0, quad i=1,ldots,m &h_i(x)=0, quad i=1,ldots,p end{aligned} $$

雖然約束條件能夠幫助我們減小搜索空間，但是如果約束條件本身就是比較復(fù)雜的形式的話，其實(shí)是一件很讓人頭痛的問(wèn)題，為此我們希望把帶約束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束的優(yōu)化問(wèn)題。為此，我們定義 Lagrangian 如下:
$$L(x,lambda, u)=f_0(x)+sum_{i=1}^mlambda_if_i(x)+sum_{i=1}^p u_ih_i(x)$$
令：
$$z(x)=max_{lambdasucceq 0, u}L(x,lambda, u)$$
容易證明，對(duì)于滿足約束條件的 x，有$f_0(x)=z(x)$，因?yàn)榧s束條件$h_i(x)=0$，即式子最后一項(xiàng)為0，又因?yàn)?lambdageq 0$且約束條件$f_i(x)leq 0$，因此式子的第二項(xiàng)最大值為0，所以L的最大值即$z(x)=f_0(x)$.
所以，帶約束條件的原問(wèn)題(primal problem)轉(zhuǎn)換為不帶約束條件的優(yōu)化問(wèn)題，即：
$$min_x z(x)$$
也即(記為$p^*$)：
$$p^*=min_x max_{lambdasucceq 0, u} L(x, lambda, u)$$
因?yàn)槿绻紗?wèn)題有最優(yōu)值，那么肯定是在滿足約束條件的某個(gè) x? 取得，而對(duì)于所有滿足約束條件的$ x$ ，$z(x)$ 和 $f_0(x)$ 都是相等的。
這個(gè)原問(wèn)題(primal problem)的對(duì)偶問(wèn)題(dual problem)將$min$和$max$調(diào)換了位置(記為$d^*$)：
$$d^*=max_{lambdasucceq 0, u} min_x L(x, lambda, u)$$
可以證明$d^*leq p^*$，此這個(gè)性質(zhì)叫做弱對(duì)偶(weak duality) ，對(duì)于所有的優(yōu)化問(wèn)題都成立。注意，無(wú)論原問(wèn)題是什么形式，它的對(duì)偶問(wèn)題總是凸優(yōu)化問(wèn)題(convex optimization)。
強(qiáng)對(duì)偶(strong duality)即$d^*=p^*$，在SVM中滿足KTT(Karush-Kuhn-Tucker)條件，通過(guò)求解對(duì)偶問(wèn)題間接求解原始問(wèn)題。

根據(jù)上面的補(bǔ)充，繼續(xù)如下推導(dǎo)。
引入拉格朗日乘子(Lagrange multiplier)構(gòu)造拉格朗日函數(shù) ,( 其中拉格朗日乘子$alpha=(alpha_{1},alpha_{2},...alpha_{n})^{T}$ )
$$L(w, b, alpha)=frac{1}{2}left |w ight |^{2}-sum_{i=1}^nalpha _{i}(gamma_{i}(w^{T}+b)-1)$$
要求解：
$$ min_{w,b} max_{alpha_{i}succeq 0} L(w, b, alpha)=p^*$$
轉(zhuǎn)換為對(duì)偶問(wèn)題：
$$ max_{alpha_{i}succeq 0} min_{w,b} L(w, b, alpha)=d^*$$

先求$L(w, b, alpha)$對(duì) $w$,$b$的極小，再求對(duì)$alpha$的極大。

求$min_{w,b} L(w, b, alpha)$ ：將拉格朗日函數(shù)$L(w, b, alpha)$分別對(duì)$w$,$b$求偏導(dǎo)數(shù)并令其等于0。

$$ abla_{w}L(w, b, alpha)=0 hspace{0.6cm}和 hspace{0.6cm} abla_L(w, b, alpha)=0$$
得到
$$w=sum_{i=1}^nalpha_{i}y_{i}x_{i} hspace{0.6cm}和 hspace{0.6cm}sum_{i=1}^nalpha_{i}y_{i}=0$$
將上面兩式帶入拉格朗日函數(shù)L，得到：
$$min_{w,b} L(w, b, alpha)=-frac{1}{2}sum_{i,j=1}^nalpha_{i}alpha_{j}y_{i}y_{j}x_{i}^Tx_{j}+sum_{i=1}^nalpha_{i}$$

詳細(xì)推導(dǎo)補(bǔ)充如下：

接下來(lái)求$min_{w,b} L(w, b, alpha)$對(duì) $alpha$的極大

$$ max-frac{1}{2}sum_{i,j=1}^nalpha_{i}alpha_{j}y_{i}y_{j}x_{i}^Tx_{j}+sum_{i=1}^nalpha_{i} s.t., alpha_{i}geq 0, i=1,...,n sum_{i=1}^nalpha_{i}y_{i}=0$$
將 $alpha^{*}=(alpha_{1},alpha_{2},...alpha_{n})^{T}$ 求解出來(lái)之后，即可求出 $w^{*}$ 和 $b^{*}$
$$w^{*}=sum_{i=1}^nalpha_{i}y_{i}x_{i}$$
$$b^{*}=y_{i}-sum_{i=1}^nalpha_{i}^{*}y_{i}(x_{i} cdot x_{j})$$
二次規(guī)劃求解可以使用更加優(yōu)化的SMO(Sequential Minimal Optimization)替代，更加高效，暫時(shí)自己還沒(méi)有看懂，先放著。

個(gè)人感覺(jué)SVM挺難理解的，前前后后參考了很多資料，感謝大神們的總結(jié)和指導(dǎo)，自己仍有不足，若有錯(cuò)漏歡迎指出。有引用部分，侵刪。
參考如下：
1.SVM三重境界
2.《統(tǒng)計(jì)學(xué)習(xí)方法》 李航
3.支持向量機(jī)：Duality
4.《機(jī)器學(xué)習(xí)》 周志華