支持向量機-數(shù)學前沿

1、基于支持向量機的進展研究介紹摘要：支持向量機作為一種新型的短期預測的算法， 越來越受到人們的重視。 本文對其研究 的歷史進程給予了說明， 并介紹了一些目前的熱門研究算法以及其研究的思想。 重點介紹了 支持向量機的回歸算法，此種算法對于少數(shù)據(jù)的短期預測具有較好的預測效果。 最后本文對 其應用前景及發(fā)展方向予以了介紹。關鍵詞：支持向量機；回歸算法；短期預測0引言支持向量機（Support Vector Machine，簡稱 SVM是由Cortes&Vapnik 1995年首先提出 來的，是近年來機器學習研究的一項重大成果。它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應用到

2、函數(shù)擬合等其他機器學習問題中1。支持向量機方法是建立在統(tǒng)計學習理論的VC維理論和結構風險最小原理基礎上的，根據(jù)有限的樣本信息在模型的復雜性（即對特定訓練樣本的學習精度）和學習能力（即無錯誤 地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力2。它是一種監(jiān)督式學習的方法，它廣泛的應用于統(tǒng)計分類以及回歸分析中。支持向量機屬于一般化線性分類器。他們也可以認為是提克洛夫規(guī)范化（Tikhonov Regularization ）方法的一個特例 同。這族分類器的特點是他們能夠同時最小化經(jīng)驗誤差與最大化幾何邊緣區(qū)。因此支持向量機也被稱為最大邊緣區(qū)分類器。根據(jù)統(tǒng)計學習理論，如果數(shù)據(jù)服從某個（固定但

3、未知）分布，要 使機器的實際輸出與理想輸出之間的誤差盡可能小，則機器應當遵循結構風險最小化原理， 而不是經(jīng)驗風險最小化原理，通俗的說就是應當使錯誤概率的上界最小化。支持向量機正是這一理論的具體實現(xiàn)。與傳統(tǒng)的人工神經(jīng)網(wǎng)絡相比，支持向量機不僅結構簡單，而且各種技術性能尤其泛化能力明顯提高，這已經(jīng)被大量實驗證實5。目前，國內(nèi)對支持向量機的研究還剛剛起步，本文介紹支持向量機的一些新進展，希望引起大家的重視。1支持向量機1.1什么是支持向量機所謂支持向量是指那些在間隔區(qū)邊緣的訓練樣本點。這里的“機（machine ,機器）”實際上是一個算法。在機器學習領域，常把一些算法看作是一個機器。支持向量機（Sup

4、port vector mach in es ，SVM）與神經(jīng)網(wǎng)絡類似，都是學習型的機制，但與神 經(jīng)網(wǎng)絡不同的是SVM使用的是數(shù)學方法和優(yōu)化技術。支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。1.2支持向量機的思想支持向量機是數(shù)據(jù)挖掘的一項新技術，以統(tǒng)計學習理論為基礎，針對小樣本數(shù)據(jù)建立新的理論體系，追求在有限樣本下的最優(yōu)解。其核心思想就是利用核函數(shù)將輸入樣本空間映射 到高維特征空間，在這個空間中求一個最優(yōu)分類面，得到

5、輸入和輸出變量間的非線性關系。 它是一個凸二次優(yōu)化問題，適合解決小樣本問題， 并能夠推廣到函數(shù)擬合等其他的機器學習問題中來。1.3支持向量機的理論研究支持向量機的算法一經(jīng)提出，就得到國內(nèi)外學者的高度關注。學術界普遍認為它 是繼神經(jīng)網(wǎng)絡之后的一個新的研究方向。在短短的幾年里，取得了一系列的令人矚目 的研究成果。雖然支持向量機的發(fā)展時間很短，但是由于它的產(chǎn)生是基于統(tǒng)計學習理論的，因 此具有堅實的理論基礎。近幾年涌現(xiàn)出大量的理論研究成果，更為其應用研究奠定了 堅實的基礎。如Anthonyetal （1999）等人給出了關于硬領域支持向量機學習誤差的嚴格 理論界限，Shawe-Taylor （2000

6、）和Cristianini （ 2000）也給出了類似的關于軟領域支持 向量機和回歸情況下的誤差界限；West on etal （1998）和Vap nik （1998）等研究了支持向量機的泛化性能及其在多值分類和回歸問題的擴展問題；Smola（ 1998）和Schoelkopf（1999 ）提出了支持向量機一般意義下的損失函數(shù)數(shù)學描述；脊回歸是由Tikhonov（1963）提出的一種具有特殊形式的正則化網(wǎng)絡，Poggio et al。（ 1990），Poggio（ 1975）等將其應用到正則化網(wǎng)絡的學習中。Smola et al。（ 1999 ）研究了狀態(tài)空間中脊回歸的應用，Poggio e

