Welcome To My Blog
支持向量機(jī)(support vector machine,SVM)是一種二分類模型,它的基本模型是定義在特征空間上的間隔最大的線性分類器,間隔最大使它有別于感知機(jī).
有3類支持向量機(jī)模型:
1. 線性可分支持向量機(jī)
2. 線性支持向量機(jī)
3. 非線性支持向量機(jī)
(這三種模型建立思路很像,求解過程不同)
一.線性可分支持向量機(jī)
幾何間隔與函數(shù)間隔的引出
超平面wx+b=0外一點(diǎn)x0到超平面的距離公式(幾何間隔):
分母是w的二范式,不隨x0的改變而改變,所以可以分子|wx0+b|能夠相對(duì)地表示點(diǎn)x0距離超平面wx+b=0的遠(yuǎn)近.
一個(gè)點(diǎn)距離分離超平面的遠(yuǎn)近可以表示分類預(yù)測(cè)的確信程度.
wx0+b的符號(hào)與類標(biāo)記y0的符號(hào)是否一致能夠表示分類是否正確.
所以,可用y0(wx0+b)來表示分類的正確性及確信度,這就是函數(shù)間隔(functional margin)
函數(shù)間隔
超平面(w,b)關(guān)于樣本點(diǎn)xi的函數(shù)間隔為:
超平面(w,b)關(guān)于訓(xùn)練集T的函數(shù)間隔為:
幾何間隔
超平面(w,b)關(guān)于樣本點(diǎn)xi的幾何間隔為:
超平面(w,b)關(guān)于訓(xùn)練集T的幾何間隔為:
硬間隔最大化
找到了超平面(w,b)關(guān)于訓(xùn)練集T的幾何間隔后,自然地希望最大化這個(gè)幾何間隔以保證之后分類預(yù)測(cè)的確信程度
目標(biāo)函數(shù)和約束如下:
約束表示超平面(w,b)關(guān)于任意樣本點(diǎn)的幾何間隔大于等于超平面(w,b)關(guān)于訓(xùn)練集T的幾何間隔
在約束中約去||w||并展開γ^
求出w,b的話問題就解決了,先別急,讓我們化簡(jiǎn)一下上面的式子
注意到,如果對(duì)w,b同比例的放縮,即變成kw,kb,函數(shù)間隔yi(wxi+b)也會(huì)成比例k變化,而超平面(w,b)沒有變化,
此時(shí)原問題和約束變?yōu)?
約掉k后,目標(biāo)函數(shù)和約束沒有改變,說明對(duì)w,b進(jìn)行同比例放縮絲毫不影響目標(biāo)函數(shù)和約束,那么可以選取合適的k讓函數(shù)間隔γ^=1,也就是
這樣一來,目標(biāo)函數(shù)和約束就變成了:
把||w||挪到分子上平方一下再乘個(gè)常數(shù)就有了:
比最初的形式簡(jiǎn)化了不少,這是個(gè)帶約束問題,通過Lagrange Multiplier拉格朗日乘子法化成無約束問題:
(原問題:極大極小)
具體原理可參考之前的文章Lagrange duality拉格朗日對(duì)偶性
對(duì)偶形式:
其中:
所以有:
進(jìn)而有(最終形式):
下面的約束是求 min L(w,b,α)時(shí)得到的
這是個(gè)凸二次規(guī)劃問題(目標(biāo)函數(shù)是二次函數(shù),不等式約束是仿射函數(shù))
求解得到α*=(α1,α2,...,αN)^t,這是對(duì)偶問題的解,
可由α*得到w*,b*
之所以能從對(duì)偶問題獲得原問題的解,是因?yàn)樵瓎栴}為凸二次規(guī)劃問題,并且解α*,w*,b* 滿足KKT條件
有了w*,b*就能得到最大間隔分離超平面和分類決策函數(shù):
支持向量
通過由α*得到w*,b*的公式可以知道,對(duì)應(yīng)α*=0的實(shí)例xi對(duì)超平面(w*,b*)的兩個(gè)參數(shù)都沒有貢獻(xiàn),只有對(duì)應(yīng)α*＞0的實(shí)例xi對(duì)超平面(w*,b*)的兩個(gè)參數(shù)有貢獻(xiàn),也就是說超平面完全由對(duì)應(yīng)α*＞0的實(shí)例決定,這些實(shí)例稱為支持向量,由KKT的互補(bǔ)條件知,若α*＞0,則有y(wx+b)-1=0,即wx+b=±1,說明支持向量都在間隔邊界上
小結(jié)
對(duì)于線性可分SVM學(xué)習(xí)來說:
- 模型為分離超平面和決策函數(shù)
- 學(xué)習(xí)策略:硬間隔最大化(間隔的描述及約束)
- 學(xué)習(xí)算法:凸二次規(guī)劃
二.線性支持向量機(jī)
通常情況下,訓(xùn)練數(shù)據(jù)中有一些特異點(diǎn)(outlier),將這些特異點(diǎn)去掉后,剩下的大部分樣本點(diǎn)組成的集合是線性可分的.線性不可分意味著不是所有點(diǎn)都滿足函數(shù)間隔大于等于1的約束,為解決這個(gè)問題,引入一個(gè)松弛變量ζi≥0,使函數(shù)間隔加上松弛變量后大于等于1.即,y(wx+b)+ζ≥1
軟間隔最大化
對(duì)每個(gè)松弛變量ζi,支付一個(gè)代價(jià)ζi,目標(biāo)函數(shù)變?yōu)?br>
這里C>0稱為懲罰參數(shù),C越大則對(duì)錯(cuò)誤分類的懲罰越大
最小化上述目標(biāo)函數(shù)實(shí)現(xiàn)的是軟間隔最大化,最小化上式包含兩層含義:使1/2||w||^2盡量小,即間隔盡量大,同時(shí)使誤分類點(diǎn)的個(gè)數(shù)盡量小.
硬間隔就是真正的間隔,軟間隔是包含了代價(jià)項(xiàng)ζ的硬間隔
由上分析便得到了線性支持向量機(jī)的學(xué)習(xí)目標(biāo):
化為拉格朗日形式(不帶約束)的原問題:
對(duì)偶問題:
其中:
進(jìn)而:
所以對(duì)偶問題的最終形式:
與線性可分SVM的對(duì)偶最終形式相比只是α的約束不同,約束增強(qiáng)了
求解得到α*=(α1,α2,...,αN)^t,這是對(duì)偶問題的解,
可由α*得到w*,b*
有了w*,b*就能得到最大間隔分離超平面和分類決策函數(shù):
支持向量
和線性可分SVM類似,超平面完全由對(duì)應(yīng)α*＞0的實(shí)例決定,這些實(shí)例稱為支持向量,但是線性SVM的支持向量不一定都在間隔邊界上
KKT互補(bǔ)條件之一:α*(y(w*x+b)+ζ-1)=0
當(dāng)0<αi<C時(shí),ζi=0,則y(w*x+b)-1=0,此時(shí)支持向量在間隔邊界上
當(dāng)αi=C時(shí),ζi>0,支持向量可能在:
間隔邊界與超平面之間:0<ζi<1
超平面上:ζi=1
誤分類一側(cè):ζi>1
Hinge Loss Function合頁損失函數(shù)
線性SVM的學(xué)習(xí)還有另一種等價(jià)模型,即最小化目標(biāo)函數(shù):
證明新目標(biāo)函數(shù)與原問題等價(jià)時(shí),主要抓住三點(diǎn):
1. hinge loss≥0
2. 令[1-y(wx+b)]_+=ζ
3. 討論1-y(wx+b)的取值范圍
L(y(wx+b))說明了:
1. 點(diǎn)到超平面的函數(shù)距離≥1時(shí),損失為0
2. 點(diǎn)到超平面的函數(shù)距離＜1時(shí),損失為1-y(wx+b)
下圖藍(lán)線代表hinge loss的圖像
小結(jié)
對(duì)于線性SVM學(xué)習(xí)來說:
- 模型為分離超平面和決策函數(shù)(線性SVM的對(duì)偶形式)
- 學(xué)習(xí)策略:軟間隔最大化(間隔的描述及約束)
- 學(xué)習(xí)算法:凸二次規(guī)劃
三.非線性支持向量機(jī)
用線性分類方法求解非線性分類任務(wù)分為兩步:
1. 將訓(xùn)練數(shù)據(jù)從輸入空間(歐式空間或離散集合)映射到新的特征空間(希爾伯特空間)使數(shù)據(jù)在新特征空間中線性可分
2. 在新特征空間中用線性分類學(xué)習(xí)方法從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)分類模型,使得輸入空間中的超曲面模型對(duì)應(yīng)特征空間中的超平面模型
Kernel trick(核技巧)便屬于這樣的方法
目標(biāo)
K(x1,x2)=φ(x1)φ(x2)是個(gè)對(duì)稱函數(shù),叫作正定核(positive definite kernel)
一般只定義K(x1,x2),而不顯式地定義φ(x),那么如何保證K(x1,x2)是正定核呢?
正定核的充要條件:
證明過程需要預(yù)備知識(shí):構(gòu)造希爾伯特空間
- 定義映射φ并構(gòu)成向量空間S(對(duì)加法和數(shù)乘運(yùn)算封閉的集合)
- 在S上定義內(nèi)積構(gòu)成內(nèi)積空間(用到了歐式空間Gram矩陣的半正定性)
- 將內(nèi)積空間S完備化為希爾伯特空間
由α*得到b*
分類決策函數(shù)
常用的核函數(shù)
正定核的充要條件在構(gòu)造核函數(shù)時(shí)很有用.但對(duì)于一個(gè)具體函數(shù)K(x,z)來說,檢驗(yàn)它是否為正定核并不容易,因?yàn)樾枰獙?duì)任意有限輸入集{x1,x2,...,xm}驗(yàn)證K對(duì)應(yīng)的Gram矩陣(在希爾伯特空間)是否為半正定的.實(shí)際問題中往往應(yīng)用已有的核函數(shù)
- 多項(xiàng)式核函數(shù)(polynomial kernel function)
34.png
對(duì)應(yīng)的支持向量機(jī)是一個(gè)p次多項(xiàng)式分類器,分類決策函數(shù)為:
35.png - 高斯核函數(shù)(Gaussian kernel function)
36.png
對(duì)應(yīng)的支持向量機(jī)是高斯徑向基函數(shù)(radial basis function)分類器,分類決策函數(shù)為:
37.png - 字符串核函數(shù)(string kernel function)
定義在字符串集合上的核函數(shù),字符串核函數(shù)應(yīng)用在文本分類,信息檢索,生物信息學(xué)等方面.
k_n(s,t)給出了字符串s和t中長(zhǎng)度等于n的所有子串組成的特征向量的余弦相似度(cosine similarity).直觀上,兩個(gè)字符串相同的子串越多,它們就越相似,字符串核函數(shù)的值就越大.字符串核函數(shù)可以由動(dòng)態(tài)規(guī)劃快速計(jì)算
SMO算法
SMO:sequential minimal optimization
利用SMO算法實(shí)現(xiàn)SVM的學(xué)習(xí)
SMO算法包括兩個(gè)部分:
- 求解兩個(gè)變量二次規(guī)劃的解析方法(線性規(guī)劃;把握好對(duì)g(x)和Ei的理解)
- 選擇變量的啟發(fā)式方法(KKT;|E1-E2|最大)
參考:李航,統(tǒng)計(jì)學(xué)習(xí)方法
