陳冰梅，樊曉平，周志明，李雪榮

CHEN Bing-mei1,2, FAN Xiao-ping1, ZHOU Zhi-ming3, LI Xue-rong2

（1. 中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083；2. 中南大學(xué) 湘雅二醫(yī)院，長沙 410011）3. 長沙環(huán)境保護(hù)職業(yè)技術(shù)學(xué)院，長沙 410004）

支持向量機(jī)原理及展望

The principle and prospect of support vector machine

陳冰梅1,2，樊曉平1，周志明3，李雪榮2

CHEN Bing-mei1,2, FAN Xiao-ping1, ZHOU Zhi-ming3, LI Xue-rong2

（1. 中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083；2. 中南大學(xué) 湘雅二醫(yī)院，長沙 410011）3. 長沙環(huán)境保護(hù)職業(yè)技術(shù)學(xué)院，長沙 410004）

支持向量機(jī)(SVM)是90年代中期發(fā)展起來的基于統(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á)到在統(tǒng)計(jì)樣本量較少的情況下，亦能獲得良好統(tǒng)計(jì)規(guī)律的目的。該方法不但算法簡單,而且具有較好的“魯棒”性，與神經(jīng)網(wǎng)絡(luò)相比，它的優(yōu)點(diǎn)是訓(xùn)練算法中不存在局部極小值問題，在解決小樣本、非線性及高維模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中，現(xiàn)在已經(jīng)在許多領(lǐng)域取得了成功的應(yīng)用。

支持向量機(jī)；神經(jīng)網(wǎng)絡(luò)；分類器；核函數(shù)

0 引言

支持向量機(jī)(Support Vector Machine,SVM)是由Vapnik領(lǐng)導(dǎo)的AT&TBell實(shí)驗(yàn)室研究小組在1963年提出的一種新的非常有潛力的分類技術(shù)，SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的模式識(shí)別方法，主要應(yīng)用于模式識(shí)別領(lǐng)域。由于當(dāng)時(shí)這些研究尚不十分完善，在解決模式識(shí)別問題中往往趨于保守，且數(shù)學(xué)上比較艱澀，這些研究一直沒有得到充分的重視。直到90年代，統(tǒng)計(jì)學(xué)習(xí)理論 (Statistical Learning Theory，SLT)的實(shí)現(xiàn)和由于神經(jīng)網(wǎng)絡(luò)等較新興的機(jī)器學(xué)習(xí)方法的研究遇到一些重要的困難，比如如何確定網(wǎng)絡(luò)結(jié)構(gòu)的問題、過學(xué)習(xí)與欠學(xué)習(xí)問題、局部極小點(diǎn)問題等，使得SVM迅速發(fā)展和完善，在解決小樣本、非線性及高維模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中，從此迅速的發(fā)展起來，現(xiàn)在已經(jīng)在許多領(lǐng)域取得了成功的應(yīng)用。

1 基本原理

假設(shè)如圖1這些數(shù)據(jù)點(diǎn)是n維實(shí)空間中的點(diǎn)。我們希望能夠把這些點(diǎn)通過一個(gè)n-1維的超平面分開。通常這個(gè)被稱為線性分類器。有很多分類器都符合這個(gè)要求。但是我們還希望找到分類最佳的平面，即使得屬于兩個(gè)不同類的數(shù)據(jù)點(diǎn)間隔最大的那個(gè)面，該面亦稱為最大間隔超平面。如果我們能夠找到這個(gè)面，那么這個(gè)分類器就稱為最大間隔分類器。

圖1 多種分類超平面示意圖

如圖1有很多個(gè)分類器(超平面)可以把數(shù)據(jù)分開，但是只有一個(gè)能夠達(dá)到最大分割。

支持向量機(jī)將向量映射到一個(gè)更高維的空間里，在這個(gè)空間里建立有一個(gè)最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個(gè)互相平行的超平面。建立方向合適的分隔超平面使兩個(gè)與之平行的超平面間的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。

支持向量機(jī)屬于一般化線性分類器。他們也可以認(rèn)為是提克洛夫規(guī)則化（Tikhonov Regularization）方法的一個(gè)特例。這種分類器的特點(diǎn)是他們能夠同時(shí)最小化經(jīng)驗(yàn)誤差與最大化幾何邊緣區(qū)。因此支持向量機(jī)也被稱為最大邊緣區(qū)分類器。

所謂支持向量是指那些在間隔區(qū)邊緣的訓(xùn)練樣本點(diǎn)。 這里的“機(jī)（machine,機(jī)器）”實(shí)際上是一個(gè)算法。在機(jī)器學(xué)習(xí)領(lǐng)域，常把一些算法看做是一個(gè)機(jī)器。

