簡介：

支持向量機(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，以及對應(yīng)的分類決策函數(shù)f(x)=sign(w*x b),，稱之為線性可分支持向量機(jī),。

根據(jù)點(diǎn)到直線距離公式：

其中A為w向量，C為b,，因?yàn)槌矫娴膟值為0,，所以對于支持向量機(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ī)劃約束問題常用的辦法是引入拉格朗日乘子,，通過求解對偶問題得到原始問題的解。這就是線性可分支持向量機(jī)的對偶算法,。

首先定義拉格朗日函數(shù),，對每個(gè)不等式約束引入拉格朗日乘子αi>=0,i=1,2,3....n.拉格朗日函數(shù)為：

這樣就把帶有約束問題的求極值問題轉(zhuǎn)為無約束求極值問題，接下來根據(jù)拉格朗日對偶性求解原始問題的對偶問題：

以上就是求解線性可分支持向量機(jī)的全部過程,，求解得到w和b之后就可以得到分類超平面：

以及分類決策函數(shù)：

根據(jù)圖9中w*和b*的結(jié)果可以看出,，w*和b*只依賴于αi>0對應(yīng)的(xi，yi)樣本點(diǎn),，這些樣本點(diǎn)稱為支持向量,。

線性支持向量機(jī)

當(dāng)數(shù)據(jù)近似線性可分時(shí)，也就是說數(shù)據(jù)中存在噪聲點(diǎn),，我們通過引入松弛因子,，使函數(shù)間隔加上松弛因子ξ后大于等于1，這樣約束條件就變成：

對于每個(gè)松弛因子ξi需要支付一個(gè)代價(jià),，所以目標(biāo)函數(shù)也就是代價(jià)函數(shù)變?yōu)椋?/p>
圖13

其中C>0稱為懲罰參數(shù),，是超參數(shù)需要我們手動(dòng)調(diào)參，C值越大時(shí)對誤分類的懲罰增大,，支持向量機(jī)的間隔寬度越窄,，C值越小時(shí)對誤分類的懲罰越小，支持向量機(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>
圖15

用ξ替代max部分,，就是ξ<=1-y*(w*x b),，所以帶有約束條件的目標(biāo)(代價(jià))函數(shù)就變?yōu)橄旅娴男问剑?/p>
圖16

所以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)榍蠼夂唵危强梢院芊奖愕囊牒撕瘮?shù)K(x,z),。

通過引入核函數(shù)之后,，對偶問題的目標(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)知識或者交叉驗(yàn)證的方式選擇核函數(shù),，但是如果無先驗(yàn)知識的情況下,，一般選擇高斯核。為什么選擇高斯核呢,？因?yàn)榭梢詫?shù)據(jù)映射到無窮維空間,。

SMO序列最小最優(yōu)化

該學(xué)習(xí)方法是為了簡單求解SVM中的參數(shù)的一個(gè)算法，并不是很重要（調(diào)包俠^-^）,，所以沒有很詳細(xì)的看,，以后有時(shí)間看完再更新到本文中。

待更新,。,。

參考書籍:

《統(tǒng)計(jì)學(xué)習(xí)方法》李航 著

《機(jī)器學(xué)習(xí)》 周志華? 著

《小象學(xué)院機(jī)器學(xué)習(xí)課程》 鄒博

?