通俗易懂的支持向量機(jī)SVM
SVM 的原理和目標(biāo)
幾個基本概念
線性可分SVM——線性 SVM——非線性 SVM
1、線性可分SVM歹颓,表示可以用一根線非常清晰的劃分兩個區(qū)域殃姓;線到支持向量的距離 d 就是最小的。
2童芹、線性 SVM涝滴,表示用一根線劃分區(qū)域后绣版,可能存在誤判點(diǎn),但還是線性的歼疮;線到支持向量的距離不一定是最小的杂抽,但忽略其他非規(guī)則的支持向量。
3韩脏、非線性 SVM缩麸,表示使用核函數(shù)之后,把低維的非線性轉(zhuǎn)換為高維線性
復(fù)習(xí)下函數(shù)和向量
假如有個方程
y=x/2-1可以變化為 -x+2y+2=0
f(x,y)=-x+2y+2,其中紅色的就是他的法向量
寫成向量的形式:
改寫下
前面的系數(shù)項(xiàng)可以令其為
x赡矢,y 的那一項(xiàng)杭朱,其實(shí)可以演變?yōu)?n行,所以可以簡化為
后面的2是常數(shù)項(xiàng)济竹,用 b 代替
這樣處理完痕檬,我們的式子可以修改為
其中 w 就是我們的法線方向,x 是我們的參數(shù)送浊,b 是截距項(xiàng)。
此時如果有個 帶入式子得到是正值丘跌,那么就在法線的同方向袭景;否則在法線的逆方向。如果等于0闭树,那么該點(diǎn)就在線上耸棒。
f(x1,x2)代表一個線报辱,f(x1,x2,x3)代表一個面与殃,如果是 n 維的,那么給他一個牛逼的名稱“超平面”,由于這個名字太牛逼幅疼,所以低維的也叫超平面米奸。
計算過程和算法步驟
接入給定一個特征空間上的訓(xùn)練數(shù)據(jù)集,
其中
這里為什么 y 取值+1和-1爽篷?
因?yàn)檫@樣取值方便后面的推導(dǎo)悴晰,如果非要把+1和-1換為+3和-8什么的,其實(shí)沒有什么不同逐工。后面推導(dǎo)不受影響铡溪。
寫成+1和-1的話,那么我們的,那么泪喊,兩邊同時乘以 yj棕硫,得到,這樣我們就可以很方便的得到兩個標(biāo)記相乘等于兩個標(biāo)記相除袒啼。如果選擇不同的值饲帅,就得不到上面的式子。
推導(dǎo)目標(biāo)函數(shù)
分割平面:
訓(xùn)練集:x1瘤泪,x2灶泵,x3......
目標(biāo)集:y1,y2,y3...... y屬于1和-1的集合
新數(shù)據(jù)的分類:sign(y(x))
根據(jù)題設(shè)
其中就是一個映射对途,就是原封不動一階映射赦邻,二階映射的例子如下:
{1,x1实檀,x2,x3}==>{1,x1,x2,x3,x12,x22,x3^2,x1x2,x2x3,x1x3}把原來的四維轉(zhuǎn)換成10維惶洲。
接下來就有
其中:y(x)為預(yù)測值,y 為真實(shí)值膳犹,他們互為推導(dǎo)恬吕。最終他們的乘積大于0.
從而可以得到下面的公式(其實(shí)是點(diǎn)到直線的距離)
我們的目標(biāo)函數(shù):
解釋:對于所有的樣本到平面的距離求最近,也就是最小值须床,然后得到的這些平面里面根據(jù) w 和 b再求 最大值铐料。
如何優(yōu)化
轉(zhuǎn)換等價問題,直接來解決的確棘手豺旬。先來看
線性可分的這個圖
可以看出钠惩,有3個支持向量。
上虛線五角星的那個點(diǎn)到紅線的距離是一個值族阅,而且是最近的一個距離篓跛,假如該距離為 d=3,那么也就是
兩邊同時除以3
也就是范數(shù) w 乘以3坦刀,但是對整個方程來說位置是不發(fā)生變化的愧沟。(其實(shí) w 是我們要求的蔬咬,可以隨便設(shè)置,總能得到右邊為1)
打個比方沐寺,假如有個方程 f(x,y)=ax+by+c=0,有個點(diǎn)到該線的距離為d林艘,那么我們可以除以 d,使得到改線的距離為1芽丹,可以認(rèn)為是距離歸一處理北启。那么同理我們總能得到一個 w,使得五角星那個點(diǎn)到紅線的距離為1拔第,就得有個約束條件就是咕村,好了,現(xiàn)在這個值要求取最小值蚊俺,而且又是大于等于1懈涛,那么就直接取1就是最小值。
那么新的目標(biāo)函數(shù)就變化為
一個數(shù)的倒數(shù)求最大泳猬,也就是這個數(shù)求最小批钠,也就是求這個數(shù)的平方最小,也就是求這個數(shù)平方的一半最小得封,好了埋心,公式繼續(xù)演變?yōu)椋?br>
這個就是我們需要求解的目標(biāo),假如 n=10000(n 是樣本個數(shù))忙上,也就是有1萬個下面的約束條件下求上式子的最小值拷呆,對于這個目標(biāo)函數(shù)如何來求呢?帶有約束條件的求極值問題疫粥,就想到拉格朗日乘子法茬斧。
拉格朗日乘子法和KKT條件
其實(shí)拉格朗日乘子法的約束條件是要求等于某個條件,而這里是不等于梗逮,也可以這么做项秉。
這個式子的暫且放一邊,我們來梳理下拉格朗日乘子法慷彤。
假設(shè)有個函數(shù)要求最小值娄蔼,min f(x),其中有兩部分要求瞬欧,第一部分是不等式部分:
這里所有條件的方向可以修改為
贷屎,因?yàn)榭梢栽黾迂?fù)號來改變方向,不是什么大問題艘虎。
最終也就是
第二部分是等式部分,記為
本科階段的拉格朗日乘子法只有等式部分咒吐,現(xiàn)在這里增加了不等式部分野建,針對不等式部分属划,做如下操作。
先設(shè)置一系列的候生,構(gòu)造一個新的函數(shù)
這個就是拉格朗日函數(shù)同眯。對于這個函數(shù)來說,以w為變量唯鸭,對其求導(dǎo)數(shù)须蜗,可得系數(shù)為,在二維坐標(biāo)上就是一條線,同理等目溉。
將他們畫在一張坐標(biāo)系里面明肮,
對于這3個線段求取每個 x 點(diǎn)的最小值,得到的是紅色的這個區(qū)域的線缭付,同理柿估,n 條這樣的線也可以得到這樣一個凹函數(shù),凹函數(shù)必有最大值陷猫,并且是全局最大秫舌。
那么到底是什么?
繼續(xù)看下
因?yàn)?/p>
而绣檬,所以
因?yàn)?div id="ersnjeu" class="image-package">
image
足陨,所以無論 lambda 取什么值,
,這就是說 G(x)是一個 f(x)加上一個負(fù)數(shù)娇未,那么也就是說 G(x)的最大也就是 f(x)了墨缘。
,那么要求 minf(x)也就是求
可以找到他的對偶函數(shù)
再回到我們原來的式子忘蟹,
這個式子比上面的理論要簡單點(diǎn)飒房,沒有等式約束。那么他的原始極小極大問題
他的對偶問題為極大極小問題
為了求最小值媚值,我們需要對w 和 b 分別求導(dǎo)狠毯,并且使之為0,
其中
最終得到
也就是
接下來褥芒,對 b 求偏導(dǎo)數(shù)嚼松,得到
w 不就是法向量嘛,其中包含的 alpha=0的點(diǎn)不是支撐向量锰扶,而 alpha 不為0 的才是 SV献酗。pha(x)就是核函數(shù),所有的這些在這里可以體現(xiàn)出來了坷牛。
歸納下:
繼續(xù)推導(dǎo)罕偎。。京闰。帶入 w 和 b颜及,剩下 alpha 的式子甩苛。
最后得到求 alpha 的式子
使用某種方法(SMO)求得 alpha,帶入 w 和 b 就可以求得 w俏站。
SMO 算法讯蒲,由條件可知,
[圖片上傳失敗...(image-ab4eb3-1526290967990)]
我們需要調(diào)節(jié)2個 alpha 參數(shù)肄扎,一大一小墨林,使得為0,滿足條件后求得 alpha 較大值犯祠,然后慢慢調(diào)節(jié)旭等,再得到一個較大值,這樣的按照序列求得最大的優(yōu)化方法叫 SMO
掉個方向雷则,得到
舉個例子看的明白些:
給定3個數(shù)據(jù)點(diǎn)辆雾,正例點(diǎn)x1=(3,3)T,x2=(4,3)T,反例點(diǎn) x3=(1,1)T, 求解線性可分的SVM。
解:目標(biāo)函數(shù)是
[圖片上傳失敗...(image-fbc4d6-1526290967990)]
根據(jù)
可得
其中正例就是 x1=(3,3,1) x2=(4,3,1);負(fù)例x3=(1,1,-1)
最后是表示 y 的值月劈。x1對應(yīng)的系數(shù) alpha1度迂,x2對應(yīng)的系數(shù)是 alpha2,x3對應(yīng)的系數(shù)是 alpha3.
將 alpha3=alpha1+alpha2帶入式子計算得到關(guān)羽 alpha1和 alpha2 的han 函數(shù)
對 alpha1和 alpha2求偏導(dǎo)令他為0猜揪,得到在(1.5惭墓,-1)這個點(diǎn)取到極值,但是改點(diǎn)不滿足 alpha2>0這個條件而姐,所以最小值在邊界上沒有達(dá)到腊凶。
令 alpha1=0,最小值 s(0拴念,2/13)=-2/13=-0.1538
令 alpha2=0钧萍,最小值 s(1/4,0)=-1/4=-0.25
所以得到s(alpha1,alpha2)在1/4,0處達(dá)到最小政鼠,此時 alpha3=alpha1+alpha2=0.25
所以 alpha1=alpha3=0.25對應(yīng)點(diǎn) x1和 x3構(gòu)成支持向量风瘦。
帶入公式:
這里 fai(xi)就是 xi
得到 w1=w2=0.5 b=-2
所以超平面為
圖形
x1的系數(shù)和x3的系數(shù)是0.25,而x2的系數(shù)是0公般,也就是說 x2沒有參與支持向量的構(gòu)建万搔,不是支持向量。
以上是線性可分官帘,那么線性不一定可分的咋辦呢瞬雹?
如圖
按照可分那就是實(shí)線,貌似虛線應(yīng)該更好刽虹。
若線性不可分酗捌,需要加入松弛因子[圖片上傳失敗...(image-8be0f1-1526290967990)]>=0,
此時約束條件變成:
當(dāng)
=0就是線性可分。
目標(biāo)函數(shù):
這個式子中意敛,當(dāng) C 趨向無窮大的時候馅巷,
只能取0才能保證能取最小值膛虫。C 可以認(rèn)為是允許犯錯誤的容忍程度草姻,C 太大,表示對錯誤完全不能容忍稍刀,必須要線性可分撩独。從另外角度來說,C 太大账月,那么不允許犯錯誤综膀,那么過渡帶就會窄。C 小些的話局齿,過渡帶會寬些剧劝,也就是泛化能力較強(qiáng)。
歸納下:
對應(yīng)的拉格朗日函數(shù)(注意符號抓歼,ξ>=0的變化)
然后對其求偏導(dǎo)數(shù)
將三個式子帶入
把 μ消掉了
對上式子求關(guān)羽 α 的極大讥此,得到
上式右下角的條件限制了α的取值范圍是縮小了的。
進(jìn)一步整理得到對偶問題
再進(jìn)一步構(gòu)造最優(yōu)化問題
求解得 a^*
然后計算出w 和 b
注意:計算 b 的時候需要滿足α在(0谣妻,C)之間
最終求得超平面:
損失函數(shù)分析
圓圈的點(diǎn):他們的α=C萄喳,他們是有損失的,并且哪些紅色線段表示損失值蹋半;雖然他們分的是對的他巨。但是已經(jīng)進(jìn)入敏感地帶。
方塊的星:他們的0 < α < C,是支持向量
其他點(diǎn):α = 0
損失值=1-d减江;d 是點(diǎn)到超平面的距離染突,那么過渡帶之外的損失值為0,于是得到 SVM 損失函數(shù)圖(Hindge損失)
也就是
但得到這個最小的時候辈灼,求得新的 w 和 b份企。
我們再看下
[圖片上傳失敗...(image-faff7c-1526290967990)]
這里出現(xiàn)了損失函數(shù),經(jīng)過變換得到新的損失函數(shù)
后面一項(xiàng)是 L2正則
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
序言:七十年代末茵休,一起剝皮案震驚了整個濱河市薪棒,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌榕莺,老刑警劉巖俐芯,帶你破解...
序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異钉鸯,居然都是意外死亡吧史,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
文/潘曉璐 我一進(jìn)店門唠雕,熙熙樓的掌柜王于貴愁眉苦臉地迎上來贸营,“玉大人吨述,你說我怎么就攤上這事〕” “怎么了揣云?”我有些...
文/不壞的土叔 我叫張陵,是天一觀的道長冰啃。 經(jīng)常有香客問我工碾,道長禽笑,這世上最難降的妖魔是什么橄抹? 我笑而不...
正文 為了忘掉前任屈梁,我火速辦了婚禮,結(jié)果婚禮上扇调,老公的妹妹穿的比我還像新娘矿咕。我一直安慰自己,他們只是感情好狼钮,可當(dāng)我...
文/花漫 我一把揭開白布碳柱。 她就那樣靜靜地躺著,像睡著了一般燃领。 火紅的嫁衣襯著肌膚如雪士聪。 梳的紋絲不亂的頭發(fā)上,一...
那天猛蔽,我揣著相機(jī)與錄音剥悟,去河邊找鬼。 笑死曼库,一個胖子當(dāng)著我的面吹牛区岗,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播毁枯,決...
文/蒼蘭香墨 我猛地睜開眼慈缔,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了种玛?” 一聲冷哼從身側(cè)響起藐鹤,我...
序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎赂韵,沒想到半個月后娱节,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
正文 獨(dú)居荒郊野嶺守林人離奇死亡祭示,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
正文 我和宋清朗相戀三年肄满,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
序言:一個原本活蹦亂跳的男人離奇死亡稠歉,死狀恐怖掰担,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情怒炸,我是刑警寧澤带饱,帶...
正文 年R本政府宣布,位于F島的核電站横媚,受9級特大地震影響纠炮,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜灯蝴,卻給世界環(huán)境...
文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望孝宗。 院中可真熱鬧穷躁,春花似錦、人聲如沸因妇。這莊子的主人今日做“春日...
文/蒼蘭香墨 我抬頭看了看天上的太陽婚被。三九已至狡忙,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間址芯,已是汗流浹背灾茁。 一陣腳步聲響...
我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留谷炸,地道東北人北专。 一個月前我還...
正文 我出身青樓,卻偏偏與公主長得像旬陡,于是被迫代替她去往敵國和親拓颓。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
SVM 的原理和目標(biāo) 幾個基本概念 線性可分SVM——線性 SVM——非線性 SVM 1描孟、線性可分SVM驶睦,表示可以...
【概述】 SVM訓(xùn)練分類器的方法是尋找到超平面,使正負(fù)樣本在超平面的兩側(cè)(分類正確性即“分得開”)匿醒,且樣本到超平面...
結(jié)合Scikit-learn介紹幾種常用的特征選擇方法 作者:Edwin Jarvis 特征選擇(排序)對于數(shù)據(jù)科...
【轉(zhuǎn)載】線性代數(shù)基礎(chǔ)知識 原文地址:http://blog.csdn.net/longxinchen_ml/art...
SVM支持向量機(jī) 本片文章主要記錄在學(xué)習(xí)《統(tǒng)計學(xué)習(xí)方法》中 SVM 章節(jié)的難點(diǎn)场航,不對詳細(xì)內(nèi)容進(jìn)行講解。主要是分析筆...