支持向量機(jī)引導(dǎo)課件

2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心1支持向量機(jī)引導(dǎo)孫宗寶2006年12月20日哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心學(xué)術(shù)交流2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心2內(nèi)容提要概述線性可分情況理論線性不可分情況支持向量機(jī)模型核函數(shù)支持向量機(jī)網(wǎng)絡(luò)2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心3SVM簡(jiǎn)介90年代中期在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上發(fā)展起來(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í)的理論基礎(chǔ)和嚴(yán)格的理論分析2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心4概述一、向量的內(nèi)積與超平面

2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心5概述二、最優(yōu)分類平面2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心6概述二維數(shù)據(jù)最優(yōu)分類線的基本要求：

1、要能將兩類樣本無(wú)錯(cuò)誤的分開即使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，理論上為零

2、要使兩類之間的距離最大也就是使margin最大，從而使實(shí)際風(fēng)險(xiǎn)最小2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心7概述我們要做的是什么呢？找到一個(gè)超平面(最優(yōu)分類面)，使得它能夠盡可能多的將兩類數(shù)據(jù)點(diǎn)正確的分開，同時(shí)使分開的兩類數(shù)據(jù)點(diǎn)距離分類面最遠(yuǎn)。2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心8HH2H1最優(yōu)分類平面為最優(yōu)分類平面的方程2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心9SVM原理之線性可分

設(shè)線性可分樣本集為(xi,yi),i=1,2,…,n,x∈Rd,y∈{+1,-1}是類別標(biāo)號(hào)。

則d維空間中線性判別函數(shù)的一般形式為:

g(x)=w·x+b

分類面方程為:

w·x+b=0(1)2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心10SVM原理之線性可分

將判別函數(shù)進(jìn)行歸一化,使兩類所有樣本都滿足|g(x)|≥1,即,使離分類面最近的樣本的|g(x)|=1,這樣分類間隔就等于2/‖w‖,因此間隔最大等價(jià)于使‖w‖(或‖w‖2)最小;而要求分類線對(duì)所有樣本正確分類,就是要求其滿足:

yi[(w·xi)+b]-1≥0,(i=1,2,…,n)(2)2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心11SVM原理之線性可分我們解決這樣問(wèn)題的思路是什么呢？首要的就是設(shè)法找到解決問(wèn)題的數(shù)學(xué)模型！我們的問(wèn)題是：找到滿足上述式（2）、且使‖w‖2的分類面。其實(shí)這個(gè)分類面就是最優(yōu)分類面！2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心12SVM原理之線性可分支持向量（SV）在那呢？能使式（2）

yi[(w·xi)+b]-1≥0,(i=1,2,…,n)中等號(hào)成立的，也就是位于margin上的樣本就是支持向量。2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心13SVM原理之線性可分最優(yōu)分類平面求解的數(shù)學(xué)模型我們的求解過(guò)程顯然是一個(gè)有約束條件的優(yōu)化問(wèn)題：即在式(2)的約束下,求函數(shù):φ(w)=1/2‖w‖2=1/2(w·w)(3)

的最小值。

2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心14SVM原理之線性可分求解方法---Lagrange乘子法

什么是Lagrange乘子法？看一個(gè)例子。問(wèn)題：給你一塊面積固定（等于a

的平方）板子，問(wèn)做成什么樣的長(zhǎng)方體（盒子），它具有最大的體積。2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心15SVM原理之線性可分Lagrange乘子法設(shè)長(zhǎng)方體的三個(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)題。2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心16SVM原理之線性可分Lagrange乘子法解題方法為：

1用拉格朗日方法制造一個(gè)新函數(shù)F

2在F中放進(jìn)一個(gè)未知的常數(shù)C

得到：

F=xyz+C(2xy+2xz+2yz-a2)2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心17SVM原理之線性可分Lagrange乘子法

F對(duì)x，y，z的三個(gè)自變量的偏微分分別為零，得到三個(gè)新方程式：

yz+2C(y+z)=0

xz+2C(x+z)=0

xy+2C(x+y)=0因?yàn)樽宰兞績(jī)H可能是正數(shù)，把上面的式子相除得

