2.2.5 支持向量機(jī)

支持向量機(jī)簡(jiǎn)稱(chēng)SVM，是統(tǒng)計(jì)學(xué)習(xí)理論中最新的內(nèi)容，也是最實(shí)用的部分。SVM是一種新的非常有發(fā)展前景的分類(lèi)技術(shù)，可以替代多層感知機(jī)，RBF神經(jīng)網(wǎng)絡(luò)和多項(xiàng)式神經(jīng)網(wǎng)絡(luò)等已有的學(xué)習(xí)算法。其核心內(nèi)容是在1992～1995年間提出的，目前仍處在不斷發(fā)展的階段。

SVM以結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則為理論基礎(chǔ)，通過(guò)適當(dāng)?shù)倪x擇函數(shù)子集以及該函數(shù)子集中的判別函數(shù)，使得學(xué)習(xí)機(jī)器的實(shí)際風(fēng)險(xiǎn)達(dá)到最小，保證了通過(guò)有限訓(xùn)練樣本得到的小誤差分類(lèi)器，對(duì)獨(dú)立測(cè)試集的測(cè)試誤差仍然較小。因而，SVM是一個(gè)具有最優(yōu)分類(lèi)能力和推廣能力的學(xué)習(xí)機(jī)器。

1.支持向量機(jī)理論

（1）線(xiàn)性可分的最優(yōu)分類(lèi)面

SVM是從線(xiàn)性可分情況下的最優(yōu)分類(lèi)面發(fā)展而來(lái)的，基本思想如圖2-11所示。圖中圓形和三角形代表兩類(lèi)樣本，H 為它們之間的分類(lèi)超平面，H1，H2分別為過(guò)各類(lèi)中離分類(lèi)面最近的樣本且平行于分類(lèi)面的超平面，它們之間的距離Δ稱(chēng)為分類(lèi)間隔（Margin）。

當(dāng)分類(lèi)面發(fā)生變化時(shí)，分類(lèi)間隔Δ也隨之發(fā)生變化。反之，給定分類(lèi)間隔Δ的值，也可以確定相應(yīng)的分類(lèi)超平面（也可能對(duì)應(yīng)著許多超平面，統(tǒng)稱(chēng)為超平面集合）。在Δ間隔下，超平面集合的VC維h應(yīng)滿(mǎn)足下面關(guān)系：

式中，f ( . )是單調(diào)增函數(shù)，即h與Δ2成反比關(guān)系。因此，當(dāng)訓(xùn)練樣本給定時(shí)，分類(lèi)間隔越大，則對(duì)應(yīng)的分類(lèi)超平面集合的VC維就越小。使分類(lèi)間隔最大，實(shí)際上就是對(duì)推廣能力的控制，這是SVM的核心思想之一。

最優(yōu)分類(lèi)面就是要求分類(lèi)面不但能將兩類(lèi)樣本正確分開(kāi)（訓(xùn)練錯(cuò)誤率為0），而且要使兩類(lèi)的分類(lèi)間隔最大。根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，前者是保證經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，而后者使得分類(lèi)間隔最大，導(dǎo)致VC維最小，實(shí)際上就是使推廣性的界中的置信范圍最小，從而達(dá)到使得真實(shí)風(fēng)險(xiǎn)最小的目的。

分類(lèi)面方程為wT x+b=0，如果線(xiàn)性可分，則樣本集(xi,yi)，i=1,2,…,n，x∈Rd，y∈{-1,1}滿(mǎn)足：此時(shí)分類(lèi)間隔等于2/||w||，使分類(lèi)間隔最大等價(jià)于使||w||2最小。滿(mǎn)足條件式（2-129）且使最小的分類(lèi)面就稱(chēng)為最優(yōu)分類(lèi)面，圖2-12為各分類(lèi)面與最優(yōu)分類(lèi)面的示意圖，其中，H1，H2上的訓(xùn)練樣本點(diǎn)就稱(chēng)為支持向量（SV）。

線(xiàn)性可分情況下，在結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則下的最優(yōu)超平面問(wèn)題，可以表示為如下的約束優(yōu)化問(wèn)題。即求函數(shù)

