支持向量機(jī) (Support Vector Machine)

SVM俗語：

SVM有三寶：間隔匹层、對偶呵晨、核技巧

SVM的由來

對于線性可分的問題吐限，一般可以使用PLA得到解決忽刽，但是根據(jù)其原理可以得到天揖，PLA只是負(fù)責(zé)得到一個(gè)線性可分的線/超平面，但是對于這根線/超平面跪帝，并不能保證最好今膊。

所以對于線性可分?jǐn)?shù)據(jù)來說，有無數(shù)條線/平面滿足條件伞剑，但是最完美（最完美的意思表示在在新的數(shù)據(jù)上擬合效果最好）只有一條, 魯棒性最好

margin：
the distance of hyperplane to its closest point
has at least 2 closest points (one is a positive point and one is a negative point)

總結(jié)一下
SVM = hyperplane + maximum margin

SVM關(guān)鍵詞

監(jiān)督學(xué)習(xí)斑唬，二分類器，學(xué)習(xí)策略：間隔最大化

SVM的目標(biāo)函數(shù)

對于二維平面來說，通過一條直線 $y=ax+b$ 可以將平面分成兩部分恕刘，一部分?jǐn)?shù)據(jù)為正缤谎，一部分?jǐn)?shù)據(jù)為負(fù)，由此進(jìn)行拓展雪营，對于 $d$ 維的 $x$ 弓千，其超平面的方程為：
$w^{T} x+b=0$
與之超平面對應(yīng)的分類模型為
$f(w,b) = sign(w^{T} x+b)$

首先明確一點(diǎn) $w$ 垂直與所求的超平面：
證明：任意取超平面上的兩點(diǎn) $x_{1}$ , $x_{2}$ ，其構(gòu)成向量 $x_{1}-x_{2}$
$w^{T} x_{1}+b=0$

$w^{T} x_{2}+b=0$

兩個(gè)公式相減献起，得到 $w^{T} (x_{1}-x_{2})= 0$

為了后續(xù)方便計(jì)算和說明洋访，這里做一個(gè)假設(shè)
$w^{T} x_{n}+b=1$ 其中 $x_{n}$ 為距離超平面最近的正類點(diǎn)

進(jìn)一步說明： $w^{T} x_{n}+b$ 可以為任何值，但是由于已經(jīng)確定了 $x_{n}$ 為距離超平面最近的正類點(diǎn)谴餐，所以即使結(jié)果為10或者為100或者任意大于1的值姻政，只要對其進(jìn)行歸一化，并不會對其他的點(diǎn)有任何影響（主要就是強(qiáng)調(diào)一個(gè)相對的概念）岂嗓。

1/||w||的由來.png

$w^{T} (x_{n}-x) = w^{T} (a+c) =w^{T} c = ||w||*||c||$

$||c|| = \frac{1}{\|\vec{w}\|}$

所以距離超平面最近的點(diǎn)與超平面的距離為 $\frac{1}{\|\vec{w}\|}$ ,也就是所謂的maximum margin的的表達(dá)汁展，于是SVM的目標(biāo)函數(shù)則找到了，即
$max \frac{1}{\|\vec{w}\|}$

SVM目標(biāo)函數(shù)的轉(zhuǎn)化

雖然找到了SVM的目標(biāo)函數(shù) $\frac{1}{\|\vec{w}\|}$ 厌殉，并且想要找到其的最大值食绿，但是不要忘記一個(gè)假設(shè)前提， $w^{T} x_{n}+b=1$ , 其限制了與超平面最近的正類點(diǎn)公罕，與其說是限制了與超平面最近的正類點(diǎn)器紧，不如說是限制了所有的點(diǎn)，也就是說楼眷，除開最近的點(diǎn) $w^{T} x_{n}+b=1$ 铲汪，其他點(diǎn)的得到的結(jié)果必須比1大，也就是目標(biāo)函數(shù)擴(kuò)展成：

（1）
$\max \frac{1}{\|\vec{w}\|}$

$s.t. \min |w^{T} x_{i}+b|=1 ,i = 1...N$ 其中N表示數(shù)據(jù)點(diǎn)的總數(shù)

我們對其進(jìn)行進(jìn)一步轉(zhuǎn)化
（2）

