《計(jì)算機(jī)硬件及網(wǎng)絡(luò)支持向量機(jī)》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)硬件及網(wǎng)絡(luò)支持向量機(jī)（34頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,支持向量機(jī)引導(dǎo),孫宗寶,2006年12月20日,哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心學(xué)術(shù)交流,11/13/2024,1,支持向量機(jī)引導(dǎo),孫宗寶,2006年12月20日,哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心學(xué)術(shù)交流,11/13/2024,2,內(nèi)容提要,概述,線性可分情況理論,線性不可分情況,支持向量機(jī)模型,核函數(shù),支持向量機(jī)網(wǎng)絡(luò),11/13/2024,3,SVM,簡(jiǎn)介,90年代中

2、期在統(tǒng)計(jì)學(xué)習(xí)理論的根底上開(kāi)展起來(lái)的一種機(jī)器學(xué)習(xí)方法 (Boser,Guyon,Vapnik),適合有限樣本(小樣本)問(wèn)題,在很大程度上解決了傳統(tǒng)方法如神經(jīng)網(wǎng)絡(luò)中存在的問(wèn)題，如過(guò)學(xué)習(xí)、非線性、多維問(wèn)題、局部極小點(diǎn)問(wèn)題等,統(tǒng)計(jì)學(xué)習(xí)理論和支持向量機(jī)被視為機(jī)器學(xué)習(xí)問(wèn)題的一個(gè)根本框架，傳統(tǒng)的方法都可以看作是SVM方法的一種實(shí)現(xiàn),有堅(jiān)實(shí)的理論根底和嚴(yán)格的理論分析,11/13/2024,4,概述,一、向量的內(nèi)積與超平面,11/13/2024,5,概述,二、最優(yōu)分類平面,11/13/2024,6,概述,二維數(shù)據(jù)最優(yōu)分類線的根本要求：,1、要能將兩類樣本無(wú)錯(cuò)誤的分開(kāi),即使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，理論上為零,2、要使兩類之

3、間的距離最大,也就是使margin最大，從而使實(shí)際風(fēng)險(xiǎn)最小,11/13/2024,7,概述,我們要做的是什么呢？,找到一個(gè)超平面(最優(yōu)分類面)，使得它能夠盡可能多的將兩類數(shù)據(jù)點(diǎn)正確的分開(kāi)，同時(shí)使分開(kāi)的兩類數(shù)據(jù)點(diǎn)距離分類面最遠(yuǎn)。,11/13/2024,8,H,H,2,H,1,最優(yōu)分類平面,為最優(yōu)分類平面的方程,11/13/2024,9,SVM原理之線性可分,設(shè)線性可分樣本集為(xi,yi),i=1,2,n,xRd,y+1,-1是類別標(biāo)號(hào)。,那么d維空間中線性判別函數(shù)的一般形式為:,g(x)=wx+b,分類面方程為:,wx+b=0 (1),11/13/2024,10,SVM原理之線性可分,將判別函

4、數(shù)進(jìn)行歸一化,使兩類所有樣本都滿足|g(x)|1,即,使離分類面最近的樣本的|g(x)|=1,這樣分類間隔就等于2/w,因此,間隔最大等價(jià)于使w(或w,2,)最小;,而,要求分類線對(duì)所有樣本正確分類,就是要求其滿足:,y,i,(wx,i,)+b-10,(i=1,2,n)(2),11/13/2024,11,SVM原理之線性可分,我們解決這樣問(wèn)題的思路是什么呢？,首要的就是設(shè)法找到解決問(wèn)題的數(shù)學(xué)模型！,我們的問(wèn)題是：,找到滿足上述式2、且使w2的分類面。,其實(shí)這個(gè)分類面就是最優(yōu)分類面！,11/13/2024,12,SVM原理之線性可分,支持向量SV在那呢？,能使式2,yi(wxi)+b-10,(i

5、=1,2,n),中等號(hào)成立的，也就是位于margin 上的樣本就是支持向量。,11/13/2024,13,SVM原理之線性可分,最優(yōu)分類平面求解的數(shù)學(xué)模型,我們的求解過(guò)程顯然是一個(gè)有 約束條件的優(yōu)化問(wèn)題：,即在式(2)的約束下,求函數(shù):,(w)=1/2w,2,=1/2(ww)(3),的最小值。,11/13/2024,14,SVM原理之線性可分,求解方法-Lagrange 乘子法,什么是Lagrange 乘子法？,看一個(gè)例子。,問(wèn)題：給你一塊面積固定等于a 的平方 板子，問(wèn)做成什么樣的長(zhǎng)方體盒子，它具有最大的體積。,11/13/2024,15,SVM原理之線性可分,Lagrange 乘子法,設(shè)長(zhǎng)

