【概述】 SVM訓(xùn)練分類器的方法是尋找到超平面，使正負(fù)樣本在超平面的兩側(cè)（分類正確性即“分得開”），且樣本到超平面的幾何間隔最大（分類確信度即“分得好”）。? 每個(gè)樣本點(diǎn)xi的幾何間隔至少是γ，要求γ首先是>0（分類正確），然后盡力求γ的最大值（分得好，要γ>1）。

? ? ?另外γ值是由少數(shù)在margin上的點(diǎn)決定的（引出支持向量的概念，名字還挺形象的！這些向量“撐”起了分界線）。

注：SVM算法的特點(diǎn)是巧妙地利用了很多零散的數(shù)學(xué)知識(shí)和技巧，所以要消化學(xué)習(xí)如何針對(duì)分類繼續(xù)優(yōu)化、追求分離平面唯一性的需求，如何構(gòu)造約束最優(yōu)化問題（通過構(gòu)造目標(biāo)函數(shù)，充分利用已有的數(shù)學(xué)計(jì)算技巧）

7.1.2 函數(shù)間隔和幾何間隔

“間隔”的作用和意義：一個(gè)點(diǎn)距離分離超平面的遠(yuǎn)近，可以用來表示分類預(yù)測(cè)的確信程度，有以下原則：在超平面w.x+b=0確定的情況下：|w.x+b|能夠相對(duì)表示點(diǎn)x距離超平面的遠(yuǎn)近，而w.x+b的符號(hào)與類標(biāo)記的符號(hào)是否一致（例如：點(diǎn)在正側(cè)，w.xi+b大于0，而yi為1，yi大于0，分類正確；點(diǎn)在負(fù)側(cè)，w.xi+b小于0，yi為-1，符號(hào)一致，分類正確；反之符號(hào)不一致）。

1、函數(shù)間隔（又稱函數(shù)距離）

進(jìn)而引出函數(shù)間隔functional margin的概念，用函數(shù)距離y(w.x+b)來表示分類的正確性（符號(hào)，大于0表示分類正確）和確信度（距離大?。?/p>

1）分類正確性：如果y(w.x+b)>0,則認(rèn)為分類正確，否則錯(cuò)誤。

2）分類確信度：且y(w.x+b)的值越大，分類結(jié)果的確信度越大，反之亦然

定義超平面(w,b)關(guān)于訓(xùn)練集T的函數(shù)間隔為超平面(w,b)關(guān)于T中所有樣本點(diǎn)(xi,yi)的函數(shù)間隔的最小值，γ^=min(i=1,...,N)下的γ^

2、幾何間隔（又稱幾何距離）

如上述函數(shù)間隔的概念，樣本點(diǎn)(xi,yi)與超平面(w,b)之間的函數(shù)間隔定義為γ^=yi(w.xi+b)

但這樣帶來一個(gè)問題，w和b同時(shí)縮小或放大m倍，"這時(shí)超平面沒有變化"，但函數(shù)間隔卻變化了。所以需要將w的大小固定下來，例如||w||=1，使得函數(shù)間隔固定-->這時(shí)得出幾何間隔。

幾何間隔的定義如下：ri=yi(w/||w||.xi+b/||w||)

幾何間隔

實(shí)際上，幾何間隔就是點(diǎn)到超平面的距離，點(diǎn)(xi,yi)到直線ax+by+c=0的距離公式是

點(diǎn)到超平面距離

因此在二維空間，幾何間隔就是點(diǎn)到直線的距離，在三維或以上空間中，幾何間隔就是點(diǎn)到超平面的距離。而函數(shù)距離就是上述公式的分子，沒有歸一化。

注：對(duì)于yi這些標(biāo)簽，如果在分離超平面的負(fù)側(cè)，yi=-1，運(yùn)算時(shí)要留意

舉例1：如果訓(xùn)練集中的點(diǎn)A在超平面的負(fù)側(cè)，即yi=-1，那么點(diǎn)與超平面的距離為：

ri=-(w/||w||.xi+b/||w||)

定義超平面(w,b)關(guān)于樣本點(diǎn)(xi,yi)的幾何間隔一般是實(shí)例點(diǎn)到超平面的“帶符號(hào)”的距離（signed distance），只有當(dāng)樣本點(diǎn)被超平面正確分類時(shí)，幾何間隔才是“實(shí)例點(diǎn)到超平面的距離”。

注：以上描述的含義是，當(dāng)不正確分類時(shí)得出r=yi(w/||w||.xi+b/||w||)小于0，例如yi=-1，wx+b大于0 或者 yi=1，wx+b小于0

為何關(guān)注幾何間隔？

