支持向量機

圖來源：《機器學(xué)習(xí)》周志華著

超平面用方程表示為

w^Tx+b=0

肛响，

\gamma=\frac{2}{||w||}

為間隔(margin)姨谷。我們需要找到具有最大間隔的劃分超平面，故得到：

\underset{w,b}{argmin}\frac12||w||^2

s.t. y_i(w^Tx+b)>=1,i=1,2,...,m

1.問題求解：

(1)拉格朗日乘子法

定義拉格朗日函數(shù)
$L(w,b,\mu)=\frac{1}{2}||w||^2+\sum_{i=1}^{m}\mu_i(1-y_i(w^Tx+b))$ 棚品，
KKT條件為：
$\begin{cases} \mu _{ i }>=0 \\ 1-y_{ i }(w^{ T }x+b)<=0 \\ \mu_i(1-y_i(w^Tx+b))=0\end{cases}$
求極值蚜迅，則令
$\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}\mu_iy_ix_i=0$
$\frac{\partial{L}}{\partial捎泻}=\sum_{i=1}^{m}\mu_iy_i=0$
得到：
$w=\sum_{i=1}^{m}\mu_iy_ix_i$
$\sum_{i=1}^{m}\mu_iy_i=0$
代入 $L(w,b,\mu)$ 消去 $w$ 和 $b$ ,得到原問題的對偶問題為
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
由KKT條件得到：對于任意訓(xùn)練樣本 $(x_i,y_i)$ 總有 $\mu_i=0$ 或 $y_i(w^Tx_i+b)=1$ ,這就意味著當(dāng) $\mu_i=0$ 時侦鹏，該樣本并不會對 $f(x)=w^Tx+b$ 產(chǎn)生而任何影響，當(dāng) $y_i(w^Tx_i+b)=1$ 時臀叙，此時意味著訓(xùn)練樣本在最大間隔的邊界上略水，該樣本點稱之為支持向量。

(2)對偶問題求解：

2.核函數(shù)

假設(shè)樣本線性可分劝萤，即存在一個超平面對樣本進(jìn)行分類渊涝。而實際任務(wù)中，樣本往往是非線性可分床嫌。此時跨释，我們將 $x_i$ 映射到高維特征空間，在特征空間中找到超平面使得樣本線性可分厌处，記 $\phi(x_i)$ 為 $x_i$ 映射到高維特征空間所對應(yīng)的特征向量鳖谈。
因此，對應(yīng)的模型可以表示為
$f(x)=w^T\phi(x)+b$
實際只需要求解如下函數(shù)：
$\underset{w,b}{argmin}\frac12||w||^2$
$s.t. y_i(w^T\phi(x_i)+b)>=1,i=1,2,...,m$
對偶問題為：
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_j\phi(x_i)^T\phi(x_j)$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
當(dāng)特征空間維度很高時阔涉，計算 $\phi(x_i)^T\phi(x_j)$ 困難缆娃，故定義核函數(shù) $k(.,.)$ 使得 $\phi(x_i)^T\phi(x_j)=k(x_i,x_j)$ ,
則對偶問題重寫為：
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_jk(x_i,x_j)$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
求解該對偶問題得到
$f(x)=\sum_{i=1}^{m}\mu_iy_i\phi(x_i)^Tx+b$
$=\sum_{i=1}^{m}\mu_iy_ik(x_i,x)+b$

3.軟間隔

圖中紅色樣本是被分錯的

前面介紹的支持向量機形式是要求所有樣本均滿足約束 $y_i(w^Tx+b)>=1,i=1,2,...,m$ ，即所有樣本都必須劃分正確瑰排，這稱為"硬間隔" (hard margin)贯要，而軟間隔則是允許某些樣本不滿足約束。當(dāng)然我們是希望這樣不滿足約束的樣本越少越好椭住。因此目標(biāo)函數(shù)定義為
$\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{0/1}( y_i(w^Tx+b)-1)$ ,其中
$l_{0/1}(z)=\begin{cases} 1\quad ,if\quad z<0 \\ 0\quad ,otherwise \end{cases}$

由于 $l_{0/1}$ 非凸崇渗、非連續(xù)，常用其他損失函數(shù)替代，如下圖所示:

三種常見的替代損失函數(shù):hinge損失宅广，指數(shù)損失葫掉，對率損失

采用hinge損失得到：

\underset{w,b}{argmin}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}max(0, 1-y_i(w^Tx+b))

引入松弛變量得到:

軟間隔支持向量機

