硬間隔線性支撐向量機(jī)

假設(shè)給定一個(gè)特征空間上的訓(xùn)練數(shù)據(jù)集：

T={Gi,yD,62,丫2),…，(XNJN)}

n

其中，XjGRzYie(+l,-l),i=1,2,…,N,Xj為第i個(gè)特征向量或?qū)嵗?%為%的類標(biāo)記，當(dāng)y=1時(shí)，稱Xj為

正例，當(dāng)力=-1時(shí)，稱片為負(fù)例；',力)為樣本點(diǎn)。

假設(shè)訓(xùn)練數(shù)據(jù)集是線性可分的(存在硬間隔)，那么學(xué)習(xí)的目標(biāo)是在特征空間找到一個(gè)分別超平面，能將實(shí)

例分到不同的類。分別超平面方程w-x+b=O,它由法向量W和截距b確定，可用(w,b)表示。分別超平面

將特征空間分為兩部分，一部分是三類，一部分是負(fù)類。法向量指向的一側(cè)為正類，另一側(cè)是負(fù)類。

一般地，當(dāng)訓(xùn)練數(shù)據(jù)集線性可分時(shí)，存在無窮個(gè)分別超平面可將兩類數(shù)據(jù)正確分開,感知機(jī)利用誤分類最小

的策略，求得分別超平面，不過這是的解有無窮多。線性可分支撐向量機(jī)利用間隔最大化求最優(yōu)分別超平面，

解唯一。

一、模型推導(dǎo)

L函數(shù)間隔：一般來說,一個(gè)點(diǎn)距離分別超平面的遠(yuǎn)近可以表示分類預(yù)料的確信程度。在超平面w?x+b=0

確定的狀況下，|w?x+b|能夠相對(duì)地表示(留意：真實(shí)距離為野手)點(diǎn)x距離超平面的遠(yuǎn)近.而w?x+b的

IWII

符號(hào)與類標(biāo)記y的符號(hào)是否一樣能夠表示分類是否正確。所以可用標(biāo)量y(w-x+b)來表示分類的正確性及確信

度，值為正表示分類正確，值為負(fù)表示分類錯(cuò)誤"

超平猷w,b)關(guān)于樣本版X,,y、的函數(shù)間隔為:

Yi=yj(w-Xj+b)

超平面叫切關(guān)于訓(xùn)練數(shù)據(jù)集T的函數(shù)間隔：

Y=min%=minVj(w-x；+b)

i=l,2,...,Ni=l,2，…,N

2.幾何間隔：函數(shù)間隔可以表示分類預(yù)料的正確性及確信度，但是選擇分別超平面時(shí)，只有函數(shù)間隔還不夠。

因?yàn)橹灰杀壤刈兏黽和b,雖然超平面并沒有變更，但函數(shù)間隔(它是(w,b)的線性函數(shù))卻依原比例同

等變更。為了將(w,b)表示的超平面的唯Tt,即每個(gè)超平面對(duì)應(yīng)Rn+1中的唯一向量(w,b),可以對(duì)法向量W

加以規(guī)范化約束IIW11=1,這時(shí)函數(shù)間隔稱為幾何間隔。

超平躍w,b)關(guān)于樣本虱A,y、的幾何間隔為:

Yi_/wb\

丫戶而"隊(duì)而小+而)

超平面w,b)關(guān)于訓(xùn)練數(shù)據(jù)集T的幾何間隔為:

丫=口萼%-=用%力(高?*+島)

3.間隔最大化

支撐向量機(jī)學(xué)1習(xí)的基本想法是求解能夠正確劃分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的分別超平面。對(duì)于線性可分

的訓(xùn)練數(shù)據(jù)集而言，線性可分分別超平面有無窮多個(gè),每一個(gè)都是一個(gè)感知機(jī)，但是幾何間隔最大的分別超

平面時(shí)唯一的。

間隔最大化的直觀說明是：對(duì)訓(xùn)練數(shù)據(jù)集找到幾何間隔最大的超平面意味著以充分大的卻新都對(duì)訓(xùn)練數(shù)據(jù)進(jìn)

