[機(jī)器學(xué)習(xí)算法]支持向量機(jī)

原理

分類學(xué)習(xí)最基本的思想就是基于訓(xùn)練集 $D$ 在樣本空間中找到一個劃分超平面，將不同類別的樣本區(qū)分開窥摄。但是事實(shí)上镶奉，能將訓(xùn)練樣本劃分開的超平面可能有很多，如下圖所示崭放，我們的任務(wù)就是尋找到最優(yōu)的劃分超平面哨苛。

image.png

劃分超平面的線性方程可以表達(dá)為：

$w^Tx+b=0$
其中 $w$ 為法向量，決定了超平面的方向币砂； $b$ 為位移項(xiàng)移国，決定了超平面與原點(diǎn)之間的距離。劃分超平面可由法向量 $w$ 和位移項(xiàng) $b$ 確定道伟，我們將其記為 $(w,b)$ 迹缀。樣本空間中任意點(diǎn) $x$ 到超平面的 $(w,b)$ 的距離可寫為：

$r=\frac{|w^Tx+b|}{||w||}$
假設(shè)劃分超平面能將樣本正確分類使碾，那么即位于超平面兩側(cè)的分別為正例和負(fù)例，即：

$\begin{cases} \text{若}y_i=+1,\text{則有}w^Tx+b>0\\ \text{若}y_i=-1,\text{則有}w^Tx+b<0 \end{cases}$
我們構(gòu)建如下模型：
$\begin{cases} w^Tx+b\geq+1,y_i=+1\\ w^Tx+b\leq-1,y_i=-1 \end{cases}$
其中距離超平面最近的幾個訓(xùn)練點(diǎn)正好使上式等號成立祝懂，它們被稱為“支持向量”support vector票摇，任意兩個異類支持向量到超平面的距離之和為：

$y=\frac{2}{||w||}$
它也被稱為“間隔”margin。支持向量與間隔的含義如下圖所示：

image.png

支持向量機(jī)模型

為了找到合適的劃分超平面使得產(chǎn)生的分類結(jié)果是最魯棒的(即對未見示例的泛化能力最強(qiáng))砚蓬，我們令劃分超平面的“間隔”最大化：
$\max_{w,b}\quad\frac{2}{||w||} \\ s.t. \quad y_i(w^Tx+b)\geq1,i=1,2,...,m$
等價于：
$\min_{w,b}\quad\frac{1}{2}||w||^2 \\ s.t. \quad y_i(w^Tx+b)\geq1,i=1,2,...,m$

參數(shù)求解

對上式使用拉格朗日乘子法可以得到:

$L(w,b,a)=\frac{1}{2}||w||^2+\sum_{i=1}^{m}a_i(1-y_i(w^Tx_i+b))$
對 $w$ 和 $b$ 求偏導(dǎo)為零后：

$w=\sum_{i=1}^{m}a_iy_ix_i, 0=\sum_{i=1}^{m}a_iy_i$
將求完偏導(dǎo)后的值代入原方程后可以消去 $w$ 和 $b$ ,得到對偶問題：
$\max_{a} \quad\sum_{i=1}^{m}a_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}a_ia_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}a_iy_i=0,a_i\geq0$
通過對偶問題解出 $a$ 后矢门，求出 $w$ 和 $b$ 的值即可得到模型：

$f(x)=w^Tx+b=\sum_{i=1}^{m}a_iy_ix_i^Tx_+b$
上述過程需要滿足KKT(Karush-Kuhn-Tucker)條件，即要求：
$\begin{cases} a_i\geq0\\ y_if(x_i)-1\geq0\\ a_i(y_if(x_i)-1)=0 \end{cases}$
從而對于任意的訓(xùn)練樣本 $(x_i,y_i)$ 總有 $a_i=0$ 或者 $y_if(x_i)=1$ 灰蛙。若 $a_i=0$ 祟剔，則模型中不會出現(xiàn)該樣本，也就不會對 $f(x)$ 有影響摩梧；若 $a_i>0$ 物延，則必然有 $y_if(x_i)=1$ ,所對應(yīng)的樣本點(diǎn)正好在最大間隔邊界上，是一個支持向量仅父。
這說明：訓(xùn)練完成后叛薯，大部分的訓(xùn)練樣本不需要保留，最終模型只與支持向量有關(guān)笙纤。

SMO算法