因?yàn)閹缀伍g隔與樣本的誤分類次數(shù)存在關(guān)系（見《統(tǒng)計(jì)學(xué)習(xí)方法》第二章“感知機(jī)”的證明）

誤分類次數(shù)≤(2R/δ)^2，其中其中δ就是樣本集合到分類超平面的距離

R=max||xi||，i=1,...,n，即R是所有樣本中（xi是以向量表示的第i個(gè)樣本）向量長(zhǎng)度最長(zhǎng)的值（即代表樣本的分布有多么廣）。結(jié)論是“當(dāng)樣本已知的情況下”，誤分類次數(shù)的上界由幾何間隔決定?！?/p>

為何要選擇幾何間隔評(píng)價(jià)“解”（系數(shù)組）是否最優(yōu)的指標(biāo)？

因?yàn)閹缀伍g隔越大的解，誤差的上界越小。因此最大化幾何間隔，就成為學(xué)習(xí)的目標(biāo)。

注：必須反復(fù)強(qiáng)調(diào)的是，xi不是要求的變量，而是已知的樣本，而要求的主要是w、a、b這些系數(shù)和算子（在這里，不要將xi當(dāng)成變量，xi代表樣本，是已知的（訓(xùn)練集中的樣本已知是哪些標(biāo)簽分類，是用來學(xué)習(xí)的））

7.1.3 間隔最大化

1、最大間隔分離超平面（助記：找到γ，或者找到間隔最小的點(diǎn)，再求超平面使得γ的值最大）

SVM的基本想法是“除了分得開，更要分得好”，所以引出了“有約束”的“最優(yōu)化問題”，式子如下：

argmax(w,b) ? ?γ? ? ? ? ? ? ? ? ? (7.9)? #最大化幾何間隔γ

s.t. yi(w/||w||.xi+b/||w||)大于等于γ， (7.10) #超平面跟每個(gè)樣本點(diǎn)的幾何間隔至少是γ

這里隱含的意義：

每個(gè)樣本點(diǎn)xi的幾何間隔至少是γ，說明γ首先是>0（分類正確），然后盡力求γ的最大值（分得好），另外γ值是由少數(shù)在margin分割線上的點(diǎn)決定的（引出支持向量的概念）。

考慮到幾何間隔和函數(shù)間隔的關(guān)系（7.8）

γ=γ^/||w||? ? （7.8）

【得出】

argmax(w,b) γ^/||w||? ? ? （7.11）#希望最大化超平面(w,b)對(duì)訓(xùn)練集T的間隔

s.t. yi(w.xi+b)≥γ^? ? ? ? ? ? ? （7.12）#要求(w,b)對(duì)每個(gè)訓(xùn)練樣本點(diǎn)的間隔至少是γ

有以下幾點(diǎn)設(shè)定：

1）最大化-->最小化：對(duì)凸函數(shù)來說，求最大值往往需要轉(zhuǎn)化為求最小值，注意到“最大化1/||w||”和"最小化1/2||w||^2"是等價(jià)的

2）函數(shù)間隔γ^取“1”：函數(shù)間隔取值不影響最優(yōu)化問題的解（例如將w和b按比例改為λw和λb，這時(shí)函數(shù)間隔成為λγ^）；函數(shù)間隔的這個(gè)變更對(duì)上述最優(yōu)化問題的不等式約束沒有影響（大于等于的關(guān)系不變）。這樣，就可以取γ^=1，將γ^=1代入上面的最優(yōu)化問題

經(jīng)過上述設(shè)定，所以得出以下“線性可分SVM的最優(yōu)化問題”：

argmin(w,b) 1/2||w||^2 ? ? ? (7.13) ? ?

s.t. yi(w.xi+b)-1≥0 ? ? ? ? ? ? （7.14）



算法7.1（線性可分SVM學(xué)習(xí)算法-最大間隔法）

輸入：線性可分訓(xùn)練數(shù)據(jù)集T={(x1,y1),(x2,y2),...,(xN,yN)},其中xi∈χ=Rn，yi∈Υ={-1,+1}，i=1,2,...,N；

輸出：最大間隔分離超平面和分類決策函數(shù)

1）構(gòu)造并求解約束最優(yōu)化問題

argmin 1/2||w||^2

s.t. yi(w.xi+b)-1≥0,i=1,2,...,N

求得最優(yōu)解w*，b*。

2)由此得到最佳分離超平面：w*.x+b*=0

由此得到分類決策函數(shù)：f(x)=sign(w*.x+b*)

2、支持向量和間隔邊界

引出“支持向量”概念：支持向量是訓(xùn)練數(shù)據(jù)集中的樣本點(diǎn)跟分離超平面距離最近的樣本點(diǎn)的實(shí)例（support vector）