$\underset{w,b}{argmin}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i$
$s.t. y_i(w^Tx+b)>=1-\xi_i,i=1,2,...,m$
$\xi_i>=0,i=1,2,...,m$
采用拉格朗日乘子法
$L(w,b,\alpha,\xi,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i+\sum_{i=1}^{m}\alpha_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_{i=1}^{m}\mu_i\xi_i$ ，求極值乘碑，令
$\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}\alpha_iy_ix_i=0 \Rightarrow w=\sum_{i=1}^{m}\alpha_iy_ix_i$
$\frac{\partial{L}}{\partial挖息}=\sum_{i=1}^{m}\alpha_iy_i=0$
$\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0 \Rightarrow C=\alpha_i+\mu_i$
帶入L得到原問題的對偶問題為:
$\underset{\alpha}{argmax}\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}\alpha_iy_i=0$
$0<=\alpha_i<=C,i=1,2,...,m$
KKT條件要求:
$\begin{cases} \alpha _{ i }>=0, \mu_i>=0\\ 1-\xi_i-y_{ i }(w^{ T }x+b)<=0 \\\xi_i>=0\\ \alpha_{ i }(1-\xi_i-y_{ i }(w^{ T }x+b))=0 \\\mu_i\xi_i=0\end{cases}$
由此可得：

對于任意 $(x_i,y_i)$ ,當(dāng) $\alpha_i=0$ 時，該樣本不會對 $f(x)$ 產(chǎn)生任何影響兽肤；當(dāng) $\alpha_i>0$ 時套腹，必有 $y_{ i }(w^{ T }x+b)=1-\xi_i$ ,此時該樣本是支持向量。當(dāng) $\alpha_i<C$ 時资铡， $\mu_i>0$ ,則 $\xi_i=0$ ,此時樣本處于最大間隔邊界上电禀，當(dāng) $\alpha_i=C$ 時， $\mu_i=0$ 笤休，則 $\xi_i>0$ 尖飞；若 $\xi_i>1$ ,樣本被錯誤分類;若 $\xi_i<1$ ,樣本落在最大間隔內(nèi)部。
軟間隔支持向量機模型僅與支持向量有關(guān)店雅。

4.支持向量回歸

（1）考慮 $f(x)$ 與 $y$ 最多允許有 $\varepsilon$ 的誤差
（2）構(gòu)建寬度為 $2\varepsilon$ 的間隔帶政基，如圖：

落入間隔帶的樣本被認(rèn)為是預(yù)測正確的

目標(biāo)函數(shù)：

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{\varepsilon}( f(x_i)-y_i)

l_{\varepsilon}(z)=\begin{cases} 0\quad ,if\quad |z|<=\varepsilon \\|z|-\varepsilon\quad ,otherwise \end{cases}

可允許間隔帶兩側(cè)的松弛程度有所不同，故引入松弛變量

\xi

和

\overset{\wedge}{\xi}

,得到SVR問題：

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

s.t. f(x_i)-y_i<=\varepsilon+\xi_i

y_i- f(x_i)<=\varepsilon+\overset{\wedge}{\xi}_i

\xi_i>=0,\overset{\wedge}{\xi}_i>=0,i=1,2,...,m

拉格朗日乘子法

L(w,b,\xi,\overset{\wedge}{\xi},\alpha,\overset{\wedge}{\alpha},\mu,\overset{\wedge}{\mu})=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

+\sum_{i=1}^{m}\alpha_i( f(x_i)-y_i-\varepsilon-\xi_i)+\sum_{i=1}^{m}\overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)

-\sum_{i=1}^{m}\mu_i\xi_i-\sum_{i=1}^{m}\overset{\wedge}{\mu}_i\overset{\wedge}{\xi}_i

闹啦，求極值沮明，令

\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i=0 \Rightarrow w=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i

\frac{\partial{L}}{\partial}=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0 \Rightarrow C=\alpha_i+\mu_i

\frac{\partial{L}}{\partial{\overset{\wedge}{\xi}_i}}=C-\overset{\wedge}{\alpha}_i-\overset{\wedge}{\mu}_i=0 \Rightarrow C=\overset{\wedge}{\alpha}_i+\overset{\wedge}{\mu}_i

代入L,得到SVR的對偶問題：

\underset{\alpha,\overset{\wedge}{\alpha}}{argmax}\sum_{i=1}^{m}y_i(\overset{\wedge}{\alpha}_i-\alpha_i)-\varepsilon(\overset{\wedge}{\alpha}_i+\alpha_i)

-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)(\overset{\wedge}{\alpha}_j-\alpha_j)x_i^Tx_j

s.t. \sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