6、方體的三個(gè)棱長(zhǎng)為x，y，z，那么其體積f 為三個(gè)邊長(zhǎng)的乘積：,f(x,y,z)=xyz,本問(wèn)題要求外表積為a 的平方，于是長(zhǎng)方體的6面的面積可以寫成：,2xy+2xz+2yz=a2,即 2xy+2xz+2yz-a2=0,這個(gè)問(wèn)題轉(zhuǎn)化為了有約束條件的優(yōu)化問(wèn)題。,11/13/2024,16,SVM原理之線性可分,Lagrange 乘子法,解題方法為：,1 用拉格朗日方法制造一個(gè)新函數(shù),F,2 在,F,中放進(jìn)一個(gè)未知的常數(shù),C,得到：,F=xyz+C(2xy+2xz+2yz-a,2,),11/13/2024,17,SVM原理之線性可分,Lagrange 乘子法,F對(duì),x，y，z 的三個(gè)自變量的偏微分

7、分別為零，得到三個(gè)新方程式：,yz+2,C,(,y,+,z,),=,0,xz,+2,C,(,x,+,z,)=0,xy,+2,C,(,x,+,y,)=0,因?yàn)樽宰兞績(jī)H可能是正數(shù)，把上面的式子相除得,(,x/y,)=(,x,+,z,)/(,y,+,z,),(,y,/,z,)=(,x,+,y,)/(,x,+,z,),11/13/2024,18,SVM原理之線性可分,Lagrange 乘子法,由此得出只有各個(gè)自變量的值相等才可以維持上面的關(guān)系，再由約束條件得到它們的值是：,x=y=z=(a/6),11/13/2024,19,SVM原理之線性可分,構(gòu)造拉格朗日函數(shù):,L(w,b,a)=(ww),a,i,

8、y,i,(wx,i,)+b-1,其中:a,i,0為L(zhǎng)agrange系數(shù)。求式(3)的極小值就是對(duì)w和b求拉氏函數(shù)的極小值。求L對(duì)w和b的偏微分，并令其等于0,可轉(zhuǎn)化為對(duì)偶問(wèn)題:,在約束條件 a,i,y,i,=0,ai0,i=1,2,n之下對(duì),a,i,0求式(5)的最大值:,11/13/2024,20,SVM原理之線性可分,W(a)=ai-aiajyiyj(xi.xj)5,假設(shè)ai*為最優(yōu)解，那么,w*=i=1.n ai*yixi 6,即最優(yōu)分類面的權(quán)系數(shù)向量式訓(xùn)練樣本的線性組合。,11/13/2024,21,SVM原理之線性可分,這是一個(gè)不等式約束的二次函數(shù)極值問(wèn)題，存在唯一解，并且解必須滿足

