昨天給自己打了一針雞血之後，今天說幹就幹！上午粗略地掃了一下周志華的西瓜書，感覺《支援向量機》這章寫的數學公式有點多，有點懵那啥(ノへ￣、)
支援向量機在高維或無限維空間中構造超平面或超平面集合，其可以用于分類、回歸或其他任務。直覺來說，分類邊界距離最近的訓練資料點越遠越好，因為這樣可以縮小分類器的泛化誤差。說白了，就是要基于訓練集在樣本空間中找一個劃分超平面，将不同類别的樣本分開。也可以了解為對原空間進行升維，把在本來次元上不可用一個平面分割的類别在更高的次元可分。為了更直覺的了解一下，請看下圖！
支援向量 (Support Vector)是指在訓練集 (Training data set)中，在分類時給予最多資訊的點集合，如下圖，被紅色框圍起來的這四個訓練資料點就被稱之為支援向量機。 支援向量就是與分類邊界距離最近的訓練資料點。從支援向量機的最佳化問題可以推導出一個重要性質：支援向量機的分類邊界可由支援向量決定，而與其他資料點無關。這也是它們稱為“支援向量”的原因。
對于二維資料集，将資料集分隔開的直線稱為分隔超平面，如果分隔的是三維的，分類的就是面，如果是更高維的就是超平面。支援向量機建構一個或多個高維（甚至是無限多元）的超平面來分類資料點，将分類的決策邊界統稱為超平面。分布在超平面一側的所有資料都屬于某個類别，而分布在另一側的所有資料都屬于另一個類别。好的分類邊界（也就是求的超平面）要距離最近的訓練點越遠越好，因為這樣可以減低分類器的泛化誤差。在支援向量機中，分類邊界與最近的訓練資料點之間的距離稱為間隔（margin），支援向量機的目标即為找出間隔最大的超平面來作為分類邊界。線性可分SVM就是在訓練集中學習得到一個線性分類器，也就是得到一個超平面：$f(x)=sign(\boldsymbol{\omega}^{T}\boldsymbol{x}+b)$,線性可分表明當$\boldsymbol{\omega}^{T}\boldsymbol{x}+b>0$時，對應的$f(x)=1$,相應的當$\boldsymbol{\omega}^{T}\boldsymbol{x}+b<0$時，對應的$f(x) = -1$,而$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=0$就是所要尋找的超平面，此時對應的超平面為硬間隔超平面。（關于硬間隔和軟間隔後文細說）
什麼是間隔（margin）？
對于于訓練樣本集$D = \{ (\boldsymbol{x_{1}},y_{1}),(\boldsymbol{x_{2}},y_{2}),...,(\boldsymbol{x_{m}},y_{m})\},y_{i}\epsilon\{-1 , +1\}$.在樣本空間$D$中，劃分超平面可通過如下線性方程來描述：
$$
\boldsymbol{\omega}^{T}\boldsymbol{x}+b=0,
其中$\boldsymbol{\omega}=(\omega_{1};\omega_{2};...;\omega_{d})$為法向量，決定了超平面的方向；$b$為位移項，決定了超平面與原點的距離。顯然，劃分超平面可以由$\boldsymbol{\omega}$和$b$唯一确定。設空間中任意一個樣本點到達超平面的距離 $λ$ , 假定對于一個點$x$ 它投影到超平面上對應的點為$x_{0}$，我們可以得出
x = x_{0} + \lambda\frac{\boldsymbol{\omega}}{||\boldsymbol{\omega}||},
其中$||\boldsymbol{\omega}||$為$\boldsymbol{\omega}$的二範數，可以了解為長度，$\frac{\boldsymbol{\omega}}{||\boldsymbol{\omega}||}$可以了解為機關法向量，又因為$x_{0}$是超平面上的點，是以有$\boldsymbol{\omega}^{T}\boldsymbol{x}_{0}+b = 0$,結合上式可以求得點$x$與超平面之間的距離關系
\lambda = \frac{|\boldsymbol{\omega}^{T}\boldsymbol{x}+b|}{||\boldsymbol{\omega}||}
注：$||\omega||_{2}(or ||\omega||)=(\sum_{i=1}^{n}|x_{i}|^{2})^{\frac{1}{2}}$
好了，假設我們得到了超平面$(\boldsymbol{\omega},b)$,那麼就可以進行以下的神操作來求間隔了！
首先，在左圖中找到兩個和這個超平面平行且距離相等的超平面：$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=-1$和$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=1$，保證在這兩個超平面之間沒有任何樣本點，這兩個超平面勢必包含的是距離分隔超平面最近的點（也就是支援向量），那麼問題就可轉化為最大化這兩個超平面之間的距離。它們之間的距離可表示為：$\gamma = \frac{2}{||\mathbf{w}||}$。這就是所謂的“間隔”了！那麼問題就是最大化$\left \| \boldsymbol{\omega}\right \|^{-1}$，可以轉化為最小化$\left \| \boldsymbol{\omega}\right \|^{2}$。最後結合兩個超平面之間沒有任何樣本點這個限制，則有：對于任何一個正樣本$y_{i}=+1$，它都要處在$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=1$這個超平面的右邊，即要保證：$y=\boldsymbol{\omega}^{T}\boldsymbol{x}+b\geqslant +1$，同理對于任何一個負樣本$y_{i}=-1$，它都要處于$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=1$的左邊，也就是要保證：$y=\boldsymbol{\omega}^{T}\boldsymbol{x}+b\leqslant -1$，于是可以合并為：$y_{i}(\boldsymbol{\omega}^{T}\boldsymbol{x}+b)\geqslant 1$。
于是尋找最優超平面的問題就可以轉化為二次規劃問題：
\left\{\begin{matrix} \underset{\boldsymbol{\omega},b}{min}\frac{1}{2}||\boldsymbol{\omega}||^{2}\\ s.t. y_{i} (\boldsymbol{\omega}^{T}\boldsymbol{x}+b ) \geqslant 1 ,i = 1,2,...,m\end{matrix}\right.\;(3)
這就是支援向量機（SVM）的基本型。
上文說到尋找最優超平面的問題就可以轉化為二次規劃問題，準确的來講，因為目标函數是一個二次的，限制條件是線性的，是以它是一個凸的二次規劃（convex quadratic programming）問題。能直接用二次規劃函數包解決，但是對于這個問題的求解我們有更高效的解法——拉格朗日對偶（Langrange Dual），原因如下：
原問題下，求解算法的複雜度與樣本次元（等于權值$\boldsymbol{\omega}$的次元）有關，而在對偶問題下，求解算法的複雜度與樣本數量（等于拉格朗日算子a的數量）有關
如果做線性分類，且樣本次元低于樣本數量的話，在原問題下求解就好了；但如果做非線性分類，那就會涉及到升維（比如使用高斯核做核函數，其實是将樣本升到無窮維），升維後的樣本次元往往會遠大于樣本數量，此時顯然在對偶問題下求解會更好。
支援向量機中用到了高維映射，但是映射函數的具體形式幾乎完全不可确定，而求解對偶問題之後，可以使用核函數來解決這個問題。
好吧，說了這麼多優點，還是來見識一下“拉格朗日對偶”吧！
拉格朗日乘子法很多人在大一的高數課就應該學過，當時是用來求極值的（其實這裡也是求極值(/▽＼)），是一種尋找多元函數在一組等式限制下極值的方法，通過引入拉格朗日乘子，可以将有$d$個變量與$k$個限制條件的最優化問題轉化為具有轉化為具有$d+k$個變量的無限制優化問題求解。所謂對偶問題，簡單來說就是要求這個問題的解可以通過求另外一個問題來得出。
首先将原模型的每條限制添加拉格朗日乘子$\alpha_{i}$，則該問題的拉格朗日函數可以寫為
L (\boldsymbol{\omega},b,\boldsymbol{\alpha}) = \frac{1}{2}\left \| \boldsymbol{\omega} \right \|^{2} + \sum_{i = 1}^{m}\alpha_{i}(1-y_{i}(\boldsymbol{\omega}^{T}\boldsymbol{x}_{i}+b)),\;(2)
其中，$\boldsymbol{\alpha}=(\alpha_{1};\alpha_{2};...;\alpha_{m}).$令$L (\boldsymbol{\omega},b,\boldsymbol{\alpha}) $對$\boldsymbol{\omega}$和$b$求偏導為零可得
\frac{\partial L}{\partial \boldsymbol{\omega}} = 0 \rightarrow w = \sum_{i = 1}^{m}\alpha_{i}y_{i}\boldsymbol{x}_{i}
\frac{\partial L}{\partial b} = 0 \rightarrow \sum_{i = 1}^{m}\alpha_{i}y_{i} = 0
證明過程如下
\frac{\partial L (\boldsymbol{\omega},b,\boldsymbol{\alpha})}{\partial \boldsymbol{\omega}}
= \frac{\partial \frac{1}{2}\boldsymbol{\omega}^{T}\boldsymbol{\omega}}{\partial \boldsymbol{\omega}}-\sum_{i = 1}^{m}\frac{\partial \alpha_{i}y_{i}\boldsymbol{\omega}^{T}\boldsymbol{x}_{i}}{\partial \boldsymbol{\omega}}
=\boldsymbol{\omega}-\sum_{i = 1}^{m}\alpha_{i}y_{i}\boldsymbol{x}_{i}=0
注：求解過程要用到矩陣求導，之前寫過寫過一篇矩陣求導總結，強力推薦看！不是自吹自擂，反正，現在遇到的所有矩陣（向量）求導問題都能解決了！
将求導結果帶入對偶式$L$，可以得到
L (\boldsymbol{\omega},b,\boldsymbol{\alpha}) = \sum_{i = 1}^{n}\alpha_{i}- \frac{1}{2} \sum_{i= 1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\boldsymbol{x}_{i}^{T}\boldsymbol{x}_{j}
于是，我們就得到了原式的對偶問題
\underset{\alpha}{max}\sum_{i = 1}^{n}\alpha_{i}- \frac{1}{2} \sum_{i= 1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\boldsymbol{x}_{i}^{T}\boldsymbol{x}_{j}\;(1)
s.t.\;\sum_{i=1}^{m}\alpha_{i}y_{i}=0,\;\alpha_{i}\geqslant0,i=1,2...,m.
解出$\boldsymbol{\alpha}$後，求出$\boldsymbol{\omega}$與$b$即可得到模型
f(\boldsymbol{x})=\boldsymbol{\omega}^{T}\boldsymbol{x}+b
=\sum_{i=1}^{m}\alpha_{i}y_{i}\boldsymbol{x}_{i}^{T}\boldsymbol{x}+b.\;(4)
從對偶問題（1）解出的$\alpha_{i}$是式（2)中的拉格朗日乘子，它恰對應着訓練樣本$(\boldsymbol(x)_{i},y_{i}$。因為式（3）中有限制不等式，是以上述過程需滿足KKT條件，即要求
\left\{\begin{matrix}\alpha_{i} \geqslant 0\\y_{i}f(\boldsymbol{x}_{i})-1 \geqslant 0 \\ \alpha_{i}(y_{i}f(\boldsymbol{x}_{i})-1) = 0\end{matrix}\right.
于是，對于任意訓練樣本$\boldsymbol{x}_{i},y_{i}$,總有$\alpha_{i}=0$或$y_{i}f(\boldsymbol{x}_{i})=1$。若$\alpha_{i}=0$，則該樣本将不會在式（4）的求和中出現，也就不會對$f(x)$有任何影響；若$\alpha_{i}>0$，則必有$y_{i}f(\boldsymbol{x}_{i})=1$，所對應的樣本點位于最大間隔邊界上，是一個支援向量（可以看看前文的圖）。這顯示出支援向量機的一個充要性質：訓練完成後，大部分的訓練樣本都不需要保留，最終模型僅與支援向量有關。
前文在提到過拉格朗提對偶的優勢，在看完原始模型到對偶問題以及對偶模型化簡的推導，再次說明一下：原問題下，求解算法的複雜度與樣本次元（等于權值$\boldsymbol{\omega}$的次元）有關，而在對偶問題下，求解算法的複雜度與樣本數量（等于拉格朗日算子a的數量）有關。從推到的最後結果來看，我們是消除了$\boldsymbol{\omega}$，并将優化函數變為了關于拉格朗日乘子的二次規劃問題。
在周志華《機器學習》中提到了一個高效的算法——SMO（Sequential Minimal Optimization）。還在學習中(→_→).......
一邊學看周志華的這本《機器學習》裡“顯然”就給出的公式，一邊還要複習高數。。。尤其是SVM這章，就恨沒把高數書帶回家(ノへ￣、)
參考：
<a href="http://blog.csdn.net/xidiancoder/article/details/50913607">安東的技術部落格</a>
<a href="https://zh.wikipedia.org/wiki/">維基百科</a>
<a href="http://www.cnblogs.com/ybjourney/p/4740999.html">oYabea-機器學習（三）—支援向量機（1）</a>
周志華《機器學習》