7、t al ，（ 1990） Smola （ 1998） , Schoelkopf （ 1999 ）等討論了正則化網(wǎng)絡和支持向量機的關系。隨著支持向量機理論上的深入研究，出現(xiàn)了許多變種支持向量機，如Smola （ 1999）提出的用于分類和回歸的支持向量機。另外，一些學者還擴展了支持向量機概念，女口Man gasaria n （ 1999 ）等人通用支持向量機。2算法簡介2.1支持向量機的訓練算法支持向量機的最終求解問題歸結為一個有約束的二次型規(guī)劃問題?？梢岳脴藴识涡蛢?yōu)化技術來求解這個優(yōu)化問題，如牛頓法、共扼梯度法、內(nèi)點法等。但是，這些方法只適合 小樣本情況，當樣本數(shù)目較大時，算法復雜度會急

8、劇增加，而且占用極大的系統(tǒng)內(nèi)存。為降低計算資源、提高算法效率，很多研究者已經(jīng)提出了許多針對大規(guī)模樣本集的訓練算法：2.1.1塊算法1995年，cortes和vapnik提出了塊算法，其出發(fā)點是刪除矩陣中對應于Lagrange乘子為零的行和列不會對最終的結果產(chǎn)生影響。算法的每一步中都加入固定數(shù)量的樣本，同時保留上一步中剩下的具有非零 Lagrange乘子的樣本，以及M（事先確定的）個不滿足KKT條件的最差的 樣本：如果不滿足KKT條件的樣本數(shù)不足M個,則將不滿足條件的樣本全部加入。每個子問題都采用上一個子問題的結果作為初始值。最后所有非零Lagrange乘子都被找到，從而解決了原來的二次規(guī)劃問題

9、。當支持向量數(shù)遠遠小于樣本數(shù)時，算法效率較高。然而，當樣本集中的支持向量數(shù)目很大時，其算法復雜度仍然很大。2.1.2分解算法1997年，Osuna提出了分解算法（Decomposition Algorithm ），并將其應用于人臉檢測中。 其主要思想是將訓練樣本集分為工作集B和非工作集N,集合B中包含樣本個數(shù)至少和支持向量的個數(shù)一樣多。 作為子問題的樣本集進行 SVMH練。在每一個子問題的訓練過程中，N中的所有樣本相對應的Lagra nge乘子固定不變。子問題訓練結束后，用所得到的決策函數(shù)對N中的樣本進行測試，用違反KTT條件最嚴重的樣本替換初始工作集中Lagrange乘子為零的樣本。Osu

10、na分解算法關鍵在于每次迭代過程中如何選擇工作集B,如何確定替換策略，如何確定工作集B的大小。2.1.3序列最小優(yōu)化算法1998年，P1att提出了順序最小優(yōu)化算法 fsequential Mjnimal OptimizaIion ，SMO）。其基 本思想是將工作樣本集的規(guī)模減到了最小為兩個樣本，迭代過程中直接解析求解，提高了子問題的運算速度；此外，SM算法的工作集選擇采用啟發(fā)式，通過兩個嵌套的循環(huán)來尋找待優(yōu)化的樣本。外層循環(huán)尋找違反KKT條件的樣本，作為工作集的第一個樣本。內(nèi)層循環(huán)開始選擇進入工作集的第二個樣本，選擇的原則是盡量使這樣一對樣本取得最大的優(yōu)化步長。這種啟發(fā)式的樣本選擇策略大大加

11、快了算法的收斂速度。SM(算法主要耗時在KKT條件的判斷上。針對SM算法，S S Keerthi在判優(yōu)條件和循環(huán)策略上做出了重大改進，即在判別最優(yōu)條 件時用兩個閾值代替一個閾值，并且提出了確定工作集的方法，使得算法更加合理，速度更快。該算法在訓練線性支持向量機時，可以獲得非常好的性能，但在訓練非線性支持向量機時，算法速度會大大減慢。針對不同的問題，其計算復雜度差別很大。2.1.4增量式算法Callwenberghs (2001)提出了一種增量減量式學習方法，考慮了增加或減少一個訓練樣 本對Lagrange系數(shù)和支持向量機的影響，實驗表明算法是有效的。在減少一個樣本時，給出 了模型選擇算法LOO

12、(Leave one out)的形象解釋。Ralaiv01a(2001)提出了另一種增量式學習 方法。其思想為基于高斯核的局部特性，只更新對學習機器輸出影響最大的Lagra nge系數(shù)，以減少計算復雜度。另外，Suyke ns(2001)提出了一種周期最小二乘支持向量機用于時間序列的預測。Carozza et al(2000)和Xiao Rong et a1 . (2000)等人也分別提出了一些增量式學習 的支持向量機訓練算法。2.2支持向量機的回歸算法給定樣本集(, yi),人己疋,R , i =1, , , n。設線性回歸函數(shù)為：f (x)二 wT *x b最佳回歸函數(shù)可以轉化為求解下列函

13、數(shù)的最優(yōu)解:111min w2s.tf(x) yi 羋乜，i=1, , , nf (x) - yi 豈 i ； ,i =1, , , n式中C為懲罰因子；，：為松弛變量的上下限。這是一個凸二次問題，為求解這個最 優(yōu)化問題我們引入 Lagrange函數(shù):n)- aj； - f (n)im12 nL(w,b, i, i*,a,a*, , *)= o w -C ( i :2imnn-E ai+yi-f(x)-瓦曲+)i di 3分別對w , b ,求偏導，得到:昱丸，丄=0, 2=0 ,:w : bi根據(jù)上式求得：嚴nZ-耳)=0i厶n*“ w =瓦(aai )xC aj / i = 0, i =