9、(Kuhn-Tucker條件):,aiyi(w*xi+b)-1=0,i=1.n 7,顯然，只有支持向量的系數(shù)a,i,不為0,即只有支持向量影響最終的劃分結(jié)果。,這是為什么？,11/13/2024,22,SVM原理之線性可分,于是式6,w*=i=1.n ai*yixi,可以寫成：,w=,a,i,y,i,x,i,可以看出，只有支持向量影響最終的劃分結(jié)果,，,最優(yōu)分類面的權(quán)系數(shù)向量是訓(xùn)練樣本向量的線性組合。,8,11/13/2024,23,SVM原理之線性可分,假設(shè)ai*為最優(yōu)解,求解上述問(wèn)題后得到的最優(yōu)分類函數(shù)是:,f(x)=sgn(w*x)+b*=sgnai*yi(xix)+b*,其中:sgn(

10、)為符號(hào)函數(shù),b*是分類的閾值,可以由任意一個(gè)支持向量用式(2)求得,或通過(guò)兩類中任意一對(duì)支持向量取中值求得。對(duì)于給定的未知樣本x,只需計(jì)算sgn(wx+b),即可判定x所屬的分類。對(duì)于非支持向量ai 都為0。,11/13/2024,24,SVM原理之線性不可分,對(duì)于線性不可分的樣本,希望使誤分類的點(diǎn)數(shù)最小,為此在式(2)中引入松弛變量i0,即：,yi(wxi)+b-1+i0,(i=1,2,n)9,/yi(wxi)+b-10,(i=1,2,n)(2),11/13/2024,25,SVM原理之線性不可分,在式(9)中,對(duì)于給定的常數(shù)C,求出使,(w,)=(ww)+C i 10,取極小值的w,b,

11、這一優(yōu)化問(wèn)題同樣需要變換為用拉格朗日乘子表示的對(duì)偶問(wèn)題,變換的過(guò)程與前面線性可分樣本的對(duì)偶問(wèn)題類似,結(jié)果也幾乎完全相同,只是約束條件略有變化:,a,i,y,i,=0,(0a,i,C,i=1,2,n)(11),C反映了在復(fù)雜性和不可分樣本所占比例之間的折中。,11/13/2024,26,支持向量機(jī),如果用內(nèi)積K(x,x)代替最優(yōu)分類面中的點(diǎn)積,就相當(dāng)于把原特征空間變換到了某一新的特征空間,此時(shí)優(yōu)化函數(shù)變?yōu)?,W(a)=a,i,-a,i,a,j,y,i,y,j,K,(x,i,x,j,),相應(yīng)的判別函數(shù)也應(yīng)變?yōu)?,f(x)=sgn,a,i,*,y,i,k,(x,i,x)+b,*,11/13/2024

12、,27,支持向量機(jī),算法的其他條件均不變,這就是支持向量機(jī)。,所以，原問(wèn)題就轉(zhuǎn)化成了找SV的問(wèn)題，而求SV的過(guò)程就是解一個(gè),二次規(guī)劃,(有約束的)，二次規(guī)劃無(wú)局部極值，只有一個(gè)最值，所以SV的求解不會(huì)有 不收斂 或者 收斂到局部極小 的問(wèn)題。而VC維又保證了機(jī)器的容量，不可能過(guò)學(xué)習(xí)(因?yàn)闄C(jī)器的結(jié)構(gòu)已經(jīng)固定),具體的求解方法可以參考運(yùn)籌學(xué)中約束二次規(guī)劃的求解,11/13/2024,28,非線性分類面,非線性可分的數(shù)據(jù)樣本在高維空間有可能轉(zhuǎn)化為線性可分。,在訓(xùn)練問(wèn)題中，涉及到訓(xùn)練樣本的數(shù)據(jù)計(jì)算只有兩個(gè)樣本向量點(diǎn)乘的形式,使用函數(shù) ,將所有樣本點(diǎn)映射到高為空間，那么新的樣本集為,設(shè)函數(shù),內(nèi)核函數(shù)(Kernel function),11/13/2024,29,一個(gè)能實(shí)現(xiàn)非線性關(guān)系到線性關(guān)系變換的實(shí)例,取：,那么,11/13/2024,30,核函數(shù),11/13/2024,31,核函數(shù),Mercer條件,對(duì)于任意的對(duì)稱函數(shù)K(,x,x,)，它是某個(gè)特征空間中的內(nèi)積運(yùn)算的充分必要條件是，對(duì)于任意的(x)0且2(,x,)d,x,0,11/13/2024,32,支持向量網(wǎng)絡(luò),11/13/2024,33,通常的內(nèi)核函數(shù),線性內(nèi)核,多項(xiàng)式內(nèi)核,徑向基函數(shù)內(nèi)核(RBF),S形內(nèi)核,謝謝大家,!,11/13/2024,34,