行分類。也就是說，不僅將正負(fù)實(shí)例點(diǎn)要分開，而且對(duì)最難分的實(shí)例點(diǎn)(離超平面最近的點(diǎn))也有足夠多大

的確信度將它們分開。

因此所要優(yōu)化的問題表示為：

max丫

改寫為,

max-——-

w.b||W||

s.t.yj(w-Xj+b)>y,i=1,2,N

y的取值不影響最優(yōu)化問題的解(假如w,b?是最優(yōu)解，那么入w?，入b?也是最優(yōu)解，因此y是變動(dòng)的可以取到隨

意值，假如固定y,w*,b?也就變得唯一了)，令？=1,等價(jià)變換為，

max--------

w,b||W||

s.t.yj(w-Xj4-b)>1,i=1,2,...,N

(目標(biāo)函數(shù)是支撐間隔，約束是樣本點(diǎn)在間隔邊界或外側(cè)，目標(biāo)是找尋支撐向量使得間隔最大化)等價(jià)變換

為(標(biāo)準(zhǔn)無等式約束的凸二次規(guī)劃，這是為了運(yùn)算便利)，

min-IIwII2

s.t.1—yj(w,Xj+b)<0,i=1,2,N

凸二次規(guī)劃問題存在全局最優(yōu)解w?力?。

(4)分別超平面與分類決策函數(shù)

分別超平面:

w*?x+b"=0

分類決策函數(shù):

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

(5)支撐向量與間隔邊界

在線性可分狀況下，訓(xùn)練數(shù)據(jù)集的樣本點(diǎn)中與分別超平面距離最近的樣本點(diǎn)的實(shí)例稱為支撐向量，支撐向量

是使約束條件等號(hào)成立的點(diǎn)，即1-%(w?為+b)=0,對(duì)于正例點(diǎn)，支撐向量在超平面w?*+b=1上，對(duì)

于負(fù)例點(diǎn)，支撐向量在超平面W?%+b=-1上，沒有實(shí)例點(diǎn)落在這兩個(gè)平行的超平面(間隔邊界)之間，

這兩個(gè)超平面之間的距離稱為間隔,它依靠于分別超平面的法向量W,等于扁。

在確定分別超平面時(shí)只有支持向量起作用，而其他實(shí)例點(diǎn)并不起作用。假如移動(dòng)支持向量將變更所求的解，

但是假如在間隔邊界以外移動(dòng)其他實(shí)例點(diǎn)，甚至去掉這些點(diǎn)，則解是不會(huì)變更的。明顯支撐向量是訓(xùn)練集中

重要的樣本。

二、模型求解

將原始問題轉(zhuǎn)化為L(zhǎng)agrange對(duì)偶問題,通過求解對(duì)偶問題來獲得原始問題的最優(yōu)解：對(duì)每個(gè)不等式約束引入

Lagrange乘子四，

1.Lagrange對(duì)偶函數(shù):

NN

2-W(Xiyi(wXi+b)+W

L(w,b,a)=

i=li=l

其中a=...,0tN)T為拉格朗日乘子向量，四N0,i=1,2,...,NO

2.對(duì)偶問題：

maxminL(w,b,a)

aw,b

(1)求minL(w,b,a)

w,b

N

一W四%Xi

VwL(w,b,a)=w0

i=l

N

VL(w,b,a)=一26力=

b0

i=l

得出

N

Xi

w=W四%

i=l

N

w四月=°

i=i

帶入拉格朗日函數(shù)，得出

NNN//N\\N

minL(w,b,a)四巧力竹??牛)一分四力|(W修).Xj+b)+乏%

i=lj=li=l\\j=l/Ii=l

1NNN

=一工W%咿yR,牛)+26

i=lj=li=l

(2)求maxminL(w,b,a)

aw,b

1NNN

-5WW%咿”(Xi,Xj)+W?i

