支持向量機(jī)（三）——線性支持向量機(jī)

〇枝缔、說(shuō)明

支持向量機(jī)(Support Vector Machine,SVM)是監(jiān)督學(xué)習(xí)中非常經(jīng)典的算法开仰。筆者主要參考學(xué)習(xí)的是李航老師《統(tǒng)計(jì)學(xué)習(xí)方法（第二版）》[1]和周志華老師的西瓜書(shū)《機(jī)器學(xué)習(xí)》[2]役电。

如有錯(cuò)誤疏漏惊科，煩請(qǐng)指正科阎。如要轉(zhuǎn)載闯两，請(qǐng)聯(lián)系筆者俘枫，hpfhepf@gmail.com腥沽。

一、問(wèn)題引出

一方面鸠蚪，線性可分支持向量機(jī)只適用于線性可分的訓(xùn)練數(shù)據(jù)集今阳，對(duì)于線性不可分的訓(xùn)練數(shù)據(jù)集則是無(wú)能為力的师溅。

另一方面，即使訓(xùn)練數(shù)據(jù)集線性可分盾舌，線性可分支持向量機(jī)強(qiáng)依賴于離分類超平面最近的樣本[3]墓臭，過(guò)擬合的風(fēng)險(xiǎn)很大。

這時(shí)候就需要有一定容錯(cuò)能力的分類模型妖谴，線性支持向量機(jī)窿锉，或者叫軟間隔支持向量機(jī)，就可以做到這樣的容錯(cuò)性膝舅。

二嗡载、模型描述

這里我采用周志華老師西瓜書(shū)[2]的思路來(lái)整理這部分。

對(duì)于線性可分支持向量機(jī)仍稀，要求所有樣本滿足以下約束

$y_{i}(w\cdot x_{i}+b)\geq 1, \ i=1,2,\dots,N \tag{1}$

而軟間隔則允許某些樣本不滿足這樣的約束洼滚。

在最大化間隔的同時(shí)，不滿足約束的樣本要盡量少技潘。此時(shí)遥巴，優(yōu)化目標(biāo)可以寫(xiě)為

$\mathop{min}\limits_{w,b} \quad \frac{1}{2} ||w||^2+C\sum_{i=1}^N L(y_{i}(w \cdot x_{i}+b)-1) \tag{2}$

其中， $L(z)$ 是一般化的損失函數(shù)享幽， $C>0$ 被稱作懲罰參數(shù)铲掐，調(diào)節(jié)間隔最大化和參數(shù)懲罰這二者關(guān)系。

我們先看懲罰參數(shù) $C$ 值桩。當(dāng) $C$ 值較大時(shí)對(duì)誤分類懲罰較大摆霉，特別地，當(dāng)C取無(wú)窮大時(shí)颠毙，所有樣本都要滿足式 $(1)$ 約束斯入，模型等價(jià)于線性可分支持向量機(jī)[3]；當(dāng) $C$ 取有限值時(shí)蛀蜜，模型允許一些樣本不滿足約束。

接下來(lái)討論損失函數(shù) $L(z)$ 增蹭。當(dāng) $L(z)$ 使用不同的損失函數(shù)時(shí)的模型狀態(tài)滴某，周志華老師的西瓜書(shū)[2]有簡(jiǎn)單討論。當(dāng) $L(z)$ 是合頁(yè)損失函數(shù)時(shí)滋迈，模型就是線性支持向量機(jī)霎奢。李航老師《統(tǒng)計(jì)學(xué)習(xí)方法（第二版）》[1]的相關(guān)章節(jié)證明了線性支持向量機(jī)和基于合頁(yè)損失函數(shù)的優(yōu)化問(wèn)題的等價(jià)性。合頁(yè)損失函數(shù)如下

圖1[2]

當(dāng) $L(z) = L_{hinge}(z)$ 時(shí)饼灿，式 $(2)$ 可重寫(xiě)為

$\mathop{min}\limits_{w,b} \quad \frac{1}{2} ||w||^2+C\sum_{i=1}^N max(0,1-y_{i}(w\cdot x_{i}+b)) \tag{4}$

引入松弛變量 $\xi_{i} \geq 0$ 幕侠，將上式再重寫(xiě)為

優(yōu)化問(wèn)題一：

$\begin{split}&\mathop{min}\limits_{w,b} \ & \frac{1}{2} ||w||^2+C\sum_{i=1}^N \xi _{i} \\& s.t. & y_{i}(w\cdot x+b)\geq 1-\xi _{i} \\&& \xi_{i} \geq 0, \ i=1,2,\dots,N\end{split}\tag{5}$

三、拉格朗日對(duì)偶問(wèn)題推導(dǎo)

與線性可分支持向量機(jī)類似碍彭，線性支持向量機(jī)（式 $(5)$ ）的拉格朗日對(duì)偶函數(shù)如下

