從線性可分 SVM 到線性 SVM

從現(xiàn)實(shí)情況引出線性 SVM

線性可分 SVM诚欠，這種 SVM 學(xué)習(xí)的訓(xùn)練數(shù)據(jù)本身就是線性可分的——可以很清晰地在特征向量空間里分成正集和負(fù)集。

線性可分 SVM 正負(fù)樣本之間的間隔叫做“硬間隔”漾岳，也就是說(shuō)在這個(gè)“隔離帶”里面，肯定不會(huì)出現(xiàn)任何訓(xùn)練樣本粉寞。

我們不難想到尼荆，這種情況在現(xiàn)實(shí)生活中其實(shí)是很少見的。更多的時(shí)候唧垦，可能是像下面這個(gè)樣子：

image

如果沒(méi)有紅圈里那兩個(gè)點(diǎn)捅儒，本來(lái)可以很好的分割：

enter image description here

可是，偏偏多了那兩個(gè)點(diǎn)振亮！都找不到分隔超平面了巧还！像下圖這樣，分來(lái)分去坊秸，怎么都分不開：

enter image description here

如果我們不那么“軸”麸祷，不是完全禁止兩個(gè)輔助超平面之間有任何樣本點(diǎn)。而是允許個(gè)別樣本出現(xiàn)在“隔離帶”里面褒搔，那樣是不是會(huì)變得好分得多阶牍？比如像下面這樣：

enter image description here

這樣看起來(lái)也很合理啊。而且星瘾，一般情況下走孽，怎么能保證樣本就一定能夠被分隔得清清楚楚呢？從直覺(jué)上我們也覺(jué)得琳状，允許一部分樣本存在于“隔離帶”內(nèi)更合理磕瓷。

正是基于這種想法贺纲，相對(duì)于之前講的線性可分 SVM 的硬間隔（Hard Margin）融虽，人們提出了軟間隔（Soft Margin） 的概念损肛。

相應(yīng)的屡久，對(duì)應(yīng)于軟間隔的 SVM胧洒，也就叫做線性 SVM脱柱。

下面我們對(duì)照來(lái)看一看它們：

線性可分 SVM

線性可分 SVM 成立的前提是訓(xùn)練樣本在向量空間中線性可分脊阴，即存在一個(gè)超平面能夠?qū)⒉煌惖臉颖就耆珡氐浊覠o(wú)一錯(cuò)漏地分開疟游。

用數(shù)學(xué)式子表達(dá)审洞，全部訓(xùn)練樣本滿足如下約束條件：

wxi+b?1,yi=1 wxi+b?1,yi=?1

這時(shí)莱睁，wxi+b=1 和 wxi+b=?1 這兩個(gè)超平面之間的間隔叫做硬間隔待讳。位于它們兩個(gè)正中的 wxi+b=0 是最大分割超平面。

線性 SVM

硬間隔到軟間隔

由于樣本線性可分的情況在現(xiàn)實(shí)當(dāng)中出現(xiàn)很少仰剿，為了更有效地應(yīng)對(duì)實(shí)際問(wèn)題创淡，我們不再要求所有不同類的樣本全部線性可分，也就是不再要求硬間隔存在南吮。

取而代之的是將不同類樣本之間的硬間隔變成軟間隔琳彩，即允許部分樣本不滿足約束條件： yi(wxi+b)?1。

當(dāng)然部凑，我們還是希望不滿足硬間隔條件的樣本盡量少露乏，還能夠是一個(gè)“軟”間隔，而非間隔根本不存在涂邀。

為了度量這個(gè)間隔“軟”到何種程度瘟仿，我們針對(duì)每一個(gè)樣本 (xi,yi)，引入一個(gè)松弛變量 ξi比勉，令 ξi?0劳较，且 yi(wxi+b)?1?ξi。

對(duì)應(yīng)到圖形上是這樣：

enter image description here

這樣看起來(lái)浩聋，確實(shí)比硬間隔合理多了观蜗。

****優(yōu)化目標(biāo)****

于是，我們的優(yōu)化目標(biāo)就從原來(lái)的：

minw,b||w||22

s.t.1?yi(wxi+b)?0,i=1,2,...,m

變成了：

minw,b,ξ12||w||2+C∑mi=1ξi

s.t.yi(wxi+b)?1?ξi,i=1,2,...,m;ξi?0,i=1,2,...,m

其中 C 是一個(gè)大于0的常數(shù)衣洁，若 C 為無(wú)窮大墓捻，則 ξi 必然為無(wú)窮小，否則將無(wú)法最小化主問(wèn)題闸与。如此一來(lái)毙替，線性 SVM 就又變成了線性可分 SVM。