圖2 在超平面上的樣本點(diǎn)也稱為支持向量

如圖2設(shè)樣本屬于兩個(gè)類，用該樣本訓(xùn)練svm得到的最大間隔超平面。在超平面上的樣本點(diǎn)也稱為支持向量，支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性（即對特定訓(xùn)練樣本的學(xué)習(xí)精度）和學(xué)習(xí)能力（即無錯(cuò)誤地識(shí)別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力 。

支持向量機(jī)(Support vector machines，SVM)與神經(jīng)網(wǎng)絡(luò)類似，都是學(xué)習(xí)型的機(jī)制，但與神經(jīng)網(wǎng)絡(luò)不同的是SVM使用的是數(shù)學(xué)方法和優(yōu)化技術(shù)。

2 支持向量機(jī)的算法

SVM的支持向量機(jī)的主要思想可以概括為兩點(diǎn):

1）它是針對線性可分情況進(jìn)行分析，對于線性不可分的情況,通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對樣本的非線性特征進(jìn)行線性分析成為可能；

2）它基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論之上在特征空間中建構(gòu)最優(yōu)分割超平面，使得學(xué)習(xí)器得到全局最優(yōu)化，并且在整個(gè)樣本空間的期望風(fēng)險(xiǎn)以某個(gè)概率滿足一定上界。

支持向量機(jī)的目標(biāo)就是要根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理，構(gòu)造一個(gè)目標(biāo)函數(shù)將兩類模式盡可能地區(qū)分開來，通常分為兩類情況來討論：線性可分與線性不可分。

2.1 線性可分情況

在線性可分的情況下，就會(huì)存在一個(gè)超平面使得訓(xùn)練樣本完全分開，該超平面可描述為:

w ·x + b = 0 (1)

其中，“·”是點(diǎn)積, w是n維向量, b為偏移量。

最優(yōu)超平面是使得每一類數(shù)據(jù)與超平面距離最近的向量與超平面之間的距離最大的這樣的平面，最優(yōu)超平面可以通過解下面的二次優(yōu)化問題來獲得：

滿足約束條件：

在特征數(shù)目特別大的情況，可以將此二次規(guī)劃問題轉(zhuǎn)化為其對偶問題：

滿足約束條件：

這里α=(α1,...,αn)是Lagrange 乘子，b*是最優(yōu)超平面的法向量， 是最優(yōu)超平面的偏移量,在這類優(yōu)化問題的求解與分析中，KKT條件將起到很重要的作用，在(7) 式中,其解必須滿足：

從式(5)可知,那些aι=0的樣本對分類沒有任何作用，只有那些aι>0的樣本才對分類起作用，這些樣本稱為支持向量，故最終的分類函數(shù)為：

根據(jù)f (x)的符號(hào)來確定X 的歸屬。

2.2 線性不可分的情況

對于線性不可分的情況,可以把樣本X 映射到一個(gè)高維特征空間H，并在此空間中運(yùn)用原空間的函數(shù)來實(shí)現(xiàn)內(nèi)積運(yùn)算，這樣將非線性問題轉(zhuǎn)換成另一空間的線性問題來獲得一個(gè)樣本的歸屬，根據(jù)泛函的有關(guān)理論，只要一種核函數(shù)滿足Mercer條件,它就對應(yīng)某一空間中的內(nèi)積，因此只要在最優(yōu)分類面上采用適當(dāng)?shù)膬?nèi)積函數(shù)就可以實(shí)現(xiàn)這種線性不可分的分類問題。此時(shí)的目標(biāo)函數(shù)為：

其相應(yīng)的分類函數(shù)為:

2.3 內(nèi)積核函數(shù)

SVM的關(guān)鍵在于核函數(shù)。低維空間向量集通常難于劃分，解決的方法是將它們映射到高維空間。但這個(gè)辦法帶來的困難就是計(jì)算復(fù)雜度的增加，而核函數(shù)正好巧妙地解決了這個(gè)問題。也就是說，只要選用適當(dāng)?shù)暮撕瘮?shù)，就可以得到高維空間的分類函數(shù)。在SVM理論中，采用不同的核函數(shù)將導(dǎo)致不同的SVM算法。目前有三類用的較多的內(nèi)積核函數(shù)：第一類是

我們所能得到的是p階多項(xiàng)式分類器，第二類是徑向基函數(shù)（RBF），也稱作高斯核函數(shù)：

第三類是Sigmoid函數(shù)：

這時(shí)SVM實(shí)現(xiàn)的就是包含一個(gè)隱層感知器，隱層結(jié)點(diǎn)數(shù)是由算法自動(dòng)確定的。究竟用哪一種核函數(shù)比較好，這還是取決你對數(shù)據(jù)處理的要求，不過建議可以使用徑向基函數(shù)。

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