$L(w,b,\xi;\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_{i} + \sum_{i=1}^N\alpha_{i}(1-\xi_{i}-y_{i}(w\cdot x_{i}+b))-\sum_{i=1}^N\mu_{i}\xi_{i} \tag{6}$

原問(wèn)題（式 $(5)$ ）是凸優(yōu)化問(wèn)題晤硕，則優(yōu)化問(wèn)題 $\mathop{max}\limits_{\alpha,\mu} \ \mathop{min}\limits_{w,b,\xi} \ L(w,b,\xi;\alpha,\mu)$ 與原問(wèn)題等價(jià)悼潭。

第一步，求 $L(w,b,\xi;\alpha,\mu)$ 對(duì) $w,b,\xi$ 的極小值舞箍。

$\frac{\partial}{\partial w} L(w,b,\xi;\alpha,\mu)=w-\sum_{i=1}^N \alpha_{i}y_{i}x_{i}=0 \tag{7}$

$\frac{\partial}{\partial b} L(w,b,\xi;\alpha,\mu)=-\sum_{i=1}^N \alpha_{i}y_{i}=0 \tag{8}$

$\frac{\partial}{\partial \xi_{i}} L(w,b,\xi;\alpha,\mu)=C-\alpha_{i}-\mu_{i}=0 \tag{9}$

得

$w=\sum_{i=1}^N \alpha_{i}y_{i}x_{i} \tag{10}$

$\sum_{i=1}^N \alpha_{i}y_{i}=0 \tag{11}$

$C-\alpha_{i}-\mu_{i}=0 \tag{12}$

將式 $(10)-(12)$ 代入式 $(6)$ 舰褪，可得

$\mathop{min}\limits_{w,b,\xi} L(w,b,\xi;\alpha,\mu) = -\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} \tag{13}$

第二步，求 $\mathop{min}\limits_{w,b,\xi} L(w,b,\xi;\alpha,\mu)$ 對(duì) $\alpha,\mu$ 的極大值疏橄，即得對(duì)偶問(wèn)題占拍。

這里需要注意，式 $(13)$ 等號(hào)右邊表達(dá)式?jīng)]有 $\mu$ 捎迫，直接求解對(duì) $\alpha$ 的極大值即可晃酒。對(duì)偶問(wèn)題如下

$\begin{split}&\mathop{max}\limits_{\alpha} \ &-\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} \\& s.t. & \sum_{i=1}^N \alpha_{i} y_{i}=0 \\&& C-\alpha_{i}-\mu_{i}=0 \\&& \alpha_{i} \geq 0 \\&& \mu_{i} \geq 0, \ \ i=1,2,\dots,N\end{split} \tag{14}$

上式中，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cmu" alt="\mu" mathimg="1">不在最優(yōu)化表達(dá)式中窄绒，可以利用等式約束消去掖疮，簡(jiǎn)化約束。再把求極大轉(zhuǎn)換成求極小颗祝，得到對(duì)偶問(wèn)題如下

優(yōu)化問(wèn)題二：

$\begin{split}&\mathop{min}\limits_{\alpha} \ &\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) - \sum_{i=1}^N \alpha_{i} \\& s.t. & \sum_{i=1}^N \alpha_{i} y_{i}=0 \\&& 0\leq \alpha_{i} \leq C \ \ i=1,2,\dots,N\end{split} \tag{15}$

第三步浊闪，求解分類超平面和分類模型。

對(duì)于已求解出優(yōu)化問(wèn)題二（式 $(15)$ ）的最優(yōu)解 $\alpha^*$ 螺戳，則類似于線性可分支持向量機(jī)[3]的推導(dǎo)過(guò)程搁宾。

原問(wèn)題（式 $(5)$ ）是凸優(yōu)化問(wèn)題，則滿足KKT條件的點(diǎn)是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解（具體請(qǐng)參見(jiàn)[4]）

$\begin{align}& y_{i}(w^*\cdot x_{i}+b^*)\geq 1-\xi^* _{i},\ i=1,2,\dots,N \tag{16a}\\& \xi^*_{i} \geq 0, \ i=1,2,\dots,N \tag{16b} \\& \alpha^*_{i} \geq 0, \ i=1,2,\dots,N \tag{16c} \\& \alpha^*_{i}(y_{i}(w^*\cdot x_{i}+b^*)-1+\xi^*_{i})=0 \tag{16d} \\& \mu^*_{i}\xi^*_{i}=0, \ i=1,2,\dots,N \tag{16e}\\& \frac{\partial}{\partial w} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=w^*-\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i}=0 \tag{16f} \\& \frac{\partial}{\partial b} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=-\sum_{i=1}^N \alpha^*_{i}y_{i}=0 \tag{16g} \\& \frac{\partial}{\partial \xi_{i}} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=C-\alpha^*_{i}-\mu^*_{i}=0 , \ i=1,2,\dots,N\tag{16h} \end{align}$