的最小化。為此，可以定義如下的Lagrange函數(shù)：

式中，αi≥0為各樣本對(duì)應(yīng)的Lagrange系數(shù)。

求解式（2-131）的最小值，可以令該泛函對(duì)w和b求偏導(dǎo)，并令它們等于0，這樣就可以把上述求最優(yōu)分類(lèi)面的問(wèn)題轉(zhuǎn)化為較簡(jiǎn)單的對(duì)偶問(wèn)題，即在約束條件

下，求下列函數(shù)最大值時(shí)的解αi：

αi為原問(wèn)題中與每個(gè)約束條件即式（2-129）對(duì)應(yīng)的Lagrange乘子。這是一個(gè)不等式約束下二次函數(shù)尋優(yōu)的問(wèn)題，存在唯一解。容易證明，解將只有一部分（通常是少部分）不為零，該部分對(duì)應(yīng)的樣本就是支持向量。

假設(shè)為最優(yōu)解，則最優(yōu)分類(lèi)面的權(quán)系數(shù)向量為

即最優(yōu)分類(lèi)面的權(quán)系數(shù)向量是訓(xùn)練樣本中支持向量的線(xiàn)性組合。得到支持向量及向量w*后，分類(lèi)器中的閾值b*，可以通過(guò)兩類(lèi)中任意一對(duì)支持向量取中值得到。

式中，x*(1)、x*(-1)分別表示兩類(lèi)中任意一個(gè)支持向量。

根據(jù)前面所得到的支持向量以及其相關(guān)的系數(shù)，就可以得到上述問(wèn)題的最優(yōu)分類(lèi)判別函數(shù)（指示函數(shù)）：

（2）線(xiàn)性不可分的最優(yōu)分類(lèi)面

上面的方法是訓(xùn)練樣本在線(xiàn)性可分的情況下，保證全部樣本能被正確地分類(lèi)，即經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp為0的前提下，通過(guò)對(duì)分類(lèi)間隔最大化，使分類(lèi)器獲得最好的推廣能力。若訓(xùn)練集是線(xiàn)性不可分的，或事先不知道它是否線(xiàn)性可分的，我們可以通過(guò)引入非負(fù)松弛變量(ξi,i=1,2,…,n)來(lái)允許錯(cuò)分樣本的存在。這時(shí)，式（2-129）變?yōu)?/p>

容許錯(cuò)分的分類(lèi)超平面稱(chēng)為軟間隔分類(lèi)超平面。圖2-13為訓(xùn)練集在線(xiàn)性不可分的情況下軟間隔分類(lèi)超平面示意圖。由于允許存在錯(cuò)分樣本，此時(shí)的軟間隔分類(lèi)超平面表示在剔除那些錯(cuò)分樣本后最大分類(lèi)間隔的超平面。

此時(shí)，最小泛函由式（2-130）變?yōu)?/p>

式中，C >0是一個(gè)自定義的懲罰因子，它控制對(duì)錯(cuò)分樣本懲罰的程度，用來(lái)控制樣本偏差與機(jī)器推廣能力之間的折中。C越大，懲罰就越大，對(duì)錯(cuò)分樣本的約束程度就越大。

用與求解最優(yōu)分類(lèi)面時(shí)同樣的方法求解式（2-139）的優(yōu)化問(wèn)題，同樣得到一個(gè)求二次函數(shù)的極值問(wèn)題，其結(jié)果與線(xiàn)性可分情況下得到的式（2-132）～式（2-137）幾乎完全相同，只是條件式（2-133）變?yōu)?/p>

（3）支持向量機(jī)的概念

