通俗易懂的支持向量機(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ù)和向量

假如有個方程


image

y=x/2-1可以變化為 -x+2y+2=0
f(x,y)=-x+2y+2,其中紅色的就是他的法向量
寫成向量的形式:


image

改寫下
image

前面的系數(shù)項(xiàng)可以令其為
image

x赡矢,y 的那一項(xiàng)杭朱,其實(shí)可以演變?yōu)?n行,所以可以簡化為
image

后面的2是常數(shù)項(xiàng)济竹,用 b 代替
這樣處理完痕檬,我們的式子可以修改為
image

其中 w 就是我們的法線方向,x 是我們的參數(shù)送浊,b 是截距項(xiàng)。

此時如果有個
image

帶入式子得到是正值丘跌,那么就在法線的同方向袭景;否則在法線的逆方向。如果等于0闭树,那么該點(diǎn)就在線上耸棒。

f(x1,x2)代表一個線报辱,f(x1,x2,x3)代表一個面与殃,如果是 n 維的,那么給他一個牛逼的名稱“超平面”,由于這個名字太牛逼幅疼,所以低維的也叫超平面米奸。

計算過程和算法步驟

接入給定一個特征空間上的訓(xùn)練數(shù)據(jù)集,


image

其中


image

image

這里為什么 y 取值+1和-1爽篷?
因?yàn)檫@樣取值方便后面的推導(dǎo)悴晰,如果非要把+1和-1換為+3和-8什么的,其實(shí)沒有什么不同逐工。后面推導(dǎo)不受影響铡溪。

寫成+1和-1的話,那么我們的
image
,那么
image
泪喊,兩邊同時乘以 yj棕硫,得到
image

,這樣我們就可以很方便的得到兩個標(biāo)記相乘等于兩個標(biāo)記相除袒啼。如果選擇不同的值饲帅,就得不到上面的式子。

推導(dǎo)目標(biāo)函數(shù)

分割平面:

image

訓(xùn)練集:x1瘤泪,x2灶泵,x3......
目標(biāo)集:y1,y2,y3...... y屬于1和-1的集合
新數(shù)據(jù)的分類:sign(y(x))
根據(jù)題設(shè)
image

其中
image
就是一個映射对途,
image
就是原封不動一階映射赦邻,二階映射的例子如下:
{1,x1实檀,x2,x3}==>{1,x1,x2,x3,x12,x22,x3^2,x1x2,x2x3,x1x3}把原來的四維轉(zhuǎn)換成10維惶洲。
接下來就有
image

其中:y(x)為預(yù)測值,y 為真實(shí)值膳犹,他們互為推導(dǎo)恬吕。最終他們的乘積大于0.
從而可以得到下面的公式(其實(shí)是點(diǎn)到直線的距離)
image

我們的目標(biāo)函數(shù):
image

解釋:對于所有的樣本到平面的距離求最近,也就是最小值须床,然后得到的這些平面里面根據(jù) w 和 b再求 最大值铐料。

如何優(yōu)化

轉(zhuǎn)換等價問題,直接來解決的確棘手豺旬。先來看
線性可分的這個圖


image

可以看出钠惩,有3個支持向量。

上虛線五角星的那個點(diǎn)到紅線的距離是一個值族阅,而且是最近的一個距離篓跛,假如該距離為 d=3,那么也就是
image

兩邊同時除以3
image

也就是范數(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拔第,就得有個約束條件就是
image
咕村,好了,現(xiàn)在這個值要求取最小值蚊俺,而且又是大于等于1懈涛,那么就直接取1就是最小值。
那么新的目標(biāo)函數(shù)就變化為
image

一個數(shù)的倒數(shù)求最大泳猬,也就是這個數(shù)求最小批钠,也就是求這個數(shù)的平方最小,也就是求這個數(shù)平方的一半最小得封,好了埋心,公式繼續(xù)演變?yōu)椋?br>
image

這個就是我們需要求解的目標(biāo),假如 n=10000(n 是樣本個數(shù))忙上,也就是有1萬個下面的約束條件下求上式子的最小值拷呆,對于這個目標(biāo)函數(shù)如何來求呢?帶有約束條件的求極值問題疫粥,就想到拉格朗日乘子法茬斧。

拉格朗日乘子法和KKT條件

其實(shí)拉格朗日乘子法的約束條件是要求等于某個條件,而這里是不等于梗逮,也可以這么做项秉。

image

這個式子的暫且放一邊,我們來梳理下拉格朗日乘子法慷彤。


假設(shè)有個函數(shù)要求最小值娄蔼,min f(x),其中有兩部分要求瞬欧,第一部分是不等式部分:


