1、實用標準文案支持向量機簡介摘要：支持向量機方法是建立在統計學習理論的 VC維理論和結構風險最小原理 基礎上的，根據有限的樣本信息在模型的復雜性（即對特定訓練樣本的學習精度） 和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以求獲得最 好的推廣能力。我們通常希望分類的過程是一個機器學習的過程。這些數據點 是n維實空間中的點。我們希望能夠把這些點通過一個n-1維的超平面分開。通常這個被稱為線性分類器。有很多分類器都符合這個要求。但是我們還希望找 到分類最佳的平面，即使得屬于兩個不同類的數據點間隔最大的那個面，該面亦 稱為最大間隔超平面。如果我們能夠找到這個面，那么這個分類器就稱為最大間

2、 隔分類器。關鍵字：VC理論結構風險最小原則學習能力1、SVM的產生與發展自1995年Vapnik在統計學習理論的基礎上提出 SVM作為模式識別的新方 法之后，SVM 一直倍受關注。同年，Vap nik和Cortes提出軟間隔（soft margin）SVM，通過引進松弛變量i度量數據Xi的誤分類（分類出現錯誤時i大 于0），同時在目標函數中增加一個分量用來懲罰非零松弛變量（即代價函數），SVM的尋優過程即是大的分隔間距和小的誤差補償之間的平衡過程；1996年，Vapnik等人又提出支持向量回歸 （Support Vector Regression，SVR）的方法 用于解決擬合問題。SVR同S

3、VM的出發點都是尋找最優超平面，但SVR的目的不 是找到兩種數據的分割平面，而是找到能準確預測數據分布的平面，兩者最終都轉換為最優化問題的求解；1998年，Weston等人根據SVM原理提出了用于解決多類分類的 SVM 方法(Multi-Class Support Vector Mach in es , Multi-SVM)，通過將多類分類轉化成二類分類，將SVM應用于多分類問題的判 斷：此外，在SVM算法的基本框架下，研究者針對不同的方面提出了很多相關 的改進算法。例如，Suykens提出的最小二乘支持向量機(Least SquareSupport Vector Machine ，LS SV

4、M)算法，Joachims 等人提出的 SVM-1ight ， 張學工提出的中心支持向量機(Central Support Vector Machine，CSVM)，Scholkoph和Smola基于二次規劃提出的v-SVM等。此后，臺灣大學林智仁(Lin Chih-Jen)教授等對SVM的典型應用進行總結，并設計開發出較為完善的SVM工 具包，也就是 LIBSVM(A Library for Support Vector Machines)。上述改進模型中，v-SVM是一種軟間隔分類器模型，其原理是通過引進參數 v,來調整支持 向量數占輸入數據比例的下限，以及參數 來度量超平面偏差，代替通常

5、依靠經 驗選取的軟間隔分類懲罰參數，改善分類效果；LS-SVM則是用等式約束代替傳統SVM中的不等式約束，將求解QP問題變成解一組等式方程來提高算法效率； LIBSVM是一個通用的SVM軟件包，可以解決分類、回歸以及分布估計等問題， 它提供常用的幾種核函數可由用戶選擇，并且具有不平衡樣本加權和多類分類等 功能，此外，交叉驗證(cross validation)方法也是LIBSVM對核函數參數選取問 題所做的一個突出貢獻；SVM-1ight的特點則是通過引進縮水(shrinking)逐步 簡化QP問題，以及緩存(caching)技術降低迭代運算的計算代價來解決大規模樣 本條件下SVM學習的復雜性