前面分別介紹了在線(xiàn)性分類(lèi)和非線(xiàn)性情況下，如何求解最優(yōu)超平面。而在實(shí)際應(yīng)用中，分類(lèi)問(wèn)題往往是一個(gè)非線(xiàn)性的問(wèn)題，理想的分類(lèi)面應(yīng)該是非線(xiàn)性的。對(duì)非線(xiàn)性問(wèn)題，可以通過(guò)非線(xiàn)性變換，將非線(xiàn)性問(wèn)題轉(zhuǎn)化為某個(gè)高維空間中的線(xiàn)性問(wèn)題，在變換后的高維空間中求其最優(yōu)分類(lèi)面。支持向量機(jī)方法處理非線(xiàn)性問(wèn)題的方法是，首先將訓(xùn)練集從原始模式空間經(jīng)過(guò)特定函數(shù)的非線(xiàn)性變換，映射到高維特征空間，然后，在高維特征空間中，尋找最優(yōu)分類(lèi)超平面，該超平面實(shí)際上對(duì)應(yīng)著原始模式空間中的非線(xiàn)性分類(lèi)面，如圖2-14所示。

因此，支持向量機(jī)方法在處理非線(xiàn)性分類(lèi)問(wèn)題時(shí)，僅比線(xiàn)性情況多了一個(gè)非線(xiàn)性映射環(huán)節(jié)。假定該非線(xiàn)性映射為

則式（2-134）中的優(yōu)化問(wèn)題就可以轉(zhuǎn)變?yōu)?/p>

式（2-141）的非線(xiàn)性變換可能比較復(fù)雜，從而使式（2-142）的計(jì)算非常困難以至于難以實(shí)現(xiàn)。但是注意到，在上面的對(duì)偶問(wèn)題中，訓(xùn)練算法僅使用了高維特征空間中的點(diǎn)積，即?(xi)·?(x j)，而沒(méi)有單獨(dú)的映射?(xi)出現(xiàn)。因此，如果能夠找到一個(gè)函數(shù)K，使得定理（Mercer條件）：對(duì)于任意的對(duì)稱(chēng)函數(shù)K(x, x＇ )，它是某個(gè)特征空間中的內(nèi)積運(yùn)算的充分必要條件是，對(duì)于任意的?(x)≠0且∫?2(x)dx<∞有

這樣，在高維特征空間中，實(shí)際上只需要進(jìn)行內(nèi)積運(yùn)算，而這種內(nèi)積運(yùn)算是可以用原空間中的函數(shù)來(lái)實(shí)現(xiàn)的，我們甚至沒(méi)有必要知道變換映射?(?)的形式。根據(jù)泛函的有關(guān)理論，只要一種內(nèi)積函數(shù)K(xi,xj)滿(mǎn)足如下定理中的Mercer條件，它就對(duì)應(yīng)某一變換空間中的內(nèi)積。

因此在求最優(yōu)分類(lèi)面時(shí)，采用適當(dāng)?shù)膬?nèi)積函數(shù)K(xi, xj)就可以實(shí)現(xiàn)某一非線(xiàn)性變換后的線(xiàn)性分類(lèi)，而計(jì)算復(fù)雜度卻沒(méi)有增加，此時(shí)目標(biāo)函數(shù)式（2-134）與式（2-142）變?yōu)?/p>

而相應(yīng)的最優(yōu)分類(lèi)面的判別函數(shù)式（2-137）也變?yōu)?/p>

這就是支持向量機(jī)（SVM）。概括地說(shuō)，支持向量機(jī)就是首先通過(guò)用內(nèi)積函數(shù)定義的非線(xiàn)性變換將輸入空間變換到一個(gè)高維空間，在這個(gè)空間中求（廣義）最優(yōu)分類(lèi)面。最優(yōu)向量機(jī)分類(lèi)函數(shù)形式上類(lèi)似于一個(gè)神經(jīng)網(wǎng)絡(luò)，輸出是中間結(jié)點(diǎn)的線(xiàn)性組合，每個(gè)中間結(jié)點(diǎn)對(duì)應(yīng)一個(gè)支持向量，如圖2-15所示。

2.支持向量機(jī)模型的建立

SVM中可供調(diào)整的參數(shù)不多，其模型的確立主要是核函數(shù)的形式及其參數(shù)，如采用多項(xiàng)式核函數(shù)就要確定q的值，而對(duì)于高斯徑向基核函數(shù)則要確定σ的值。關(guān)于核函數(shù)的特性與選擇的問(wèn)題，在前面已經(jīng)做了分析和說(shuō)明。對(duì)于分類(lèi)問(wèn)題，標(biāo)準(zhǔn)SVM的另一個(gè)可調(diào)節(jié)的參數(shù)是懲罰系數(shù)C。