這種點(diǎn)滿足幾何間隔=γ-->yi(w.xi+b)=γ，因?yàn)棣萌≈?，即

yi(w.xi+b)-1=0

1）對(duì)于yi=+1的正例點(diǎn)，支持向量在超平面H1:w.x+b=1

2）對(duì)于yi=-1的負(fù)例點(diǎn)，支持向量在超平面H2:w.x+b=-1

由于γ^取值1，所以兩個(gè)超平面的幾何距離依賴于超平面H0的法向量w，即幾何距離是是2/||w||，詳見圖7.3（支持向量），H1和H2成為間隔邊界

【重要】在決定分離超平面時(shí)，只有支持向量起作用，而其他實(shí)例點(diǎn)不起作用。由于支持向量在確定分離超平面中起到?jīng)Q定性作用，所以將這種分類模型成為“支持向量機(jī)”。

習(xí)題7.1 已知一個(gè)如圖7.4的訓(xùn)練數(shù)據(jù)集，正例點(diǎn)是x1=(3,3)^T，x2=(4,3)^T，負(fù)例點(diǎn)是x3=(1,1)^T，試求最大間隔分離超平面H0.

7.1.4 學(xué)習(xí)的對(duì)偶算法

1、帶約束的線性分類器問題如下

min 1/2||w||^2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7.13）

s.t. yi(w.xi+b)-1≥0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7.14）

下面進(jìn)行重要的推導(dǎo)，帶約束的最小值問題如何通過拉格朗日的對(duì)偶算法來解決。那什么是拉格朗日對(duì)偶性呢？簡(jiǎn)單來講，就是通過拉格朗日函數(shù)將約束條件融合到目標(biāo)函數(shù)里去，從而只用一個(gè)函數(shù)表達(dá)式便能清楚的表達(dá)出我們的問題。

求解SVM基本型不太方便，于是乎求解其對(duì)偶問題，對(duì)偶問題是一個(gè)不等式約束問題，求不等式約束問題采用KKT條件，KKT條件中有一個(gè)條件很有意思，就是 a*g（x）=0，要么拉格朗日乘子為0，要么g（x）=0，g（x）=0，表示樣本是支持向量，也就是只有支持向量才使得g（x）=0，而a=0的樣本就不需要了。

轉(zhuǎn)化如下：

(7.18)

求解策略：為了得到對(duì)偶問題的解，先求L(w,b,a)對(duì)w、b的極小，再求對(duì)a的極大

1）求min(w,b)L(w,b,a)

將拉格朗日函數(shù)L(w,b,a)分別對(duì)w、b求偏導(dǎo)并令其等于0

▽wL(w,b,a) = w-Σaiyixi=0

▽bL(w,b,a) = -?Σaiyi=0

得到

w=Σaiyixi ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7.19）

Σaiyi=0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7.20）

將(7.19)代入拉格朗日函數(shù)(7.18)，即得

L(w,b,a)

=1/2 ||w||^2 ?- ?Σaiyi(w.xi+b)+Σai

=1/2 ΣΣaiajyiyj(xi.xj)

因?yàn)檫@時(shí)候，L函數(shù)取最小值，所以得出

min(w,b)? L(w,b,a) = -1/2 ΣΣaiajyiyj(xi.xj) ?+ Σai

2）求min(w,b) L(w,b,a) 對(duì) a的極大，也就是對(duì)偶問題

對(duì)偶問題 ?min(x)max(μ)L(x,μ)=max(μ)min(x)L(x,μ)=min(x)f(x)

max(a) -1/2ΣΣaiajyiyj(xi.xj)? +Σai ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7.21）

s.t. ?Σaiyi=0

將式（7.21）的目標(biāo)函數(shù)由求極大值轉(zhuǎn)換為求最小值，就轉(zhuǎn)化為下面與之等價(jià)的對(duì)偶最優(yōu)化問題（將前面的-號(hào)變成+號(hào)）

? ? ? ? ? ?max(a)?-1/2ΣΣaiajyiyj(xi.xj)? +?Σai

===>? min(a)? 1/2ΣΣaiajyiyj(xi.xj)? -? Σai ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7.22）

? ? ? ? ? ?s.t. Σaiyi=0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7.23）

? ? ? ? ? ai ≥0，I=1,2,...,N ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7.24）

通過上述處理，原始問題求w解轉(zhuǎn)化為對(duì)偶問題求a解，并引出內(nèi)積 （7.22）--（7.24）

