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

在《統計學習方法》中，這樣描述：

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

函數間隔(function margin)定義：對于給定訓練數據集T和超平面$(w, b)$,定義超平面$(w,b)$關于樣本點$(x_{i},y_{i})$的函數間隔為$$widehat{gamma _{i}}=y_{i}(wcdot x_{i}+b)$$
定義超平面$(w,b)$關于數據集T的幾何間隔為超平面$(w,b)$T中所有樣本點$(x_{i},y_{i})$的函數間隔之最小值，即$$widehat{gamma}=minwidehat{gamma _{i}}$$
幾何間隔(geimetric margin)定義：對于給定訓練數據集T和超平面$(w, b)$,定義超平面$(w,b)$關于樣本點
$(x_{i},y_{i})$的幾何間隔為$$gamma _{i}=y_{i}(frac{w}{left | w ight |}cdot x_{i}+frac{b}{left | w ight |})$$
定義超平面$(w,b)$關于數據集T的幾何間隔為超平面$(w,b)$T中所有樣本點$(x_{i},y_{i})$的函數間隔之最小值，即$$gamma=mingamma _{i}$$
因為如果超平面參數$w$和$b$成比例改變，雖然超平面不變，但是函數間隔離變了。因此使用幾何間隔，并且令$left | w ight |=1$，下圖為《機器學習》中的一張插圖。

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

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

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

$$ 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} $$

雖然約束條件能夠幫助我們減小搜索空間，但是如果約束條件本身就是比較復雜的形式的話，其實是一件很讓人頭痛的問題，為此我們希望把帶約束的優化問題轉化為無約束的優化問題。為此，我們定義 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)轉換為不帶約束條件的優化問題，即：
$$min_x z(x)$$
也即(記為$p^*$)：
$$p^*=min_x max_{lambdasucceq 0, u} L(x, lambda, u)$$
因為如果原始問題有最優值，那么肯定是在滿足約束條件的某個 x? 取得，而對于所有滿足約束條件的$ x$ ，$z(x)$ 和 $f_0(x)$ 都是相等的。
這個原問題(primal problem)的對偶問題(dual problem)將$min$和$max$調換了位置(記為$d^*$)：
$$d^*=max_{lambdasucceq 0, u} min_x L(x, lambda, u)$$
可以證明$d^*leq p^*$，此這個性質叫做弱對偶(weak duality) ，對于所有的優化問題都成立。注意，無論原問題是什么形式，它的對偶問題總是凸優化問題(convex optimization)。
強對偶(strong duality)即$d^*=p^*$，在SVM中滿足KTT(Karush-Kuhn-Tucker)條件，通過求解對偶問題間接求解原始問題。

根據上面的補充，繼續如下推導。
引入拉格朗日乘子(Lagrange multiplier)構造拉格朗日函數 ,( 其中拉格朗日乘子$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^*$$
轉換為對偶問題：
$$ 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)$ ：將拉格朗日函數$L(w, b, alpha)$分別對$w$,$b$求偏導數并令其等于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$$
將上面兩式帶入拉格朗日函數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}$$

詳細推導補充如下：

接下來求$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})$$
二次規劃求解可以使用更加優化的SMO(Sequential Minimal Optimization)替代，更加高效，暫時自己還沒有看懂，先放著。

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