簡(jiǎn)介：
支持向量機(jī)（SVM）是一種二分類的監(jiān)督學(xué)習(xí)模型，他的基本模型是定義在特征空間上的間隔最大的線性模型。他與感知機(jī)的區(qū)別是，感知機(jī)只要找到可以將數(shù)據(jù)正確劃分的超平面即可，而SVM需要找到間隔最大的超平面將數(shù)據(jù)劃分開。所以感知機(jī)的超平面可以有無數(shù)個(gè)，但是SVM的超平面只有一個(gè)。此外，SVM在引入核函數(shù)之后可以處理非線性問題。
SVM根據(jù)數(shù)據(jù)的不同可以分為以下三種形式：
1.線性可分支持向量機(jī)，也叫做硬間隔支持向量機(jī)，處理的數(shù)據(jù)是線性可分的，通過硬間隔最大化來學(xué)習(xí)一個(gè)線性可分的模型。
2.線性支持向量機(jī)，也叫做軟間隔支持向量機(jī)，當(dāng)數(shù)據(jù)近似線性可分時(shí)，通過引入松弛因子，軟間隔最大化學(xué)習(xí)一個(gè)線性可分的模型。
3.非線性支持向量機(jī)，當(dāng)數(shù)據(jù)線性不可分時(shí)，通過引入核函數(shù)將數(shù)據(jù)映射到高維空間后，學(xué)習(xí)得到一個(gè)非線性支持向量機(jī)。
線性可分支持向量機(jī)
考慮一個(gè)二分類問題，當(dāng)數(shù)據(jù)可以在分布空間中通過一個(gè)超平面將正負(fù)樣例分割開，一面為正類，一面為負(fù)類，我們就稱數(shù)據(jù)是線性可分，這個(gè)分離超平面的方程為：w*x+b=0。而在線性可分?jǐn)?shù)據(jù)中存在著無數(shù)個(gè)超平面可以將數(shù)據(jù)分割開（參考感知機(jī)），我們要找到其中最好的超平面，這個(gè)超平面不僅可以將訓(xùn)練集數(shù)據(jù)很好的劃分開，還有更好的泛化能力。下圖中很顯然直線B是最好的一條分割線，所以選擇間隔最大的一個(gè)超平面作為我們需要的最優(yōu)的超平面。
求解超平面w*x+b=0就是求w和b，以及對(duì)應(yīng)的分類決策函數(shù)f(x)=sign(w*x+b)，稱之為線性可分支持向量機(jī)。
根據(jù)點(diǎn)到直線距離公式：
其中A為w向量，C為b，因?yàn)槌矫娴膟值為0，所以對(duì)于支持向量機(jī)的點(diǎn)到超平面距離可以寫作：
又因?yàn)閣*x+b的邊界為正負(fù)1，兩個(gè)邊界到超平面的距離和γ等于2倍的r，所以圖3又可以寫作：
這就是幾何間隔。下圖是支持向量機(jī)的各個(gè)概念圖：
當(dāng)數(shù)據(jù)點(diǎn)為正類時(shí)，其y=+1，w*x+b>=+1，當(dāng)數(shù)據(jù)點(diǎn)為負(fù)類時(shí)y=-1，w*x+b<=-1，所以y*(w*x+b)始終大于等于1，其中y*(w*x+b)成為函數(shù)間隔。
要找到間隔最大的超平面，也就是要找到滿足y*(w*x+b)>=1約束條件的參數(shù)w和b，使得γ最大。即：
顯然為了最大化間隔，僅需最大化||w||，這等價(jià)于最小化||w||的2次方，所以可以重寫為：
其中目標(biāo)函數(shù)和約束函數(shù)都是連續(xù)可微的凸函數(shù)，并且目標(biāo)函數(shù)是二次函數(shù)，約束函數(shù)是仿射函數(shù)，所以該約束問題是一個(gè)凸二次規(guī)劃問題。
求解凸二次規(guī)劃約束問題常用的辦法是引入拉格朗日乘子，通過求解對(duì)偶問題得到原始問題的解。這就是線性可分支持向量機(jī)的對(duì)偶算法。
首先定義拉格朗日函數(shù)，對(duì)每個(gè)不等式約束引入拉格朗日乘子αi>=0,i=1,2,3....n.拉格朗日函數(shù)為：
這樣就把帶有約束問題的求極值問題轉(zhuǎn)為無約束求極值問題，接下來根據(jù)拉格朗日對(duì)偶性求解原始問題的對(duì)偶問題：
以上就是求解線性可分支持向量機(jī)的全部過程，求解得到w和b之后就可以得到分類超平面：
以及分類決策函數(shù)：
根據(jù)圖9中w*和b*的結(jié)果可以看出，w*和b*只依賴于αi>0對(duì)應(yīng)的(xi，yi)樣本點(diǎn)，這些樣本點(diǎn)稱為支持向量。
線性支持向量機(jī)
當(dāng)數(shù)據(jù)近似線性可分時(shí)，也就是說數(shù)據(jù)中存在噪聲點(diǎn)，我們通過引入松弛因子，使函數(shù)間隔加上松弛因子ξ后大于等于1，這樣約束條件就變成：
對(duì)于每個(gè)松弛因子ξi需要支付一個(gè)代價(jià)，所以目標(biāo)函數(shù)也就是代價(jià)函數(shù)變?yōu)椋?/p>
其中C>0稱為懲罰參數(shù)，是超參數(shù)需要我們手動(dòng)調(diào)參，C值越大時(shí)對(duì)誤分類的懲罰增大，支持向量機(jī)的間隔寬度越窄，C值越小時(shí)對(duì)誤分類的懲罰越小，支持向量機(jī)的間隔寬度越寬。而ξ的幾何意義代表著，誤分類數(shù)據(jù)點(diǎn)離正確分類一側(cè)的距離，是幾何距離。
那么這個(gè)松弛因子ξ是怎么來的呢？因?yàn)閿?shù)據(jù)是近似可分的存在著許多噪音點(diǎn)，所以當(dāng)計(jì)算代價(jià)函數(shù)時(shí)，這些誤分類點(diǎn)要算入代價(jià)函數(shù)中去。這些誤分類點(diǎn)的函數(shù)間隔y*(w*x+b)<=-1，所以代價(jià)函數(shù)可以寫成帶有0/1損失函數(shù)的集合函數(shù)，就是當(dāng)數(shù)據(jù)點(diǎn)的函數(shù)間隔減去1小于0的話(誤分類點(diǎn))，需要計(jì)算入代價(jià)函數(shù)，數(shù)據(jù)點(diǎn)的函數(shù)間隔減去1大于0的話(正確分類點(diǎn))，不需要計(jì)算入代價(jià)函數(shù)：
但是0/1損失函數(shù)的數(shù)學(xué)性質(zhì)不好，非凸非連續(xù)性。所以一般使用他的代替損失函數(shù)“hinge損失max(0,1-z)”代替它，則代價(jià)函數(shù)也就是目標(biāo)函數(shù)變?yōu)椋?/p>
用ξ替代max部分，就是ξ<=1-y*(w*x+b)，所以帶有約束條件的目標(biāo)(代價(jià))函數(shù)就變?yōu)橄旅娴男问剑?/p>
所以SVM的損失函數(shù)也可以看作是帶有L2正則項(xiàng)(||w||^2)的hinge損失函數(shù)。以上就是線性支持向量機(jī)的帶有約束條件的優(yōu)化目標(biāo)函數(shù)，求解w和b的過程與線性可分的方法一致，都是通過引入拉格朗日乘子，這里不再重復(fù)。其中一些列需要滿足的約束條件稱為KKT條件。
非線性支持向量機(jī)
當(dāng)數(shù)據(jù)樣本非線性可分時(shí)，也就是在當(dāng)前的數(shù)據(jù)空間內(nèi)（或者說當(dāng)前維度內(nèi)）無法找到一個(gè)超平面將數(shù)據(jù)分割開，那么需要我們將數(shù)據(jù)從當(dāng)前的維度映射到更高維度后，使數(shù)據(jù)變成線性可分的，而將數(shù)據(jù)映射到高維的函數(shù)稱之為核函數(shù)。
為什么在SVM求解帶有約束條件的最優(yōu)化問題時(shí)我們使用引入拉格朗日乘子方法，一是因?yàn)榍蠼夂?jiǎn)單，二是可以很方便的引入核函數(shù)K(x,z)。
通過引入核函數(shù)之后，對(duì)偶問題的目標(biāo)函數(shù)就變成：
最后求解出w*和b*之后的決策分類函數(shù)：
這樣通過核函數(shù)的引入，可以用求解線性支持向量機(jī)的方法求解非線性支持向量機(jī)。學(xué)習(xí)是隱式的，不是了解核函數(shù)是如何計(jì)算以及數(shù)據(jù)到底被映射到哪一維空間的，但是需要我們手動(dòng)的選擇核函數(shù)。常用的核函數(shù)有：
多項(xiàng)式核：
高斯核（徑向基核）:
線性核，sigmoid核以及其他核函數(shù)等。通常使用先驗(yàn)知識(shí)或者交叉驗(yàn)證的方式選擇核函數(shù)，但是如果無先驗(yàn)知識(shí)的情況下，一般選擇高斯核。為什么選擇高斯核呢？因?yàn)榭梢詫?shù)據(jù)映射到無窮維空間。
SMO序列最小最優(yōu)化
該學(xué)習(xí)方法是為了簡(jiǎn)單求解SVM中的參數(shù)的一個(gè)算法，并不是很重要（調(diào)包俠^-^），所以沒有很詳細(xì)的看，以后有時(shí)間看完再更新到本文中。
待更新。。
參考書籍:
《統(tǒng)計(jì)學(xué)習(xí)方法》李航 著
《機(jī)器學(xué)習(xí)》 周志華? 著