(1=1j=li=l

N

s.t.W四0=0

i=l

?i>0,i=1,2,...?N

轉(zhuǎn)換為求微小

1NNN

^22%%片“(4.牛)一2

(i=lj=li=l

N

WSK=°

S.t.

i=l

?i>0,i=1,2,...,N

依據(jù)對(duì)偶理論，對(duì)上述對(duì)偶優(yōu)化存在，使W,b，是原始問題的解，a*感寸偶問題的解，因此求解原始問題,

可以轉(zhuǎn)化為求解對(duì)偶問題。

3.最優(yōu)解

依據(jù)KKT條件

Vw<L(w\b\a*)=w*一況143=0----------------------(a)

VyL(w*,b*,a*)=-Sili<Yi=0-----------------------------(b)

<(Yi(W-Xj+b*)-1)=0,i=1,2,...,N-----------------------------(C)

Yi(w*-X,4-b")-1>0,i=1,2,N----------------------------------(d)

a；>0,i=1,2，…，N----------------------------------------------------(e)

由(a)求得

N

i=l

其中至少有一個(gè)硫＞0（假如a*=0,那么w*=0,b，無解，明顯它不是原始最優(yōu)化問題的解），結(jié)合KKT

條件（C），得出

Yk(w*-xk+b*)-1=0

將w*帶入KKT條件，得出

兩邊同時(shí)乘以yk,由于（yk）?=1

軟間隔線性支撐向量機(jī)

一、模型推導(dǎo)

假如樣本集中存在特異點(diǎn)使得樣本集線性不行分，即不能滿意函數(shù)間隔大于等于1不等式約束條件，為了解

決這個(gè)問題，可以對(duì)每個(gè)樣本點(diǎn)(片，%)引入一個(gè)松弛變量4>0,使函數(shù)間隔加上松弛變量大于等于1.這樣

約束條件變?yōu)?/p>

yi(w*-i+b*)>l-5i

同時(shí)對(duì)每個(gè)松弛變量&,支付一個(gè)代價(jià)年,目標(biāo)函數(shù)變成

N

min-11w||2+eV國(guó)

w,bL乙，

i=l

這里，C>0稱為懲處參數(shù)，一般由應(yīng)用問題確定，c值大時(shí)對(duì)誤分類的懲處增大，C值小時(shí)對(duì)誤分類的懲處

減小。最小化上述目標(biāo)函數(shù)有兩層含義，要使的｝IIW||2盡量小即間隔盡量大，同時(shí)使的誤分類的點(diǎn)的個(gè)數(shù)盡

量小，C是調(diào)和二者的系數(shù)。這時(shí)的間隔稱為軟間隔，因?yàn)殚g隔內(nèi)含義特異點(diǎn)。

原始優(yōu)化問題：

N

min-||w||2+eV5

w.b2Z-j

i=l

s.t.1-5j-Yi(w?X)4-b)<0,i=1,2,...,N

>0,i=1,2，…,N

這仍是一個(gè)二次凸優(yōu)化，存在全局最優(yōu)解，W的解是唯一的，但b的解不唯一，b的解存在于一個(gè)區(qū)間。

二、庭求解

仍運(yùn)用Lagrange對(duì)偶方法求解

1.Lagrange函數(shù)

1NNN