image

image

image

這里所有條件的方向可以修改為


image
贷屎,因?yàn)榭梢栽黾迂?fù)號來改變方向,不是什么大問題艘虎。
最終也就是
image

第二部分是等式部分,記為
image

本科階段的拉格朗日乘子法只有等式部分咒吐,現(xiàn)在這里增加了不等式部分野建,針對不等式部分属划,做如下操作。

先設(shè)置一系列的
image
候生,構(gòu)造一個新的函數(shù)
image

這個就是拉格朗日函數(shù)同眯。對于這個函數(shù)來說,以
image
w為變量唯鸭,對其求導(dǎo)數(shù)须蜗,可得系數(shù)為
image
,在二維坐標(biāo)上就是一條線,同理
image
image
等目溉。
將他們畫在一張坐標(biāo)系里面明肮,
image

對于這3個線段求取每個 x 點(diǎn)的最小值,得到的是紅色的這個區(qū)域的線缭付,同理柿估,n 條這樣的線也可以得到這樣一個凹函數(shù),凹函數(shù)必有最大值陷猫,并且是全局最大秫舌。

那么
image
到底是什么?

繼續(xù)看下


image

image

因?yàn)?/p>

image

image
绣檬,所以
image

因?yàn)?div id="ersnjeu" class="image-package">
image
足陨,所以無論 lambda 取什么值,
image

,這就是說 G(x)是一個 f(x)加上一個負(fù)數(shù)娇未,那么也就是說 G(x)的最大也就是 f(x)了墨缘。
image
,那么要求 minf(x)也就是求
image

可以找到他的對偶函數(shù)
image

再回到我們原來的式子忘蟹,


image

這個式子比上面的理論要簡單點(diǎn)飒房,沒有等式約束。那么他的原始極小極大問題
image
他的對偶問題為極大極小問題
image

為了求最小值媚值,我們需要對w 和 b 分別求導(dǎo)狠毯,并且使之為0,
其中


image

最終得到


image

也就是
image

接下來褥芒,對 b 求偏導(dǎo)數(shù)嚼松,得到
image

w 不就是法向量嘛,其中包含的 alpha=0的點(diǎn)不是支撐向量锰扶,而 alpha 不為0 的才是 SV献酗。pha(x)就是核函數(shù),所有的這些在這里可以體現(xiàn)出來了坷牛。
歸納下:


image

繼續(xù)推導(dǎo)罕偎。。京闰。帶入 w 和 b颜及,剩下 alpha 的式子甩苛。


image

最后得到求 alpha 的式子


image

使用某種方法(SMO)求得 alpha,帶入 w 和 b 就可以求得 w俏站。

SMO 算法讯蒲,由條件可知,
[圖片上傳失敗...(image-ab4eb3-1526290967990)]
我們需要調(diào)節(jié)2個 alpha 參數(shù)肄扎,一大一小墨林,使得為0,滿足條件后求得 alpha 較大值犯祠,然后慢慢調(diào)節(jié)旭等,再得到一個較大值,這樣的按照序列求得最大的優(yōu)化方法叫 SMO

掉個方向雷则,得到


image

舉個例子看的明白些:
給定3個數(shù)據(jù)點(diǎn)辆雾,正例點(diǎn)x1=(3,3)T,x2=(4,3)T,反例點(diǎn) x3=(1,1)T, 求解線性可分的SVM。


image

解:目標(biāo)函數(shù)是


image

[圖片上傳失敗...(image-fbc4d6-1526290967990)]
根據(jù)


image

可得
image

其中正例就是 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ù)


image

對 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)成支持向量风瘦。
帶入公式:


image

這里 fai(xi)就是 xi

得到 w1=w2=0.5 b=-2
所以超平面為


image

圖形


image

x1的系數(shù)和x3的系數(shù)是0.25,而x2的系數(shù)是0公般,也就是說 x2沒有參與支持向量的構(gòu)建万搔,不是支持向量。

以上是線性可分官帘,那么線性不一定可分的咋辦呢瞬雹?
如圖


image

按照可分那就是實(shí)線,貌似虛線應(yīng)該更好刽虹。
若線性不可分酗捌,需要加入松弛因子[圖片上傳失敗...(image-8be0f1-1526290967990)]>=0,
此時約束條件變成:


image
當(dāng)
image
=0就是線性可分。
目標(biāo)函數(shù):
image

這個式子中意敛,當(dāng) C 趨向無窮大的時候馅巷,
image
只能取0才能保證能取最小值膛虫。C 可以認(rèn)為是允許犯錯誤的容忍程度草姻,C 太大,表示對錯誤完全不能容忍稍刀,必須要線性可分撩独。從另外角度來說,C 太大账月,那么不允許犯錯誤综膀,那么過渡帶就會窄。C 小些的話局齿,過渡帶會寬些剧劝,也就是泛化能力較強(qiáng)。

