SVM分類器中的最優(yōu)化問題

1、SVM分類器中的最優(yōu)化問題 電子工程學(xué)院 周嬌 201622021121摘要支持向量機(jī)（Support Vector Machines,SVM）是一種分類方法，它通過學(xué)會(huì)一個(gè)分類函數(shù)或者分類模型，該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項(xiàng)映射到給定類別中的某一個(gè)，從而可以用于預(yù)測(cè)未知類別數(shù)據(jù)的類別。所謂支持向量機(jī)，顧名思義，分為兩個(gè)部分了解：一，什么是支持向量（簡單來說，就是支持或支撐平面上把兩類類別劃分開來的超平面的向量點(diǎn)）；二，這里的“機(jī)（machine，機(jī)器）”便是一個(gè)算法。支持向量機(jī)是基于統(tǒng)計(jì)學(xué)習(xí)理論的一種機(jī)器學(xué)習(xí)方法，通過尋求結(jié)構(gòu)化風(fēng)險(xiǎn)最小來提高學(xué)習(xí)機(jī)泛化能力，實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍的最小化，從而達(dá)

2、到在統(tǒng)計(jì)樣本量較少的情況下，亦能獲得良好統(tǒng)計(jì)規(guī)律的目的。在本文中，主要介紹了如何通過求解最優(yōu)化問題來得到SVM分類器的最佳參數(shù)，使得SVM分類器的性能最好。一、 線性分類如圖（1），在二維平面上有兩種不同的數(shù)據(jù)點(diǎn)，分別用紅色和藍(lán)色來表示，紅顏色的線就把這兩種不同顏色的數(shù)據(jù)點(diǎn)分開來了。這些數(shù)據(jù)點(diǎn)在多維空間中就是向量，紅顏色的線就是一個(gè)超平面。 圖（1） 圖（2）假設(shè) 是 維空間中的一個(gè)數(shù)據(jù)點(diǎn)，其中是這個(gè)數(shù)據(jù)點(diǎn)的個(gè)特征，令 , 1, z0-1, z<0 (1.1)在圖（1）中，處在紅線左邊的數(shù)據(jù)點(diǎn)，其y值為-1，反之，處在紅線右邊的數(shù)據(jù)點(diǎn)其y值為1。這樣，根據(jù)y的值就把這個(gè)數(shù)據(jù)點(diǎn)分類了。那么

3、分類的重點(diǎn)就在如何構(gòu)造這個(gè)函數(shù)。 設(shè)圖（1）中的超平面（即紅線）其表達(dá)式為 ，則= (1.2)直觀上表示數(shù)據(jù)點(diǎn)到超平面的幾何間隔，去掉分子的絕對(duì)值就有了正負(fù)性，是法向量，是截距。表示了數(shù)據(jù)點(diǎn)到超平面的函數(shù)間隔，如圖（2）所示。由于是這個(gè)數(shù)據(jù)點(diǎn)的個(gè)特征，就是對(duì)特征進(jìn)行線性組合，即給每一個(gè)特征加上一個(gè)權(quán)重。 因?yàn)?1, z0-1, z<0 ，=，=1或-1分別表示兩個(gè)類別，而的正負(fù)決定它該分到哪個(gè)類別，所以我們以和 符號(hào)是否一致來判斷分類是否正確。令 i=yi() (1.3)則>0表示分類正確，否則分類錯(cuò)誤。 那么我們需要求解出和這兩個(gè)參數(shù)。二、 最大間隔分類器對(duì)一個(gè)數(shù)據(jù)點(diǎn)進(jìn)行分析，當(dāng)

