支持向量機(jī)中的優(yōu)化關(guān)系推導(dǎo)

杜世平 智巖

[摘要]支持向量機(jī)（SVM）是通過尋找最優(yōu)分離超平面實(shí)現(xiàn)分類的目標(biāo)。但是這個(gè)過程涉及負(fù)責(zé)的邏輯過程。本文通過詳細(xì)解釋SVM的相關(guān)邏輯關(guān)系，展示了SVM中解決優(yōu)化問題的一般性數(shù)值關(guān)系推導(dǎo)。

[關(guān)鍵字]支持向量機(jī);分離超平面;優(yōu)化問題;最大化間隔

Vapnik[1]提出SVM算法[2，3，4]用于解決兩類問題，第一類是線性可分的問題第二類是線性不可分問題。本文討論svm能夠解決的線性可分問題為例，介紹SVM。

注意到，使用margin最大的條件來求解支持向量引出的問題就是這樣的直線并不唯一。理論分析表明，支持向量機(jī)尋找的最優(yōu)的分類直線應(yīng)該滿足：（1）該直線分開了兩類;（2）該直線最大化了間隔（margin）;（3）該直線處于間隔的中間，到所有支持向量的距離相等。即支持向量就是分離超平面最近的那些點(diǎn)（“最近的意思是，點(diǎn)和直線可以剛好相交”）。支持向量機(jī)就是尋找空間中的一條能夠?qū)㈩悇e不同的對(duì)象以最大間隔分割開來的直線，這條直線與兩側(cè)的支持向量直線的距離相等。

上述關(guān)于是基于二維特征空間的結(jié)果，而在高維空間中，直線將變成超平面。理論表明，上述結(jié)論卻是一致的?，F(xiàn)在，我們開始尋找最優(yōu)的分類超平面的過程。為了說明這個(gè)問題，我們首先看“線性可分”的定義：

假定訓(xùn)練樣本是線性可分的，SVM需要尋找的是最大化間隔的超平面，則這個(gè)優(yōu)化問題可寫成如下形式：

之所以有以上關(guān)系，是因?yàn)?，我們可以假定w是一個(gè)m維的向量具體的，設(shè)，則，||w||2=w12+w22+ ... wm2。這就是說，SVM的優(yōu)化問題就是最小化w模的平方，且有N個(gè)限制條件。為了推出這個(gè)優(yōu)化問題，我們注意到如下兩個(gè)事實(shí)：

2 二次規(guī)劃

定義：二次規(guī)劃[5，6]的定義包括兩個(gè)條件：（1）目標(biāo)函數(shù)是二次項(xiàng);（2）限制條件是一次項(xiàng)。

在最優(yōu)化理論中，如果一個(gè)問題是凸優(yōu)化問題，我們就可以把它當(dāng)成一個(gè)已經(jīng)解決的問題。因?yàn)橥箖?yōu)化問題只有唯一一個(gè)全局的極值。我們可以用梯度下降法來求得它的解。

3 線性不可分及其求解

如果訓(xùn)練樣本線性不可分，那么以上優(yōu)化問題的解釋什么？顯然是無解。即不存在（w，b）使得它滿足上述N各限制條件。對(duì)于線性不可分的情形，我們需要適當(dāng)放松限制條件，使得上面的優(yōu)化問題變的有解。放松限制條件的思路是，對(duì)于每個(gè)訓(xùn)練樣本xi與其標(biāo)簽yi，我們需要設(shè)置一個(gè)松弛變量δi。于是，我們可將上面的N個(gè)不等式的限制條件放松為如下的限制條件：yi（wTxi + b）≥1-δi ，（i=1 ， ... ， N）。

那就是說，在線性不可分的情況下，我們不可能讓所有的yi乘以wTxi + b大于等于1。于是，注意到，我們引入δi，作用到不等式的右邊，可以看到，只要每個(gè)δi足夠的大，那么，上面的N個(gè)不等式的限制條件都是可以成立的。當(dāng)然，我們應(yīng)該增加新的限制條件以阻止δi無限變大，讓它限定在一個(gè)合理的范圍內(nèi)。最終，我們可以獲得改造后的SVM的優(yōu)化版本：

兩個(gè)限制條件分析如下：第一個(gè)條件保證每個(gè)δi是大于等于0的。限制條件（2）將以前的難以達(dá)到的不等式變的容易達(dá)到。再看目標(biāo)函數(shù)，以前的目標(biāo)函數(shù)只需要最小化模的方的一半，而現(xiàn)在的目標(biāo)函數(shù)增加了一項(xiàng)，即所有的δi的總和，這就不但要求w的模越小越好，還要求每個(gè)δi的和越小越好。

在這里強(qiáng)調(diào)的是，平衡兩項(xiàng)的比例因子C是認(rèn)為設(shè)定的，我們把一個(gè)算法中，人為設(shè)定參數(shù)叫做算法的超參數(shù)（hyperparameter）。一般來說，在實(shí)際應(yīng)用中，我們會(huì)不斷的變化C的值，同時(shí)對(duì)每個(gè)C，我們要測(cè)試算法的識(shí)別率。然后我們選取識(shí)別率達(dá)到最大的超參數(shù)C的值。顯然如果一個(gè)算法的超參數(shù)越多，意味著算法需要手動(dòng)調(diào)整優(yōu)化的地方越多，這樣算法的自動(dòng)性就會(huì)降低，SVM是超參數(shù)很少的算法模型。

4 從低維到高維的映射

