賈 凝

（陜西郵電職業(yè)技術(shù)學(xué)院，西安 712000）

0 引言

傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法和最小二乘法都是基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化準(zhǔn)則提出來(lái)的，即最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)(訓(xùn)練誤差)從而試圖使期望風(fēng)險(xiǎn)最小化。而支持向量機(jī)(Support Vector Machine-SVM)是由AT&T貝爾實(shí)驗(yàn)室的研究小組于1995年在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上提出來(lái)的一類(lèi)新型的機(jī)器學(xué)習(xí)方法。它是結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則基本思想的具體實(shí)現(xiàn)，為了最小化期望風(fēng)險(xiǎn)，做到同時(shí)最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍，即以訓(xùn)練誤差作為優(yōu)化問(wèn)題的約束條件，而以置信范圍值最小化作為優(yōu)化問(wèn)題的目標(biāo)來(lái)實(shí)現(xiàn)。所以支持向量機(jī)的泛化能力要明顯優(yōu)于神經(jīng)網(wǎng)絡(luò)等傳統(tǒng)的學(xué)習(xí)方法[1]。

支持向量機(jī)的主要思想可以概括為兩點(diǎn)：（1）它開(kāi)始是針對(duì)線(xiàn)性可分情況進(jìn)行分析的，后來(lái)對(duì)于線(xiàn)性不可分的情況，通過(guò)使用非線(xiàn)性映射算法將低維輸入空間線(xiàn)性不可分的樣本映射到高維屬性空間使其線(xiàn)性可分，使得在高維屬性空間采用線(xiàn)性算法對(duì)樣本的非線(xiàn)性特性進(jìn)行分析成為可能；（2）它通過(guò)使用結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則在屬性空間構(gòu)造最優(yōu)分割超平面，使得機(jī)器學(xué)習(xí)得到全局最優(yōu)化，解決了過(guò)學(xué)習(xí)問(wèn)題，對(duì)樣本具有較好的泛化能力。另外，由于支持向量機(jī)的訓(xùn)練問(wèn)題本質(zhì)上是一個(gè)經(jīng)典的二次規(guī)劃問(wèn)題，避免了局部最優(yōu)解，有效地克服了維數(shù)災(zāi)難，而且可以利用最優(yōu)化理論中許多成熟的算法。正是基于支持向量機(jī)的上述優(yōu)勢(shì)，無(wú)論在理論基礎(chǔ)上還是在應(yīng)用前景上，SVM都具有其它機(jī)器學(xué)習(xí)方法難以比擬的優(yōu)越性，它已經(jīng)在模式識(shí)別和回歸估計(jì)方面取得越來(lái)越多的進(jìn)展。用于回歸估計(jì)的支持向量機(jī)方法在非線(xiàn)性系統(tǒng)辨識(shí)，預(yù)測(cè)預(yù)報(bào)，建模與控制等領(lǐng)域都有潛在的廣泛應(yīng)用，使得對(duì)其進(jìn)行研究顯得非常重要[2]。

1 統(tǒng)計(jì)學(xué)習(xí)理論（SLT）

SVM的理論基礎(chǔ)是統(tǒng)計(jì)學(xué)習(xí)理論，它是對(duì)結(jié)構(gòu)風(fēng)險(xiǎn)最小化歸納原則的一種實(shí)現(xiàn)。SLT是研究小樣本統(tǒng)計(jì)和預(yù)測(cè)的理論，主要內(nèi)容包括四方面[3]：

（1）經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化標(biāo)準(zhǔn)統(tǒng)計(jì)學(xué)習(xí)的一致性條件；

（2）在這些條件下關(guān)于統(tǒng)計(jì)學(xué)習(xí)方法推廣性的界的結(jié)論；

（3）在這些界的基礎(chǔ)上建立的小樣本歸納推理準(zhǔn)則；

（4）實(shí)現(xiàn)新的準(zhǔn)則的實(shí)際方法(算法)。

其中，核心內(nèi)容是：VC維、推廣性的界、結(jié)構(gòu)風(fēng)險(xiǎn)最小化（SRM）原則[4]。

實(shí)現(xiàn)SRM原則可以有兩種思路：（1）保持置信范圍固定(通過(guò)選擇一個(gè)適當(dāng)?shù)慕Y(jié)構(gòu))并最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)；（2）保持經(jīng)驗(yàn)風(fēng)險(xiǎn)固定并最小化置信范圍SVM就是第二種思路的實(shí)現(xiàn)：設(shè)計(jì)函數(shù)集的某種結(jié)構(gòu)使每個(gè)子集中都能夠取得最小的經(jīng)驗(yàn)風(fēng)險(xiǎn)(如使訓(xùn)練誤差為0)，然后選擇適當(dāng)?shù)淖蛹怪眯欧秶钚?，則這個(gè)子集使經(jīng)驗(yàn)最小的函數(shù)便是最優(yōu)函數(shù)。