4、它到超平面的幾何間隔越大的時(shí)候，分類正確的把握率越大。對(duì)于一個(gè)包含n 個(gè)點(diǎn)的數(shù)據(jù)集x(x1,x2,xn)，我們可以很自然地定義它的間隔為所有這n 個(gè)點(diǎn)的間隔中最小的那個(gè)。于是，為了使得分類的把握盡量大，我們希望所選擇的超平面能夠最大化這n個(gè)間隔值。令 =mini ,i=1,2,n (2.1) 所以最大間隔分類器的目標(biāo)函數(shù)為 max (2.2) 條件為 i=yi ，i=1,2,n (2.3)即 yi ，i=1,2,n (2.4) 其中=，即= ，由于和的值可以縮放，令=1，則最優(yōu)化問題轉(zhuǎn)為： max 1 (2.5) s.t. yi1 ，i=1,2,n (2.6)通過求解這個(gè)最優(yōu)化問題，我們可以得

5、到一個(gè)最大間隔分類器，如圖（2）所示，中間的紅線為最優(yōu)超平面，另外兩條虛線到紅線的距離都等于1，即=1。三、 從原始問題到對(duì)偶問題及求解。原規(guī)劃即：max 1 (3.1) s.t. yi1 ，i=1,2,n (3.2)由于求1的最大值相當(dāng)于求122的最小值，所以上述問題等價(jià)于： min 122 (3.3) s.t.yi-10 ，i=1,2,n (3.4)容易證明這是個(gè)凸優(yōu)化問題。構(gòu)造Lagrange函數(shù)將其變?yōu)闊o約束的最優(yōu)化問題，給每一個(gè)約束條件加上一個(gè)Lagrange乘子=(1,2,n)T(其中i0,i=1,2,n)： (3.5)令 maxi0 (3.6)容易驗(yàn)證，當(dāng)某個(gè)約束條件不滿足時(shí)，例

6、如，那么顯然有+（此時(shí)i= +）。而當(dāng)所有約束條件都滿足時(shí)，則有（此時(shí)i=0），亦即我們最初要最小化的量。因此，在要求約束條件得到滿足的情況下最小化，實(shí)際上等價(jià)于直接最小化（因?yàn)槿绻s束條件沒有得到滿足，會(huì)等于無窮大，自然不會(huì)是我們所要求的最小值。）具體寫出來，我們現(xiàn)在的目標(biāo)函數(shù)變成了： min,b=min,bmaxi0=p* (3.7)這里用p*表示這個(gè)問題的最優(yōu)值，也是原問題的最優(yōu)值?，F(xiàn)在我們把最小和最大的位置交換一下： maxi0min,b=q* (3.8)式（3.8）是（3.7）的對(duì)偶問題，p*是的上確界（即最小上界），q*是的下確界（最大下界），顯然p*q*，當(dāng)且僅當(dāng)原問題滿足Sla

7、ter條件（即存在xi使得原規(guī)劃的約束條件嚴(yán)格成立，即yi-1=0）時(shí)，等號(hào)成立。上文已說明此優(yōu)化為凸優(yōu)化，所以Kuhn-Tucker條件為某個(gè)數(shù)據(jù)點(diǎn)x*是最優(yōu)解的充要條件。所以當(dāng)xi滿足KKT條件時(shí)，xi才是min,b的最優(yōu)解。當(dāng)同時(shí)滿足Slater條件和KKT條件時(shí)，原規(guī)劃可以取到最優(yōu)值且為p*（p*=q*）。求解過程：要求解這個(gè)對(duì)偶問題，先求出關(guān)于，b的最小值，再對(duì)求最大。1、 先把當(dāng)做常數(shù)，求出關(guān)于，b的偏導(dǎo)（即求min,b）關(guān)于，b求最小值，也是極值 L=- i=1niyixi=0 (3.9) Lb=-i=1niyi=0 (3.10) =i=1niyixi (3.11) i=1niy

