支持向量機(jī)的求解過(guò)程

一、支持向量機(jī)的求解過(guò)程

個(gè)人理解：下文所有下標(biāo)i、j均可相互替換，c和C表示同一常數(shù)。

支持向量機(jī)的對(duì)偶問(wèn)題為： 最大化：θ(α,β)=∑αi-1/2∑∑yiyjαiαjφ(Xi)Tφ(Xj)；

限制條件：（1）0≤αi≤C，i=1~N；（2）∑αiyi=0，i=1~N。

因?yàn)棣?Xi)Tφ(Xj)=K(Xi,Xj)（K(Xi,Xj)為核函數(shù)，詳見(jiàn)），所以只需知道核函數(shù)K(Xi,Xj)即可求解該對(duì)偶問(wèn)題。該對(duì)偶問(wèn)題解的結(jié)構(gòu)為一組αi的值（個(gè)人理解：αi的值同時(shí)也為αj的值），其中i=1~N。

解得αi的值后可根據(jù)ω=∑αiyiφ(Xi)求解ω的值（支持向量機(jī)問(wèn)題需解得超平面ωTφ(X)+b=0中的ω和b的值），但因?yàn)棣?Xi)不一定具有顯式表達(dá)式，所以ω不一定具有顯式表達(dá)式。

雖然ω不一定具有顯式表達(dá)式，但ωTφ(X)+b的形式可以通過(guò)核函數(shù)K(X1,X2)求得，下文介紹具體求解過(guò)程：

因?yàn)棣?∑αjyjφ(Xj)，所以ωTφ(Xj)=∑αjyjφ(Xj)Tφ(Xi)=∑αjyjK(Xj,Xi)。

根據(jù)KKT條件（KKT條件見(jiàn)機(jī)器學(xué)習(xí)相關(guān)介紹（12）——支持向量機(jī)（原問(wèn)題和對(duì)偶問(wèn)題）），且持向量機(jī)的對(duì)偶問(wèn)題的另一個(gè)形式為： 最大化：θ(α,β)=inf{1/2||ω||2-C∑βiδi+∑αi[1+δi-yiωTφ(Xi)-yib]}； 限制條件：（1）αi≥0，i=1~N；（2）βi≥0，i=1~N。

可得：對(duì)所有的i=1~N，βiδi=0且αi[1+δi-yiωTφ(Xi)-yib]=0。

根據(jù)βiδi=0可得(c-αi)δi=0（個(gè)人理解：此步驟也需根據(jù)機(jī)器學(xué)習(xí)相關(guān)介紹（13）——支持向量機(jī)（轉(zhuǎn)化為對(duì)偶問(wèn)題）中求偏導(dǎo)得出的等式αi+βi=C）

若對(duì)某個(gè)i，αi≠0且αi≠c，則根據(jù)KKT條件，則有δi=0且1+δi-yiωTφ(Xi)-yib=0。

又因?yàn)閥iωTφ(Xi)=∑αiyjyiK(Xj,Xi)，所以只需使用一個(gè)滿足0＜αi＜c的αi值，即可通過(guò)下式求得b： b=(1-∑αjyjyiK(Xj,Xi))/yi

綜上，ωTφ(X)+b=∑αiyiK(Xi,X)+b，即在不知道φ(X)，只知道K(X1,X2)的情況下，ωTφ(X)+b的表達(dá)式也可被求出。該結(jié)論被稱為“核函數(shù)戲法”（KERNEL TRICK）。

最終，支持向量機(jī)的判別標(biāo)準(zhǔn)為： 若∑αiyiK(Xi,X)+b≥0，則X∈C1； 若∑αiyiK(Xi,X)+b＜0，則X∈C2。

二、支持向量機(jī)的算法流程

（1）訓(xùn)練過(guò)程

輸入訓(xùn)練數(shù)據(jù){(Xi,yi)}，i=1~N，其中，yi=±1。并求解： 最大化：θ(α,β)=∑αi-1/2∑∑yiyjαiαjφ(Xi)Tφ(Xj)；

限制條件：

（1）0≤αi≤C，i=1~N；（2）∑αiyi=0，i=1~N。

得出一組αi的值，再通過(guò)一個(gè)滿足0＜αi＜c的αi值，根據(jù)下式求b： b=(1-∑αjyjyiK(Xj,Xi))/yi

求解出αi和b后，支持向量機(jī)的訓(xùn)練過(guò)程完成。

（2）測(cè)試過(guò)程

考察測(cè)試數(shù)據(jù)X，預(yù)測(cè)其類別y： 若∑αiyiK(Xi,X)+b≥0，則y=+1（X∈C1）； 若∑αiyiK(Xi,X)+b＜0，則y=-1（X∈C2）。

審核編輯：劉清