當(dāng) C 為有限值的時(shí)候践樱，才能允許部分樣本不遵守約束條件 1–yi(wxi+b)?0厂画。

這就是線性 SVM 的主問(wèn)題！

對(duì)偶法最優(yōu)化線性 SVM 主問(wèn)題

算法思路

上面我們得出了線性 SVM 的主問(wèn)題拷邢。

現(xiàn)在來(lái)回顧一下上節(jié)課我們講解的袱院，用對(duì)偶法求解線性可分 SVM 的主問(wèn)題的思路——當(dāng)時(shí)一共分了7步，不過(guò)這7步再抽象一下瞭稼，大致可以分為4個(gè)階段忽洛。

****Stage-1：根據(jù)主問(wèn)題構(gòu)建拉格朗日函數(shù)，由拉格朗日函數(shù)的對(duì)偶性环肘，將主問(wèn)題轉(zhuǎn)化為極大極小化拉格朗日函數(shù)的對(duì)偶問(wèn)題欲虚。

****Stage-2：分步求解極大極小問(wèn)題。

在每次求解極值的過(guò)程中都是先對(duì)對(duì)應(yīng)的函數(shù)求梯度悔雹，再令梯度為0复哆。以此來(lái)推導(dǎo)出主問(wèn)題參數(shù)和拉格朗日乘子之間的關(guān)系欣喧。

再將用拉格朗日乘子表達(dá)的主問(wèn)題參數(shù)帶回到拉格朗日函數(shù)中，最終一步步將整個(gè)對(duì)偶問(wèn)題推導(dǎo)為拉格朗日乘子和樣本 (xi,yi) 之間的關(guān)系梯找。

****Stage-3：通過(guò)最小化拉格朗日乘子與樣本量組成的函數(shù)（也就是 Stage-2 的結(jié)果）唆阿，求出拉格朗日乘子的值。

這里锈锤，可以用 SMO 算法進(jìn)行求解驯鳖。

****Stage-4：將 Stage-3 求出的拉格朗日乘子的值帶回到 Stage-2 中確定的乘子與主問(wèn)題參數(shù)關(guān)系的等式中浅辙，求解主問(wèn)題參數(shù)摔握。

再根據(jù)主問(wèn)題參數(shù)構(gòu)造最終的分隔超平面和決策函數(shù)丁寄。

主問(wèn)題求解

現(xiàn)在我們就按這個(gè)思路來(lái)對(duì)線性 SVM 主問(wèn)題進(jìn)行求解。

首先屑埋，將主問(wèn)題寫成我們熟悉的約束條件小于等于0的形式，如下：

minw,b,ξ12||w||2+C∑mi=1ξi

s.t.1?ξi?yi(wxi+b)?0,i=1,2,...,m;?ξi?0,i=1,2,...,m

然后開始逐步求解：

****1. 構(gòu)建拉格朗日函數(shù)如下：****

L(w,b,ξ,α,μ)=12||w||2+C∑mi=1ξi+∑mi=1αi[1?ξi?yi(wxi+b)]+∑mi=1(?μiξi)

αi?0,μi?0

其中 αi 和 μi 是拉格朗日乘子团搞，而 w、b 和 ξi 是主問(wèn)題參數(shù)复隆。

根據(jù)主問(wèn)題的對(duì)偶性，主問(wèn)題的對(duì)偶問(wèn)題是：

maxα,μminw,b,ξL(w,b,ξ,α,μ)

****2. 極大極小化拉格朗日函數(shù)****

(1)極小化

首先 對(duì) w亏栈、b 和 ξ 極小化 L(w,b,ξ,α,μ)——分別對(duì) w览爵、b和ξi 求偏導(dǎo)，然后令導(dǎo)數(shù)為0俱济，得出如下關(guān)系：

w=∑mi=1αiyixi

0=∑mi=1αiyi

C=αi+μi

將這些關(guān)系帶入線性 SVM 主問(wèn)題的拉格朗日函數(shù)，得到：

minw,b,ξL(w,b,ξ,α,μ)=∑mi=1αi?12∑mi=1∑mj=1αiαjyiyj(xi?xj)

(2)極大化

然后蔚携，就要對(duì) α 和 μ 進(jìn)行極大化。

因?yàn)樯厦鏄O小化的結(jié)果中只有 α 而沒(méi)有 μ，所以現(xiàn)在只需要極大化 α 就好：

maxα,μminw,b,ξL(w,b,ξ,α,μ)=maxα(∑mi=1αi?12∑mi=1∑mj=1αiαjyiyj(xi?xj))

s.t.∑mi=1αiyi=0;C?αi?μi=0;αi?0;μi?0;i=1,2,...,m

****3. SMO 算法求解對(duì)偶問(wèn)題****