本節(jié)主要討論懲罰系數(shù)C的問(wèn)題，另外還將討論SVM的實(shí)現(xiàn)算法和多類(lèi)問(wèn)題解決方法。

（1）懲罰系數(shù)C

已知，在線(xiàn)性不可分的情況下，求最優(yōu)分類(lèi)面問(wèn)題等同于求解下列問(wèn)題。

式中，C >0，為懲罰系數(shù)。

這是一個(gè)二次規(guī)劃問(wèn)題，可通過(guò)Lagrange方法求解，轉(zhuǎn)化為如下問(wèn)題。

最優(yōu)分類(lèi)面的權(quán)系數(shù)為

可見(jiàn)，最優(yōu)分類(lèi)面的權(quán)系數(shù)向量是訓(xùn)練樣本向量的線(xiàn)性組合。

對(duì)比式（2-151）和式（2-133），可以看出，由于C的引入，αi的值受到限制，C越小，αi的值也就越小，又由式（2-152）可知，||w||也變小，而2/||w||是兩類(lèi)之間的間隔，它的大小也體現(xiàn)了SVM泛化能力的強(qiáng)弱，間隔越大，泛化能力越強(qiáng)，反之，則泛化能力越弱。所以C越小，兩類(lèi)之間的間隔越大，SVM泛化能力越強(qiáng)，但顯然這時(shí)SVM的分類(lèi)準(zhǔn)確率要降低。同理，C越大，兩類(lèi)之間的間隔越小，SVM泛化能力就越差，但這時(shí)的SVM分類(lèi)準(zhǔn)確率可以得到提高。

從上面的分析知道，懲罰系數(shù)C可以控制SVM的泛化性能和錯(cuò)分率之間的折中。C不宜太大，也不宜太小。C的值太大時(shí)，雖然此時(shí)樣本的識(shí)別率高，SVM的分類(lèi)性能很好（如果不出現(xiàn)過(guò)適應(yīng)的話(huà)），但此時(shí)的泛化性能較低。再看看對(duì)偶問(wèn)題，懲罰系數(shù)C的值越大，Lagrange算子αi的約束力就越大，這就意味著要花更長(zhǎng)的訓(xùn)練時(shí)間。這兩個(gè)現(xiàn)象是互相聯(lián)系的，過(guò)長(zhǎng)的訓(xùn)練時(shí)間，往往意味著過(guò)適應(yīng)和低下的泛化能力。其解決辦法就是減小C。但是C的值也不宜太小。注意到線(xiàn)性不可分的情況下，0≤αi≤C，C的值太小時(shí)，所有的αi自然也會(huì)很小，泛化能力雖然高，但準(zhǔn)確率無(wú)法保證。

（2）SVM學(xué)習(xí)算法的步驟

SVM學(xué)習(xí)算法的步驟如下：

（a）獲取學(xué)習(xí)樣本(xi,yi)，i=1,2,…,n；

（b）選擇進(jìn)行非線(xiàn)性變換的核函數(shù)及對(duì)錯(cuò)分（誤差）進(jìn)行懲罰的懲罰因子C；

（c）形成二次優(yōu)化問(wèn)題；

（d）用優(yōu)化方法（如Chunking，SMO算法）解該優(yōu)化問(wèn)題；

（e）獲得α，α*及b的值，代入方程中，獲得分類(lèi)的支持向量機(jī)；

（f）將需要預(yù)測(cè)或分類(lèi)的數(shù)據(jù)代入支持向量機(jī)方程中獲得結(jié)果。

（3）SVM多類(lèi)分類(lèi)器算法

由前面的內(nèi)容可知，標(biāo)準(zhǔn)SVM最基本的理論是針對(duì)二分類(lèi)問(wèn)題的，然而，在實(shí)際應(yīng)用中有許多多分類(lèi)問(wèn)題，要解決多分類(lèi)問(wèn)題必須輔以一定的策略，常用的方法有以下幾種：