6、問題。2、支持向量機基礎2.1統計學習理論基礎與傳統統計學理論相比，統計學習理論 (Statistical learni ng theory或SLT)是一種專門研究小樣本條件下機器學習規律的理論。該理論是針對小樣本統計問題建立起的一套新型理論體系，在該體系下的統計推理規則不僅考慮了對漸近性 能的要求，而且追求在有限信息條件下得到最優結果。Vapnik等人從上世紀六、 七十年代開始致力于該領域研究，直到九十年代中期，有限樣本條件下的機器學 習理論才逐漸成熟起來，形成了比較完善的理論體系一一統計學習理論。統計學習理論的主要核心內容包括：(1)經驗風險最小化準則下統計學習一 致性條件；(2)這些條件

7、下關于統計學習方法推廣性的界的結論；(3)這些界的基礎上建立的小樣本歸納推理準則；(4)發現新的準則的實際方法(算法)。2.2 SVM原理SVM方法是20世紀90年代初Vapnik等人根據統計學習理論提出的一種新 的機器學習方法，它以結構風險最小化原則為理論基礎， 通過適當地選擇函數子 集及該子集中的判別函數，使學習機器的實際風險達到最小，保證了通過有限訓 練樣本得到的小誤差分類器，對獨立測試集的測試誤差仍然較小。支持向量機的基本思想是：首先，在線性可分情況下，在原空間尋找兩類樣 本的最優分類超平面。在線性不可分的情況下，加入了松弛變量進行分析，通過 使用非線性映射將低維輸入空間的樣本映射到高

8、維屬性空間使其變為線性情況， 從而使得在高維屬性空間采用線性算法對樣本的非線性進行分析成為可能，并在 該特征空間中尋找最優分類超平面。 其次，它通過使用結構風險最小化原理在屬 性空間構建最優分類超平面，使得分類器得到全局最優，并在整個樣本空間的期 望風險以某個概率滿足一定上界。其突出的優點表現在：(1)基于統計學習理論中結構風險最小化原則和 VC維 理論，具有良好的泛化能力，即由有限的訓練樣本得到的小的誤差能夠保證使獨 立的測試集仍保持小的誤差。(2)支持向量機的求解問題對應的是一個凸優化問 題，因此局部最優解一定是全局最優解。(3)核函數的成功應用，將非線性問題 轉化為線性問題求解。(4)分

9、類間隔的最大化，使得支持向量機算法具有較好的 魯棒性。由于SVM自身的突出優勢，因此被越來越多的研究人員作為強有力的 學習工具，以解決模式識別、回歸估計等領域的難題。3支持向量機相關理論3.1學習問題訓練器(S),條件概率分布函數F(y|x)，期望響應y和輸入向量x關系為F(x)y=f(x,v)學習機器(LM )，輸入-輸出映射函數集y=f(x,w) ，w W，W是參數集合學習問題就是從給定的函數集f(x,w),w W中選擇出能夠最好的逼近訓練器響應的函數。而這種選擇是基于訓練集的，訓練集由根據聯合分布F(x,y)=F(x)F(y|x)抽取的n個獨立同分布樣本(xi,yi) ,i=1,2,n組