根據(jù)式 $(16f)$ 可得

$w^*=\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i} \tag{17}$

觀察式 $(16d)$ 倔幼、 $(16e)$ 和 $(16h)$ 盖腿，先看式 $(16d)$ ，當(dāng) $0 <\alpha^*_{i}<C$ 時(shí)损同，有

$y_{i}(w^* \cdot x_{i}+b^*)=1-\xi^*_{i} \tag{18}$

再看式 $(16h)$ 翩腐，當(dāng) $0 <\alpha^*_{i}<C$ 時(shí)，有? $\mu^*_{i}=C-\alpha^*_{i}>0 \tag{19}$

此時(shí)再看式 $(16e)$ 膏燃，當(dāng) $\mu^*_{i} >0$ 時(shí)茂卦，必有 $\xi^*_{i}=0$ ，綜上討論组哩，當(dāng) $0 <\alpha^*_{i}<C$ 時(shí)等龙，有

$y_{i}(w^* \cdot x_{i}+b^*)=1 \tag{20}$

再將式 $(17)$ 代入上式，并于式 $(17)$ 聯(lián)立伶贰，可得線性支持向量機(jī)的最優(yōu)分類超平面參數(shù)為

$\begin{align}& w^*=\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i} \\& b* =y^*_{j}-\sum_{i=1}^N \alpha^*_{i}y_{i}(x_{i} \cdot x_{j}) , \ 0 </p><p>這里需要注意蛛砰，在李航老師《統(tǒng)計(jì)學(xué)習(xí)方法（第二版）》[1]相關(guān)章節(jié)中，和式<img class=$

這里需要注意黍衙，在李航老師《統(tǒng)計(jì)學(xué)習(xí)方法（第二版）》[1]相關(guān)章節(jié)中泥畅，和式 $(16h)$ 相同表達(dá)的式子是不嚴(yán)謹(jǐn)?shù)模绻麤](méi)看到這一段琅翻，這句話略過(guò)位仁。

四柑贞、支持向量

線性支持向量機(jī)的支持向量會(huì)復(fù)雜一些。如下圖

圖1[1]

首先障癌，定義 $\alpha^*_{i}>0$ 的樣本點(diǎn) $(x_{i},y_{i})$ 為支持向量凌外。

其次，每個(gè)支持向量 $(x_{i},y_{i})$ 到其對(duì)應(yīng)的間隔邊界的距離為 $\frac{\xi^*_{i}}{||w^*||}$ 涛浙。推導(dǎo)過(guò)程如下康辑。

點(diǎn)到超平面的距離公式為： $r=\frac{|w\cdot x+b|}{||w||}$

先看正類，正類的間隔邊界超平面為： $w^*\cdot x+b^*=1$ 轿亮，對(duì)應(yīng)的點(diǎn)到間隔邊界超平面的距離公式為： $r=\frac{|w^*\cdot x_{i}+(b^*-1)|}{||w^*||}$ 疮薇。對(duì)于正例的支持向量，有 $y_{i}=+1$ 我注，根據(jù)式 $(18)$ 按咒，有 $w^*\cdot x_{i} +b^*-1=\xi^*_{i}$ ，代入距離公式但骨，即可到結(jié)論励七。

負(fù)類推導(dǎo)過(guò)程類似。

再次奔缠，根據(jù)以上結(jié)論掠抬，分析支持向量。

根據(jù)上面式 $(16e)$ 和 $(16h)$ 校哎，消去 $\mu^*_{i}$ 两波，則有

$(C-\alpha^*_{i})\xi^*_{i}=0, \ i=1,2,\dots,N \tag{22}$

第一種情況，當(dāng) $0<\alpha^*_{i}<C$ 時(shí)闷哆，則 $\xi^*_{i}=0$ 腰奋，則此支持向量到對(duì)應(yīng)間隔邊界的距離 $r=\frac{\xi^*_{i}}{||w^*||}=0$ ，即此支持向量在間隔邊界超平面上抱怔。

第二種情況劣坊，當(dāng) $\alpha^*_{i}=C$ 且 $0<\xi^*_{i} <1$ 時(shí)，此支持向量到對(duì)應(yīng)間隔邊界的距離 $r=\frac{\xi^*_{i}}{||w^*||}<\frac{1}{||w^*||}$ 野蝇，此支持向量分類正確讼稚，在間隔邊界與分離超平面之間冤今。