這個(gè)問題中變量是w，目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)（再次強(qiáng)調(diào)不要將xi看成是自變量，xi代表已知的樣本），這種規(guī)劃問題成為“二次規(guī)劃”（Quadriatic Progamming,QP）；同時(shí)由于可行域是一個(gè)凸集，因此是一個(gè)“凸二次規(guī)劃”。

定理7.2 設(shè)a*= (a1*，a2*，...，ai*)^T，是對(duì)偶最優(yōu)化問題（7.22）-（7.24）的解，則存在下標(biāo)j，使得aj*>0，并可按照下列式子求得原始最優(yōu)化問題（7.13）-（7.14）的解w*、b*

w* =? Σai*yixi ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7.25）注：w*是解

b* =Σyj -Σai*yi(xi.xj)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7.26）

從7.25和7.26可知，w*和b*只依賴于訓(xùn)練數(shù)據(jù)中對(duì)應(yīng)于a*>0的樣本點(diǎn)(xi,yi)，而其他樣本點(diǎn)對(duì)w*和b*沒有影響，所以稱“訓(xùn)練數(shù)據(jù)中對(duì)應(yīng)于ai* > 0的實(shí)例點(diǎn)xi∈R”為支持向量。

證明如下：

▽wL(w,b,a) = w-Σaiyixi=0

▽bL(w,b,a) = -Σaiyi=0

得到：

w* = Σai*yixi

其中至少有一個(gè)aj不為0（aj>0），對(duì)此j有yj(w*xj+b*)-1=0 ? ? ? ?（7.28）

將(7.25) w* =?Σai*yixi 代入 （7.28）得到?

有yj(Σai*yixi*xj+b*) =1

=>?Σai*yjyixi*xj+yj.b*=yj^2 ?（注：yj^2=1）

=>(兩邊都除以yj)?yj=b*-?Σai*yixi*xj?

=>b*= yj - Σai*yi(xi*xj)

由此定理可知，

由于g(x)=<w.x>+b，代入w* =Σai*yixi?

這里只有x才是變量，同時(shí)注意到式子中x和xi是向量，將不是向量的量從內(nèi)積符號(hào)拿出來，得到g(x) 的式子為：

g(x)= Σaiyi<xi,x>+b

由此分離超平面可以寫成：?Σai*yi(xi*xj) + b* =0 ? ? ? ? ? ? ? ? ? ? ? ? ?（7.29）?

分類決策函數(shù)可以寫成： f(x)=sign[Σai*yi(xi*xj)+b*] ? ? ? ? ? ? （7.30） （對(duì)偶形式）

（7.29）和 （7.30）的含義：分類決策函數(shù)只依賴于輸入x和訓(xùn)練樣本輸入的內(nèi)積（xi.xj）也寫作<xi,xj>，式（7.30）稱為線性可分支持向量機(jī)的對(duì)偶形式。

注意：上述變換中，看到式子中x才是變量，也就是你要分類哪篇文檔，就把該文檔的向量表示代入到 x的位置，而所有的xi統(tǒng)統(tǒng)都是已知的樣本。還注意到式子中只有xi和x是向量，因此一部分可以從內(nèi)積符號(hào)中拿出來。

算法7.2（線性可分支持向量機(jī)學(xué)習(xí)算法）

輸入：線性可分訓(xùn)練集T={(x1,y1),(x2,y2),...,(xN,yN)},其中xi∈χ=Rn，yi∈Υ={-1,+1}，i=1,2,...,N；

輸出：分離超平面和分類決策函數(shù)

1）構(gòu)造并求解約束最優(yōu)化問題

min 1/2?

Σ Σaiajyiyj(xi.xj) - Σai

? ? ? ? ? ? s.t. Σaiyi=0

? ? ? ? ? ? a ≥ 0，i=1,2,...,N

求得最優(yōu)解a*=(a1,a2,...,an)^T

2）計(jì)算

w* = Σaiyixi

并選擇a*的一個(gè)正分量aj*>0，計(jì)算

b*=yj-Σai*yi<xi,xj> ? 注：xi和xj的內(nèi)積

3）求得分離超平面

w*x+b*=0

4）求得分類決策函數(shù)

f(x)=sign(w*.x+b*)

7.3 非線性支持向量機(jī)與核函數(shù)