L(w,b,$aM=彳Hw儼+CW8-￡ai(H(w?Xi+b)—1+&)—W內(nèi)七

i=li=li=l

其中，cqN0,內(nèi)N0。

2.對(duì)偶問題：

maxminL(w,b,ga,n)

apw,b，E

(1)求嬲L(w,b<a,p)

VwL(w,b,*a,p)=w一1四力x,=0

i=l

N

VbL(w,b,$a,u)=-Za.yi=0

i=l

V[L(w,b,a,p)=C-1T-aT-pT=0

得出

N

w=乏四力Xi

i=l

N

WotiYi=o

i=i

C-Qj—|lj=0

帶入拉格朗日函數(shù)，得出

minL(w,b,&aM=—?乏W叫與力"國(guó).Xj)+2四

i=lj=li=l

留意它與H無關(guān)。

(2)求maxminL(w,b,5,a,n)

aw,b，l

NNN

max一乏%%力力(、,’%)+W%

22i=l

N

stW%%=0

i=l

a,>0,i=1?2,...,N

Pi>0,i=

C—a；—|ij=0fi=1,2,...,N

消去內(nèi)，轉(zhuǎn)換為求微小

min

a

i=lj=li=l

N

S.t.WaiYi=0

i=l

ctj>0,i=1,2,...?N

0<aj<C

(3)最優(yōu)解

依據(jù)KKT條件

Vw*Mw*,b*I，a*N)=w*—優(yōu)=a；/Xi=0(a)

VbxL(w*,b*W,Q)=-型Ei=0------(b)

T

VvL(w*,b*,「a\n*)=C-l-a--p*=0--(c)

a；(yi(w*?Xj+b*)—1+《；)=0,i=1,2,...,N----------------(d)

癡后=0,i=l,2,...,N---------------------------------------(e)

>0,i=1,2,...,N------------------------------------------(f)

y.(w*?*+b*)-1+培N0,i=1,2,,N---------------------(g)

a*>0,i=1,2,...,N-----------------------------------------(h)

>0,i=1,2，…，N……--------------------------……——(i)

由(a)求得

N

w*=2^a；yixi

i=l

由(c)、(e)、(i)得出

(C-嗚崗=0

C-a；>0

再結(jié)合(f)得出

假如a；<C,那么尋=0；假如a：=C,^>0;................................(j)

由(d),(h)得出

假如a；>0,那么R(w*?Xj+b")-1+埼=0;假如嗚=0,y((w*?X]+b*)—1+*不確定；--------(k)

由(j),(k)得出

假如0Va；VC,那么百=0,yi(w-?Xi+b")-1+4=0,因此為(w*?Xi+b?)=1;

N

b*=ykXj)

j=i

由(j),(g)得出

假如a；=0,那么可=0,yi(w*X1+b*)>l；這說明Xi位于間隔邊界上或以外；

由⑴，(k)得出

假如a；=C,那么％(w*?與+b*)=1-Z0;

此種狀況下，進(jìn)一步探討：

假如￥=0,那么Xi在間隔邊界上；

假如0V<1,那么由分類正確，*在間隔邊界與分別超平面之間；

假如￥=I,那么Xi在分界面上；

假如K>1,那么Xi在分別超平面誤分一側(cè)；

因此可以看出，軟間隔的支撐向量(a；>0)*或者在間隔邊界上，或者在間隔邊界與分別超平面之間，或

者在分別超平面誤分一側(cè)。

3.支撐向量的另一種說明

最小化以下目標(biāo)函數(shù)：

N

2

，口-Yi(w-X,+b)]++A||w||

i=l

第一項(xiàng)是閱歷損失或閱歷風(fēng)險(xiǎn)，函數(shù)稱為合頁(yè)損失函數(shù)L(y(w-x+b))=[l-yi(w-xi+b)]+,下標(biāo)"+"表

示以下取正值得函數(shù)。

「1fzZ>0

[Z]+=10z<0

也就是說，當(dāng)樣本點(diǎn)被正確分類且函數(shù)間隔大于1時(shí),損失函數(shù)為0,否則(片為支撐向量時(shí))損失函數(shù)是

1-y4w?片+b),其次項(xiàng)是系數(shù)為4的w的L2范數(shù)，是正則化項(xiàng)；這兩種優(yōu)化是等價(jià)的(通過變量替換方

法)；

非線性支撐向量機(jī)

對(duì)于分類問題是非線性的（線性模型無法將正負(fù)實(shí)例正確分開），可以利用核技巧，進(jìn)行一個(gè)非線性變換，

將非線性問題變換為線性問題，通過解變換后的線性問題的方法求解原來的非線性問題。

用線性分類方法求解非線性分類問題問題分兩步：首先運(yùn)用一個(gè)變換將原空間的數(shù)據(jù)映射到新空間；然后再

新空間里用線性分類學(xué)習(xí)方法從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)分類模型；

核技巧應(yīng)用到支持向量機(jī)，其基本思想：

通過一個(gè)非線性變換將輸入空間（歐氏空間R11或離散集合）對(duì)應(yīng)于一個(gè)特征空間（希爾伯特空間H）,

使得在輸入空間W中的超曲面模型對(duì)應(yīng)于特征空間H中的超平面模型（支撐向量機(jī)），這樣分類問題的學(xué)習(xí)

任務(wù)通過在特征空間中求解線性支撐向量機(jī)就可以完成。

一、非線性支撐向量機(jī)

在線性支撐向量機(jī)的對(duì)偶問題中,無論是目標(biāo)函數(shù)還是決策函數(shù)（分別超平面）都只涉及輸入實(shí)例與實(shí)

例之潮勺內(nèi)積,假如把這個(gè)內(nèi)積。?Xj看作是希爾伯特空間中的兩個(gè)特征的內(nèi)積蟻幻?（/）（%；）=K（"）=

A，Xj,其中X[=。（吟，xj=</>（%；）,那么對(duì)于在低維線性不行分的樣本氯X：,i=1,2，…,N],假如通過映

蝌變換到高維希爾伯特空恒心》,i=1,2，…,N）變得線性可分（假設(shè)能找到這樣的合適的映射g）z那么就可

以運(yùn)用核函數(shù)代替計(jì)算xa,這里Xj未知,但x]x；,K?，M）艮雙