$\min ||w||$

$s.t. \min |w^{T} x_{i}+b|=1 ,i = 1...N$

我們對第（2）中第二個(gè)限制進(jìn)行分解罐柳，得到
(3)

$\min ||w||$

$\forall i , |w^{T} x_{i}+b| \geq1 ,i = 1...N$

這里需要解釋一下（2）到（3）的過程掌腰，其實(shí)嚴(yán)格來說（2）的限制和（3）的限制其實(shí)不對等，因?yàn)椋?）中說明是最近的點(diǎn)距離為1张吉，但是（3）中說明的是所有點(diǎn)距離大于等于1齿梁，這里是對于（2）來說是一個(gè)充分不必要條件，唯一的風(fēng)險(xiǎn)就是所有的點(diǎn)都比1大肮蛹，舉個(gè)例子勺择，比如說一共5個(gè)點(diǎn)，對于（2）的話距離的列表可能為[1,2,3,4,5]蔗崎，對于（3）來說可能為[10,20,30,40,50]酵幕。

這里就需要重新回到我們之前提到的相對距離的概念了扰藕，這個(gè)結(jié)果10的得到其實(shí)是 $w^{T} x_{i}+b = 10$ 缓苛，所以只要將 $w$ 和 $b$ 的除以10，最近距離的點(diǎn)結(jié)果依舊是1，所以在這里的話（2）和（3）的限制是相等的未桥。

對（3）進(jìn)一步轉(zhuǎn)化得到（4）笔刹，這里還進(jìn)行一步轉(zhuǎn)化的原因是為了利用已有的凸優(yōu)化理論，使用1/2是為了方便后續(xù)計(jì)算
（4）
$\min \frac{1}{2} w^{T} \cdot w$

$\forall i , |w^{T} x_{i}+b| \geq1 ,i = 1...N$

這里我們可以發(fā)現(xiàn)其實(shí)限制有N個(gè)冬耿， $|w^{T} x_{i}+b| \geq1$ 帶上絕對值符號不利于后續(xù)的計(jì)算舌菜，所以對其進(jìn)行分解，
當(dāng)point為正類時(shí)亦镶， $w^{T} x_{i}+b \geq1$ 日月， $y_{i} = +1$
當(dāng)point為正類時(shí)， $w^{T} x_{i}+b \leq1$ 缤骨， $y_{i} = -1$
所以限制轉(zhuǎn)化為
$\forall i , y_{i} (w^{T} x_{i}+b) \geq1 ,i = 1...N$

這樣目標(biāo)函數(shù)求解問題得到的最終的完美形式：

$\min \frac{1}{2} w^{T} \cdot w$

$\forall i , y_{i} (w^{T} x_{i}+b) \geq1 ,i = 1...N$

優(yōu)化問題求解（數(shù)學(xué)背景）

通過上述一系列的轉(zhuǎn)化爱咬，可以發(fā)現(xiàn)，最終目標(biāo)函數(shù)的求解本質(zhì)上是一個(gè)線性規(guī)劃的優(yōu)化問題绊起，其中給定的約束有 $N$ 個(gè)（ $N$ 個(gè)點(diǎn)精拟，所以有 $N$ 個(gè)不等式），未知參數(shù)有 $d+1$ 個(gè)（ $d$ 個(gè) $w$ 和 $1$ 個(gè) $b$ )虱歪，目標(biāo)函數(shù)是二次的蜂绎。

拉格朗日乘子法

拉格朗日乘子法：有約束情況下求函數(shù)極值的方法,這里借助拉格朗日乘子法引出對偶問題
https://www.youtube.com/watch?v=lDehPPIgQpI
https://charlesliuyx.github.io/2017/09/20/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%B3%95%E5%92%8CKKT%E6%9D%A1%E4%BB%B6/

這里我們將原問題稱為 $p1$ ,
$p1$ 的拉格朗日函數(shù) $p2$ 為（更多信息參考上述鏈接，這里直接給出結(jié)論）：
$L(w, b, \lambda)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left[1-y_{i}\left(w^{T} x_{i}+b\right)\right]$

$\lambda_{i} \geq 0$

$1- y_{i}(w^{T} x_{i}+b) \leq 0$

