機器學(xué)習(xí)-第六章 支持向量機(SVM) 6.1 間隔與支持向量
開倍速觀看視頻之后箫踩，對課本所說的會更加了解桦山。支持向量機講解:https://www.bilibili.com/video/av77638697?p=6
給定一個數(shù)據(jù)集D={(x1 ,y1 ),(x2 ,y2 ),……,(xm ,ym )}，yi ∈{-1,+1}。對于分類學(xué)習(xí)來說侧漓，最基本的想法就是找出一個超平面，能夠把不同類別的樣本分開监氢。
對于上圖的分類布蔗，我們會想用一個超平面劃分兩類藤违，可以看出，劃分兩類的超平面有多種纵揍，那我們應(yīng)該選擇哪一種呢顿乒？
在樣本空間中陕凹，超平面的線性方程如下：
1 ,w2 ,……,wd )為法向量悍抑，決定了超平面的方向 鳄炉；b為位移項(截距)，決定了超平面與原點 之間的距離搜骡。劃分超平面最終由w和b確定拂盯，記為(w,b)。i ,yi )∈D谈竿，i =1，則wT xi +b>0摸吠；若yi = -1空凸，則有wT xi +b < 0，令由于上面這個轉(zhuǎn)換詳解過于復(fù)雜寸痢，可以看視頻詳解呀洲，這里不作說明。對于距離超平面最近的樣本點啼止，我們稱為"支持向量" 道逗。兩個異類支持向量到超平面的距離之和 稱為間隔，如下為了盡可能劃分類別正確献烦，我們可以轉(zhuǎn)化為找到具有"最大間隔" 的超平面滓窍，即找到w和b，使得γ最大巩那，即而最大化間隔吏夯，就需要最大化||w||-1 此蜈，相當(dāng)于最小化||w||2 ，則目標(biāo)可以重寫為這就是支持向量機(SVM)的基本模型锦亦。
6.2 對偶問題
原始問題與對偶問題以及KKT條件的關(guān)系解釋https://blog.csdn.net/fkyyly/article/details/86488582
原始問題與對偶問題的視頻講解:https://www.bilibili.com/video/av77638697?p=11
原始問題轉(zhuǎn)化為對偶問題:https://www.bilibili.com/video/av77638697?p=12
對于上式，是一個凸函數(shù)二次規(guī)劃的問題杠园。我們可以對上式使用拉格朗日乘子法 得到原始問題的對偶問題顾瞪。
對每個約束條件添加拉格朗日乘子αi ，且αi ≥0抛蚁，則該問題的優(yōu)化函數(shù)為
先求優(yōu)化函數(shù)對于w和b的極小值即陈醒，對w和b求偏導(dǎo)，令偏導(dǎo)為0瞧甩，有接著將w代入優(yōu)化函數(shù)得到可以看出钉跷，對w和b求偏導(dǎo)之后代入，再考慮對b求偏導(dǎo)得到的約束肚逸，就得到了對偶問題得到優(yōu)化函數(shù)只剩下α作為參數(shù)爷辙，只要求優(yōu)化函數(shù)的極大值纬朝，就可以求出α藕帜，進(jìn)而求出w和b，再代入我們的模型胸完，就可以了务冕，假設(shè)我們的模型是f(x) = wT x + b血当，則上述過程要滿足KKT條件對于對偶問題，我們該如何求解α呢禀忆？我們用的就是SMO算法 SMO基本思路 ：先固定αi 之外的所有參數(shù)臊旭，然后求αi 上的極值。SMO步驟： 每次選擇兩個變量αi 和αj 箩退，并固定其他參數(shù)离熏，分別對αi 和αj 求偏導(dǎo)為0，得到αi 和αj 戴涝，若符合約束條件就不用算滋戳，若不符合約束條件，再更新αi 和αj 喊括，代入對偶問題的目標(biāo)函數(shù)胧瓜，直到符合條件。可以看出郑什，SMO固定了其他的參數(shù)府喳，僅僅考慮αi 和αj ，因此對偶問題中的約束條件可以重寫為其中的c通過重寫之后的約束條件蘑拯，我們可以將對偶問題中的目標(biāo)函數(shù)的αj 消去钝满，只剩下αi 一個變量兜粘，這時我們的約束只有KKT里面的αi ≥0，對αi 求導(dǎo)為0弯蚜，得到αi 孔轴，再求出aj ，通過這樣子我們可以更高效的求出ai 和aj 碎捺。求出α之后路鹰，代入就可以計算出w了。使用所有支持向量求解的平均值 s ,ys )i >0,i = 1,2,3……,m}為所有支持向量的下標(biāo)集晋柱。
支持向量機的代碼實現(xiàn)：https://blog.csdn.net/qq_43608884/article/details/88658216
6.3 核函數(shù)
在前面的討論中，我們假設(shè)訓(xùn)練樣本都是線性可分的诵叁，上述SVM也只是在處理線性可分的數(shù)據(jù)雁竞。事實上，我們很多數(shù)據(jù)都是非線性可分的拧额。
對于非線性的情況碑诉，SVM 的處理方法是選擇一個核函數(shù) κ(?,?) ，通過將數(shù)據(jù)映射φ到高維空間侥锦，來解決在原始空間中線性不可分的問題进栽。
具體來說，在線性不可分的情況下捎拯，支持向量機首先在低維空間中完成計算泪幌，然后通過核函數(shù)將輸入空間映射到高維特征空間盲厌，最終在高維特征空間中構(gòu)造出最優(yōu)分離超平面署照，從而把平面上本身不好分的非線性數(shù)據(jù)分開。
類似，原始問題為對偶問題為其中懂扼，紅色方框里面的式子禁荸，表示的是樣本xi 和xj 映射到特征空間之后的內(nèi)積，當(dāng)屬性空間的維數(shù)很大時阀湿，直接計算內(nèi)積是很困難的赶熟，因此，有即xi 和xj 在屬性空間 中的內(nèi)積等于在原始樣本空間 中通過函數(shù)K(·,·)計算的結(jié)果陷嘴。函數(shù)K(·,·)映砖，就是核函數(shù) 。
常用的核函數(shù)K(·,·)有以下幾種關(guān)于核函數(shù)邑退，有下面三個關(guān)系：
若k1 和k2 為核函數(shù)竹宋，則對于任意正數(shù)γ1 和γ2 ，其線性組合γ1 k1 +γ2 k2 也為核函數(shù)
若k1 和k2 為核函數(shù)地技，則核函數(shù)的直積也為核函數(shù)
若k1 和k2 為核函數(shù)蜈七，則對于任意函數(shù)g(x)也是核函數(shù)
對文本數(shù)據(jù)通常采用線性核，情況不明時可先嘗試高斯核莫矗。
支持向量機的非線性代碼實現(xiàn)https://blog.csdn.net/kt513226724/article/details/80413018
6.4 軟間隔與正則化
在上述中的支持向量機中飒硅，我們要求所有樣本都要滿足約束，即都被劃分正確作谚，這叫做"硬間隔" 狡相。可實際上食磕，很難確定合適的核函數(shù)使得樣本在特種空間中線性可分尽棕，不允許分類錯誤的樣本。"軟間隔" 。
軟間隔允許某些樣本不滿足約束條件单绑，也要讓這些樣本很少回官。則優(yōu)化目標(biāo)可以寫為其中C是一個常數(shù)，可以理解為問題正則化時加入的參數(shù)搂橙。當(dāng)C趨于無窮大時歉提，所有樣本均滿足原來硬間隔的約束條件；當(dāng)C取有限值時区转，允許一些樣本不滿足約束苔巨。"0/1損失函數(shù)" 的不可微、不連續(xù)废离，數(shù)學(xué)性質(zhì)較差侄泽，于是我們可以用其他函數(shù)替代損失函數(shù)，稱為"替代損失函數(shù)" 蜻韭，通常數(shù)學(xué)性質(zhì)較好悼尾，通常有以下三種替代損失函數(shù)：下面我們使用hinge損失函數(shù)來優(yōu)化目標(biāo)。
首先對訓(xùn)練集的每個樣本(xi ,yi )引入一個松弛變量 ξi ≥0肖方，使函數(shù)間隔加上松弛變量大于等于1闺魏，也就是說，約束條件變?yōu)?/p>
對比硬間隔最大化俯画，可以看到我們對樣本到超平面的函數(shù)距離的要求放松了析桥，之前是一定要大于等于1，現(xiàn)在只需要加上一個大于等于0的松弛變量能大于等于1就可以了。當(dāng)引入了ξ之后烹骨，也是需要成本的翻伺，所以硬間隔到軟間隔的優(yōu)化目標(biāo)變?yōu)?div id="n59iqlr" class="image-package">
硬間隔到軟間隔
接著我們對軟間隔支持向量機進(jìn)行目標(biāo)函數(shù)的優(yōu)化。通過拉格朗日乘子法得到
對w沮焕、b和ξ求偏導(dǎo)為0吨岭，得到
將他們代入拉格朗日函數(shù)
此時我們就得到了，原始問題的對偶問題峦树，
接著用SMO算法算出α辣辫，就可以得到w，然后再計算b魁巩，與硬間隔類似急灭。
對于上述過程，也需要滿足KKT條件
對于訓(xùn)練樣本(x
i ,y
i )谷遂，有
1）若α=0葬馋，那么y
i (w
T x
i +b)-1≥0，即樣本在間隔邊界之外肾扰，即被正確分類畴嘶。
2）若0<α<C，那么ξ
i =0集晚，y
i (w
T x
i +b)-1=0窗悯，即樣本在間隔邊界上。
3）若α=C偷拔，則μ
i =0蒋院，該樣本點是有可能正確分類、也有可能分類錯誤莲绰，此時考試ξ
i 欺旧。
① 如果0≤ξ
i ≤1，那么樣本點在超平面和間隔邊界之間钉蒲，但是被正確分類切端。
② 如果ξ
i =1彻坛，那么樣本點在超平面上顷啼，無法被正確分類。
③ 如果ξ
i ＞1昌屉，樣本點被分類錯誤钙蒙。
對于，允許誤差的優(yōu)化目標(biāo)函數(shù)间驮，我們可以寫為更加一般的形式
Ω(f)稱為"結(jié)構(gòu)風(fēng)險"躬厌，用于描述模型f的某些性質(zhì)；
第二項的Σ
m l(f(x
i ),y
i )稱為"經(jīng)驗風(fēng)險"，用于描述模型與訓(xùn)練數(shù)據(jù)的契合度扛施。
C稱為正則化常數(shù)鸿捧，用于對結(jié)構(gòu)風(fēng)險和經(jīng)驗風(fēng)險進(jìn)行折中。
上式被稱為"正則化問題"疙渣，Ω(f)稱為正則化項匙奴，C為正則化常數(shù)。
6.5 支持向量回歸(SVR)
上面講到的SVM是用于分類任務(wù) 的妄荔，而對于回歸任務(wù) 泼菌，我們使用SVR。
SVM分類啦租，就是找到一個平面哗伯，讓兩個分類集合的支持向量或者所有的數(shù)據(jù)離分類平面最遠(yuǎn)；
SVR假設(shè)f(x)與y之間最多有ε的偏差恳蹲，即以f(x)為中心伴澄，允許f(x)+ε和f(x)-ε的誤差，構(gòu)建一個2ε的間隔阱缓。
SVR的形式如下
由于間隔帶的兩側(cè)松弛程度有所不同非凌，所有引入松弛變量ξ
i 和ξ^
i ，則原始問題重寫為
接著我們要求對偶問題荆针。首先引入拉格朗日乘子敞嗡，可以得到拉格朗日函數(shù)
令L對w、b航背、ξ
i 喉悴、ξ^
i 的偏導(dǎo)為0，可得到
將它們代入L玖媚，可以得到對偶問題
上述過程中箕肃，要滿足KKT條件
將上面求得的w代入我們原來的模型f(x) = wT x + b，得到SVR的解
由KKT可以看出今魔，對每個樣本(x
i ,y
i )有:
1）(C - α
i )ξ
i =0 勺像，2）α
i (f(x
i ) - y
i - ε - ξ
i )=0。
于是通過SMO算法得到α
i 之后错森，若0<α
i <C吟宦，則必有ξ
i =0，可以得到b
實際上涩维，我們更常用的是：選取所有滿足0 < a
i < C的樣本求解b之后取平均值殃姓。
若考慮映射到高維空間則有
最終通過上述類似的求解過程，我們得到SVR可以表示為
6.6 核方法
對于SVM和SVR，它們的優(yōu)化問題都是類似下面的式子
而SVR和SVM學(xué)得的模型總能表示為核函數(shù)K(x,x
i )的線性組合蜗侈，所以上式的模型也可以寫成為核函數(shù)的線性組合
對于上面這個結(jié)論篷牌，就是
"表示定理"
人們基于核函數(shù)的學(xué)習(xí)方法，稱為
"核方法" 踏幻。最常見的娃磺，是通過引入核函數(shù)來將線性學(xué)習(xí)擴展為非線性。
下面以"核線性判別分析"(KLDA)為例叫倍，演示如何引入核函數(shù)進(jìn)行非線性擴展偷卧。
我們難以直到映射φ的具體形式，因此使用核函數(shù)K(x,x
i ) = φ(x
i )
T φ(x)來表達(dá)映射和特征空間F吆倦。
把J(w)作為式子6.57中的損失函數(shù)听诸，令Ω=0，有
由表示定理得蚕泽，
再由式6.59得
最后編輯于 ：2020.02.10 23:25:00
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
序言：七十年代末晌梨，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子须妻，更是在濱河造成了極大的恐慌仔蝌，老刑警劉巖，帶你破解...
序言：濱河連續(xù)發(fā)生了三起死亡事件荒吏，死亡現(xiàn)場離奇詭異敛惊，居然都是意外死亡，警方通過查閱死者的電腦和手機绰更，發(fā)現(xiàn)死者居然都...
文/潘曉璐 我一進(jìn)店門瞧挤，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人儡湾，你說我怎么就攤上這事特恬。” “怎么了徐钠？”我有些...
文/不壞的土叔 我叫張陵癌刽，是天一觀的道長。 經(jīng)常有香客問我尝丐，道長显拜，這世上最難降的妖魔是什么？ 我笑而不...
正文 為了忘掉前任摊崭，我火速辦了婚禮讼油，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘呢簸。我一直安慰自己，他們只是感情好，可當(dāng)我...
文/花漫 我一把揭開白布根时。 她就那樣靜靜地躺著瘦赫，像睡著了一般。 火紅的嫁衣襯著肌膚如雪蛤迎。 梳的紋絲不亂的頭發(fā)上确虱，一...
那天，我揣著相機與錄音替裆，去河邊找鬼校辩。 笑死，一個胖子當(dāng)著我的面吹牛辆童，可吹牛的內(nèi)容都是我干的宜咒。 我是一名探鬼主播，決...
文/蒼蘭香墨 我猛地睜開眼把鉴，長吁一口氣：“原來是場噩夢啊……” “哼故黑！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起庭砍，我...
序言：老撾萬榮一對情侶失蹤场晶，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后怠缸，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體诗轻，經(jīng)...
正文 獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
正文 我和宋清朗相戀三年揭北，在試婚紗的時候發(fā)現(xiàn)自己被綠了概耻。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
序言：一個原本活蹦亂跳的男人離奇死亡罐呼，死狀恐怖鞠柄，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情嫉柴，我是刑警寧澤厌杜，帶...
正文 年R本政府宣布，位于F島的核電站计螺，受9級特大地震影響夯尽，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜登馒，卻給世界環(huán)境...
文/蒙蒙 一匙握、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧陈轿，春花似錦圈纺、人聲如沸秦忿。這莊子的主人今日做“春日...
文/蒼蘭香墨 我抬頭看了看天上的太陽灯谣。三九已至，卻和暖如春蛔琅，著一層夾襖步出監(jiān)牢的瞬間胎许，已是汗流浹背。 一陣腳步聲響...
我被黑心中介騙來泰國打工罗售， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留辜窑，地道東北人。 一個月前我還...
正文 我出身青樓寨躁，卻偏偏與公主長得像穆碎，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子朽缎，可洞房花燭夜當(dāng)晚...
【概述】 SVM訓(xùn)練分類器的方法是尋找到超平面惨远，使正負(fù)樣本在超平面的兩側(cè)（分類正確性即“分得開”），且樣本到超平面...
SVM支持向量機 一话肖、簡介 支持向量機（support vector machines）是一種二分類模型北秽，它的目的...
支持向量機 原理 《機器學(xué)習(xí)》周志華 6.1 間隔與支持向量 給定訓(xùn)練樣本集 D，分類學(xué)習(xí)最基本的想法就是基于訓(xùn)練...
SVM支持向量機 本片文章主要記錄在學(xué)習(xí)《統(tǒng)計學(xué)習(xí)方法》中 SVM 章節(jié)的難點最筒，不對詳細(xì)內(nèi)容進(jìn)行講解贺氓。主要是分析筆...
寫在最前面 如今機器學(xué)習(xí)和深度學(xué)習(xí)如此火熱，相信很多像我一樣的普通程序猿或者還在大學(xué)校園中的同學(xué)床蜘，一定也想?yún)⑴c其中...