1)引入核函數(shù)(滿足對(duì)稱性和半正定型的函數(shù)是某高維希爾伯特空間的內(nèi)積）

只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。如果有很多基的話維度勢(shì)必會(huì)很高，計(jì)算內(nèi)積的花銷會(huì)很大，有些是無限維的，核函數(shù)能繞過高維的內(nèi)積計(jì)算，直接用核函數(shù)得到內(nèi)積。

核函數(shù)的基本想法：

1）通過一個(gè)非線性變換將輸入空間(歐式空間Rn或離散集合)對(duì)應(yīng)于一個(gè)特征空間(希爾伯特空間)，使得在輸入空間中的超曲面模型對(duì)應(yīng)于特征空間中的超平面模型(支持向量機(jī))。

2）核函數(shù)必須滿足對(duì)稱性(K(x,y) = K(y, x))及半正定性(K(x,y)>=0)。根據(jù)Mercer法則，我們知道任何滿足對(duì)稱性和半正定型的函數(shù)都是某個(gè)高維希爾伯特空間的內(nèi)積。

核函數(shù)定義：設(shè)X是輸入空間(歐式空間Rn或離散集合)，又設(shè)H為特征空間(希爾伯特空間)，如何存在一個(gè)從X到H的映射：

Ф(x): X --> H

使得對(duì)所有的x, z∈X，函數(shù)K(x, z)滿足條件:

K(x,z) =Ф(x)·Ф(z)

那么就稱K(x, z)為核函數(shù)，Ф(x)為映射函數(shù)，式中Ф(x)·Ф(z)為Ф(x)和Ф(z)的內(nèi)積。

注：引入核函數(shù)的原因是直接計(jì)算K(x,z)容易，而通過Ф(x)和Ф(z)計(jì)算K(x,z)有點(diǎn)困難。

例題：

假設(shè)輸入空間是R2，核函數(shù)是K(x, z)=(x.z)2，試找出相關(guān)的特征空間H（希爾伯特空間）和映射Φ(x)：R2------>H。

解：取特征空間H=R^3，記x=(x1,x2)^T，z=(z1,z2)^T,由于

(x, z)2=(x1z1+x2z2)2 = (x1z1)2+2 x1z1x2z2+ (x2z2)2

可以取映射

Φ(x) = [(x1)2,√2x1x2,(x2)2]^T

Φ(x).Φ(z) = (x1z1)2+2 x1z1x2z2+ (x2z2)2

注意：原空間R2，而用核技巧后的空間是R^3，實(shí)際上是升維了

2）核技巧在支持向量機(jī)中的應(yīng)用：

對(duì)支持向量機(jī)的對(duì)偶問題中跟，無論是目標(biāo)函數(shù)還是決策函數(shù)（分離超平面）都只涉及實(shí)例和實(shí)例之間的內(nèi)積。所以在對(duì)偶問題的目標(biāo)函數(shù)?1/2?ΣΣaiajyiyj(xi.xj)? -Σai 中的內(nèi)積xi.xj 可以用核函數(shù)K(xi.xj) = Φ(xi).Φ(xj) 來代替。此時(shí)對(duì)偶問題的目標(biāo)函數(shù)成為

W(a) = 1/2 ΣΣaiajyiyj K(xi.xj) -Σai中 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (7.67)

同樣分類決策函數(shù)中的內(nèi)積也可以用核函數(shù)來代替，而分類決策函數(shù)成為：

f(x) = sign [ΣaiyiΦ(xi).Φ(x) + b*] = sign [ΣaiyiK(xi.xj) + b*] ? ?（7.68）

這樣一來：原來輸入空間中的高維度內(nèi)積（升維是為了實(shí)現(xiàn)分離“超曲面”變成高維度空間的分離“超平面”）xi.xj經(jīng)過映射函數(shù)Φ轉(zhuǎn)換為特征空間（高維度空間，H空間）中的內(nèi)積Φ(xi).Φ(xj)，并在新的H空間中學(xué)習(xí)線性向量機(jī)

附錄A：最優(yōu)化問題種類

通常我們需要求解的最優(yōu)化問題有如下幾類：

1、無約束優(yōu)化問題，可以寫為:

min f(x);

對(duì)此類優(yōu)化問題，常常使用的方法就是Fermat定理，即使用求取f(x)的導(dǎo)數(shù)，然后令其為零，可以求得候選最優(yōu)值，再在這些候選值中驗(yàn)證；如果是凸函數(shù)，可以保證是最優(yōu)解。

2、有等式約束的優(yōu)化問題，可以寫為:

min f(x),

s.t. h_i(x) = 0; i =1, ..., n

對(duì)此類優(yōu)化問題，常使用拉格朗日乘子法（Lagrange Multiplier) ，即把等式約束h_i(x)用一個(gè)系數(shù)與f(x)寫為一個(gè)式子，稱為拉格朗日函數(shù)，而系數(shù)稱為拉格朗日乘子。通過拉格朗日函數(shù)對(duì)各個(gè)變量求導(dǎo)，令其為零，可以求得候選值集合，然后驗(yàn)證求得最優(yōu)值。

