支持向量機算法原理

1、支持向量機算法理論與算法研究摘要支持向量機是建立在統(tǒng)計學(xué)習(xí)理論VC維理論和結(jié)構(gòu)風(fēng)險最小化原理基礎(chǔ)上的機器學(xué)習(xí) 方法。它在解決小樣本、非線性和高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，并在很大程 度上克服了 “維數(shù)災(zāi)難”和“過學(xué)習(xí)”等問題。此外，它具有堅實的理論基礎(chǔ)，簡單明了的 數(shù)學(xué)模型，因此，在模式識別、回歸分析、函數(shù)估計、時間序列預(yù)測等領(lǐng)域都得到了長足的 發(fā)展，并被廣泛應(yīng)用于文本識別、手寫字體識別、人臉圖像識別、基因分類及時間序列預(yù)測 等。標準的支持向量機學(xué)習(xí)算法問題可以歸結(jié)為求解一個受約束的二次型規(guī)劃問題。對于 小規(guī)模的二次優(yōu)化問題，禾I用牛頓法、內(nèi)點法等成熟的經(jīng)典最優(yōu)化算法便能夠很好的求

2、解。但是當訓(xùn)練集規(guī)模很大時，就會出現(xiàn)訓(xùn)練速度慢、算法復(fù)雜、效率低下等問題。目前一 些主流的訓(xùn)練算法都是將原有大規(guī)模的QP問題分解成一系列小的QP問題，按照某種迭代策略，反復(fù)求解小的QP問題，構(gòu)造出原有大規(guī)模 的QP問題的近似解，并使該近似解逐漸收斂到最優(yōu)解。但是如何對大規(guī)模的QP問題進行 分解以及如何選擇合適的工作集是當前訓(xùn)練算法所面臨的主要問題，并且也是各個算法優(yōu)劣 的表現(xiàn)所在。另外，現(xiàn)有的大規(guī)模問題訓(xùn)練算法并不能徹底解決所面臨的問題，因此，在原 有算法上進行合理的改進或研究新的訓(xùn)練算法勢在必行。本文首先對支持向量機的理論進行 系統(tǒng)的介紹，進而對當今SVM訓(xùn)練算法進行綜述，并對未來的研究方向

3、進行展望。 關(guān)鍵詞模式識別；支持向量機；支持向量分類；支持向量回歸1統(tǒng)計學(xué)習(xí)理論（SLT簡介131.1背景現(xiàn)實世界中存在大量我們尚無法準確認識但卻可以進行觀測的事物，如何從一些觀測數(shù)據(jù) （樣本）出發(fā)得出目前尚不能通過原理分析得到的規(guī)律，進而利用這些規(guī)律預(yù)測未來的數(shù)據(jù)，這 是統(tǒng)計模式識別（基于數(shù)據(jù)的機器學(xué)習(xí)的特例）需要解決的問題。統(tǒng)計是我們面對數(shù)據(jù)而又缺乏 理論模型時最基本的（也是唯一的）分析手段。Vapnik等人早在20世紀60年代就開始研究有 限樣本情況下的機器學(xué)習(xí)問題，但這些研究長期沒有得到充分的重視。近十年來，有限樣本情況 下的機器學(xué)習(xí)理論逐漸成熟起來，形成了一個較完善的SLT體系。而同

4、時，神經(jīng)網(wǎng)絡(luò)等較新興的 機器學(xué)習(xí)方法的研究則遇到一些重要的困難，比如如何確定網(wǎng)絡(luò)結(jié)構(gòu)的問題、過擬合與欠擬合問 題、局部極小點問題等。在這種情況下，試圖從更本質(zhì)上研究機器學(xué)習(xí)的SLT體系逐步得到重 視。1992- 1995年，Vapnik等在SLT勺基礎(chǔ)上發(fā)展了 SVI算法，在解決小樣本、非線性及 高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其它機器學(xué)習(xí)問題。 很多學(xué)者認為，它們正在成為繼模式識別和神經(jīng)網(wǎng)絡(luò)研究之后機器學(xué)習(xí)領(lǐng)域中新的研究熱點，并 將推動機器學(xué)習(xí)理論和技術(shù)有重大的發(fā)展。神經(jīng)網(wǎng)絡(luò)研究容易出現(xiàn)過擬合問題，是由于學(xué)習(xí)樣本 不充分和學(xué)習(xí)機器設(shè)計不合理的原因造成的，由于