運(yùn)用核函數(shù)后的對(duì)偶問題的目標(biāo)函數(shù)成為：

1NNN

W（a）=萬(wàn)｛W叫四力力K（Xi.x。一2四

i=lj=li=l

最優(yōu)解成為

N

W*=2^afYiXi

i=l

N

4

b=yk-^a；yjK（xj-xi）

j=i

分類決策函數(shù)成為

fM=signa；yiK（Xi-x）+bj

在實(shí)際應(yīng)用中，往往依靠領(lǐng)域?qū)W問干脆選擇核函數(shù):核函數(shù)選擇的有效性須要通過試驗(yàn)驗(yàn)證。

二、核函數(shù)方法

核函數(shù)：設(shè)X是輸入空間（歐氏空間Rn的子集或離散集合）,H為特征空間（希爾伯特空間），假如存在一

個(gè)從X到H的映射，

（|）（x）:X->H

使得對(duì)全部X,zEX,函數(shù)K（x,z）滿意條件

K（x,z）=6（x）?巾（z）

則稱K（x,z）為核函數(shù)，6（x）為映射函數(shù)，（|）（x）?巾（z）為（|）（x）和6（z）內(nèi)積；

（希爾伯特空間是完備化的內(nèi)積空間,其中的每個(gè)元素是一個(gè)向量（可以無窮維），向量之間定義有內(nèi)積運(yùn)

算,且空間關(guān)于內(nèi)積誘導(dǎo)出的范數(shù)是完備的）

核技巧的想法是：在學(xué)習(xí)與預(yù)料中只定義核函數(shù)K（x,z）,而不顯示地定義映射函數(shù)也，因?yàn)橥ǔ８纱嘤?jì)算

K（x,z）比較簡(jiǎn)潔,而通過Q（x）和0⑵計(jì)算K（x,z）并不簡(jiǎn)潔。留意，0（x）是輸入空間R11到特征空間H的映射，

特征空間HT殳是高維的，甚至是無窮維的。我們須要的是特征空間中兩個(gè)特征的內(nèi)積結(jié)果,而不是特征的

表丞j假如我們能通過簡(jiǎn)潔的函數(shù)K(x,z)得到巾(x)?巾⑵的內(nèi)積，那就簡(jiǎn)化了問題，不用考慮巾的形式，這正

是核函數(shù)的妙用之處。

