杜世平 智巖

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

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

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

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

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

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

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

2 二次規(guī)劃

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

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

3 線性不可分及其求解

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

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

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

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

4 從低維到高維的映射

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

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

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

5 舉例 - 兵王問題

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

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

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

接下來就是一個神奇的事：我們在不輸入計算機規(guī)則的前提下，利用SVM，我們可以讓計算機學會判斷兵王問題是白方勝還是和棋。這是一個二分類問題。

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

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

[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.

廣州工商學院 廣東省佛山市 528138