14、1,，n最后我們在把上式代入 L函數(shù)表達式利用最小二乘法得到非線性預測的表達式為：nf(x)八佝a*)k(x,Xj) bi 12 2其中k(x,xj為核函數(shù)，本文選取的是高斯核函數(shù)：k(x,Xi)=exp(-|x-Xi 2：)。這是由于高斯核函數(shù)表示形式簡單，徑向對稱，光滑性好，任意階導數(shù)均存在。3支持向量機的應用及發(fā)展方向支持向量機的應用已經(jīng)引起了很多領域學者的重視。目前，支持向量機算法在模式識別、回歸估計、概率密度函數(shù)估計等方面都有廣泛應用。支持向量機最早在模式識別中獲得應用。貝爾實驗室率先在美國郵政手寫數(shù)字庫識別研究方面進行了試驗。試驗中，人工識別平均錯誤率是 2.5 %，用決策樹方法識

15、別錯誤率是16. 2%,采用兩層神經(jīng)網(wǎng)絡方法的錯誤率最小為5. 9%,專門針對該特定問題設計的五層神經(jīng)網(wǎng)絡錯誤率為5 .1 %,而用三種支持向量機方法得到的錯誤率分別為4.O%、4. 1 %和4. 4.2 %,且是直接采用16*16的字符點陣作為輸入，這表明了支持向量機方法具有良好的性能。MIT用支持向量機進行的人臉檢測實驗也取得了良好效果，通過直接訓練非線性SVM分類器進行人臉與非人臉的分類，取得了較好效果。 支持向量機也被廣泛地應用于圖像處理，在圖像分割(Reyna , 2000)、圖像檢測(Keren , 2001; Vailaya , 2002)和圖像檢索(Timl , 2000; G

16、uo, 2002)等方面都得到了良好應用。支持向量機還被用于遙感圖像分析(Brown , 2000)。語音識別也是支持向量機的應用領域(Xin Don &2001)。其它模式識別實驗還包括文本字體識別(Balllma nn , 2002)、人臉識別(Kim , 2001)、三維物體識別(Schwe nkcr, 2001)等。支持向 量機在工業(yè)領域的應用研究正逐漸受到研究者的重視。Drezet (1998)將支持向量機用于系統(tǒng)辨識，進行線性和非線性動態(tài)系統(tǒng)的辨識。de Kruif(2001)將支持向量機用于前饋學習控制，Suyke ns(2001)將最小二乘支持向量機應用于非線性系統(tǒng)的最優(yōu)控制。

17、Chetsky(1999)將支持向量機應用于內(nèi)燃機故障的診斷。Gao Junfen g(2002)也利用支持向量機對工業(yè)過程的故障診斷進行了應用研究，并獲得了較高的診斷率。此外，支持向量機在生物發(fā)酵、化工領域、電力 系統(tǒng)短期負荷預測等領域也得到了良好的應用，并在解決數(shù)據(jù)挖掘、 概率密度估計等其它應用問題中也顯示了良好性能。4總結在短短的幾年中，針對支持向量機的研究，從理論到應用都取得了許多可喜進展。但也必須看到，人們對統(tǒng)計學習理論以及基于該理論框架下的支持向量機的研究，還處于比較初級的階段，依然存在大量富有挑戰(zhàn)性的理論和應用問題需要解決。盡管目前尚無法肯定統(tǒng)計學習理論及其理論框架下的支持向量機在理論和應用研究方面將有多大的突破性成果，但可以肯定的是，支持向量機是一個很有發(fā)展前途的研究方向。 盡管目前支持向量機在工業(yè)過程控制領域的應用研究還比較少， 但是它所表現(xiàn)出來的優(yōu) 良性能， 預示著其將在工業(yè)控制領域大放異彩。 支持向量機并非是解決復雜機器學習問題的 唯一選擇， 但該方法一經(jīng)出現(xiàn)就引起大量國內(nèi)外學者的高度關注， 并得以迅速發(fā)展。 這與其 在工程應用中的適用性以及該理論和技術的日漸成熟化、系統(tǒng)化是分不開