最小化問題 $p1$ : $\min_{w, b} \frac{1}{2} w^{T} \cdot w$ 轉(zhuǎn)化為 $p2:$ $\min _{w, b} \max _{\lambda} L(w, b ,\lambda)$
$p1$ 對 $w, b$ 的函數(shù)笋鄙， $w,b$ 為自變量
$p2$ 首先以 $\lambda$ 為自變量求 $L$ 的最大值 $L1$ 师枣，隨后以 $w,b$ 為自變量求得到的 $L1$ 中的最小值，其本質(zhì)上還是對 $w, b$ 的函數(shù)

使用拉格朗日乘子的好處：
將帶約束的問題轉(zhuǎn)化為無約束的問題局装，這里指的帶約束是指對參數(shù) $w,b$ 的限制條件

但是描述 $p2$ 的時(shí)候可以知道其實(shí)是帶了 $1- y_{i}(w^{T} x_{i}+b) \leq 0$ 坛吁，這樣子的話其實(shí)還是會有對參數(shù) $w,b$ 的約束，其實(shí)這個(gè)約束可以舍去铐尚，因?yàn)楹瘮?shù) $L$ 天然的帶有 $1- y_{i}(w^{T} x_{i}+b) \leq 0$ 約束

解釋：https://www.youtube.com/watch?v=WeoASoHnTpc&list=PLOxMGJ_8X74Z1N3OcacUaCxiXaGNHtFw2&index=2

Lagrange的奇妙之處.png

對偶的引出

目標(biāo)函數(shù)是二次拨脉，約束條件是線性，=> 凸二次規(guī)劃問題 (QPP,Quadratic programming problem)宣增，理想情況可以使用一些QP的套件直接進(jìn)行求解得到答案玫膀，但是存在樣本維度過高或者樣本數(shù)很多，或者存在樣本特征升維的一些情況爹脾，QP可能就不太能夠直接求解帖旨，由此引入了對偶求解的概念。

由于將問題 $p1$ 轉(zhuǎn)化成了 $p2$ ,為了求解的方便灵妨，可以將 $p2$ 轉(zhuǎn)化為其對偶問題 $p3$

$p2: \min _{w, b} \max _{\lambda} L(w, b ,\lambda)$

$p3: \max _{\lambda} \min _{w, b} L(w, b ,\lambda)$

這里需要提及一個(gè)關(guān)于對偶問題的性質(zhì)：
1.弱對偶性——對偶問題 $\leqslant$ 原問題
$\max \min L \leqslant \min \max L$

簡單的來說就是小的里面最大的小不會比大的里面最小的大（雞頭<鳳尾）
證明：
https://www.youtube.com/watch?v=bscvk5n_TsM&list=PLOxMGJ_8X74Z1N3OcacUaCxiXaGNHtFw2&index=5

2.強(qiáng)對偶性
$\max \min L = \min \max L$

凸二次函數(shù)優(yōu)化問題 + 約束線性 ---> 滿足強(qiáng)對偶關(guān)系

根據(jù)上述的定理可以發(fā)現(xiàn)通過這樣一步的對偶問題轉(zhuǎn)換解阅，我們把本來需要求的以 $\lambda$ 為參數(shù)的 $L$ 的最大值后以以 $w,b$ 為參數(shù)的最小值(本質(zhì)上未知數(shù)是 $w,b$ ) 轉(zhuǎn)換成
以 $w,b$ 為參數(shù)的 $L$ 的最小值后以 $\lambda$ 為參數(shù)的最大值(本質(zhì)上未知數(shù)是 $\lambda$ )

對偶問題轉(zhuǎn)化1.png

對偶問題轉(zhuǎn)化2.png

KKT

一句話解釋：對偶問題具有強(qiáng)對偶性 <=> KKT

KTT與w* ,b*求解.png

總結(jié)：
SVM參數(shù)的求解主要是通過問題的不斷轉(zhuǎn)化得到的
其主要流程為：
1.原始的約束問題 $p1$ 通過拉格朗日函數(shù)轉(zhuǎn)化為無約束問題 $p2$
2.通過 $p2$ 的強(qiáng)對偶性轉(zhuǎn)換成為對偶問題 $p3$
3.在 $p3$ 滿足KKT的條件下進(jìn)行 $w^{*},b^{*}$ 的求解