歸納下:


image

對應(yīng)的拉格朗日函數(shù)(注意符號抓歼,ξ>=0的變化)


image

然后對其求偏導(dǎo)數(shù)


image

將三個式子帶入


image
把 μ消掉了
對上式子求關(guān)羽 α 的極大讥此,得到
image

上式右下角的條件限制了α的取值范圍是縮小了的。

進(jìn)一步整理得到對偶問題


image

再進(jìn)一步構(gòu)造最優(yōu)化問題


image

求解得 a^*
然后計算出w 和 b
image

注意:計算 b 的時候需要滿足α在(0谣妻,C)之間

最終求得超平面:
image

損失函數(shù)分析

image

圓圈的點(diǎn):他們的α=C萄喳,他們是有損失的,并且哪些紅色線段表示損失值蹋半;雖然他們分的是對的他巨。但是已經(jīng)進(jìn)入敏感地帶。
方塊的星:他們的0 < α < C,是支持向量
其他點(diǎn):α = 0

損失值=1-d减江;d 是點(diǎn)到超平面的距離染突,那么過渡帶之外的損失值為0,于是得到 SVM 損失函數(shù)圖(Hindge損失)


image

也就是
image

但得到這個最小的時候辈灼,求得新的 w 和 b份企。

我們再看下
[圖片上傳失敗...(image-faff7c-1526290967990)]
這里出現(xiàn)了損失函數(shù),經(jīng)過變換得到新的損失函數(shù)


image

后面一項(xiàng)是 L2正則

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末茵休,一起剝皮案震驚了整個濱河市薪棒,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌榕莺,老刑警劉巖俐芯,帶你破解...
    沈念sama閱讀 221,430評論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異钉鸯,居然都是意外死亡吧史,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,406評論 3 398
  • 文/潘曉璐 我一進(jìn)店門唠雕,熙熙樓的掌柜王于貴愁眉苦臉地迎上來贸营,“玉大人吨述,你說我怎么就攤上這事〕” “怎么了揣云?”我有些...
    開封第一講書人閱讀 167,834評論 0 360
  • 文/不壞的土叔 我叫張陵,是天一觀的道長冰啃。 經(jīng)常有香客問我工碾,道長禽笑,這世上最難降的妖魔是什么橄抹? 我笑而不...
    開封第一講書人閱讀 59,543評論 1 296
  • 正文 為了忘掉前任屈梁,我火速辦了婚禮,結(jié)果婚禮上扇调,老公的妹妹穿的比我還像新娘矿咕。我一直安慰自己,他們只是感情好狼钮,可當(dāng)我...
    茶點(diǎn)故事閱讀 68,547評論 6 397
  • 文/花漫 我一把揭開白布碳柱。 她就那樣靜靜地躺著,像睡著了一般燃领。 火紅的嫁衣襯著肌膚如雪士聪。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,196評論 1 308
  • 那天猛蔽,我揣著相機(jī)與錄音剥悟,去河邊找鬼。 笑死曼库,一個胖子當(dāng)著我的面吹牛区岗,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播毁枯,決...
    沈念sama閱讀 40,776評論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼慈缔,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了种玛?” 一聲冷哼從身側(cè)響起藐鹤,我...
    開封第一講書人閱讀 39,671評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎赂韵,沒想到半個月后娱节,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,221評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡祭示,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,303評論 3 340
  • 正文 我和宋清朗相戀三年肄满,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,444評論 1 352
  • 序言:一個原本活蹦亂跳的男人離奇死亡稠歉,死狀恐怖掰担,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情怒炸,我是刑警寧澤带饱,帶...
    沈念sama閱讀 36,134評論 5 350
  • 正文 年R本政府宣布,位于F島的核電站横媚,受9級特大地震影響纠炮,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜灯蝴,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,810評論 3 333
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望孝宗。 院中可真熱鬧穷躁,春花似錦、人聲如沸因妇。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,285評論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽婚被。三九已至狡忙,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間址芯,已是汗流浹背灾茁。 一陣腳步聲響...
    開封第一講書人閱讀 33,399評論 1 272
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留谷炸,地道東北人北专。 一個月前我還...
    沈念sama閱讀 48,837評論 3 376
  • 正文 我出身青樓,卻偏偏與公主長得像旬陡,于是被迫代替她去往敵國和親拓颓。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,455評論 2 359

推薦閱讀更多精彩內(nèi)容