1）它是專門針對有限樣本情況的，其目標(biāo)是得到現(xiàn)有信息下的最優(yōu)解而不僅僅是樣本數(shù)趨于無窮大時(shí)的最優(yōu)值；

2）算法最終將轉(zhuǎn)化成為一個(gè)二次型尋優(yōu)問題，從理論上說，得到的將是全局最優(yōu)點(diǎn)，解決了在神經(jīng)網(wǎng)絡(luò)方法中無法避免的局部極值問題；

3）算法將實(shí)際問題通過非線性變換轉(zhuǎn)換到高維的特征空間(Feature Space)，在高維空間中構(gòu)造線性判別函數(shù)來實(shí)現(xiàn)原空間中的非線性判別函數(shù)，特殊性質(zhì)能保證機(jī)器有較好的推廣能力，同時(shí)它巧妙地解決了維數(shù)問題，其算法復(fù)雜度與樣本維數(shù)無關(guān)；

4）在SVM方法中，只要定義不同的內(nèi)積函數(shù)，就可以實(shí)現(xiàn)多項(xiàng)式逼近、貝葉斯分類器、徑向基函數(shù)(Radial Basic Function或RBF)方法、多層感知器網(wǎng)絡(luò)等許多現(xiàn)有學(xué)習(xí)算法。

5）該方法不但算法簡單,而且具有較好的“魯棒”性。

4 結(jié)束語

支持向量機(jī)算法是一個(gè)凸二次優(yōu)化問題,能夠保證找到的極值解就是全局最優(yōu)解，是神經(jīng)網(wǎng)絡(luò)領(lǐng)域取得的一項(xiàng)重大突破。與神經(jīng)網(wǎng)絡(luò)相比，它的優(yōu)點(diǎn)是訓(xùn)練算法中不存在局部極小值問題，可以自動(dòng)設(shè)計(jì)模型復(fù)雜度(例如隱層節(jié)點(diǎn)數(shù))，不存在維數(shù)災(zāi)難問題，泛化能力強(qiáng)，SVM已初步表現(xiàn)出很多優(yōu)于已有方法的性能。 SVM正在成為繼神經(jīng)網(wǎng)絡(luò)研究之后新的研究熱點(diǎn)，并將推動(dòng)機(jī)器學(xué)習(xí)理論和技術(shù)有重大的發(fā)展。

支持向量機(jī)能非常成功地處理回歸問題(時(shí)間序列分析)、模式識(shí)別(分類問題、判別分析)、 概率密度函數(shù)估計(jì)等諸多問題，并可推廣于預(yù)測和綜合評(píng)價(jià)等領(lǐng)域，例如，在模式識(shí)別方面，對于手寫數(shù)字識(shí)別、語音識(shí)別、人臉圖像識(shí)別、文章分類等問題，SVM算法在精度上已經(jīng)超過傳統(tǒng)的學(xué)習(xí)算法或與之不相上下。目前國際上支持向量機(jī)理論研究和實(shí)際應(yīng)用兩方面都正處于飛速發(fā)展階段。

[1] B.E.Boser,I.M.Guyon,and V.N.Vapnik. A training algorithm for optimal margin classifiers.In D.Haussler, editor,5th Annual ACM Workshop on COLT,pages 144-152,Pittsburgh,PA,1992.ACM Press.

[2] Corinna Cortes and V.Vapnik,"Support-Vector Networks,Machine Learning,20,1995,1.

[3] 張艷.一類基于支持向量機(jī)的軟件故障預(yù)測方法[J].小型微型計(jì)算機(jī)系統(tǒng),2010.31(7):1380-1383.

[4] 杜樹新,吳鐵軍.模式識(shí)別中的支持向量機(jī)方法[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版), 2003,9,37(5):521-526.

[5] 劉渤海.基于ANN和SVM的質(zhì)量預(yù)測方法研究[J].制造業(yè)自動(dòng)化,2010.32(5):152-155.

[6] 韋抒.應(yīng)用支持向量機(jī)實(shí)現(xiàn)轉(zhuǎn)子故障的模式分類[J].制造業(yè)自動(dòng)化,2009.31(7):82-85.

TP273

A

1009-0134(2010)12(上)-0136-03

10.3969/j.issn.1009-0134.2010.12(上).45

2010-08-17

國家自然科學(xué)基金題（39270262）

陳冰梅（1963 -），女，廣西玉林人，高級(jí)，工程師，在讀博士，研究方向?yàn)槿斯ぶ悄芎椭悄苡?jì)算。