3、有不等式約束的優(yōu)化問題，可以寫為：

min f(x),

s.t. g_i(x) <= 0; i =1, ..., n

h_j(x) = 0; j =1, ..., m

對(duì)第3類優(yōu)化問題，常用KKT條件。

同樣地，我們把所有的等式、不等式約束與f(x)寫為一個(gè)式子，也叫拉格朗日函數(shù)，系數(shù)也稱拉格朗日乘子，通過一些條件，可以求出最優(yōu)值的必要條件，這個(gè)條件稱為KKT條件。

KKT條件是說最優(yōu)值必須滿足以下條件：

1. L(a, b, x)對(duì)x求導(dǎo)為零；

2. h(x) =0;

3. a*g(x) = 0;

求取這三個(gè)等式之后就能得到候選最優(yōu)值。

其中第三個(gè)式子非常有趣，因?yàn)間(x)<=0，如果要滿足這個(gè)等式，必須a=0或者g(x)=0. 這是SVM的很多重要性質(zhì)的來源，如支持向量的概念。

根據(jù)拉格朗日方法，對(duì)應(yīng)的拉格朗日函數(shù)為

求函數(shù)z=f(x,y)在滿足φ(x,y)=0的條件極值，可以轉(zhuǎn)化求為函數(shù)F(x,y,λ)=f(x,y)+λφ(x,y)的無條件極值問題。

附錄B KKT對(duì)偶解釋（為何min max=max min=f(x)?）

http://blog.csdn.net/wusnake123/article/details/58635726? 拉格朗日數(shù)乘法

【KKT的定義】KKT條件是指在滿足一些有規(guī)則的條件下, 一個(gè)非線性規(guī)劃(Nonlinear Programming)問題能有最優(yōu)化解法的一個(gè)必要和充分條件.這是一個(gè)廣義化拉格朗日乘數(shù)的成果. 一般地, 一個(gè)最優(yōu)化數(shù)學(xué)模型的列標(biāo)準(zhǔn)形式參考開頭的式子, 所謂 Karush-Kuhn-Tucker 最優(yōu)化條件，就是指上式的最優(yōu)點(diǎn)x?必須滿足下面的條件:

1)約束條件滿足gi(x?)≤0,i=1,2,…,p, 以及,hj(x?)=0,j=1,2,…,q

2).?f(x?)+∑i=1μi?gi(x?)+∑j=1λj?hj(x?)=0, 其中?為梯度算子;

3)λj≠0且不等式約束條件滿足μi≥0,μigi(x?)=0,i=1,2,…,p。

KKT條件第一項(xiàng)是說最優(yōu)點(diǎn)x?必須滿足所有等式及不等式限制條件, 也就是說最優(yōu)點(diǎn)必須是一個(gè)可行解, 這一點(diǎn)自然是毋庸置疑的.?

第二項(xiàng)表明在最優(yōu)點(diǎn)x?, ?f必須是?gi和?hj的線性組合, μi和λj都叫作拉格朗日乘子. 所不同的是不等式限制條件有方向性, 所以每一個(gè)μi都必須大于或等于零, 而等式限制條件沒有方向性，所以λj沒有符號(hào)的限制, 其符號(hào)要視等式限制條件的寫法而定.

以下舉例介紹KTT 的由來

推導(dǎo)思路：從上述三個(gè)條件（湊出這些條件就能實(shí)現(xiàn)對(duì)偶，形成KTT條件求最優(yōu)解）

令L(x,μ)=f(x)+Σμkgk(x) ? #注：這里f(x)代表目標(biāo)函數(shù)，g(x)表示約束函數(shù)

∵ μk≥0，gk(x)≤0 ====>? μkg(x)≤0

∴ max(μ)L(x,μ)=f(x) ? ? ? ? ? ? ? ? ? ? ? ? （公式2）

∴ min(x)f(x)=min(x)max(μ)L(x,μ) ? ?（公式3）

代入

max(μ)min(x)L(x,μ)

=max(μ)[min(x)f(x)+min(x)μg(x)]

=max(μ)min(x)f(x)+max(μ)min(x)μg(x)

=min(x)f(x)+max(μ)min(x)μg(x)

？為何max(μ)min(x)f(x)=min(x)f(x)

又∵ μk≥0，gk(x)≤0

∴ min(x)μg(x)有以下兩個(gè)條件的取值

1）取值為“0” ? ? ? ? ? ? ? ? ? ? ? ? ?當(dāng)μ=0 或 g(x)=0

2）取值為“-∞”（負(fù)無窮）? ? 當(dāng)μ>0 或g(x)<0 ??