8、i=0 (3.12)將式（3.11）和（3.12）代入到式（3.5）中 =12T-Ti=1niyixi-bi=1niyi+i=1ni =12Ti=1niyixi-Ti=1niyixi+i=1ni =i=1ni-12(i=1niyixi)Ti=1niyixi =i=1ni-12i=1nj=1niyijyjxiTxi (3.13)2、 從式（3.13）可以看出只包含=(1,2,n)T這一個(gè)變量（用來訓(xùn)練SVM分類器的數(shù)據(jù)集x(x1,x2,xn)和每個(gè)數(shù)據(jù)點(diǎn)的類別yi是已知的）。對(duì)式（3.13）求關(guān)于的最大值，根據(jù)式（3.12）得到最優(yōu)化問題: max i=1ni-12i=1nj=1niyijyjx

9、iTxi s.t. i=1niyi=0 i0,i=1,2,n運(yùn)用SMO算法（序列最小最優(yōu)化算法）求以上最優(yōu)化問題，此算法太繁瑣，可以查找SMO算法的資料來了解，此處不贅述。3、 求出=(1,2,n)T之后，根據(jù)式（3.11）求出；b是截距,如圖（3）所示，紅線是分割超平面，另外兩條虛線到紅線的距離相等，為兩種數(shù)據(jù)點(diǎn)到分割平面的最小距離，則：b=-12b1+b2=-12(mini:yi=1+maxi:yi=-1) （3.14） 圖（3） 圖（4） 至此，這個(gè)分類器的參數(shù)都已經(jīng)解出來了。四、 使用松弛變量處理離群點(diǎn)數(shù)據(jù)本身是線性結(jié)構(gòu)，但是由于噪聲的影響，導(dǎo)致一些數(shù)據(jù)點(diǎn)偏離正常位置很遠(yuǎn)，這樣的數(shù)據(jù)點(diǎn)

10、就叫做離群點(diǎn)。圖（4）就是數(shù)據(jù)中有離群點(diǎn)存在的情況。 在圖（4）中，因?yàn)殡x群點(diǎn)（用黑圈圈起來的藍(lán)色的數(shù)據(jù)點(diǎn)）的存在，導(dǎo)致分類的超平面發(fā)生了偏離。分類的超平面本應(yīng)該是中間的那根紅線，但是由于離群點(diǎn)的存在，發(fā)生了偏差，變成了中間那條黑色的虛線。這樣一來，當(dāng)我們用這個(gè)學(xué)習(xí)好的SVM分類器對(duì)新的數(shù)據(jù)點(diǎn)進(jìn)行分類的時(shí)候就有可能發(fā)生誤判。為了解決這個(gè)問題，我們將離群點(diǎn)移回本來的位置，這就通過在約束條件中添加松弛變量ci(i=1,2,n)來實(shí)現(xiàn)，ci就對(duì)應(yīng)于數(shù)據(jù)點(diǎn)允許偏離的距離。原來的約束條件式（2.6）就變成 yi-ci1 ，i=1,2,n （4.1）但是ci的取值也必須受到約束，即i=1nci要盡可能小。

11、那么目標(biāo)函數(shù)就由（3.3）變?yōu)椋?min 122+i=1nci （4.4）是一個(gè)參數(shù)，用來控制目標(biāo)函數(shù)中兩項(xiàng)（即尋求間隔最大的分割超平面和保證數(shù)據(jù)點(diǎn)偏差量最?。┑臋?quán)重。那么這個(gè)最優(yōu)化問題變?yōu)椋?min 122+i=1nci s.t.yi-ci1 ，i=1,2,n ci0 , i=1,2,n其求解方法與第三節(jié)中的方法一致。五、 存在的問題這樣構(gòu)建的分類器對(duì)于線性可分的情況很有效，但是對(duì)于線性不可分的情況，例如圖（6）中的情況，其效果就不那么好了。需要去構(gòu)造一些新的最優(yōu)化問題來對(duì)非線性可分的數(shù)據(jù)進(jìn)行分類。 圖（6）參考文獻(xiàn)1、支持向量機(jī)導(dǎo)論，美 Nello Cristianini / John Shawe-Taylor 著；2、Statistical behavior and consistency of classification methods based on convex risk minimization張潼3、Stat