一、什么是支持向量機(jī)
支持向量機(jī)(Suport Vector Machine,常簡(jiǎn)稱為SVM)倡勇,是一個(gè)監(jiān)督式學(xué)習(xí)的方式殖告。支持向量機(jī)屬于一般化線性分類器,這類分類器的特點(diǎn)是能夠同時(shí)最小化經(jīng)驗(yàn)誤差與最大化幾何邊緣區(qū)晴圾,因此支持向量機(jī)機(jī)也被稱為最大邊緣區(qū)分類器。
藍(lán)色和紅色的線圈出來的點(diǎn)就是所謂的支持向量噪奄,離分界線最近的點(diǎn)死姚,如果去掉這些點(diǎn),直線多半要改變位置勤篮。Classifier Boundary就是決策函數(shù)f(x)都毒,在兩個(gè)類的中間。紅色和藍(lán)色之間的間隙就是我們要的最大化分類的間隙碰缔。
二温鸽、關(guān)于拉格朗日乘子法和KKT條件
1.關(guān)于拉格朗日乘子法
有拉格朗日乘子法的地方,必然是一個(gè)組合優(yōu)化問題手负。比如
這是一個(gè)帶等式約束的優(yōu)化問題,有目標(biāo)值姑尺,有約束條件竟终,不能直接求導(dǎo)∏畜可以使用拉格朗日方法统捶,把這個(gè)約束乘以一個(gè)系數(shù)加到目標(biāo)函數(shù)中去,這樣相當(dāng)與既考慮了原目標(biāo)函數(shù)柄粹,也考慮了約束條件喘鸟。然后分別對(duì)x求導(dǎo)等于0,
把它帶點(diǎn)菜約束條件中去驻右,可以看到什黑,2個(gè)變量兩個(gè)等式,最終可再帶回去求x就可以了堪夭。更高一層愕把,帶有不等式的約束問題怎么辦拣凹?需要用更一般化的拉格朗日乘子法,即KKT條件恨豁,來求解這個(gè)問題嚣镜。
2.關(guān)于KKT條件
任何原始問題約束條件無非最多三種,等式約束橘蜜,大于號(hào)約束菊匿,小于號(hào)約束,而這三種最終通過將約束方程簡(jiǎn)化成兩類:約束方程等于0和約束方程小于0计福。
假設(shè)原始問題約束條件為下例所示:
那么把約束條件變個(gè)樣子
現(xiàn)在拿到目標(biāo)函數(shù)中去變成
那么KKT條件的定理是什么呢跌捆?就是如果一個(gè)優(yōu)化問題在轉(zhuǎn)變成
其中g(shù)是不等式約束,h是等式約束棒搜。那么KKT條件就是函數(shù)的最優(yōu)值疹蛉,它必定滿足下面條件:
- L對(duì)各個(gè)x求導(dǎo)為0
這三個(gè)等式很好理解,重點(diǎn)是第三個(gè)句子不好理解力麸,因?yàn)槲覀冎涝诩s束條件變完或可款,所有的,且求和還要為0克蚂。那么為什么KKT的條件是這樣的呢闺鲸?
某次的g(x)在為最優(yōu)解起作用,那么它的系數(shù)值(可以)不為0埃叭,如果某次g(x)沒有為下一次的最優(yōu)解起作用摸恍,那么它的系數(shù)就必須為0。
三赤屋、函數(shù)間隔和幾何間隔
函數(shù)間隔
對(duì)于給定的訓(xùn)練數(shù)據(jù)集T合超平面(w,b)立镶,定義超平面(w,b)關(guān)于樣本點(diǎn)的函數(shù)間隔為
函數(shù)間隔可以表示分類預(yù)測(cè)的正確性及確信度。但是選擇超平面時(shí)类早,只有函數(shù)間隔是不夠的媚媒,因子只要成比較改變和b,超平面并沒有改變涩僻,但函數(shù)間隔卻擴(kuò)大了缭召。
幾何間隔
對(duì)于給定的訓(xùn)練數(shù)據(jù)集T和超平面,定義超平面
關(guān)于樣本點(diǎn)
的幾何間隔為
,其中
為
的
范數(shù)嵌巷。
如果,那么函數(shù)間隔和幾何間隔相等室抽。如果超平面參數(shù)
成比例地改變(超平面沒有改變)搪哪,函數(shù)間隔也成比例改變,而幾何間隔不變狠半。
四噩死、間隔最大化
支持向量機(jī)的基本想法是求解能夠正確分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面颤难。對(duì)線性可分的訓(xùn)練數(shù)據(jù)集而言,線性可分分離超平面有無窮多個(gè)(等價(jià)于感知機(jī))已维,但是幾何間隔最大的分離超平面時(shí)唯一的行嗤。這里的間隔最大化被稱為硬間隔最大化。
間隔最大化的直觀解釋是:對(duì)訓(xùn)練數(shù)據(jù)集找到幾何間隔最大的超平面意味著以充分大的確信度對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分類垛耳。也就是說栅屏,不僅將正負(fù)實(shí)例點(diǎn)分開,而且對(duì)最難分的實(shí)例點(diǎn)(離超平面最近的點(diǎn))也有足夠大的確信度將他們分開堂鲜。這樣的超平面應(yīng)該對(duì)未知的新實(shí)例有很好的分類預(yù)測(cè)能力栈雳。
1.最大間隔分離超平面
下面考慮如何求一個(gè)幾何間隔最大的分離超平面,即最大間隔分離超平面缔莲。具體地哥纫,這個(gè)問題可以表示為下面的約束最優(yōu)化問題:
即我們希望最大化超平面關(guān)于訓(xùn)練數(shù)據(jù)集的集合間隔
痴奏,約束條件表示的是超平面
關(guān)于每個(gè)訓(xùn)練樣本點(diǎn)的集合間隔至少是
考慮幾何間隔和函數(shù)間隔的關(guān)系式蛀骇,可將這個(gè)問題改成為
函數(shù)間隔并不影響最優(yōu)化問題的解。事實(shí)上读拆,假設(shè)將
成比例改變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Clambda%5Comega%E5%92%8C%5Clambda%20b" alt="\lambda\omega和\lambda b" mathimg="1">,這時(shí)函數(shù)間隔變成
擅憔。函數(shù)間隔的改變對(duì)最優(yōu)化問題的不等式約束沒有影響,對(duì)目標(biāo)函數(shù)的優(yōu)化也沒有影響檐晕,也就事實(shí)說暑诸,它產(chǎn)生一個(gè)等價(jià)的最優(yōu)化問題。這樣辟灰,就可以取
个榕。將
代入上面的最優(yōu)化問題。注意最大化
和最小化
是一樣的芥喇。
于是就得到下面的線性可分支持向量機(jī)學(xué)習(xí)的最優(yōu)化問題
這是一個(gè)凸二次規(guī)劃問題(contex quadratic programming)問題笛洛。
凸優(yōu)問題是指約束最優(yōu)化問題
其中,目標(biāo)函數(shù)和約束函數(shù)
都是
上的可連續(xù)可微的凸函數(shù)乃坤,約束函數(shù)
是
的仿射函數(shù)。當(dāng)木匾函數(shù)是
是二次函數(shù)且約束函數(shù)
是仿射函數(shù)時(shí)沟蔑,上述的凸優(yōu)化問題成為凸二次規(guī)劃問題湿诊。
如果求出約束最優(yōu)化問題的解,那么就可以得出最大間隔分離超平面
及決策函數(shù)
瘦材,即線性可分支持向量機(jī)模型厅须。
五、學(xué)習(xí)的對(duì)偶算法
為了求解線性可分支持向量機(jī)的最優(yōu)化問題食棕,將它作為原始最優(yōu)化問題朗和,應(yīng)用到拉格朗日對(duì)偶性错沽,通過求解對(duì)偶問題得到原始問題的最優(yōu)解,這就是線性可支持向量機(jī)的對(duì)偶算法(dual algorithm)眶拉。這樣做的優(yōu)點(diǎn)千埃,一是對(duì)偶問題往往根據(jù)容易求解;二是自然引入核函數(shù)忆植,進(jìn)而推廣到非線性可分類問題放可。
首先構(gòu)建拉格朗日函數(shù)(Lagrange function)。為此朝刊,對(duì)每一個(gè)不等式約束引入拉格朗日乘子(Lagrange multiplier)定義拉格朗日函數(shù):
其中為拉格朗日乘子向量耀里。
根據(jù)拉格朗日對(duì)偶性,原始問題的對(duì)偶問題是極大極小問題
為了得到對(duì)偶函數(shù)問題的解拾氓,需要先求對(duì)
的極小冯挎,再求
的極大
(1)求
將拉格朗日函數(shù)分別對(duì)
求偏導(dǎo)數(shù)并令其等于0
將(1)代入拉格朗日函數(shù),并利用(2)咙鞍,即可得
即
(2)求對(duì)
的極房官,即對(duì)偶問題
將公式(3)的目標(biāo)函數(shù)由極大值轉(zhuǎn)換成求極小,就得到下面與之等價(jià)的對(duì)偶最優(yōu)化問題
(3)解
假設(shè)是對(duì)偶最優(yōu)化問題的解奶陈,則存在下標(biāo)使得
易阳,并求按下式求得原始最優(yōu)化的解
根據(jù)KKT條件成立,即得
因此
,且至少存在一個(gè)
吃粒,假設(shè)
,那么
不是原始問題的解,所以
那么分離的超平面可以寫成
決策函數(shù)可以寫成
由此可以看出潦俺,分類決策函數(shù)只依賴于輸入x和訓(xùn)練樣本輸入的內(nèi)積,式(8)稱為線性可分支持向量機(jī)的對(duì)偶形式徐勃。
案例
訓(xùn)練數(shù)據(jù)正例點(diǎn)是事示,負(fù)例點(diǎn)是
,試用線性可分支持向量機(jī)
解:根據(jù)所給數(shù)據(jù)僻肖,對(duì)偶問題是
兩個(gè)向量
和
的點(diǎn)積定義為:
解這一優(yōu)化問題臀脏,將代入目標(biāo)函數(shù)并記為
對(duì)求偏導(dǎo)令其為0劝堪,易知
處取極值,該點(diǎn)不滿足約束條件
揉稚,所以最小值應(yīng)在邊界上達(dá)到秒啦。
當(dāng)搀玖,當(dāng)
,于是
這樣,對(duì)應(yīng)的實(shí)例點(diǎn)
是支持向量含末,計(jì)算可得
,
分離超平面為
分離決策函數(shù)為
六、軟間隔最大化
線性可分問題的支持向量機(jī)學(xué)習(xí)方法即舌,對(duì)線性不可分訓(xùn)練數(shù)據(jù)是不適用的院崇,因?yàn)檫@時(shí)上述方法中的不等式約束不能都成立没讲。線性不可分意味著不能滿足函數(shù)間隔大于等于1的約束條件。為了解決這個(gè)問題,對(duì)每個(gè)樣本點(diǎn)都引入一個(gè)松弛變量
政己,使得函數(shù)間隔加上變量大于等于1懈凹,這樣約束條件變?yōu)?br>
同時(shí)對(duì)于每個(gè)松弛變量泪蔫,支付一個(gè)代價(jià)
,目標(biāo)函數(shù)由原來的
變成
C>0為懲罰參數(shù)蹦狂,一般由應(yīng)用問題解決,C值大時(shí)對(duì)誤分類的懲罰增大嗦明,C值小時(shí)對(duì)誤分類的懲罰減小笼沥。最小化木匾函數(shù)有2層意思:使得盡量小,即間隔盡量大娶牌,同時(shí)使誤分類點(diǎn)的個(gè)數(shù)盡量小奔浅,C是調(diào)和兩者的系數(shù)
七、非線性支持向量機(jī)與核函數(shù)
1.背景知識(shí)
(1)核技巧
非線性分類問題是指通過非線性模型才能很好地進(jìn)行分類的問題诗良。非線性問題往往不好求解汹桦,希望通過線性分類問題的方法解決這個(gè)問題,所采取的方法是進(jìn)行一個(gè)非線性變換鉴裹,將非線性問題變成線性問題舞骆,通過解變換后的線性問題的方法求解原來的非線性問題。
用線性分類方法求解非線性分類問題分兩步:首先使用一個(gè)變換將原來空間的數(shù)據(jù)映射到新空間径荔;然后在新空間里用線性分類學(xué)習(xí)方法從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)分類模型督禽。核技巧就屬于這樣的方法。
(2)核函數(shù)定義
設(shè)X是輸入空間(歐氏空間的子集或離散集合)总处,又設(shè)H為特征向量(希伯而空間H)狈惫,如果存在一個(gè)從X到H的映射
使得對(duì)所有,函數(shù)
滿足條件
則稱K(x,z)為核函數(shù)鹦马,為映射函數(shù)胧谈,
。通常計(jì)算K(x,z)比較容易荸频,而通話
計(jì)算K(x,z)并不容易第岖。
是輸入空間到特征空間的迎神,特征空間一般是高維的试溯,甚至是無窮維,可以看到郊酒,對(duì)于給定的核K(x,z)遇绞,特征空間H和映射函數(shù)
的取法并不唯一键袱,可以取不同的特征空間,即便是在同一特征空間也可以取不同的映射摹闽。
(3)核技巧在支持向量機(jī)中的應(yīng)用
在對(duì)偶目標(biāo)函數(shù)中的內(nèi)積可以用核函數(shù)
來代替蹄咖,此時(shí)對(duì)偶問題的目標(biāo)函數(shù)成為
這等價(jià)于經(jīng)過映射函數(shù)將原來的輸入空間變換到一個(gè)新的特征空間,將輸入空間中的內(nèi)積
變換成特征空間中的內(nèi)積
付鹿,在新的特征空間里從訓(xùn)練樣本中學(xué)習(xí)線性支持向量機(jī)澜汤。學(xué)習(xí)是隱式地在特征空間進(jìn)行的,不需要顯式地定義特征空間和營業(yè)日函數(shù)舵匾。在實(shí)際應(yīng)用中俊抵,往往依賴領(lǐng)域知識(shí)直接選擇核函數(shù)。
2.常用核函數(shù)
(1)多項(xiàng)式核函數(shù)(polynomial kernal function)
對(duì)應(yīng)的支持向量機(jī)是一個(gè)p次多項(xiàng)式分類器坐梯,在此情形下徽诲,分類決策函數(shù)成為
(2)高斯核函數(shù)(Guassian kernel function)
對(duì)應(yīng)的支持向量機(jī)是高斯徑向基函數(shù)(radial basis function)分類器。在此情形下吵血,分類決策函數(shù)成為
(3)字符串核函數(shù)
核函數(shù)不僅可以定義在歐式空間谎替,還可以定義在離散數(shù)據(jù)的集合上。比如蹋辅,字符串核函數(shù)是定義在字符串集合上的核函數(shù)钱贯。字符串核函數(shù)在文本分類、信息檢索侦另、生物信息學(xué)等方面都有應(yīng)用秩命。
兩個(gè)字符串s和t上的字符串核函數(shù)是基于映射的特征空間中的內(nèi)積:
字符串核函數(shù)給出了字符串s和t中長度等于n的所有子串組成的特征向量的余弦相似度。直觀上看淋肾,兩個(gè)字符串相同的字串越多硫麻,它們就越相似,字符串核函數(shù)的值就越大樊卓。字符串核函數(shù)可以由動(dòng)態(tài)規(guī)劃快速地計(jì)算拿愧。
八、序列最小最優(yōu)化算法
支持向量機(jī)的學(xué)習(xí)問題可以形式化為求解凸二次規(guī)劃問題碌尔,這樣的凸二次規(guī)劃問題具有全局最優(yōu)解浇辜,并且有許多最優(yōu)化算法可以用于這一問題的求解。但是當(dāng)訓(xùn)練樣本容量很大時(shí)唾戚,這些算法往往變得非常低效柳洋,以至無法使用。
序列最小最優(yōu)化(sequential minimal optimization,SMO)算法叹坦,是一種啟發(fā)式算法熊镣,其基本思路是:如果所有變量的解都滿足此最優(yōu)化問題的KKT條件,那么這個(gè)最優(yōu)化問題的解就得到了。因?yàn)镵KT條件是該最優(yōu)化問題的充分必要條件绪囱。否則测蹲,選擇兩個(gè)變量,固定其他變量鬼吵,針對(duì)這兩個(gè)變量構(gòu)建一個(gè)二次規(guī)劃問題扣甲。這個(gè)二次規(guī)劃問題的目標(biāo)是使函數(shù)值變得更小。重要的是齿椅,這時(shí)子問題可以通過解析方法求解琉挖,這樣就可以大大提高整個(gè)算法的計(jì)算速度。子問題有兩個(gè)變量涣脚,一個(gè)是違反KKT條件最嚴(yán)重的那一個(gè)示辈,另一個(gè)由約束條件自動(dòng)確定。如此涩澡,SMO算法將原問題不斷分解為子問題并對(duì)子問題求解顽耳,進(jìn)而達(dá)到求解原問題的目的。
1.兩個(gè)變量二次規(guī)劃的求解辦法
假設(shè)兩個(gè)變量是妙同,其他變量
是固定的射富,于是SNO的最優(yōu)化問題的子問題可以寫成。
其中粥帚,是常數(shù)胰耗,目標(biāo)函數(shù)中省略不含
的常數(shù)項(xiàng)。
為了求解兩個(gè)變量的二次規(guī)劃問題芒涡,約束可以用二維空間中的圖形表示
不等式約束(7.3)使得在盒子[0,C][0,C]內(nèi)柴灯,等式約束(7.2)使
在平行于盒子[0,C][0,C]的對(duì)角線的直線上。因此要求的是目標(biāo)函數(shù)在一條平行于對(duì)角線的線段上最優(yōu)值费尽。這使得兩個(gè)變量的最優(yōu)化問題成為實(shí)質(zhì)上的單變量最優(yōu)化文圖赠群,不訪考慮為變量
的最優(yōu)化問題。
假設(shè)初始化可行解為旱幼,最優(yōu)化解為
查描,并且假設(shè)沿著約束方向未經(jīng)剪輯時(shí)
的最優(yōu)解為
由于需滿足不等式約束(7.3),所以最優(yōu)值
的取值范圍必須滿足條件
其中柏卤,L與H是所在對(duì)角線段端點(diǎn)的界冬三,如果
如果,則
下面首先要求沿著約束方向未經(jīng)剪輯即未考慮不等式約束(7.3)時(shí)的最優(yōu)解
缘缚,然后在解決剪輯后
的解
勾笆,我們用定理來描述這個(gè)結(jié)果
令
當(dāng)i=1,2時(shí),為函數(shù)g(x)對(duì)輸入
的預(yù)測(cè)值與真實(shí)輸出
之差
定理 最優(yōu)化問題(7.1)~(7.3)沿著約束方向未經(jīng)剪輯時(shí)的解是
其中
是輸入空間到特征空間的映射
經(jīng)剪輯后的的解是
由是