支持向量機(jī)技術(shù)綜述

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