2 線(xiàn)性支持向量機(jī)

支持向量機(jī)是Vapnik提出的源于統(tǒng)計(jì)學(xué)習(xí)理論的一種學(xué)習(xí)方法，它基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，具有很強(qiáng)的泛化能力。SVM算法是從線(xiàn)性可分情況下的最優(yōu)分離超平面提出的。所謂最優(yōu)分離超平面就是要求分類(lèi)超平面不但能將兩類(lèi)樣本無(wú)錯(cuò)誤分開(kāi)，而且要使兩類(lèi)之間的距離最大[5]。設(shè)線(xiàn)性可分樣本集為(xi,yi),i=1,…,n,x∈Rd,y∈{+1,-1},是類(lèi)別標(biāo)號(hào)，d維空間中線(xiàn)性判別函數(shù)的一般形式為g(x)=w·x+b，分類(lèi)面方程為w·x+b=0。如果存在分類(lèi)超平面w·x+b=0使得

則稱(chēng)樣本集是線(xiàn)性可分的。對(duì)于線(xiàn)性可分的問(wèn)題，就是要尋求參數(shù)(w,b)，使(l)式成立，由此得到判別函數(shù)y(x)=sgn(w·x+b)。將判別函數(shù)進(jìn)行歸一化，使兩類(lèi)所有樣本都滿(mǎn)足|g(x)|≥1，即，使離分類(lèi)面最近的樣本的|g(x)=1|，這樣分類(lèi)間隔就等于 2/||w||，因此間隔最大等價(jià)于使||w||“(或||w||2)最小;而要求分類(lèi)線(xiàn)對(duì)所有樣本正確分類(lèi)，就是要求其滿(mǎn)足:

因此，滿(mǎn)足上述條件且使||w||2最小的分類(lèi)面就是最優(yōu)分類(lèi)面。這兩類(lèi)樣本中離分類(lèi)面最近的點(diǎn)且平行于最優(yōu)分類(lèi)面的超平面上的訓(xùn)練樣本就是使式(2)式中等號(hào)成立的那些樣本，他們叫做支持向量(Support Vectors)。如圖1中所示

部分作業(yè)人員不懂各類(lèi)腳手架牌的含義，經(jīng)常出現(xiàn)到未經(jīng)驗(yàn)收合格的腳手架上作業(yè)，或者到掛黃牌的腳手架上作業(yè)不掛安全帶等違章情況。為此，項(xiàng)目部組織針對(duì)性的腳手架安全培訓(xùn)，全員覆蓋。同時(shí)，組織現(xiàn)場(chǎng)腳手架觀摩，明確告知作業(yè)人員各類(lèi)腳手架牌含義，避免違規(guī)行為再次發(fā)生。

根據(jù)上面的討論，最優(yōu)分類(lèi)超平面問(wèn)題可以表示成如下的約束優(yōu)化問(wèn)題:

3 非線(xiàn)性支持向量機(jī)

從上面的討論的最優(yōu)分類(lèi)超平面和廣義最優(yōu)分類(lèi)超平面看出，其最終的分類(lèi)決策函數(shù)中只包含待分類(lèi)樣本與訓(xùn)練樣本中的支持向量的內(nèi)積運(yùn)算(x·xi)，同樣，它的求解過(guò)程式中也只涉及訓(xùn)練樣本之間的內(nèi)積運(yùn)算(xi·xj)，可見(jiàn)，要解決一個(gè)特征空間中的最優(yōu)線(xiàn)性分類(lèi)問(wèn)題，我們只需要知道這個(gè)空間中的內(nèi)積運(yùn)算即可。如果一個(gè)問(wèn)題在其定義的空間不是線(xiàn)性可分的，這時(shí)可以考慮構(gòu)造新的特征向量，把問(wèn)題轉(zhuǎn)換到一個(gè)新的空間中，這個(gè)空間一般比原空間維數(shù)增加，但卻可以用線(xiàn)性判別函數(shù)實(shí)現(xiàn)原空間中的非線(xiàn)性判別函數(shù)。比如構(gòu)造y=[1xx2]T，就可以用g(y)=aTy的線(xiàn)性函數(shù)實(shí)現(xiàn)g(x)=c0+c1x+c2x2的二次判別函數(shù)，其中廣義權(quán)向量a=[c0,c1,c2]T。實(shí)際上，一般來(lái)說(shuō)，對(duì)于任意高次判別函數(shù)，都可以通過(guò)適當(dāng)?shù)淖儞Q轉(zhuǎn)化為另一空間中的線(xiàn)性判別函數(shù)來(lái)處理。把這種變換空間中的線(xiàn)性判別函數(shù)稱(chēng)作原問(wèn)題的廣義線(xiàn)性判別函數(shù)。但是，雖然這種變換理論上可以用簡(jiǎn)單的線(xiàn)性判別函數(shù)來(lái)解決十分復(fù)雜的問(wèn)題，但由于變換空間中的維數(shù)往往很高，容易陷入所謂維數(shù)災(zāi)難而使問(wèn)題變得實(shí)際上不可實(shí)現(xiàn)。因此，廣義線(xiàn)性判別函數(shù)的思想只在一些相對(duì)不十分復(fù)雜的非線(xiàn)性問(wèn)題中能夠應(yīng)用[6]。