5、此矛盾的存在，所以造成在有限樣本情況下：1）經(jīng)驗風(fēng)險最小不一定意味著期望風(fēng) 險最?。?）學(xué)習(xí)機器的復(fù)雜性不但與所研究的系統(tǒng)有關(guān)，而且要和有限的學(xué)習(xí)樣本相適應(yīng)。 SLT體系及其SVMJ法在解決“小樣本難題”過程中所取得的核函數(shù)應(yīng)用等方面的突出進展令 人鼓舞，已被認為是目前針對小樣本統(tǒng)計估計和預(yù)測學(xué)習(xí)的最佳理論。1.2原理Vapnik的SLT勺核心內(nèi)容包括下列四個方面：1）經(jīng)驗風(fēng)險最小化原則下統(tǒng)計學(xué)習(xí)一致性的條件；2)在這些條件下關(guān)于統(tǒng)計學(xué)習(xí)方法推廣性的界的結(jié)論；3)在這些界的基礎(chǔ)上建立的小樣本歸納推理原則；4)實現(xiàn)這些新的原則的實際方法(算法)。設(shè)訓(xùn)練樣本集為兇，yn,xn ,xRm,yR，其擬

6、合(建模)的數(shù)學(xué)實質(zhì)是從函數(shù)集中選 出合適的函數(shù)f(x)，使風(fēng)險函數(shù)：R f 二 XYW 一 f (x)2P(x, y) dxdy(1)為最小。但因其中的幾率分布函數(shù)P(x,為未知，上式無法計算，更無法求其極小。傳統(tǒng)的統(tǒng)計數(shù)學(xué)遂假定上述風(fēng)險函數(shù)可用經(jīng)驗風(fēng)險函數(shù)Rempf 代替：Rempg (y吟)2根據(jù)大數(shù)定律，式(2)只有當樣本數(shù)n趨于無窮大且函數(shù)集足夠小時才成立。這實際上是假定最小 二乘意義的擬合誤差最小作為建模的最佳判據(jù)，結(jié)果導(dǎo)致擬合能力過強的算法的預(yù)報能力反而降 低。為此 SLT用結(jié)構(gòu)風(fēng)險函數(shù)Rhf 代替Remp f ，并證明了 Rhf可用下列函數(shù)求極小而得：r“麗 2n /h+1)I

7、 n(6/4):.心、miinRempf + jj(3)此處n為訓(xùn)練樣本數(shù)目，S為VC維空間結(jié)構(gòu)，h為VC維數(shù)，即對函數(shù)集復(fù)雜性或者學(xué)習(xí) 能力的度量。1-為表征計算的可靠程度的參數(shù)。SLT要求在控制以VC維為標志的擬合能力上界(以限制過擬合)的前提下追求擬合精度。 控制VC維的方法有三大類：1拉大兩類樣本點集在特征空間中的間隔；2縮小兩類樣本點各自在特征空間中的分布范圍；3降低特征空間維數(shù)。一般認為特征空間維數(shù)是控制過擬合的唯一手段，而新理論強調(diào)靠前兩種手段可以保證在高維特征空間的運算 仍有低的VC維，從而保證限制過擬合。對于分類學(xué)習(xí)問題，傳統(tǒng)的模式識別方法強調(diào)降維，而SVM與此相反。對于特征

8、空間中兩類點不能靠超平面分開的非線性問題，SVM采用映照方法將其映照到更高維的空間，并求得最佳區(qū)分二類樣本點的超平面方程，作為判別未知樣本的判據(jù)。這樣，空間維數(shù)雖 較高，但VC維仍可壓低，從而限制了過擬合。即使已知樣本較少，仍能有效地作統(tǒng)計預(yù)報。對于回歸建模問題，傳統(tǒng)的化學(xué)計量學(xué)算法在擬合訓(xùn)練樣本時，將有限樣本數(shù)據(jù)中的誤差也 擬合進數(shù)學(xué)模型了。針對傳統(tǒng)方法這一缺點，SVR采用“；不敏感函數(shù)”，即對于用f (x)擬合目標值y時f(x)=wTx+b,目標值乂擬合在yi-wTx-b蘭e時，即認為進一步擬合 是無意義的。這樣擬合得到的不是唯一解，而是一組無限多個解。SVR方法是在一定約束條件 下，以w