對(duì)于給定的核函數(shù)K(x,z),特征空間H(希爾伯特子空間)和映射函數(shù)巾的取法不唯一，因?yàn)楹撕瘮?shù)給出

的是映射后的內(nèi)積結(jié)果，所選取的映射過程可能是不同的。

核函繳定定理：設(shè)K：XxXtR是對(duì)稱函數(shù)，則K(x,z)為正定核函數(shù)的充要條件是對(duì)隨意引€X,i=

1,2,…,m,K(x,z)對(duì)應(yīng)的Gram矩陣:K=[K6?內(nèi))mxm]是半正定的。

對(duì)于一個(gè)詳細(xì)函數(shù)K(x,z)來說，檢驗(yàn)它是否為正定核函數(shù)并不簡(jiǎn)潔，因?yàn)橐?duì)隨意有限輸入集驗(yàn)證K對(duì)應(yīng)

的Gram矩陣是否為半正定。在實(shí)際問題中往往應(yīng)用已有的核函數(shù)。

常用核函數(shù)：

(1)多項(xiàng)式核函數(shù)：K(x,z)=(x?z+1尸,對(duì)應(yīng)的支撐向量機(jī)是一個(gè)p次多項(xiàng)式分類器；

(2)高斯核函數(shù)：K(x,z)=exp(-甯)，對(duì)應(yīng)的支撐向量機(jī)是高斯徑向基函數(shù)分類器；

(3)字符串核函數(shù)：

1)基本定義：

有限字符表￡；

字符串s:s(l)s(2)...s(|s|)z字符串s的長(zhǎng)度|s|,空字符串長(zhǎng)度為0;

字符串連接：St,5和L分別是字符串；

長(zhǎng)度為n的字符串集合￡n；

全部字符串的集合：￡*=11二()即；

S的子串u:給定一個(gè)指標(biāo)序列i=1wii<i2<…<i|U|4⑸,u=s(i)=s(i1)s(i2)...s(i|U|),其

長(zhǎng)度記作I⑴=i|u|-h+1,假如i是連續(xù)的,則1。)=|u|；否則l(i)>|嘰

2)映射定義:

假設(shè)S是長(zhǎng)度大于或等于n字符串的集合,s是S的元素,建立字符串集合S到特征空間Hn=R曖的映射

6式S),RE”表示定義祗n卜的實(shí)數(shù)空間，其每一維對(duì)應(yīng)一個(gè)字符串ueXn,映射將字符串s對(duì)應(yīng)于空

間中R*的一個(gè)向量,其在u維上的取值為

[071(s)]〃=Si：S(i)=U^(0Z

這里,0<A<1是一個(gè)衰減參數(shù),1(。表示字符串i的長(zhǎng)度,求和在S中全部與u相同的子串上迸行。

說明：u代表維,如在字符串u維,明顯空間有腰維,每一維是字母表工上的一個(gè)長(zhǎng)度為n的字符串;

s(i)是表示通過指標(biāo)序列i,表示的一個(gè)s的子串，這個(gè)子串可以不連續(xù)；s(i)=u表示s的子串s(i)等于u;

l(i)是子串s(i)在s中的指標(biāo)序列i的最終一個(gè)重量減去第一個(gè)重量然后加一；

例子：假設(shè)Z為英文字符集，n為3,S為長(zhǎng)度大于或等于3的字符串集合，考慮將字符集S映射到特征空間

H3=產(chǎn)3,%的一維對(duì)應(yīng)于字符串a(chǎn)sd,這是，字符串"Nasdaq"在這一維上的值是[內(nèi)(Nasdaq)Kd=

5

只有T子串a(chǎn)sd,序號(hào)是234;字符串"lassdas"在這一維上的值是[加(lassdas)]asd=2A,因?yàn)橛袃?/p>

個(gè)asd,序號(hào)分別為236,246;

3)核函數(shù)

兩個(gè)字符創(chuàng)s和t的字符串核函數(shù)是基于映射的特征空間中的內(nèi)積：

kn(S,t)=如(S)]“血(￡)]〃=WW貂⑴

