SVM分類器中的最優(yōu)化問題[分享借鑒]

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

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

3、點就在如何構(gòu)造這個函數(shù)。 設(shè)圖（1）中的超平面（即紅線）其表達式為 ，則= (1.2)直觀上表示數(shù)據(jù)點到超平面的幾何間隔，去掉分子的絕對值就有了正負性，是法向量，是截距。表示了數(shù)據(jù)點到超平面的函數(shù)間隔，如圖（2）所示。由于是這個數(shù)據(jù)點的個特征，就是對特征進行線性組合，即給每一個特征加上一個權(quán)重。 因為 1, z0-1, z0表示分類正確，否則分類錯誤。 那么我們需要求解出和這兩個參數(shù)。二、 最大間隔分類器對一個數(shù)據(jù)點進行分析，當它到超平面的幾何間隔越大的時候，分類正確的把握率越大。對于一個包含n 個點的數(shù)據(jù)集x(x1,x2,xn)，我們可以很自然地定義它的間隔為所有這n 個點的間隔中最小的那個

4、。于是，為了使得分類的把握盡量大，我們希望所選擇的超平面能夠最大化這n個間隔值。令 =mini ,i=1,2,n (2.1) 所以最大間隔分類器的目標函數(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)通過求解這個最優(yōu)化問題，我們可以得到一個最大間隔分類器，如圖（2）所示，中間的紅線為最優(yōu)超平面，另外兩條虛線到紅線的距離都等于1，即=1。三、 從原始問題到對偶問題及求解。原規(guī)劃即：max 1 (3.1

5、) s.t. yi1 ，i=1,2,n (3.2)由于求1的最大值相當于求122的最小值，所以上述問題等價于： min 122 (3.3) s.t.yi-10 ，i=1,2,n (3.4)容易證明這是個凸優(yōu)化問題。構(gòu)造Lagrange函數(shù)將其變?yōu)闊o約束的最優(yōu)化問題，給每一個約束條件加上一個Lagrange乘子=(1,2,n)T(其中i0,i=1,2,n)： (3.5)令 maxi0 (3.6)容易驗證，當某個約束條件不滿足時，例如，那么顯然有+（此時i= +）。而當所有約束條件都滿足時，則有（此時i=0），亦即我們最初要最小化的量。因此，在要求約束條件得到滿足的情況下最小化，實際上等價于直接最

6、小化（因為如果約束條件沒有得到滿足，會等于無窮大，自然不會是我們所要求的最小值。）具體寫出來，我們現(xiàn)在的目標函數(shù)變成了： min,b=min,bmaxi0=p* (3.7)這里用p*表示這個問題的最優(yōu)值，也是原問題的最優(yōu)值?，F(xiàn)在我們把最小和最大的位置交換一下： maxi0min,b=q* (3.8)式（3.8）是（3.7）的對偶問題，p*是的上確界（即最小上界），q*是的下確界（最大下界），顯然p*q*，當且僅當原問題滿足Slater條件（即存在xi使得原規(guī)劃的約束條件嚴格成立，即yi-1=0）時，等號成立。上文已說明此優(yōu)化為凸優(yōu)化，所以Kuhn-Tucker條件為某個數(shù)據(jù)點x*是最優(yōu)解的充要

7、條件。所以當xi滿足KKT條件時，xi才是min,b的最優(yōu)解。當同時滿足Slater條件和KKT條件時，原規(guī)劃可以取到最優(yōu)值且為p*（p*=q*）。求解過程：要求解這個對偶問題，先求出關(guān)于，b的最小值，再對求最大。1、 先把當做常數(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=1niyi=0 (3.12)將式（3.11）和（3.12）代入到式（3.5）中 =12T-Ti=1niyixi-bi=1niyi+i=1ni =12Ti=1niyixi-Ti=

8、1niyixi+i=1ni =i=1ni-12(i=1niyixi)Ti=1niyixi =i=1ni-12i=1nj=1niyijyjxiTxi (3.13)2、 從式（3.13）可以看出只包含=(1,2,n)T這一個變量（用來訓練SVM分類器的數(shù)據(jù)集x(x1,x2,xn)和每個數(shù)據(jù)點的類別yi是已知的）。對式（3.13）求關(guān)于的最大值，根據(jù)式（3.12）得到最優(yōu)化問題: max i=1ni-12i=1nj=1niyijyjxiTxi s.t. i=1niyi=0 i0,i=1,2,n運用SMO算法（序列最小最優(yōu)化算法）求以上最優(yōu)化問題，此算法太繁瑣，可以查找SMO算法的資料來了解，此處不贅

9、述。3、 求出=(1,2,n)T之后，根據(jù)式（3.11）求出；b是截距,如圖（3）所示，紅線是分割超平面，另外兩條虛線到紅線的距離相等，為兩種數(shù)據(jù)點到分割平面的最小距離，則：b=-12b1+b2=-12(mini:yi=1+maxi:yi=-1) （3.14） 圖（3） 圖（4） 至此，這個分類器的參數(shù)都已經(jīng)解出來了。四、 使用松弛變量處理離群點數(shù)據(jù)本身是線性結(jié)構(gòu)，但是由于噪聲的影響，導(dǎo)致一些數(shù)據(jù)點偏離正常位置很遠，這樣的數(shù)據(jù)點就叫做離群點。圖（4）就是數(shù)據(jù)中有離群點存在的情況。 在圖（4）中，因為離群點（用黑圈圈起來的藍色的數(shù)據(jù)點）的存在，導(dǎo)致分類的超平面發(fā)生了偏離。分類的超平面本應(yīng)該是中間

10、的那根紅線，但是由于離群點的存在，發(fā)生了偏差，變成了中間那條黑色的虛線。這樣一來，當我們用這個學習好的SVM分類器對新的數(shù)據(jù)點進行分類的時候就有可能發(fā)生誤判。為了解決這個問題，我們將離群點移回本來的位置，這就通過在約束條件中添加松弛變量ci(i=1,2,n)來實現(xiàn)，ci就對應(yīng)于數(shù)據(jù)點允許偏離的距離。原來的約束條件式（2.6）就變成 yi-ci1 ，i=1,2,n （4.1）但是ci的取值也必須受到約束，即i=1nci要盡可能小。那么目標函數(shù)就由（3.3）變?yōu)椋?min 122+i=1nci （4.4）是一個參數(shù)，用來控制目標函數(shù)中兩項（即尋求間隔最大的分割超平面和保證數(shù)據(jù)點偏差量最?。┑臋?quán)重。

11、那么這個最優(yōu)化問題變?yōu)椋?min 122+i=1nci s.t.yi-ci1 ，i=1,2,n ci0 , i=1,2,n其求解方法與第三節(jié)中的方法一致。五、 存在的問題這樣構(gòu)建的分類器對于線性可分的情況很有效，但是對于線性不可分的情況，例如圖（6）中的情況，其效果就不那么好了。需要去構(gòu)造一些新的最優(yōu)化問題來對非線性可分的數(shù)據(jù)進行分類。 圖（6）參考文獻1、支持向量機導(dǎo)論，美 Nello Cristianini / John Shawe-Taylor 著；2、Statistical behavior and consistency of classification methods based on convex risk minimization張潼3、Statistical analysis of some multi-category large margin classificati