按照廣義線(xiàn)性判別函數(shù)的思路，要解決一個(gè)非線(xiàn)性問(wèn)題，我們可以設(shè)法將它通過(guò)非線(xiàn)性變換轉(zhuǎn)換為另一個(gè)空間中的線(xiàn)性問(wèn)題，在這個(gè)空間中求最優(yōu)或廣義最優(yōu)分類(lèi)超平面?？紤]到廣義最優(yōu)分類(lèi)超平面的性質(zhì)，在這個(gè)變換空間中，我們只需進(jìn)行內(nèi)積運(yùn)算。而進(jìn)一步看，我們甚至沒(méi)有必要知道采用的非線(xiàn)性變換的形式，而只需要知道它的內(nèi)積運(yùn)算即可。只要變換空間中的內(nèi)積可以用原空間中的變量直接計(jì)算得到(通常是這個(gè)的)，則即使變換空間的維數(shù)增加很多，在其中求解最優(yōu)分類(lèi)面的問(wèn)題并沒(méi)有增加多少計(jì)算復(fù)雜度。

支持向量機(jī)的基本思想可以概括為:首先通過(guò)非線(xiàn)性變換將輸入空間變換到一個(gè)高維空間，然后在這個(gè)新空間中求取最優(yōu)線(xiàn)性分類(lèi)超平面，而這種非線(xiàn)性變換是通過(guò)定義適當(dāng)?shù)膬?nèi)積函數(shù)實(shí)現(xiàn)的[7]。SVM中不同的內(nèi)積核函數(shù)將形成不同的算法。目前研究最多的核函數(shù)主要有三類(lèi)，一是多項(xiàng)式核函數(shù)

二是徑向基函數(shù)(RBF)

三是sigmoid函數(shù)

由于徑向基函數(shù)可以逼近任意非線(xiàn)性函數(shù)，因此，本文選取徑向基函數(shù)作為支持向量機(jī)的核函數(shù)來(lái)進(jìn)行研究。

4 支持向量機(jī)與boosting算法的綜合建模

Boosting是20世紀(jì)90年代來(lái)提出的最有效的學(xué)習(xí)思想之一，它的思想起源于Valiant提出的PAC學(xué)習(xí)模型，valiant提出了弱學(xué)習(xí)和強(qiáng)學(xué)習(xí)的概念，認(rèn)為準(zhǔn)確率僅比隨機(jī)猜測(cè)略高的學(xué)習(xí)算法稱(chēng)為弱學(xué)習(xí)算法，識(shí)別準(zhǔn)確率很高并能在多項(xiàng)式時(shí)間內(nèi)完成的算法稱(chēng)為強(qiáng)學(xué)習(xí)算法。同時(shí)，Valiant首次提出了兩種算法的等價(jià)性問(wèn)題，即任意給定比隨機(jī)猜測(cè)略高的弱學(xué)習(xí)算法，是否可以將其提升為強(qiáng)學(xué)習(xí)算法?如果二者等價(jià)，那么只需找到一個(gè)比隨機(jī)猜測(cè)略高的弱學(xué)習(xí)算法就可以將其提升為強(qiáng)學(xué)習(xí)算法，而不必尋找很難獲得的強(qiáng)學(xué)習(xí)算法。1990年，Schapire最先構(gòu)造出一種多項(xiàng)式級(jí)的算法，對(duì)該問(wèn)題作出了證明，這就是最初的Boosting算法。1997年，F(xiàn)reund和Schapire提出了Adaboost算法[8]。

（1）初始化觀測(cè)權(quán)值 wi=1/N,i=1,2,…，N

(2)設(shè)定C，γ的初始值γini，和最大值γmax以及每次調(diào)整的步長(zhǎng) γstep。