uernuern(ij)：s(i)=t(j)=u

它給出了字符串s和t中長(zhǎng)度等于n的全部子串組成的特征向量的余弦相像度.直觀上，兩個(gè)字符串相同的

子串越多，它們就越相像，字符串核函數(shù)的值就越大，字符串核函數(shù)可以由動(dòng)態(tài)規(guī)劃快速計(jì)算。

序列最小最優(yōu)化算法

支撐向量機(jī)的學(xué)習(xí)問題可以形式化為求解凸二次規(guī)劃問題，具有全局最優(yōu)解，并且有許多最優(yōu)化算法可以用

于求解這一問題。但是當(dāng)訓(xùn)練樣本容量很大時(shí),這些算法往往變得特別低效。序列最小最優(yōu)化算法，由Platt

在1998年提出，它是一種啟發(fā)式算法，相對(duì)上匕較高效。

SMO算法基本思路是：假如全部變量的解都滿意次最優(yōu)化問題的KKT條件，那么這個(gè)最優(yōu)化問題的解就得

到了，因?yàn)镵KT條件是該最優(yōu)化問題的充分必要條件,否則，選擇兩個(gè)變量，固定其他變量，針對(duì)這個(gè)兩個(gè)

變量構(gòu)建一個(gè)二次規(guī)劃問題，這個(gè)二次規(guī)劃問題關(guān)于這兩個(gè)變量的解應(yīng)當(dāng)更接近原始二次規(guī)劃問題的解，因

為這會(huì)使得原始二次規(guī)劃問題的目標(biāo)函數(shù)值變得更小。重要的是，這時(shí)子問題可以通過解析方法求解，子問

題有兩個(gè)變量，一個(gè)是違反KKT條件最嚴(yán)峻的那一個(gè)，另一個(gè)莊約束條件自動(dòng)確定-如此，算法將原問題不

斷分解為子問題并對(duì)子問題求解，進(jìn)而達(dá)到求解原問題的目的。

原始優(yōu)化問題：

N

min-||w||2+eV4

w,b，EZ乙」

i=l

s.tyj(w-X,+b)>1-,i=1,2,...,N

>0,i=1,2,N

對(duì)偶問題：

〔NNN

嗎“萬(wàn)2W四%力丫加收”牛)一￡四

i=lj=li=l

N

S.t.乏aiVi=0

i=l

0<Qj<C,i=1,2,...,N

子問題的兩個(gè)變量只有一個(gè)是自由變量，假設(shè)％,。2為兩個(gè)變量，固定。3，?4，…，?N，那么依據(jù)上面的等

式約束可知：

N

?1Y1=-2

i=3

由于yi*Yi=1/所以

N

=-YiW四%

i=2

假如確定，那么由也隨之確定，所以子問題中同時(shí)更新兩個(gè)變量。

優(yōu)化子問題：

SMO算法包含兩個(gè)部分：求解兩個(gè)兩個(gè)變量二次規(guī)劃的解析方法和選擇變量的啟發(fā)式方法。不失一般性，假

設(shè)選擇的兩個(gè)變量是,。2，其他變量。3，，…，ON固定，于是SMO的優(yōu)化問題的子問題可以寫成：

]]NN

minW(%,a?)=5Kna?+-K22a^+yiy2K12a1a2-+a2)+丫必'+y2c2[力四長(zhǎng)2

，a2i=3i=3

N

s.t.a1y1+a2y2=-^aiyi=<;

i=3

0<aj<C,i=1,2

其中,舊=K(Xj,Xj),ij=1,2，…,N,s是常數(shù)，目標(biāo)函數(shù)中省略了不含四,。2的常數(shù)項(xiàng)。

(1)求解兩變量二次規(guī)劃的解析方法：

■可行解范圍：

假設(shè)子問題的初始可行解為哨M,嗎”，最優(yōu)解為吧ew,anew,明顯最優(yōu)解受等式約束(直線約束)和

