支持向量機技術綜述

支持向量機技術綜述

0支持向量機簡介基于數(shù)據(jù)的機器學習是現(xiàn)代智能技術的一個重要方面。我們從觀察數(shù)據(jù)（樣本）開始找到規(guī)律，并使用這些規(guī)律預測未來數(shù)據(jù)或未觀察數(shù)據(jù)的預測。傳統(tǒng)的機器學習的神經(jīng)網(wǎng)絡方法基于經(jīng)驗風險最小化原則(EmpiricalRiskMinimization,簡稱ERM),泛化能力較差,其網(wǎng)絡結(jié)構(gòu)選擇存在過學習和局部極小點等問題,目前無法克服。支持向量機(SVM)是Vapnik等人提出的一類新型機器學習方法,是以統(tǒng)計學習理論為基礎的,因而具有嚴格的理論和數(shù)學基礎,與神經(jīng)網(wǎng)絡的學習方法相比,支持向量機是基于結(jié)構(gòu)風險最小化(StructuralRiskMinimization)原則,保證了學習機器具有良好的泛化能力,由于支持向量算法最終可轉(zhuǎn)化為凸優(yōu)化問題,保證了算法的全局最優(yōu)性,避免了神經(jīng)網(wǎng)絡無法解決的局部最小問題。由于其出色的學習性能,該技術已經(jīng)成為機器學習界的研究熱點,隨著研究的深入,SVM已推廣到多類分類問題中,并展現(xiàn)了良好的學習和泛化性能。文中介紹用于分類的支持向量機的理論基礎,其次提出了支持向量機的分類算法,并分析了目前支持向量機存在的一些問題,對其應用前景進行了展望。1基于erm準則的學習方法機器學習的目的是根據(jù)給定的訓練樣本求對某系統(tǒng)的輸入輸出之間依賴關系的估計,使它能夠?qū)ξ粗獢?shù)據(jù)做出盡可能準確的估計。機器學習問題可以形式化地表示為:輸入變量與輸出變量之間存在某種未知依賴關系,即存在一個未知的聯(lián)合概率p(x,y),機器學習根據(jù)n個獨立同分布觀測樣本:(x1,y1),(x2,y2),…,(xn,yn)(1)從給定的函數(shù)集F(x,w)中選擇具有最佳權(quán)值向量w的函數(shù)對依賴關系進行估計,使實際響應的“最佳”逼近。函數(shù)逼近的質(zhì)量常用損失函數(shù)或者偏差函數(shù)L(y,F(x,w))表示。損失函數(shù)L(y,F(x,w))的期望值定義為風險泛函:R(w)=∫L(y,F(x,w))dp(x,y)(2)式中,p(x,y)是輸入向量x和期望向量y的聯(lián)合概率分布。學習的目的就是使風險函數(shù)最小。式(2)定義的期望風險函數(shù)最小化必須依賴關于聯(lián)合概率p(x,y)的信息。但是,在實際的機器學習問題中,只能利用樣本式(1)的信息,因此期望風險函數(shù)并無法直接計算和最小化。根據(jù)概率論中大數(shù)定理的思想,人們自然想到用算術平均代替式(2)中的數(shù)學期望,于是定義Remp(w)=1ΝΝ∑i=1L(yiRemp(w)=1N∑i=1NL(yi;F(xi,w))(3)來逼近式(2)定義的期望風險函數(shù)。由于Remp(w)是用已知的訓練樣本(即經(jīng)驗數(shù)據(jù))定義的,因此稱作經(jīng)驗風險(EmpiricalRiskMinimization,簡稱ERM)。但實際上得到的樣本數(shù)是有限的,在樣本數(shù)目有限的情況下,不能保證有好的預測效果,因此,需要一種能夠指導人們在小樣本情況下建立有效的學習和推廣性理論。根據(jù)統(tǒng)計學習理論,在二分類的情況下,經(jīng)驗風險和實際風險之間以概率1-η存在如下關系:R(w)≤Remp(w)+√|h(ln(2n/h)+1)-ln(η/4)n|(4)R(w)≤Remp(w)+∣∣h(ln(2n/h)+1)?ln(η/4)n∣∣???????????????√(4)其中,h是VC維,n是樣本數(shù)。上式表明,學習機的實際風險由經(jīng)驗風險和置信區(qū)間兩部分組成,它和學習集的VC維和訓練樣本數(shù)有關。可以簡單地表示為:R(w)=Remp(w)+>(h/n)(5)上式表明,在有限訓練樣本的情況下,即使Remp(w)較小,也不能保證真實風險R(w)取最小值。因此,希望找一種新的方法使R(w)最小。ERM準則只強調(diào)經(jīng)驗風險最小(訓練誤差),沒有最小化置信范圍值,因此基于ERM準則的學習方法的學習能力強,但泛化能力較差,導致出現(xiàn)過學習現(xiàn)象,例如神經(jīng)網(wǎng)絡。最大化泛化能力不僅需要最小化經(jīng)驗風險,而且應最小化置信范圍值?；诖怂枷?統(tǒng)計學習理論提出一種新的策略,即把函數(shù)集構(gòu)造為一個函數(shù)子集序列,使各個子集按照VC維的大小排列,在每個子集中尋找最小經(jīng)驗風險,在子集間折衷考慮經(jīng)驗風險和置信范圍,取得實際經(jīng)驗風險最小,這種思想稱作結(jié)構(gòu)風險最小化或有序風險最小化(StructuralRiskMinimization,簡稱SRM)準則,如圖1所示。SVM是結(jié)構(gòu)風險最小化思想的具體實現(xiàn),它不像神經(jīng)網(wǎng)絡等傳統(tǒng)方法那樣以訓練誤差最小化作為優(yōu)化目標,而是以訓練誤差作為優(yōu)化問題的約束條件,以置信范圍值最小化作為優(yōu)化目標。2支持向量機用于排序2.1基于非線性映射的方法定義最優(yōu)線性超平面,并把尋找最優(yōu)線性超平面的算法歸結(jié)為求解一個凸規(guī)劃問題。進而基于Mercer核展開定理,通過非線性映射φ,把樣本空間映射到一個高維乃至于無窮維的特征空間(Hilbert空間),使在樣本空間中可以應用線性學習機的方法解決樣本空間中的高度非線性分類問題。簡單地說就是升維和線性化。2.2最優(yōu)超平面的定義支持向量機是從線性可分情況下的最優(yōu)分類面發(fā)展而來的,也是統(tǒng)計學習理論中最實用的部分,考慮如圖2的一個用某特征空間的超平面對給定訓練數(shù)據(jù)集作二類分類的問題。給定一組訓練樣本集(x1,y1),(x2,y2),…,(xl,yl),其中xi∈RN為N維向量,yi∈{-1,1}在線性可分的情況下,在特征空間中可以構(gòu)造多個分割平面(如:H1,H2…),這個超平面被定義為:(w·x)+b=0(6)同時,這個分類面能將兩類(1,-1)無誤差地完全分開,即滿足:(w·xi)+b≥1,forallxi∈1(w·xi)+b≤1,forallxi∈-1(7)在所有的分類面內(nèi),要尋找的是最優(yōu)超平面,這個最優(yōu)超平面是指滿足兩類的分類空隙dist最大,即每類距離超平面最近的樣本到超平面的距離之和最大。這個距離被稱為邊(Margin),可以證明:dist=2∥w∥(8)dist=2∥w∥(8)根據(jù)以上分析,求解最優(yōu)超平面就相當于在式(7)的約束條件下,求式(8)的最大值,這樣建立線性支持向量機的問題轉(zhuǎn)化為求解如下的一個二次凸規(guī)劃問題:{min12∥w∥2s.t.yi((w?xi)+b)≥1(9){min12∥w∥2s.t.yi((w?xi)+b)≥1(9)該約束優(yōu)化問題可以用Lagrange方法求解,得到最優(yōu)超平面決策函數(shù)為:Μ(x)=sgn(l∑i=1α*iyi(x?xi)+b*)(10)M(x)=sgn(∑i=1lα?iyi(x?xi)+b?)(10)根據(jù)Vapnik等的分析,判定分類面函數(shù)的VC維存在如下的定理:假設訓練樣本完全包含在一個最大直徑為Dmax的球內(nèi),不同類別樣本之間的最小邊際距離是Mmin,則分類面函數(shù)的VC維h滿足h≤D2max2max/M2min2min+1(11)可見,SVM通過最大化邊際距離Mmin,實現(xiàn)對VC維大小的控制,降低模型復雜度,從而體現(xiàn)SRM原理。2.3最優(yōu)超平面函數(shù)考慮到可能存在一些樣本不能被超平面正確分類,即對線性不可分情況,可以引入松弛變量ξi≥0,i=1,2,…,l,得到新的凸規(guī)劃問題:{min12∥w∥2+Cl∑i=1ξis.t.yi((w?xi)+b)≥1-ξi(i=1,?,l)ξi≥0(i=1,?,l)(12)求解問題(12)與求解問題(9)本質(zhì)上是一樣的。得到的最優(yōu)超平面決策函數(shù)仍然為:Μ(x)=sgn(l∑i=1α*iyi(x?xi)+b*)對于多類線性分類問題的一種解決辦法式把它轉(zhuǎn)化為多個兩類線性分類問題解決。K類分類問題可以轉(zhuǎn)化為K個二類劃分問題。其中每個二類劃分都是判斷樣本點屬于第i類或不屬于第i類。2.4支持向量機的mercer函數(shù)對于空間L內(nèi)非線性分類問題,可以通過一非線性變換Φ(x),將數(shù)據(jù)x從原空間L映射到一個高維特征空間H,再在空間H建立最優(yōu)分類面。這時的分類函數(shù)是:Μ(x)=sgn((w*?Φ(x))+b*)=sgn(∑S.V.α*iyi(Φ(xi)?Φ(x))+b*)(13)這里只是用Φ(x)和Φ(xi)代替了x和xi,因此計算過程相同。根據(jù)Mercer定理知由點積定義的核必是Mercer核:K(x,y)=(Φ(x)·Φ(y)),則上式可以化簡為:Μ(x)=sgn(∑S.V.α*iyiΚ(xi,x)+b*)(14)這種核函數(shù)的變換處理,為支持向量機提供了極大的靈活性,使其有了更廣泛的應用范圍。常見的核函數(shù)類型有:多項式核函數(shù)、徑向基函數(shù)RBF、樣條核函數(shù)。3支持向量機簡介支持向量機是基于統(tǒng)計學習理論的新的機器學習方法,具有嚴格的理論基礎,能夠較好地解決小樣本、非線性、高維數(shù)和局部最小點等問題,在許多問題上它有著其他統(tǒng)計學習方法難以比擬的優(yōu)越性,支持向量機在模式識別(字符識別、文本自動分類、人臉檢測、頭的姿態(tài)識別)、函數(shù)逼近、時間序列預測、故障識別和預測、信息安全、電力系統(tǒng)及電力電子等方面都有很好的應用前景,因此成為20世紀90年代末發(fā)展最快的研究方向之一。文中深入推導了用于解決分類問題的S