上面我們得到支持向量機(jī)的對偶問題：
$\max_{a} \quad\sum_{i=1}^{m}a_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}a_ia_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}a_iy_i=0,a_i\geq0$
這本身是一個二次規(guī)劃問題耗溜，可以利用通用的二次規(guī)劃算法來求解。但是因?yàn)樵搯栴}的規(guī)模正比于訓(xùn)練樣本數(shù)省容，這會在實(shí)際任務(wù)中造成很大的開銷抖拴。為此人們通過利用問題本身的特性，提出了SMO(Sequential Minimal Optimization)算法:

SMO算法：基本思路是固定 $a_i$ 之外的所有參數(shù)腥椒，然后求 $a_i$ 上的極值城舞。由于存在約束，因此如果固定 $a_i$ 之外的其他參數(shù)寞酿，那么 $a_i$ 可直接由其他參數(shù)導(dǎo)出家夺。因此SMO每次選擇兩個變量 $a_i$ 和 $a_j$ 并固定其他參數(shù)，在參數(shù)初始化后不斷執(zhí)行如下兩個步驟直至收斂：

選取一對需更新的 $a_i$ 和 $a_j$
固定 $a_i$ 和 $a_j$ 以外的其他參數(shù)伐弹，求解規(guī)劃問題獲得更新后的 $a_i$ 和 $a_j$

核函數(shù)

在前面的推導(dǎo)過程中拉馋，我們假設(shè)訓(xùn)練樣本是線性可分的，即存在一個劃分超平面能將訓(xùn)練樣本正確分類惨好，但在現(xiàn)實(shí)任務(wù)中煌茴，原始樣本空間可能并不存在一個能正確劃分兩類樣本的超平面。如下圖左側(cè)的圖就是非線性可分的日川。
假若我們能將樣本從原始空間映射到一個更高緯度的特征空間蔓腐，使得樣本在該特征空間內(nèi)線性可分，那么支持向量機(jī)就可以繼續(xù)使用龄句。比如下圖右側(cè)的圖就是將原始的二維空間映射到一個合適的三維空間回论，從而找到了合適的劃分超平面散罕。

image.png

映射到高維度的支持向量機(jī)模型可以表示為：

$f(x)=w^T\phi(x)+b,\text{其中}\phi(x)\text{表示將}x\text{映射后的特征向量}$

$\min_{w,b}\quad\frac{1}{2}||w||^2$

$s.t.\quad y_i(w^T\phi(x)+b)\geq1$
其對偶問題是：
$\max_{a}\quad \sum_{i=1}^{m}a_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}a_ia_jy_iy_j\phi(x_i)^T\phi(x_j)$
$s.t. \quad\sum_{i=1}^{m}a_iy_i=0,a_i\geq0$
其中 $\phi(x_i)^T\phi(x_j)$ 是樣本 $x_i$ 和 $x_j$ 映射到高維空間后的內(nèi)積。直接計(jì)算高維空間的內(nèi)積是比較困難的傀蓉，為了避開這個障礙欧漱，我們可以設(shè)想這么一個函數(shù)在原始樣本空間即可計(jì)算在高維特征空間的內(nèi)積。

$k(x_i,x_j)=<\phi(x_i),\phi(x_j)>=\phi(x_i)^T\phi(x_j)$
最終的模型可以寫成：

$f(x)=w^T\phi(x)+b=\sum_{i=1}^{m}a_iy_i\phi(x_i)^T\phi(x)+b=\sum_{i=1}^{m}a_iy_ik(x,x_i)+b$
上述我們提到的 $k(·,·)$ 就是核函數(shù)kernel function葬燎。
我們希望樣本在特征空間中是線性可分的误甚，因此合適的特征空間對支持向量機(jī)的性能至關(guān)重要，然后在不知道特征映射的形式時谱净，我們并不知道什么樣的核函數(shù)是最合適的窑邦，而核函數(shù)也僅是隱式地定義了這個特征空間。因此核函數(shù)的選擇是支持向量機(jī)模型的最大影響因素壕探。
常用的核函數(shù)包括了線性核冈钦、多項(xiàng)式核、高斯核浩蓉、拉普拉斯核和Sigmoid核等派继。如下表所示：

image.png

另外宾袜，不同核函數(shù)經(jīng)過組合后也可形成新的核函數(shù)捻艳，比如：

若 $k_1$ 和 $k_2$ 為核函數(shù)，則對于任意正數(shù) $y_1$ 和 $y_2$ 庆猫，其線性組合 $y_1k_1+y_2k_2$ 也是核函數(shù)
若 $k_1$ 和 $k_2$ 為核函數(shù)认轨，則核函數(shù)的直積也是核函數(shù)
若 $k_1$ 為核函數(shù)，則對于任意函數(shù) $g(x)$ , $k(x,z)=g(x)k_1(x,z)g(z)$ 也是核函數(shù)