所以當(dāng)取值“0”的時(shí)候有最大值

==>

∴ max(μ)min(x)μg(x)=0，此時(shí)μ=0 或 g(x)=0.

∴ max(μ)min(x)L(x,μ)=min(x)f(x)+max(μ)minxμg(x)=minxf(x) ? ? （公式4）

聯(lián)合（公式3）和（公式4）我們得到min(x)max(μ)L(x,μ)=max(μ)min(x)L(x,μ)，也就是

min(x)max(μ)L(x,μ)=max(μ)min(x)L(x,μ)=min(x)f(x)

我們把maxμminxL(x,μ)稱為原問題minxmaxμL(x,μ)的對(duì)偶問題

上式表明“當(dāng)滿足一定條件時(shí)”，原問題（prmial）的解、對(duì)偶問題（duality）的解、以及min(x)f(x)是相同的，且在最優(yōu)解x*處，μ=0或g(x*)=0。

將x*代入(公式2)得到max(μ)L(x*,μ)=f(x*)，由(公式4)得到max(μ)min(x)L(x*,μ)=f(x*)，（對(duì)"max(μ)min(x)L(x*,μ)=max(μ)L(x*,μ)”)兩邊消去max(μ)，所以L(x*,μ)=min(x)L(x*,μ)（式子表示x*的時(shí)候，L(x,μ)得到最小值），說明x*也是L(x,μ)的極值點(diǎn)。

【小結(jié)】

KKT條件是拉格朗日乘子法的泛化（見附錄B說明），如果我們將等式約束和不等式約束一并納進(jìn)來如下所示：

注：由于下標(biāo)x輸入不方便，min(x)是指對(duì)x求最小值（常通過偏導(dǎo)操作實(shí)現(xiàn)）等同于

附錄C：從||w||引出范數(shù)的定義

||w||是什么符號(hào)？||w||叫做向量w的范數(shù)，范數(shù)是對(duì)向量長(zhǎng)度的一種度量。

我們常說的向量長(zhǎng)度其實(shí)指的是它的L2范數(shù)，范數(shù)最一般的表示形式為p-范數(shù)，可以寫成如下表達(dá)式

向量w=(w1, w2, w3,…… wn)

它的p級(jí)范數(shù)為

附錄E：python實(shí)現(xiàn)SVM實(shí)例（LIBSVM）

http://www.cnblogs.com/luyaoblog/p/6775342.html

http://www.cnblogs.com/harvey888/p/5852687.html

http://blog.csdn.net/zouxy09/article/details/17292011

數(shù)據(jù)文件CSV的鏈接

附錄E：工程實(shí)踐

總的來說實(shí)驗(yàn)一、二，其結(jié)果驗(yàn)證了Vapnik等人的結(jié)論，即不同的核函數(shù)對(duì)SVM性能的影響不大，反而核函數(shù)的參數(shù)和懲罰因子C是影響SVM性能的關(guān)鍵因素，因此選擇合適的核函數(shù)參數(shù)和懲罰因子C對(duì)學(xué)習(xí)機(jī)器的性能至關(guān)重要

附錄F：數(shù)學(xué)符號(hào)表（用于輸入公式）

2 3 ± × ÷ ∽ ≈ ≌ ≒ ≠ ≡ ≤ ≥ Σ ∈ ∞ ∝ ∩ ∪ ∫ √

б μ ? δ ε γ α β γ Ω Ψ Σ θ η λ π τ φ ω ψ ‰←↑→↓↖↗↘↙∴∵

∠∟∥∣∶∷⊥⊿⌒□△◇○?◎☆?①②③④⑤⑥⑦⑧⑨⑩°‰?℃℉№

123≈≡≠＝≤≥＜＞≮≯∷±?＋－×÷／

∫∮∝∞∧∨∑∏∪∩∈∵∴⊥∥∠⌒⊙≌∽√ ▽

αβγδεζηθικλμνξοπρστυφχψω ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩ

§№☆★○●◎◇◆□℃‰■△▲※→←↑↓↖↗↘↙

〓¤°＃＆＠＼︿＿￣―♂♀～Δ▽▽▽▽▽▽▽▽

㈠㈡㈢㈣㈤㈥㈦㈧㈨㈩①②③④⑤⑥⑦⑧⑨⑩▽▽▽▽▽▽

?2f/?x2=2y2，?2f/?x?y=4xy，?2f/?y2=2x2，?2f/?y?x=4xy。?求偏導(dǎo)符號(hào)

附錄G

一般來說，求最小值問題就是一個(gè)優(yōu)化問題（規(guī)劃），由兩部分組成：目標(biāo)函數(shù)和約束條件