·標(biāo)準(zhǔn)算法。對(duì)于k-類(lèi)問(wèn)題應(yīng)構(gòu)造k個(gè)分類(lèi)器，第i個(gè)SVM用第i類(lèi)中的訓(xùn)練樣本作為正的訓(xùn)練樣本，將其他的樣本作為負(fù)的訓(xùn)練樣本。這個(gè)算法稱(chēng)為一對(duì)多方法(one-against-rest )。

·一對(duì)一算法(one-against-one)。該算法在 k 類(lèi)訓(xùn)練樣本中構(gòu)造所有可能的二類(lèi)分類(lèi)器，每類(lèi)僅在k類(lèi)中的二類(lèi)訓(xùn)練樣本上訓(xùn)練，結(jié)果共構(gòu)造個(gè)分類(lèi)器。組合這些二類(lèi)分類(lèi)器很自然地用到了投票法，得票最多的類(lèi)為新點(diǎn)所屬的類(lèi)。

·k-類(lèi)SVM算法。該算法對(duì)所有的樣本使用同一個(gè)二次規(guī)劃，只需要一次就可以決定分類(lèi)。Weston提出了兩種新的k-類(lèi)SVM算法：QP-MC-SV算法和LP-MC-SV算法。這種算法很自然地在構(gòu)造決策函數(shù)時(shí)同時(shí)考慮所有的類(lèi)。

·決策導(dǎo)向循環(huán)圖算法。Platt等提出了一個(gè)新的學(xué)習(xí)構(gòu)架——決策導(dǎo)向循環(huán)圖（Decision Directed Acyclic Graph，DDAG），該方法將多個(gè)二類(lèi)分類(lèi)器組合成k-類(lèi)分類(lèi)器。對(duì)于k-

·類(lèi)問(wèn)題，DDAG含有個(gè)分類(lèi)器，每個(gè)分類(lèi)器對(duì)應(yīng)二類(lèi)。

3.支持向量機(jī)模型的特點(diǎn)

支持向量機(jī)方法的幾個(gè)主要特點(diǎn)為：

·支持向量機(jī)方法是基于統(tǒng)計(jì)學(xué)習(xí)理論的結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則，與傳統(tǒng)的機(jī)器學(xué)習(xí)方法不同，它不僅使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小而且通過(guò)尋找最大間隔分解面來(lái)控制模型的復(fù)雜度，從而有效地避免了過(guò)擬合現(xiàn)象，為模型選擇的問(wèn)題提供了良好的思路；

·支持向量機(jī)法專(zhuān)門(mén)針對(duì)有限樣本情況，其目標(biāo)是得到現(xiàn)有信息下的最優(yōu)解而不僅僅是樣本數(shù)趨于無(wú)窮大時(shí)的最優(yōu)解；

·支持向量機(jī)方法最終轉(zhuǎn)化為在線(xiàn)性條件下的凸二次優(yōu)化問(wèn)題，從理論上說(shuō)，找到的極值點(diǎn)是全局最優(yōu)點(diǎn)，解決了在神經(jīng)網(wǎng)絡(luò)方法中無(wú)法避免的局部極值問(wèn)題。

支持向量機(jī)方法將實(shí)際問(wèn)題通過(guò)非線(xiàn)性映射變換到高維的特征空間，在高維空間中，通過(guò)構(gòu)造線(xiàn)性判別函數(shù)來(lái)實(shí)現(xiàn)原空間中的非線(xiàn)性判別，特殊性質(zhì)能保證機(jī)器有較好的推廣能力，同時(shí)它巧妙地解決了維數(shù)問(wèn)題，這在一定程度上解決了特征維數(shù)過(guò)大所導(dǎo)致的維數(shù)災(zāi)難問(wèn)題。

4.支持向量機(jī)在Visual C++環(huán)境中的實(shí)現(xiàn)

由于支持向量機(jī)的算法實(shí)現(xiàn)比較復(fù)雜，本書(shū)提供一個(gè)Visual C++下的支持向量機(jī)實(shí)現(xiàn)程序，具體見(jiàn)所附光盤(pán)。