這里我們要考察的是如何擴(kuò)大考察函數(shù)的范圍，從而提高處理非線性可分?jǐn)?shù)據(jù)集的能力。SVM在擴(kuò)大可選參數(shù)范圍方面可謂獨(dú)樹一幟。其它算法，如ANN，決策樹等采用的是直接產(chǎn)生更多可逆函數(shù)的方式。例如ANN中，通過多層非線性函數(shù)的組合能夠產(chǎn)生類似于橢圓的曲線，從而區(qū)分比如由圓圈（○）包圍的叉（×）。SVM不是直接產(chǎn)生這樣的函數(shù)，而是通過將特征空間由低維映射到高維，然后在高維特征空間當(dāng)中仍然用線性超平面對(duì)數(shù)據(jù)進(jìn)行分類。

這里有一個(gè)一般性的結(jié)論需要強(qiáng)調(diào)一下：假設(shè)在一個(gè)M維的空間上，隨機(jī)取N個(gè)訓(xùn)練樣本，隨機(jī)的對(duì)每個(gè)訓(xùn)練樣本賦予標(biāo)簽+1或者-1.并假設(shè)，這些訓(xùn)練樣本線性可分的概率為P（M），則當(dāng)M趨于無窮大時(shí)，P（M）=1。

關(guān)于這個(gè)結(jié)論，直觀上很容易理解，即當(dāng)我們?cè)黾犹卣骺臻g的維度M的時(shí)候，超平面待估計(jì)的參數(shù)（w，b）的維度也會(huì)增加。也就是說，整個(gè)算法模型的自由度會(huì)增加，當(dāng)然，就更有可能分開低維時(shí)候無法分開的數(shù)據(jù)集。上述結(jié)論告訴我們，將訓(xùn)練集樣本由低維映射到高維，能夠增加線性可分的概率。因此，我們?nèi)绾螛?gòu)造一個(gè)由低維到高維映射函數(shù)就成為關(guān)鍵性的問題。在從低維到高維的映射過程中，我們要注意核函數(shù)的使用規(guī)則：核函數(shù)K和映射函數(shù)是一一對(duì)應(yīng)的關(guān)系，知道其中一個(gè)，就可以知道另一個(gè)。

5 舉例 - 兵王問題

兵王問題是，如果在國際象棋中的殘局，黑方只剩下一個(gè)王，拜訪還剩下一個(gè)兵一個(gè)王，那么將有兩種可能：第一，白方將死黑方，白方獲勝。第二，和棋。

這兩種可能是三個(gè)棋子在棋盤的位置而確定的。為了讓大家對(duì)這個(gè)問題有更直觀的了解，需詳細(xì)的說一下與之關(guān)聯(lián)的國際象棋規(guī)則，其中有一條規(guī)則叫做“兵的升變”。也就是說，并走至對(duì)方的底線，可以升為除王外任意棋子。第二條規(guī)則就是“逼和”，也就是說，一方的王未被將軍，但是下一步它移動(dòng)到任意的地方都會(huì)被對(duì)方將死，則此時(shí)是和棋。

從這個(gè)規(guī)則中我們可以大致了解到，黑方要想防止自己被將死，有一個(gè)好消息，和一個(gè)壞消息。壞消息是，黑方必須防止兵走到底線，升變?yōu)橥?，這樣的強(qiáng)子。往后可以橫豎斜走若干步。若王后和王一起配合，一定可以將死對(duì)方的王。而好消息是，黑方可以利用逼和的規(guī)則，主動(dòng)造成無路可走的情形，從而導(dǎo)致和棋。

接下來就是一個(gè)神奇的事：我們?cè)诓惠斎胗?jì)算機(jī)規(guī)則的前提下，利用SVM，我們可以讓計(jì)算機(jī)學(xué)會(huì)判斷兵王問題是白方勝還是和棋。這是一個(gè)二分類問題。

首先，我們需要標(biāo)注好的訓(xùn)練數(shù)據(jù)集，在著名的UCI ML數(shù)據(jù)集上，我們可以下載到兵王問題的數(shù)據(jù)。在這里，我們用SVM來處理這個(gè)問題。首先我們將和棋標(biāo)簽標(biāo)為drw當(dāng)做一類。設(shè)定此時(shí)的yi=±1。將其它標(biāo)簽從1到x當(dāng)做另一類，設(shè)定此時(shí)相應(yīng)的標(biāo)簽yi=-1接下來我們用SVM的程序進(jìn)行訓(xùn)練，我們用LIBsvm工具包，就可以得到相應(yīng)的超平面方程。

[結(jié)束語] 本文詳細(xì)分析了支持向量機(jī)解決優(yōu)化問題過程中的數(shù)值關(guān)系，并給出了相關(guān)的數(shù)學(xué)推導(dǎo)，為初學(xué)者后續(xù)的相關(guān)課題學(xué)習(xí)研究給予指導(dǎo)。

[1] Guyon I ， Weston J ， Barnhill S ， et al. Gene Selection for Cancer Classification using Support Vector Machines[J]. Machine Learning， 2002， 46（1-3）：389-422.

[2] Bi J ， Vapnik V N . Learning with Rigorous Support Vector Machines[C]// Computational Learning Theory and Kernel Machines， 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop， COLT/Kernel 2003， Washington， DC， USA， August 24-27， 2003， Proceedings. DBLP， 2003.

[3] Tao Y ， Zhu X ， Huang D ， et al. Soft Sensor Modeling Based on the Soft Margin Support Vector Regression Machine[C]// IEEE International Conference on Control & Automation. IEEE， 2007.

[4] Chapelle O ， Vapnik V . Model Selection for Support Vector Machines. 2000.

[5]Fei S ， Lin Y ， Saul L K ， et al. Multiplicative Updates for Nonnegative Quadratic Programming[J]. Neural Computation， 2007， 19（8）：2004-2031.

[6]Kleinhans J M ， Sigl G . GORDIAN： VLSI placement by quadratic programming and slicing optimization[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2002， 10（3）：356-365.

廣州工商學(xué)院 廣東省佛山市 528138