9、2取極小的標準來選取數(shù)學(xué)模型的唯一解。這一求解策略使過擬合受到限制，顯著提高 了數(shù)學(xué)模型的預(yù)報能力。2支持向量分類(SVC算法2.1線性可分情形SVM!法是從線性可分情況下的最優(yōu)分類面(Optimal Hyperplane )提出的。所謂最優(yōu)分類面就是要求分類面不但能將兩類樣本點無錯誤地分開，而且要使兩類的分類空隙最大。 d維空間中線性判別函數(shù)的一般形式為gx =wtx b,分類面方程是wtx 0 我們將判別函數(shù)進行歸一化，使兩類所有樣本都滿足g x -1 ,此時離分類面最近的樣本的g(x =而要求分類面對所有樣本都能正確分類，就是要求它滿足1 yi (wtb) 1 _0,i =1,2, ,n

10、。(4)式(4)中使等號成立的那些樣本叫做支持向量(Support Vectors )。兩類樣本的分類空隙 (Margin)的間隔大?。篗argin因此，最優(yōu)分類面問題可以表示成如下的約束優(yōu)化問題，函數(shù)=2/ w即在條件(4)的約束下，求(6)的最小值。為此，可以定義如下的Lagra nge函數(shù)：nL(w,b, : ) wt w - ： J y/wk b)-1i 4其中，ai0為Lagrange系數(shù)，我們的問題是對w和b求Lagrange函數(shù)的最小值。把式(7)分別對w、b、： i求偏微分并令它們等于0，得：:Ln0= w i yi xi.：wi iyi:Ln0=y bid -i:L希0= i

11、 yi (w0 xi b) -1 = 0以上三式加上原約束條件可以把原問題轉(zhuǎn)化為如下凸二次規(guī)劃的對偶問題:n 1 n nmax 瓦 ai Z Zjy/xXj)i=12 i=1 j =1ajZ0,i =1,.，nn7為 a： yi=0s.t(8)I這是一個不等式約束下二次函數(shù)機制問題，存在唯一最優(yōu)解。若:*為最優(yōu)解，(9)nw*z“a*yiXii =1:*不為零的樣本即為支持向量，因此，最優(yōu)分類面的權(quán)系數(shù)向量是支持向量的線性組合4 o.*T.b可由約束條件aiyi (w x +b)-1=0求解，由此求得的最優(yōu)分類函數(shù)是(10)nf x 二 sgn(w ) x *b H sgn(* ai yixi

12、x b )*i=1sgn()為符號函數(shù)。2.2非線性可分情形當用一個超平面不能把兩類點完全分開時(只有少數(shù)點被錯分)，可以引入松弛變 戛(j 0, i 二行)，使超平面 wtx- b = 0滿足：y.(wTx +b)一耳(11)當0 1時樣本點*仍舊被正確分類，而當 1時樣本點*被錯分。為此，引入以下目標 函數(shù)：(w,)(12)其中C是一個正常數(shù)，稱為懲罰因子，此時SVK可以通過二次規(guī)劃(對偶規(guī)劃)來實現(xiàn)：1 maX 瓦 ai -瓦 E 閃口 j yiyj(x Xj ) i 二 2 i 二 j 生 s.t 0 蘭 ai蘭 C,i =1,.,n(13)n遲 aiyi =03支持向量機(SVM的核

13、函數(shù)若在原始空間中的簡單超平面不能得到滿意的分類效果，則必須以復(fù)雜的超曲面作為分界 面，SVMT法是如何求得這一復(fù)雜超曲面的呢？首先通過非線性變換g將輸入空間變換到一個高維空間，然后在這個新空間中求取最優(yōu)線 性分類面，而這種非線性變換是通過定義適當?shù)暮撕瘮?shù)(內(nèi)積函數(shù))實現(xiàn)的，令： TOC o 1-5 h z K*)彳(xj 區(qū))(14)用核函數(shù)K(Xi,Xj)代替最優(yōu)分類平面中的點積xt*，就相當于把原特征空間變換到了某一 新的特征空間，此時優(yōu)化函數(shù)變?yōu)椋簄n nQa 八 ai二二: i： j%yjK X ,Xj(15)i=12 i=1 j =1而相應(yīng)的判別函數(shù)式則為：f x=sgn(w )t