第三種情況扒寄，當(dāng) $\alpha^*_{i}=C$ 且 $\xi^*_{i}=1$ 時(shí)掖鱼，此支持向量到對(duì)應(yīng)間隔邊界的距離 $r=\frac{\xi^*_{i}}{||w^*||}=\frac{1}{||w^*||}$ ，此支持向量在分離超平面上乍狐。

第四種情況，當(dāng) $\alpha^*_{i}=C$ 且 $\xi^*_{i}>1$ 時(shí)固逗，此支持向量到對(duì)應(yīng)間隔邊界的距離 $r=\frac{\xi^*_{i}}{||w^*||}>\frac{1}{||w^*||}$ 浅蚪，此支持向量分類錯(cuò)誤藕帜。

這里需要注意，有沒(méi)有 $\alpha^*_{i}=C$ 和 $\xi^*_{i}=0$ 同時(shí)成立的點(diǎn)惜傲，這里沒(méi)有找到確定或否定的證據(jù)洽故。如果誰(shuí)有這方面的資料，還煩請(qǐng)告知筆者盗誊，先行謝過(guò)时甚，聯(lián)系郵箱：hpfhepf@gmail.com。

五哈踱、附錄

A荒适、參考

[1]、《統(tǒng)計(jì)學(xué)習(xí)方法（第二版）》开镣，李航著刀诬，清華大學(xué)出版社

[2]、《機(jī)器學(xué)習(xí)》邪财，周志華著陕壹，清華大學(xué)出版社

[3]、《支持向量機(jī)（一）——線性可分支持向量機(jī)導(dǎo)出》

[4]树埠、《凸優(yōu)化（八）——Lagrange對(duì)偶問(wèn)題》

B糠馆、相關(guān)目錄

[a]、支持向量機(jī)（一）——線性可分支持向量機(jī)導(dǎo)出

[b]弥奸、支持向量機(jī)（二）——線性可分支持向量機(jī)求解

[c]榨惠、支持向量機(jī)（三）——線性支持向量機(jī)

[d]、支持向量機(jī)（四）——核方法

[e]盛霎、支持向量機(jī)（五）——SMO算法

最后編輯于：2020.06.18 19:52:04

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

人面猴
序言：七十年代末赠橙，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子愤炸，更是在濱河造成了極大的恐慌期揪，老刑警劉巖，帶你破解...
沈念sama閱讀 218,682評(píng)論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件规个，死亡現(xiàn)場(chǎng)離奇詭異凤薛，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)诞仓，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,277評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)缤苫，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人墅拭，你說(shuō)我怎么就攤上這事活玲。” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 165,083評(píng)論 0贊 355
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵舒憾，是天一觀的道長(zhǎng)镀钓。經(jīng)常有香客問(wèn)我，道長(zhǎng)镀迂，這世上最難降的妖魔是什么丁溅？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,763評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮探遵，結(jié)果婚禮上窟赏，老公的妹妹穿的比我還像新娘。我一直安慰自己别凤，他們只是感情好饰序，可當(dāng)我...
茶點(diǎn)故事閱讀 67,785評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著规哪，像睡著了一般求豫。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上诉稍，一...
開(kāi)封第一講書(shū)人閱讀 51,624評(píng)論 1贊 305
城市分裂傳說(shuō)
那天蝠嘉，我揣著相機(jī)與錄音，去河邊找鬼杯巨。笑死蚤告，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的服爷。我是一名探鬼主播杜恰，決...
沈念sama閱讀 40,358評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼仍源！你這毒婦竟也來(lái)了心褐？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 39,261評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤笼踩，失蹤者是張志新（化名）和其女友劉穎逗爹，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體嚎于，經(jīng)...
沈念sama閱讀 45,722評(píng)論 1贊 315
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡掘而，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,900評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了于购。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片袍睡。...
茶點(diǎn)故事閱讀 40,030評(píng)論 1贊 350
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖肋僧，靈堂內(nèi)的尸體忽然破棺而出女蜈，到底是詐尸還是另有隱情持舆，我是刑警寧澤色瘩，帶...
沈念sama閱讀 35,737評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布伪窖，位于F島的核電站，受9級(jí)特大地震影響居兆，放射性物質(zhì)發(fā)生泄漏覆山。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,360評(píng)論 3贊 330
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一泥栖、第九天我趴在偏房一處隱蔽的房頂上張望簇宽。院中可真熱鬧，春花似錦吧享、人聲如沸魏割。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,941評(píng)論 0贊 22
一樁弒父案钢颂，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)钞它。三九已至，卻和暖如春殊鞭，著一層夾襖步出監(jiān)牢的瞬間遭垛，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,057評(píng)論 1贊 270
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工操灿，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留锯仪，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,237評(píng)論 3贊 371
代替公主和親
正文我出身青樓趾盐，卻偏偏與公主長(zhǎng)得像庶喜，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子救鲤，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,976評(píng)論 2贊 355