軟間隔與正則化

前面我們討論的支持向量機(jī)模型都是假設(shè)存在一個超平面能將不同類別的訓(xùn)練樣本完全分割開的月培，然而現(xiàn)實(shí)中很難確定合適的核函數(shù)是的訓(xùn)練樣本在特征空間中完全線性可分嘁字。即使恰好找到了某個核函數(shù)使得訓(xùn)練集在特征空間中線性可分，也很難斷定這個結(jié)果不是由過擬合所造成的杉畜。
解決該問題的方法即允許支持向量機(jī)在一些樣本上出錯纪蜒。為此，要引入“軟間隔”soft margin的概念此叠，如下圖所示：

image.png

軟間隔允許某些樣本不滿足約束：

$y_i(w^Tx_i+b)\geq1$
在最大化間隔的時候纯续，不滿足約束的樣本應(yīng)該盡可能的少，于是優(yōu)化目標(biāo)可以改寫為：

$\min_{w,b}\quad\frac{1}{2}||w||^2+C\sum_{i=1}^{m}l_{0/1}(y_i(w^Tx_i+b)-1)$
其中 $C$ 一個大于0的常數(shù)灭袁， $l_{0/1}$ 是“0/1”損失函數(shù)猬错，但是該損失函數(shù)數(shù)學(xué)性質(zhì)不佳(非凸，非連續(xù))茸歧，下面我們給出常用的三種替代損失函數(shù)：

$l_{hinge}(z)=max(0,1-z) \\ l_{exp}=exp(-z) \\ l_{log}(z)=log(1+exp(-z))$

image.png

Reference

[1] 機(jī)器學(xué)習(xí)

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

人面猴
序言：七十年代末倦炒，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子软瞎，更是在濱河造成了極大的恐慌逢唤，老刑警劉巖拉讯，帶你破解...
沈念sama閱讀 211,376評論 6贊 491
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異智玻，居然都是意外死亡遂唧，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,126評論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門吊奢，熙熙樓的掌柜王于貴愁眉苦臉地迎上來盖彭，“玉大人，你說我怎么就攤上這事页滚≌俦撸” “怎么了？”我有些...
開封第一講書人閱讀 156,966評論 0贊 347
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵裹驰，是天一觀的道長隧熙。經(jīng)常有香客問我，道長幻林，這世上最難降的妖魔是什么贞盯？我笑而不...
開封第一講書人閱讀 56,432評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮沪饺，結(jié)果婚禮上躏敢，老公的妹妹穿的比我還像新娘。我一直安慰自己整葡，他們只是感情好件余，可當(dāng)我...
茶點(diǎn)故事閱讀 65,519評論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著遭居，像睡著了一般啼器。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上俱萍，一...
開封第一講書人閱讀 49,792評論 1贊 290
城市分裂傳說
那天端壳，我揣著相機(jī)與錄音，去河邊找鬼枪蘑。笑死损谦，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的腥寇。我是一名探鬼主播成翩，決...
沈念sama閱讀 38,933評論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼赦役！你這毒婦竟也來了麻敌？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 37,701評論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤掂摔，失蹤者是張志新（化名）和其女友劉穎术羔，沒想到半個月后赢赊，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,143評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡级历，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,488評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年释移，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片寥殖。...
茶點(diǎn)故事閱讀 38,626評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡玩讳，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出嚼贡，到底是詐尸還是另有隱情熏纯，我是刑警寧澤，帶...
沈念sama閱讀 34,292評論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布粤策，位于F島的核電站樟澜，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏叮盘。R本人自食惡果不足惜秩贰，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,896評論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望柔吼。院中可真熱鬧毒费，春花似錦、人聲如沸嚷堡。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,742評論 0贊 21
一樁弒父案艇棕，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽蝌戒。三九已至，卻和暖如春沼琉，著一層夾襖步出監(jiān)牢的瞬間北苟，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,977評論 1贊 265
情欲美人皮
我被黑心中介騙來泰國打工打瘪，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留友鼻，地道東北人。一個月前我還...
沈念sama閱讀 46,324評論 2贊 360
代替公主和親
正文我出身青樓闺骚，卻偏偏與公主長得像彩扔，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子僻爽，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,494評論 2贊 348

[機(jī)器學(xué)習(xí)算法]支持向量機(jī)

原理

支持向量機(jī)模型

參數(shù)求解

SMO算法

核函數(shù)

軟間隔與正則化

Reference

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