10、成。3.2學習問題的表示學習的目的就是，在聯合概率分布函數 F(x,y)未知、所有可用的信息都包含在訓練集中的情況下，尋找函數f(x,wO)，使它(在函數類f(x,w)，(w W)R(w) L(y, f (x, w)dF(x, y)上最小化風險泛函3.3L(y, f (x,w)模式識別問題Remp ( w)經驗風險最小化原則(erM ) i0,右y f(x, w)1，若 y f(x, w)L(di, f (Xi, w)1、最小化經驗風險(訓練樣本錯誤率)：函數集 Fk=F(x,w);w Wk, k=1,2,nF1 F2 FnVC維：h1 wh2 w 韋n在使保證風險(風險的上界)最小的子集中選

11、擇使經驗風險最小的函數2、ERM的缺點用ERM準則代替期望風險最小化并沒有經過充分的理論論證，只是直觀上合理的想當然做法。這種思想卻在多年的機器學習方法研究中占據了主要地位。人們多年來將大部分注意力集中到如何更好地最小化經驗風險上。險，在很多問題中的樣本數目也離無窮大相去甚遠，如神經網絡3.4 Vapnik-Chervonenkis(VC)維1、定義：VC維是對由學習機器能夠實現的分類函數族的容量或表達力的測度。分類函數集= f(x,w):w W的VC維是能被機器對于分類函數的所有可能 二分標志無錯學習的訓練樣本的最大數量，描述了學習機器的復雜性2、學習機器實際風險的界其中n樣本數量，h是VC

12、維，是遞減函數兩種方法：神經網絡：保持置信范圍固定(通過選擇一個適當構造的機器)并最小化經 驗風險。支持向量機(SVM):保持經驗風險固定(比如等于零)并最小化置信范圍。結構風險最小化原則函數集 Fk=F(x,w);w Wk,k=1,2,nF1F2-FnVC維：hl wh2 w 韋n3.5支持向量回歸機SVM本身是針對經典的二分類問題提出的，支持向量回歸機( SupportVector Regression , SVR)是支持向量在函數回歸領域的應用。SVR與SVM分類有以下不同：SVM回歸的樣本點只有一類，所尋求的最優超平面不是使兩 類樣本點分得“最開”，而是使所有樣本點離超平面的“總偏差”

13、最小。這時樣 本點都在兩條邊界線之間，求最優回歸超平面同樣等價于求最大間隔。3.5.1 SVR基本模型對于線性情況，支持向量機函數擬合首先考慮用線性回歸函數f(x) x b擬合(Xi,yi),i1,2,., n，XiRn為輸入量，yR為輸出量，即需要確定和bjf= 0 詢巧-Pb + F=or 觀Q十b$ = Q-慎打+占-£>1.丄*卜一叢圖3-3a SVR結構圖圖3-3b不靈敏度函數懲罰函數是學習模型在學習過程中對誤差的一種度量， 一般在模型學習前己 經選定，不同的學習問題對應的損失函數一般也不同， 同一學習問題選取不同的 損失函數得到的模型也不一樣。常用的懲罰函數形式及密

14、度函數如表 3-1 o表3-1常用的損失函數和相應的密度函數損失函數名稱損失函數表達式 % i)噪聲密度p( i)文檔-不敏感12(1 )exp( | J )拉普拉斯1 |exp( i|)咼斯= exp(亍)魯棒損失2* 1 ( J： if,otherwise;2多項式分段多項式1p 1pIp 1,otherwise pHP, if2exp（才），if |exp(-2p2 (1/p)i), otherwiseexp( |)pexp( ), ifp(p 1exp(pi ), otherwise1,2,., n(3.11)式中，i,；是松弛因子，當劃分有誤差時,；都大于0，誤差不存在取0。這時，該

15、問題轉化為求優化目標函數最小化問題:i)(3.12)* 1R( , , ) 2式（3.12 ）中第一項使擬合函數更為平坦，從而提高泛化能力；第二項為減小誤 差；常數C 0表示對超出誤差 的樣本的懲罰程度。求解式（3.11）和式（3.12）可看出，這是一個凸二次優化問題，所以引入Lagrange函數：L 12nnC ( in*i)i iyi f(x)i 1* *i iyii 1nf(x)( i i* *i i)（3.13）i 1i 1式中，,i 0, i ,*0，為Lagrange 乘數，i 1,2,n。求函數L對b , i,i*的最小化，對的最大化，代入Lagrange函數得到對偶形式，最大化

16、函數:W(n(i i )( jj )(xi 為)1,j 1n* *(i i )yi( i i)i 1i 12i(3.14)其約束條件為:n*(3.15)(i i)0i 1*0 i, i CKuh n-Tucker定理，在鞍點處有：i i yi f (xi)0 i* i* yf(x) 0i i 0* *01 1 2求解式(3.14 )、( 3.15)式其實也是一個求解二次規劃問題，由得出.*0，表明ii7(3.16)*不能同時為零，還可以得出:i7(3.17)(C i) i 0* *(C i ) i 0從式(3.17 )可得出，當i C，或：C時，f(xj yi可能大于，與 其對應的x稱為邊界支

17、持向量(Boundary Support Vector， BSV)，對應圖 3-3a中虛線帶以外的點；當：(0,C)時，| f (xi) yi| ，即i 0， i* 0， 與其對應的Xj稱為標準支持向量(Normal Support Vector， NSV)，對應圖 3-3a中落在 管道上的數據點；當i=0， i =0時，與其對應的xi為非支持向 量，對應圖3-3a中 管道內的點，它們對w沒有貢獻。因此 越大，支持向量 數越少。對于標準支持向量，如果0 i C( i 0)，此時i 0，由式(3.16) 可以求出參數b:lb yi ( j j )Xj Xij 1yi ( j j 風 XiXj S

18、V同樣，對于滿足oi C( i 0)的標準支持向量，有b Yi( j j )Xj XXj SV般對所有標準支持向量分別計算b的值，然后求平均值，即1 *bYi( j j)K(Xj,xJ(3.18)NnSV 0 i CXj SVYi( j*)K(Xj,X)0 * CXj SV因此根據樣本點(Xi, yi)求得的線性擬合函數為n(3.19)*f (x) x b ( i i )xi x bi 1非線性svr的基本思想是通過事先確定的非線性映射將輸入向量映射的一個高維特征空間(Hilbert空間)中，然后在此高維空間中再進行線性回歸，從而取得在原空間非線性回歸的效果。首先將輸入量X通過映射:RnH映射

19、到高維特征空間H中用函數f(x)(x) b擬合數據區$)，1,2,.,n 。則二次規劃目標函數(3.14)式變為:式(3.20)* 1W(，) 12 in(i 11,ji)Yi中涉及到高維特征空間點積運算i)( j(Xi)j) ( (Xi)(Xj)i)(Xj)，而且函數(3.20)是未知的,高維的K(Xi,Xj)點積運算。稱KXXj)為核函數，核函數支持向量機理論只考慮高維特征空間的(Xi)(Xj)，而不直接使用函數的選取應使其為高維特征空間的一個點積， 核函數的類型有多種，常用的核函數 有:多項式核：k(x,x')( x,x；： d)P, p N,d 0；高斯核：k(x, x'

20、;)exp(屮;RBF 核：k(x,x')exp(B 樣條核：k(x, x') B2n i(x x');1 ' sin(N -)(x x)Fourier 核：k(x,x')21 ' sin (x x)因此式(3.20)變成W(4I*)-(i i)( j j) K(x x)2 i 1,j 1nn* *(i i )yi ( i i)i 1i 1(3.21 )可求的非線性擬合函數的表示式為：f(x) (x) bn(ii*)K(x,xJ bi 1(3.22)4、結論和討論以統計學習理論作為堅實的理論依據，SVM有很多優點，如基于結構風險 最小化，克服了傳

21、統方法的過學習(Overfitti ng )和陷入局部最小的問題，具 有很強的泛化能力；采用核函數方法，向高維空間映射時并不增加計算的復雜性， 又有效地克服了維數災難(Curse of Dimensionality)問題。但同時也要看到目 前SVM研究的一些局限性：(1) SVM的性能很大程度上依賴于核函數的選擇，但沒有很好的方法指導針對具體問題的核函數選擇;(2) 訓練測試SVM的速度和規模是另一個問題，尤其是對實時控制問題，速度是一個對SVM應用的很大限制因素；針對這個問題。Platt和Keerthi 等分別提出了 SMO(Sequential MinimizationOptimization)和改進的SMO方法，但還值得進一步研究；(3) 現有SVM理論僅討論具有固定懲罰系數C的情況，而實際上正負樣本 的兩種誤判往往造成損失是不同的。顯然，SVM