不等式約束(盒子約束)條件的限制：

0<嗎<C------------------------(a)

ew,dew

0<a?=y.一嗎ewy2yl=%(a；】dyi+a°y2)-agy2yi<C

化簡(jiǎn)為

ew,dew

0<a；ew=y遙_ajy2y1=a?+ag^yzYi—ctjy2y1<C

>假如y2=yi?那么

,d

0<a?+叫Id-anew<c

a?,d+嗎E-C<嗎ew<a?Id+娉d-----------------------(b)

由(a),(b)得出：

假如y?=Yir那么L=max(0,a?,d+a?ld-C)<a^ew<min(a;,d+a^d,C)=H................(C)

>假如丫2工yi<那么

,d

0<a?-嗎d+嗎ew<C

嗎Id_aold<anew<C_aold+aold.................(d)

由(a),(d)得出：

假如丫2#yi,那么L=max(O,a?ld-a?ld)<ajew<min(C-a?,d+砂,C)=H------------(e)

假如最優(yōu)解不在約束內(nèi)，必需被剪輯。假設(shè)在沿著約束方向a1yi+a2y2=q未經(jīng)剪輯時(shí)。2的最優(yōu)解為

a：w，unc；然后再求剪輯后的解嗎ew.

■下面忽視不等式約束，求取迭代解《""，UnC：

K22?2+y】y2K12%。2-（％+?2）+yi?i（金％四收1）

由于由yi=q-a2y2，得出

?iyiYi=（s-a2y2）y1

=（9-a2y2）y1

帶入目標(biāo)函數(shù)

W(a)=TK(^-ay)2+-Kai+yK(^-ay)a2~(＜；-?2y2)yi-?2+(，-a2y2)(2力5%1

2乙11乙222221222

\t=3

+y2a2(￡力四%2)

對(duì)。2求導(dǎo)

9W件鄧J+y2。力。得2)

旃=-y2Kli(S-a2y2)+K22a2+y2Kl2s-2Kl2a2+Y1Y2_1_Yz

=一丫2%遇+a2Kli+K22c2+y2Kl2S-2Kl2a2+YiYz-1一丫2(金力印打)+Vzgyi?jKJ

i2

i=3

N

力哂，+y2力印，

=一丫2&1，+?2(K11+K22-2K12)+y2Kl2s+YiYz-1-Yz

a

=2(Kn+K22-2K12)-y2y2-y1+KU(；-K12＜；+

令其為0,得到

《ew,unc(K[]+_2Kl?)=y2y2.Yi+Ku,—K2S+

將,=a?,dy!+吟dy?帶入，得到

a廣u.K+K22-2K12)

ld

?§y2+(g

ld,d工力。得2

=y2y2-yi+Ku。泮%+Kua§y2-K12a?yi-K12yj?iKii

i=3i=3

,dld

^YiOiKii-yia?Kn-y2a?K21

，d：d

y2y2-yi+K^a泮yi+Kua5y2-K12瞰yi-K12a?y2+

ld,d

-([Jyi?iKi2-yia?K12-y2a5K22

,d,d,dldld|

=y2y2-yi+Kna?yi+Kna5y2-占2?！毖?一K12a5y2-yia?Kn-y2a2＜2i

NN

lc,d工力四％1-2%四s2

+y1a?K12+y2a5K22+

=1i=l

/NN

,d

Y2-yi+(Kn+K22-2K12)a?y2+('力四K1一'為四K2

(\i=li=l

NN

=(Ku+-2K12)+y21y2-y1+

K22吟日〉YiOtiKi!-y為四與2

N

,d2%四51一丫1

=(K11+K22-2K12)a?+y2yi?iKi2-y2

i=l

令Ei=鄧1*6。+b-力，i=1,2；其中鄧舊印舊+b是對(duì)輸入Xj的預(yù)料，因此Ej表示對(duì)輸入Xj的預(yù)料

與真實(shí)輸出力之差；那么

,d

=(Li+K22