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

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

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)計學(xué)習(xí)理論的一種機(jī)器學(xué)習(xí)方法，通過尋求結(jié)構(gòu)化風(fēng)險最小來提高學(xué)習(xí)機(jī)泛化能力，實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險和置信范圍的最小化，從而達(dá)到在統(tǒng)計樣本量較少的情況下，亦能獲得良好統(tǒng)計規(guī)律的目的。該方法不但算法簡單,而且具有較好的“魯棒”性，與神經(jīng)網(wǎng)絡(luò)相比，它的優(yōu)點(diǎn)是訓(xùn)練算法中不存在局部極小值問題，在解決小樣本、非線性及高維模式識別問題中表現(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)計學(xué)習(xí)理論的模式識別方法，主要應(yīng)用于模式識別領(lǐng)域。由于當(dāng)時這些研究尚不十分完善，在解決模式識別問題中往往趨于保守，且數(shù)學(xué)上比較艱澀，這些研究一直沒有得到充分的重視。直到90年代，統(tǒng)計學(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ā)展和完善，在解決小樣本、非線性及高維模式識別問題中表現(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)通過一個n-1維的超平面分開。通常這個被稱為線性分類器。有很多分類器都符合這個要求。但是我們還希望找到分類最佳的平面，即使得屬于兩個不同類的數(shù)據(jù)點(diǎn)間隔最大的那個面，該面亦稱為最大間隔超平面。如果我們能夠找到這個面，那么這個分類器就稱為最大間隔分類器。

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

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

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

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

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

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

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

支持向量機(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)險最小化理論之上在特征空間中建構(gòu)最優(yōu)分割超平面，使得學(xué)習(xí)器得到全局最優(yōu)化，并且在整個樣本空間的期望風(fēng)險以某個概率滿足一定上界。

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

2.1 線性可分情況

在線性可分的情況下，就會存在一個超平面使得訓(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)的符號來確定X 的歸屬。

2.2 線性不可分的情況

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

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

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

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

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

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

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

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

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

2）算法最終將轉(zhuǎn)化成為一個二次型尋優(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ù)問題，其算法復(fù)雜度與樣本維數(shù)無關(guān)；

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

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

4 結(jié)束語

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

支持向量機(jī)能非常成功地處理回歸問題(時間序列分析)、模式識別(分類問題、判別分析)、 概率密度函數(shù)估計等諸多問題，并可推廣于預(yù)測和綜合評價等領(lǐng)域，例如，在模式識別方面，對于手寫數(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ī)系統(tǒng),2010.31(7):1380-1383.

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

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

[6] 韋抒.應(yīng)用支持向量機(jī)實(shí)現(xiàn)轉(zhuǎn)子故障的模式分類[J].制造業(yè)自動化,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 -），女，廣西玉林人，高級，工程師，在讀博士，研究方向?yàn)槿斯ぶ悄芎椭悄苡嬎恪?/p>