14、 (x) b =sga. yiK(Xi,X)n b )(16)i=1其中Xj為支持向量，X為未知向量，(16)式就是SVM在分類函數(shù)形式上類似于一個神經(jīng)網(wǎng) 絡(luò)，其輸出是若干中間層節(jié)點的線性組合，而每一個中間層節(jié)點對應(yīng)于輸入樣本與一個支持向 量的內(nèi)積，因此也被叫做支持向量網(wǎng)絡(luò)，如圖1圖1支持向量網(wǎng)絡(luò)預(yù)報未知樣本類別的示意圖Fig.1 The sketch map of support vector network to predict an unknown sample由于最終的判別函數(shù)中實際只包含未知向量與支持向量的內(nèi)積的線性組合，因此識別時的 計算復(fù)雜度取決于支持向量的個數(shù)。目前常用的核函數(shù)

15、形式主要有以下三類，它們都與已有的算法有對應(yīng)關(guān)系。(1)多項式形式的核函數(shù)，即Kx,n二&丁務(wù)1q，對應(yīng)SVM是一個q階多項式分類器。徑向基形式的核函數(shù)，即K(x,X.)=exp(-兇凹，對應(yīng)SVM是一種徑向基函數(shù)分 類器。S形核函數(shù)，如K(x5X.)=tanh(v(xTx)+C)5K U SVM實現(xiàn)的就是一個兩層的感知器神經(jīng)網(wǎng)絡(luò)， 只是在這里不但網(wǎng)絡(luò)的權(quán)值、而且網(wǎng)絡(luò)的隱層節(jié)點數(shù)目也是由算法自動確定的。4支持向量回歸(SVR方法SVR算法的基礎(chǔ)主要是名不敏感函數(shù)(名-insensitive function)和核函數(shù)算法。若將擬合的數(shù)學(xué)模型表達為多維空間的某一曲線，則根據(jù)；不敏感函數(shù)所得的結(jié)果

16、就是包絡(luò)該曲線和訓(xùn)練點的“；管道”。在所有樣本點中，只有分布在“管壁”上的那一部分樣本點 決定管道的位置。這一部分訓(xùn)練樣本稱為“支持向量” (support vectors) o為適應(yīng)訓(xùn)練樣本集 的非線性，傳統(tǒng)的擬合方法通常是在線性方程后面加高階項。此法誠然有效，但由此增加的可調(diào) 參數(shù)未免增加了過擬合的風(fēng)險。SVR采用核函數(shù)解決這一矛盾。用核函數(shù)代替線性方程中的線性項可以使原來的線性算法“非線性化”，即能作非線性回 歸。與此同時，弓進核函數(shù)達到了 “升維”的目的，而增加的可調(diào)參數(shù)卻很少，于是過擬合仍 能控制。 4.1線性回歸情形設(shè)樣本集為：力，音,y*xRn, y巳回歸函數(shù)用下列線性方程來表示

17、, f x 二 wtx b (17)其中C是設(shè)定的懲罰因子值，、Vapnik提出運用下列不敏感損耗函數(shù):0(18)最佳回歸函數(shù)通過求以下函數(shù)的最小極值得出，亦歹總)*卜十|主十立為松弛變量的上限與下限。for | 壓 otherwise通過下面的優(yōu)化方程:7113x(1,01*)= max-K 虬-C農(nóng)-L)-日尸=|(19)(20)在下列約束條件下:求解:11 1-zz24I 4 j 4 argmin JI-Z紀i1(1 (fr i由此可得拉格朗日方程的待定系數(shù)：i和*，從而得回歸系數(shù)和常數(shù)項:1w - 7-i 7” Xii =1b = -X Wxr - xs 12 r s r s(22)4

18、.2非線性回歸情形類似于分類問題，一個非線性模型通常需要足夠的模型數(shù)據(jù)，與非線性SV (方法相同，一個非線性映射可將數(shù)據(jù)映射到高維的特征空間中，在其中就可以進行線性回歸。運用核函 數(shù)可以避免模式升維可能產(chǎn)生的維數(shù)災(zāi)難，即通過運用一個非敏感性損耗函數(shù)，非線性SVR 勺解即可通過下面方程求出：(23)其約束條件為：(24)0a ; C. i= 1L ii=l由此可得拉格朗日待定系數(shù):i和*,回歸函數(shù)f(x )則為：(25)/(髯)二工(瓦-t7jxx)5 ChemSV應(yīng)用軟件介紹sv.以解決化學(xué)化工上問題為目的，我們參照國際文獻自編了包含SVM模塊的應(yīng)用軟件“ ChemSVM，其中SVM算法涉及到

19、凸二次規(guī)劃的求解，采用了序貫極小優(yōu)化 (Sequential Minimal Optimization ) 算法 如。由于SVM算法在應(yīng)用上不夠方便的地方主要是核函數(shù)及其參數(shù)如何選取的問題，為此，“ ChmSVM針對該問題上作了一些改進，即一方面在程序的操作界面上提供各種核函數(shù)及其參 數(shù)，給用戶自由選擇和研究的方便；另一方面，程序可用單純形優(yōu)化方法自動選出待選的核函數(shù)及其參數(shù)，并根據(jù)數(shù)據(jù)集留一法預(yù)報正確率最高的目標來確定最終計算 用核函數(shù)及其參數(shù)，從而建立推廣能力強的數(shù)學(xué)模型。以軟件使用上的方便性、算法上的先進性和 解決具體問題的有效性為目的，“ChemSVM軟件將不斷地發(fā)展和完善?！?Che

20、mSVM軟件提供了通用的支持向量機算法。在具體應(yīng)用問題上，還可以將其與數(shù)據(jù) 庫（含分門別類的數(shù)據(jù)表）、知識庫（含數(shù)據(jù)挖掘規(guī)則等）、原子參數(shù)（由系統(tǒng)自動采集）及其它 數(shù)據(jù)挖掘方法有機地集成起來。比如，“ChemSVM已與熔鹽相圖智能數(shù)據(jù)庫相融合，使SVM算法成為熔鹽相圖智能數(shù)據(jù)庫的有效的數(shù)據(jù)挖掘手段。這方面應(yīng)用成 果已另文報導(dǎo)在本刊有關(guān)SVM應(yīng)用的系列論文中22：。6應(yīng)用前景SLT和SVM算法之所以從20世紀90年代以來受到很大的重視，在于它們對有限樣本情況 下模式識別中的一些根本性問題進行了系統(tǒng)的理論研究，并且在此基礎(chǔ)上建立了一種較好的通用學(xué) 習(xí)算法。以往困擾很多機器學(xué)習(xí)方法的問題，比如模型選

21、擇與過擬合問題、非線性和維數(shù)災(zāi)難問 題、局部極小點問題等，在這里都得到了很大程度上的解決。而且，很多傳統(tǒng)的機器學(xué)習(xí)方法都可 以看作是SVM算法的一種實現(xiàn)，因而SLT和SVM被很多人視作研究機器學(xué)習(xí)問題的一個基本框架。一方面研究如何用這個新的理論框架解 決過去遇到的很多問題；另一方面則重點研究以SVM為代表的新的學(xué)習(xí)方法，研究如何讓這些理論和方法在實際應(yīng)用中發(fā)揮作用。SLT有比較堅實的理論基礎(chǔ)和嚴格的理論分析，但其中還有很多問題仍需人為決定。比如結(jié) 構(gòu)風(fēng)險最小化原則中的函數(shù)子集結(jié)構(gòu)的設(shè)計、SVM中的內(nèi)積函數(shù)（包括參數(shù)）的選擇等。尚沒有明確的理論結(jié)果指導(dǎo)我們?nèi)绾芜M行這些選擇。另外，除了在監(jiān)督模式識

22、別中 的應(yīng)用外，SLT在函數(shù)擬合、概率密度估計等機器學(xué)習(xí)問題以及在非監(jiān)督模式識別問題中的應(yīng)用也 是一個重要研究方向。我們認為，SLT和SVM算法（包括SVC和SVR有可能在化學(xué)化工領(lǐng)域得到深入和廣泛的 應(yīng)用，以往用人工神經(jīng)網(wǎng)絡(luò)、傳統(tǒng)統(tǒng)計模式識別和線性及非線性回歸等數(shù)據(jù)挖掘算法研究和處理的 化學(xué)化工數(shù)據(jù)都可能在應(yīng)用SVM算法后得到更好的處理結(jié)果23：。特別是樣本少、維數(shù)多的“小樣本難題”，應(yīng)用SVM算法建模會特別有效。可以預(yù)計，將來在分析化學(xué)的數(shù)據(jù)處理、化學(xué)數(shù)據(jù)庫的智能化、有機分子的構(gòu)效關(guān)系（QSARQSPR）分子和材料設(shè)計、試驗設(shè)計、化工生產(chǎn)優(yōu)化、以及環(huán)境化學(xué)、臨床化學(xué)、地質(zhì)探礦等多方 面都有

23、可能展開SLT和SVM算法的應(yīng)用研究，并取得良好效果。參考文獻Domine D., Devillers J., Chastrette M., Karcher W. Non-linear mappingfor structure-activity and structure-propertymodeli ng. Jour nal ofChemomatrics 1993, 7: 227-242Wang Ziyi, Jenq-Hwang, Kowalski Bruce R., ChemNets: Theory and Application, Analytical Chemistry, 1995,

24、67(9):1497-1504Ruffini R. et al., Using n eural n etwork for spri ngback mini mizati on ina channel formi ng process, SAE Trans. J. Mater. Manu facture, 1998, 107, 65Fuk un aga K. I ntroductio n to statistical pattern recog niti on. Academic.New York; 19725Che n Nia nyi（陳念貽），Qin Pei（欽佩），Che n Ruilia

25、 ng（陳瑞亮），LuWencong （陸文聰）， Applicatio n of Patter n Recog niti on in Chemistry and Chemical Engineering（模式識別在化學(xué)化工中的應(yīng)用），Peking （北京），Scie nee Publisher（科學(xué)出版社），2000Chen Nia nyi, Lu Wencong, Chemometric Methods Applied to In dustrial Optimizati on and Materials Optimal Desig n, Chemometrics and in tellig

26、e nt laboratory systems, 1999, 45, 329-333Chen Nianyi, Lu Wencong, Software Package “Materials Designer ” and its Application in Materials Research, IPMM 99, Hawaii, USA, July, 1999LU Wen co ng, YAN Li-che ng, CHEN Nia n-yi, Pattern Recog nition and ANNSApplied to the Formobility of Complex Idide,Jo

27、urnal of MolecularScie nee, 1995,11 （1） : 33Liu Liang （劉亮）， Bao Xinhua （包新華），F(xiàn)eng Jianxing （馮建星），Lu Wen co ng （陸文聰），Che n Nia nyi （陳念貽），Molecular Sievi ng of Pin aco lone（or 1-Aryletha none） Con ta ining 1H-1,2, 4-Triazole Group andTheir Reduced Products （ a -唑基-a -芳氧烷基頻哪酮（芳乙酮）及其醇式衍生物抗真菌 活性的分子篩選），Co

28、mputer and Applied Chemistry （計算機與應(yīng)用化學(xué)），2002，19 （4） :465Lu Wencong （陸文聰），Bao Xinhua （包新華），Wu Lan （吳蘭），Kong Jie（孔杰），Yan Licheng （閻立誠），Chen Nianyi （陳念貽），Studies on HierarchicalProjectio n Method Applied to Regularities of Formati on ofBi nary Complex Compou nd in MBr- M Br?System （二元漠化物系（MBr-lM Br?）中間 化合物形成規(guī)律的逐級投影法研究），Computer and Applied Chemistry（計算機與應(yīng)用化學(xué)），2002, 19：474Lu Wencong （陸文聰），F(xiàn)eng Jianxing （馮建星），Chen Nianyi （陳念貽）， Ternary Intermetallic Com