(x/y)=(x+z)/(y+z)(y/z)=(x+y)/(x+z)2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心18SVM原理之線性可分Lagrange乘子法由此得出只有各個(gè)自變量的值相等才可以維持上面的關(guān)系，再由約束條件得到它們的值是：

x=y=z=(a/√6)2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心19SVM原理之線性可分構(gòu)造拉格朗日函數(shù):L(w,b,a)=(w·w)—∑ai{yi[(w·xi)+b]-1}

其中:ai>0為L(zhǎng)agrange系數(shù)。求式(3)的極小值就是對(duì)w和b求拉氏函數(shù)的極小值。求L對(duì)w和b的偏微分，并令其等于0,可轉(zhuǎn)化為對(duì)偶問(wèn)題:

在約束條件aiyi=0,ai≥0,i=1,2,…,n之下對(duì)

ai〉0求式(5)的最大值:2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心20SVM原理之線性可分

W(a)=ai

-aiajyiyj(xi.xj)（5）若ai*為最優(yōu)解，則w*=∑i=1..nai*yixi

（6）即最優(yōu)分類面的權(quán)系數(shù)向量式訓(xùn)練樣本的線性組合。2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心21SVM原理之線性可分這是一個(gè)不等式約束的二次函數(shù)極值問(wèn)題，存在唯一解，并且解必須滿足(Kuhn-Tucker條件):ai[yi(w*xi+b)-1]=0,i=1..n

（7）

顯然，只有支持向量的系數(shù)ai不為0,

即只有支持向量影響最終的劃分結(jié)果。

這是為什么？

2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心22SVM原理之線性可分于是式（6）

w*=∑i=1..nai*yixi可以寫成：w=aiyixi

可以看出，只有支持向量影響最終的劃分結(jié)果，最優(yōu)分類面的權(quán)系數(shù)向量是訓(xùn)練樣本向量的線性組合。

（8）2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心23SVM原理之線性可分若ai*為最優(yōu)解,求解上述問(wèn)題后得到的最優(yōu)分類函數(shù)是:f(x)=sgn{(w*·x)+b*}=sgn{ai*yi(xi·x)+b*}其中:sgn()為符號(hào)函數(shù),b*是分類的閾值,可以由任意一個(gè)支持向量用式(2)求得,或通過(guò)兩類中任意一對(duì)支持向量取中值求得。對(duì)于給定的未知樣本x,只需計(jì)算sgn(w?x+b),即可判定x所屬的分類。對(duì)于非支持向量ai

都為0。2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心24SVM原理之線性不可分對(duì)于線性不可分的樣本,希望使誤分類的點(diǎn)數(shù)最小,為此在式(2)中引入松弛變量ξi≥0,即：

yi[(w·xi)+b]-1+ξi≥0,(i=1,2,…,n)（9）

//yi[(w·xi)+b]-1≥0,(i=1,2,…,n)(2)2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心25SVM原理之線性不可分在式(9)中,對(duì)于給定的常數(shù)C,求出使

φ(w,ξ)=(w·w)+C{ξi

}（10）取極小值的w,b,這一優(yōu)化問(wèn)題同樣需要變換為用拉格朗日乘子表示的對(duì)偶問(wèn)題,變換的過(guò)程與前面線性可分樣本的對(duì)偶問(wèn)題類似,結(jié)果也幾乎完全相同,只是約束條件略有變化:aiyi=0,(0≤ai≤C,i=1,2,…,n)(11)C反映了在復(fù)雜性和不可分樣本所占比例之間的折中。

2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心26支持向量機(jī)如果用內(nèi)積K(x,x′)代替最優(yōu)分類面中的點(diǎn)積,就相當(dāng)于把原特征空間變換到了某一新的特征空間,此時(shí)優(yōu)化函數(shù)變?yōu)?

W(a)=ai-aiajyiyjK(xi·xj)

相應(yīng)的判別函數(shù)也應(yīng)變?yōu)?f(x)=sgn{ai*yik(xi·x)+b*}2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心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ī)劃的求解2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心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ù)(Kernelfunction)2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心29一個(gè)能實(shí)現(xiàn)非線性關(guān)系到線性關(guān)系變換的實(shí)例取：那么2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心30核函數(shù)2023/7/19哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心