0<=\alpha_i,\overset{\wedge}{\alpha}_i<=C,i=1,2,...,m

KKT條件為：

\begin{cases} \alpha_i(f(x_i)-y_i-\varepsilon-\xi_i)=0 \\ \overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)=0 \\ \alpha_i \overset{\wedge}{\alpha}_i=0,\xi\overset{\wedge}{\xi}_i=0\\(C-\alpha_i)\xi=0,(C-\overset{\wedge}{\alpha}_i)\overset{\wedge}{\xi}_i=0 \end{cases}

當(dāng)且僅當(dāng) $f(x_i)-y_i-\varepsilon-\xi_i=0$ , $\alpha_i$ 為非零窍奋；當(dāng)且僅當(dāng) $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ , $\overset{\wedge}{\alpha}_i$ 為非零.換言之荐健，樣本 $(x_i,y_i)$ 沒有落在 $\varepsilon$ -間隔帶時， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 為非零琳袄。此外江场， $f(x_i)-y_i-\varepsilon-\xi_i=0$ 和 $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ 不能同時成立。因此窖逗， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 至少有一個為零址否。
由 $f(x)=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i^Tx+b$ 可知，只有 $(\overset{\wedge}{\alpha}_i-\alpha_i)$ 非零時碎紊， $(x_i,y_i)$ 為SVR的支持向量在张，且落在 $\varepsilon$ -間隔帶之外。落在 $\varepsilon$ -間隔帶中的樣本矮慕，滿足 $\alpha_i=\overset{\wedge}{\alpha}_i=0$

5.支持向量機與KNN

最后編輯于：2019.03.13 15:20:20

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

人面猴
序言：七十年代末帮匾，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子痴鳄，更是在濱河造成了極大的恐慌瘟斜，老刑警劉巖，帶你破解...
沈念sama閱讀 221,198評論 6贊 514
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異螺句，居然都是意外死亡虽惭，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,334評論 3贊 398
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門蛇尚，熙熙樓的掌柜王于貴愁眉苦臉地迎上來芽唇，“玉大人，你說我怎么就攤上這事取劫〈殷裕” “怎么了？”我有些...
開封第一講書人閱讀 167,643評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵谱邪，是天一觀的道長炮捧。經(jīng)常有香客問我，道長惦银，這世上最難降的妖魔是什么咆课？我笑而不...
開封第一講書人閱讀 59,495評論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮扯俱，結(jié)果婚禮上书蚪，老公的妹妹穿的比我還像新娘。我一直安慰自己迅栅，他們只是感情好殊校，可當(dāng)我...
茶點故事閱讀 68,502評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著库继，像睡著了一般。火紅的嫁衣襯著肌膚如雪窜醉。梳的紋絲不亂的頭發(fā)上宪萄，一...
開封第一講書人閱讀 52,156評論 1贊 308
城市分裂傳說
那天，我揣著相機與錄音榨惰，去河邊找鬼拜英。笑死，一個胖子當(dāng)著我的面吹牛琅催，可吹牛的內(nèi)容都是我干的居凶。我是一名探鬼主播，決...
沈念sama閱讀 40,743評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼藤抡，長吁一口氣：“原來是場噩夢啊……” “哼侠碧！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起缠黍，我...
開封第一講書人閱讀 39,659評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤弄兜，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體替饿，經(jīng)...
沈念sama閱讀 46,200評論 1贊 319
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡语泽，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 38,282評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了视卢。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片踱卵。...
茶點故事閱讀 40,424評論 1贊 352
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖据过，靈堂內(nèi)的尸體忽然破棺而出惋砂，到底是詐尸還是另有隱情，我是刑警寧澤蝶俱，帶...
沈念sama閱讀 36,107評論 5贊 349
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布班利，位于F島的核電站，受9級特大地震影響榨呆，放射性物質(zhì)發(fā)生泄漏罗标。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,789評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一积蜻、第九天我趴在偏房一處隱蔽的房頂上張望闯割。院中可真熱鬧，春花似錦竿拆、人聲如沸宙拉。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,264評論 0贊 23
一樁弒父案丙笋，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽谢澈。三九已至，卻和暖如春御板，著一層夾襖步出監(jiān)牢的瞬間锥忿，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,390評論 1贊 271
情欲美人皮
我被黑心中介騙來泰國打工怠肋，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留敬鬓，地道東北人。一個月前我還...
沈念sama閱讀 48,798評論 3贊 376
代替公主和親
正文我出身青樓笙各，卻偏偏與公主長得像钉答，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子杈抢，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 45,435評論 2贊 359