拉格朗日對偶性的求解

函數(shù)的轉(zhuǎn)換圖片復(fù)制于github.png

SMO 算法

通過上述的描述，得到最終所求的 $w^{*},b^{*}$ 為
$w^{*}=\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}$

$b^{*}=y_{k}-\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}^{T} x_{k}$

所以我們的目的為求合適的 $\lambda_{i} , i= 1...N$ ,這里就采用SMO的算法來進(jìn)行解決泌霍，由于本人水平有限货抄，暫時(shí)還沒搞懂，待到明白了再來補(bǔ)上。
下次一定蟹地，下次一定积暖。

OP優(yōu)化包

pip install cvxopt

cvxopt.png

總結(jié)

至此，SVM的整個(gè)流程基本上捋了一遍怪与，注意這里主要介紹的是硬間隔問題夺刑，但是掌握了這個(gè)，再去看軟間隔和非線性分類（核函數(shù)）分别，一定會事半功倍遍愿。

參考資料：https://github.com/ws13685555932/machine_learning_derivation/blob/master/06%20%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA.pdf
http://slidesplayer.com/slide/11358544/
https://www.zhihu.com/question/36301367
https://www.jiqizhixin.com/articles/2018-10-17-20
https://charlesliuyx.github.io/2017/09/20/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%B3%95%E5%92%8CKKT%E6%9D%A1%E4%BB%B6/
https://www.youtube.com/watch?v=lDehPPIgQpI
https://blog.csdn.net/v_JULY_v/article/details/7624837

最后編輯于：2020.04.19 14:29:13

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市耘斩，隨后出現(xiàn)的幾起案子错览，更是在濱河造成了極大的恐慌，老刑警劉巖煌往，帶你破解...
沈念sama閱讀 211,743評論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件倾哺，死亡現(xiàn)場離奇詭異，居然都是意外死亡刽脖，警方通過查閱死者的電腦和手機(jī)羞海，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,296評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來曲管，“玉大人却邓，你說我怎么就攤上這事≡核” “怎么了腊徙？”我有些...
開封第一講書人閱讀 157,285評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長檬某。經(jīng)常有香客問我撬腾，道長，這世上最難降的妖魔是什么恢恼？我笑而不...
開封第一講書人閱讀 56,485評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任民傻，我火速辦了婚禮，結(jié)果婚禮上场斑，老公的妹妹穿的比我還像新娘漓踢。我一直安慰自己，他們只是感情好漏隐，可當(dāng)我...
茶點(diǎn)故事閱讀 65,581評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布喧半。她就那樣靜靜地躺著，像睡著了一般青责。火紅的嫁衣襯著肌膚如雪挺据。梳的紋絲不亂的頭發(fā)上半沽，一...
開封第一講書人閱讀 49,821評論 1贊 290
城市分裂傳說
那天，我揣著相機(jī)與錄音吴菠，去河邊找鬼。笑死浩村，一個(gè)胖子當(dāng)著我的面吹牛做葵，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播心墅，決...
沈念sama閱讀 38,960評論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼酿矢，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了怎燥？” 一聲冷哼從身側(cè)響起瘫筐，我...
開封第一講書人閱讀 37,719評論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎铐姚，沒想到半個(gè)月后策肝，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,186評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡隐绵，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,516評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年之众，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片依许。...
茶點(diǎn)故事閱讀 38,650評論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡棺禾，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出峭跳，到底是詐尸還是另有隱情膘婶，我是刑警寧澤，帶...
沈念sama閱讀 34,329評論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布蛀醉，位于F島的核電站悬襟，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏拯刁。R本人自食惡果不足惜古胆，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,936評論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望筛璧。院中可真熱鬧逸绎，春花似錦、人聲如沸夭谤。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,757評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽朗儒。三九已至颊乘，卻和暖如春参淹，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背乏悄。一陣腳步聲響...
開封第一講書人閱讀 31,991評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工浙值，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人檩小。一個(gè)月前我還...
沈念sama閱讀 46,370評論 2贊 360
代替公主和親
正文我出身青樓开呐，卻偏偏與公主長得像，于是被迫代替她去往敵國和親规求。傳聞我的和親對象是個(gè)殘疾皇子筐付，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,527評論 2贊 349