我們將上面極大化目標(biāo)約束條件中的 μ 用 α 替換掉霉咨，并將極大化目標(biāo)求負(fù)轉(zhuǎn)為極小化問(wèn)題丽涩，得到：

maxα(∑mi=1αi?12∑mi=1∑mj=1αiαjyiyj(xi?xj))=min(12∑mi=1∑mj=1αiαjyiyj(xi?xj)?∑mi=1αi)

s.t.∑mi=1αiyi=0;0?αi?C;i=1,2,...,m

我們對(duì)照一下上一篇線性可分 SVM 最優(yōu)化過(guò)程中步驟3的結(jié)果继准，不難發(fā)現(xiàn)，兩者的極小化目標(biāo)是一樣的秒赤，所不同的就是約束條件而已。

所以，在上一篇我們用到的 SMO 算法酥诽，同樣可以用于此處边器。運(yùn)用 SMO 求解出拉格朗日乘子 α1,α2,…,αm。

****4. 根據(jù)拉格朗日乘子與主問(wèn)題參數(shù)的關(guān)系求解分隔超平面和決策函數(shù)****

由 w=∑mi=1αiyixi 求出 w眯勾。

因?yàn)樽罱K要求得的超平面滿足 wx+b=0枣宫，這一點(diǎn)是和線性可分 SVM 的超平面一樣的，因此求解 b 的過(guò)程也可以照搬：

b=1|S|∑s∈S(ys?wxs)

其中 S 是支持向量的集合。

線性 SVM 的支持向量

這里有個(gè)問(wèn)題郁轻，到底哪些樣本算是線性 SVM 的支持向量竭沫？

對(duì)于線性可分 SVM谎势，支持向量本身是很明確的须喂，就是那些落在最大分隔超平面兩側(cè)的兩個(gè)輔助超平面上的樣本。因?yàn)闃颖揪€性可分镊折，所以這兩個(gè)輔助超平面中間的硬間隔里胯府，是沒(méi)有任何樣本存在的。

但是赃泡，對(duì)于線性 SVM寒波，有些不同，這兩個(gè)輔助超平面中間是軟間隔升熊，軟間隔的區(qū)域內(nèi)也存在若干樣本俄烁。這些樣本是和輔助超平面上的樣本一樣算作支持向量呢？還是不算作支持向量级野？

比如下圖中的 sampleA 和 sampleB页屠，前者還好，只是“分得不夠清楚”蓖柔， 后者根本就“跨界”到了“對(duì)方的地盤”辰企。它們兩個(gè)到底算不算支持向量呢？

enter image description here

我們先來(lái)看看線性 SVM（又名軟間隔 SVM）主問(wèn)題拉格朗日函數(shù)的 KKT 條件：

αi?0,μi?0

yif(xi)–1+ξi?0

αi(yif(xi)–1+ξi)=0

ξi?0

μiξi=0

其中 f(x)=wx+b,i=1,2,…,m

對(duì)于任意樣本 (xi,yi)况鸣，要么 αi=0牢贸， 要么 yif(xi)–1+ξi=0。

我們又知道 w 的計(jì)算公式為：

w=∑mi=1αiyixi

其中拉格朗日乘子為0（即 αi=0）的項(xiàng)镐捧，對(duì)于 w 的值是沒(méi)有影響的潜索，能夠影響 w 的，一定是對(duì)應(yīng)拉格朗日乘子大于0的樣本懂酱。

根據(jù) KKT 條件竹习，這樣的樣本一定同時(shí)滿足 yif(xi)–1+ξi=0，也就是 yif(xi)=1–ξi列牺。所有這樣的樣本由驹，都是線性 SVM 的支持向量。

在滿足 yif(xi)=1–ξi 的前提之下，我們來(lái)看 ξi蔓榄。

若 ξi=0, 則 yif(xi)=1并炮，此時(shí)，樣本正好落在兩個(gè)輔助超平面上甥郑。所以逃魄，兩個(gè)輔助超平面上的樣本，肯定是支持向量澜搅。

若 ξi≠0：

當(dāng) ξi?1 時(shí)（例如上圖中的 ξA）伍俘，1?ξi>0， yif(xi)>0勉躺。也就是說(shuō) yi 和 f(xi) 的結(jié)果相乘雖然不為1癌瘾，但至少這個(gè)樣本還沒(méi)有被歸錯(cuò)類。

當(dāng) ξi>1時(shí)（例如上圖中的 ξB）饵溅，1?ξi<0妨退，則 yif(xi)<0，這時(shí)蜕企，樣本根本就被歸錯(cuò)了類咬荷。但是，即使如此轻掩，畢竟這樣的樣本也影響了最終 w 的取值幸乒，所以，它也是支持向量唇牧。