min ? f(x) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?#目標(biāo)函數(shù)

s.t. ci(x)≤0，i=1,2,...,p ? ? ? ? ? ? ? ? ? #注意這里是hi不等式約束

cj(x)=0，j=p+1,p+2,...,p+q ? ? ?#注意這里是等式約束

#p個(gè)是不等式約束，q個(gè)是等式約束

#上式中的x是自變量，但不限于x的維度數(shù)（例如文本分類的維度數(shù)可能達(dá)到上萬個(gè)維度）

#要求f(x)在某個(gè)點(diǎn)找到最小值，但不是在整個(gè)空間中尋找，而是在約束的條件所限定的空間找，這個(gè)有限的空間就是優(yōu)化理論提到的“可行域”

#注意到可行域中的每一個(gè)點(diǎn)都是要求滿足p+q個(gè)條件，同時(shí)可行域邊界上的點(diǎn)有一個(gè)優(yōu)秀的特性，就是可以使不等式約束。注意，這個(gè)特性后續(xù)求解起到關(guān)鍵作用，例如以下例子：

max(μ)min(x)L(x,μ)

=max(μ)[min(x)f(x)+min(x)μg(x)]

=max(μ)min(x)f(x)+max(μ)min(x)μg(x)

=min(x)f(x)+max(μ)min(x)μg(x)

又∵ μk≥0，gk(x)≤0 ? ? ? ? ? ?∴min(x)μg(x)有以下兩個(gè)條件的取值

1)取值為“0” ? ? ?當(dāng)μ=0 或 g(x)=0；2)取值為“-∞”（負(fù)無窮）? ? 當(dāng)μ>0 或g(x)<0

所以當(dāng)取值“0”的時(shí)候有最大值，因此這時(shí)μ=0 或 g(x)=0

按照定理7.2，分離超平面可以寫成

Σai*yi(xi.xj）+ b* = 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7.29）

分類決策函數(shù)可以寫成

f(x) = sign(Σai*yi（7.29）

注：這里為何是ai和aj，xi和xj，yi和yj？

2、重新審視線性分類器問題（原始問題求w解轉(zhuǎn)化為對(duì)偶問題求a解，并引出內(nèi)積）

min 1/2||w||^2 ? #注意自變量是w

s.t. yi(w.xi+b)-1≥0

需要求w的解，凸二次規(guī)劃問題的優(yōu)點(diǎn)是“容易找到解”，有全局最優(yōu)解。

下來的重要思路是將“帶不等式約束的問題”轉(zhuǎn)化為“只帶等式約束的問題--就能用拉氏算子輕松解決”（在這里，凸集邊界的點(diǎn)就起到關(guān)鍵作用）

1)需要求得一個(gè)線性函數(shù)（n維空間中的線性函數(shù)），

g(x)=wx+b，

使得所有屬于正類的點(diǎn)x+，代入后有g(shù)(x+)≥1

使得所有屬于負(fù)類的點(diǎn)x-，代入之后有g(shù)(x)≤1

注：g(x).x-或g(x).x+都會(huì)大于1，類似yi(w.xi+b)

2）求解的過程就是“求解w的過程”，w是n維向量

3）可以看出，求出w之后，就能得出超平面H、H1和H2的解

4）w如何推導(dǎo)？w是由樣本xi決定，這樣w就可以表示為樣本xi的某種組合

w=a1.x1+a2.x2+...+an.xn.

注：ai是實(shí)數(shù)值系數(shù)，又成為拉格朗日乘子；xi是樣本點(diǎn)因而是向量，n就是總樣本的個(gè)數(shù)

5）以下區(qū)別“數(shù)字和向量的乘積”以及“向量之間的乘積”，并用尖括號(hào)代表向量x1和x2的內(nèi)積（也是點(diǎn)積，注意跟向量叉積的區(qū)別）

6）g(x)的表達(dá)式修改為：g(x)=+b（林軒田視頻中，干脆就是，b為w0）

7）進(jìn)一步優(yōu)化表達(dá)式

w=a1.y1.x1+a2.y2.x2+...+an.y3.xn? ? ? ? ? （式1）

注：yi是第i個(gè)樣本的標(biāo)簽，yi=+1或yi=-1

8)? 對(duì)求和號(hào)Σ進(jìn)行簡(jiǎn)寫：w=Σ（aiyixi）

9）因此原來的g(x)表達(dá)式可以寫為：g(x)=+b=<Σ(aiyixi),x>+b

10）將上述公式的非向量提取出來，修改成以下式子：

g(x)=Σaiyi+b（式2）

11）至此，完成了將“求w”轉(zhuǎn)化成“求a”的過程