（3）對(duì)于 m=1 到 M:

(a)使用權(quán)值wi，用支持向量分類(lèi)機(jī)Gm(X)擬合訓(xùn)練數(shù)據(jù)

(b)計(jì)算訓(xùn)練誤差 εm=∑i=1Nwim·(yi≠Gm(xi))

(c)假如 εm＞0.5,則 γ＜γmax，則 γ=γ+γstep返回（a）

(e)計(jì)算 αm=log((1-erm)/errm)

(f)置wi←w·iexp[αm·I（yi≠≠Gm(xi)）],i=1,2…，N

5 結(jié)束語(yǔ)

對(duì)于支持向量機(jī)來(lái)說(shuō)，參數(shù)取值不同，對(duì)應(yīng)的分類(lèi)器性質(zhì)以及推廣識(shí)別率也將有很大差別。本文應(yīng)用以徑向基函數(shù)(RBF)為核函數(shù)的支持向量機(jī)到統(tǒng)計(jì)學(xué)領(lǐng)域。除了選取模型參數(shù)外，怎樣選取重要屬性同樣重要。

支持向量機(jī)作為一種專(zhuān)門(mén)研究小樣本的學(xué)習(xí)方法，以統(tǒng)計(jì)學(xué)習(xí)理論作為堅(jiān)實(shí)的理論依據(jù)，基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化使其克服了傳統(tǒng)模式識(shí)別方法的過(guò)學(xué)習(xí)和陷人局部最小的缺點(diǎn)，具有很強(qiáng)的泛化能力和全局最優(yōu)性;采用核函數(shù)向高維空間映射時(shí)并沒(méi)有增加計(jì)算的復(fù)雜性，又有效地克服了維數(shù)災(zāi)難間題。許多統(tǒng)計(jì)分析方法對(duì)數(shù)據(jù)的分布有一定的要求，限制了它們的使用范圍,而SVM的理論模型無(wú)須預(yù)報(bào)變量和結(jié)果變量具有某種特定的分布。

此外，本文將支持向量機(jī)與時(shí)下最流行的Boosting算法結(jié)合，建立一個(gè)綜合的AdaBoost-SVM模型，盡管從理論意義上來(lái)說(shuō)，SVM這樣一種強(qiáng)學(xué)習(xí)算法不適合作為Boosting算法的基礎(chǔ)學(xué)習(xí)器，但在本文中，我們通過(guò)在每一次迭代過(guò)程中調(diào)節(jié)支持向量機(jī)的參數(shù)，使Boosting過(guò)程中的每一個(gè)支持向量分類(lèi)機(jī)精度都滿(mǎn)足只比隨機(jī)猜測(cè)略高這個(gè)要求，建立一個(gè)動(dòng)態(tài)的AdaBoost-SVM模型。

[1]鄧乃揚(yáng)，田英杰著.數(shù)據(jù)挖掘中的新方法——支持向量機(jī)[M].北京:科學(xué)出版社，2004.

[2]V.N.Vapnik.The Nature ofStatisticalLearning Theory[M].Newyork:Spring-Verlag，1998.

[3]張學(xué)工，關(guān)于統(tǒng)計(jì)學(xué)習(xí)與支持向量機(jī)[J].自動(dòng)化學(xué)報(bào)，2000，（1）.

[4]T.Hastie，R.Tibshirani，J.Friedman 著.范明，柴玉梅等譯. 統(tǒng)計(jì)學(xué)習(xí)基礎(chǔ)—數(shù)據(jù)挖掘原理、推理與預(yù)測(cè)[M].北京:電子工業(yè)出版社，2004.

[5]盧紋岱，吳喜之.SPSS for windows統(tǒng)計(jì)分析[M].北京:電子工業(yè)出版社，2006.

[6]鄧小文，支持向量機(jī)參數(shù)選擇方法分析[J]，福建電腦，2005,(11)

[7]M.H.Zhang，Q.S.Xu,Application of Boosting to Classification Problems in Chemometrics[J].Analytica Chimica Acta，2005，167～176.

[8]據(jù)旭，王浩.基于Boosting的支持向量組合分類(lèi)器[J].合肥工業(yè)大學(xué)學(xué)報(bào)，2006,(10).

[9]王強(qiáng)，沈永平，陳英武.支持向量機(jī)規(guī)則提取[J].國(guó)防科技大學(xué)學(xué)報(bào)，2006,(2).

[10]牛艷慶，胡寶清.給予模糊AdaBoost算法的支持向量回歸機(jī)[J].模糊系統(tǒng)與數(shù)學(xué)，2006,(4).