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

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

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

函數(shù)間隔(function margin)定義：對于給定訓(xùn)練數(shù)據(jù)集T和超平面$(w, b)$,定義超平面$(w,b)$關(guā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中所有樣本點$(x_{i},y_{i})$的函數(shù)間隔之最小值，即$$widehat{gamma}=minwidehat{gamma _{i}}$$
幾何間隔(geimetric margin)定義：對于給定訓(xùn)練數(shù)據(jù)集T和超平面$(w, b)$,定義超平面$(w,b)$關(guān)于樣本點
$(x_{i},y_{i})$的幾何間隔為$$gamma _{i}=y_{i}(frac{w}{left | w ight |}cdot x_{i}+frac{b}{left | w ight |})$$
定義超平面$(w,b)$關(guān)于數(shù)據(jù)集T的幾何間隔為超平面$(w,b)$T中所有樣本點$(x_{i},y_{i})$的函數(shù)間隔之最小值，即$$gamma=mingamma _{i}$$
因為如果超平面參數(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ù)等價于$
$$minfrac{1}{2}left |w ight |^{2} hspace{0.5cm} s.t., gamma_{i}(w^{T}+b)geq 1$$

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

簡單來說，對于任意一個帶約束的優(yōu)化都可以寫成這樣的形式：

$$ 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ù)雜的形式的話，其實是一件很讓人頭痛的問題，為此我們希望把帶約束的優(yōu)化問題轉(zhuǎn)化為無約束的優(yōu)化問題。為此，我們定義 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)$$
容易證明，對于滿足約束條件的 x，有$f_0(x)=z(x)$，因為約束條件$h_i(x)=0$，即式子最后一項為0，又因為$lambdageq 0$且約束條件$f_i(x)leq 0$，因此式子的第二項最大值為0，所以L的最大值即$z(x)=f_0(x)$.
所以，帶約束條件的原問題(primal problem)轉(zhuǎn)換為不帶約束條件的優(yōu)化問題，即：
$$min_x z(x)$$
也即(記為$p^*$)：
$$p^*=min_x max_{lambdasucceq 0, u} L(x, lambda, u)$$
因為如果原始問題有最優(yōu)值，那么肯定是在滿足約束條件的某個 x? 取得，而對于所有滿足約束條件的$ x$ ，$z(x)$ 和 $f_0(x)$ 都是相等的。
這個原問題(primal problem)的對偶問題(dual problem)將$min$和$max$調(diào)換了位置(記為$d^*$)：
$$d^*=max_{lambdasucceq 0, u} min_x L(x, lambda, u)$$
可以證明$d^*leq p^*$，此這個性質(zhì)叫做弱對偶(weak duality) ，對于所有的優(yōu)化問題都成立。注意，無論原問題是什么形式，它的對偶問題總是凸優(yōu)化問題(convex optimization)。
強(qiáng)對偶(strong duality)即$d^*=p^*$，在SVM中滿足KTT(Karush-Kuhn-Tucker)條件，通過求解對偶問題間接求解原始問題。

根據(jù)上面的補充，繼續(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)換為對偶問題：
$$ max_{alpha_{i}succeq 0} min_{w,b} L(w, b, alpha)=d^*$$

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

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

$$ abla_{w}L(w, b, alpha)=0 hspace{0.6cm}和 hspace{0.6cm} abla_{b}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)補充如下：

接下來求$min_{w,b} L(w, b, alpha)$對 $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}$ 求解出來之后，即可求出 $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)替代，更加高效，暫時自己還沒有看懂，先放著。

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