支持向量機引導(dǎo)教學(xué)課件

支持向量機引導(dǎo)支持向量機引導(dǎo)支持向量機引導(dǎo)支持向量機引導(dǎo)孫宗寶2006年12月20日哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心學(xué)術(shù)交流3/20/20212哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心支持向量機引導(dǎo)孫宗寶2006年12月20日哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心學(xué)術(shù)交流3/20/20213哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心概述一、向量的內(nèi)積與超平面

7/23/20236哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心概述二、最優(yōu)分類平面7/23/20237哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心概述二維數(shù)據(jù)最優(yōu)分類線的基本要求：1、要能將兩類樣本無錯誤的分開即使經(jīng)驗風(fēng)險最小，理論上為零

2、要使兩類之間的距離最大也就是使margin最大，從而使實際風(fēng)險最小7/23/20238哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心概述我們要做的是什么呢？找到一個超平面(最優(yōu)分類面)，使得它能夠盡可能多的將兩類數(shù)據(jù)點正確的分開，同時使分開的兩類數(shù)據(jù)點距離分類面最遠。7/23/20239哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心HH2H1最優(yōu)分類平面為最優(yōu)分類平面的方程7/23/202310哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分設(shè)線性可分樣本集為(xi,yi),i=1,2,…,n,x∈Rd,y∈{+1,-1}是類別標號。

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

g(x)=w·x+b分類面方程為:

w·x+b=0(1)7/23/202311哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分將判別函數(shù)進行歸一化,使兩類所有樣本都滿足|g(x)|≥1,即,使離分類面最近的樣本的|g(x)|=1,這樣分類間隔就等于2/‖w‖,因此間隔最大等價于使‖w‖(或‖w‖2)最小;而要求分類線對所有樣本正確分類,就是要求其滿足:

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

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

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

什么是Lagrange乘子法？看一個例子。問題：給你一塊面積固定（等于a的平方）板子，問做成什么樣的長方體（盒子），它具有最大的體積。7/23/202316哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分Lagrange乘子法設(shè)長方體的三個棱長為x，y，z，則其體積f為三個邊長的乘積：

f(x,y,z)=xyz本問題要求表面積為a的平方，于是長方體的6面的面積可以寫成：2xy+2xz+2yz=a2即2xy+2xz+2yz-a2=0這個問題轉(zhuǎn)化為了有約束條件的優(yōu)化問題。7/23/202317哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分Lagrange乘子法解題方法為：1用拉格朗日方法制造一個新函數(shù)F

2在F中放進一個未知的常數(shù)C

得到：

F=xyz+C(2xy+2xz+2yz-a2)7/23/202318哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分Lagrange乘子法F對x，y，z的三個自變量的偏微分分別為零，得到三個新方程式：yz+2C(y+z)=0

xz+2C(x+z)=0

xy+2C(x+y)=0因為自變量僅可能是正數(shù)，把上面的式子相除得(x/y)=(x+z)/(y+z)(y/z)=(x+y)/(x+z)7/23/202319哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分Lagrange乘子法由此得出只有各個自變量的值相等才可以維持上面的關(guān)系，再由約束條件得到它們的值是：x=y=z=(a/√6)7/23/202320哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分構(gòu)造拉格朗日函數(shù):L(w,b,a)=(w·w)—∑ai{yi[(w·xi)+b]-1}其中:ai>0為Lagrange系數(shù)。求式(3)的極小值就是對w和b求拉氏函數(shù)的極小值。求L對w和b的偏微分，并令其等于0,可轉(zhuǎn)化為對偶問題:在約束條件aiyi=0,ai≥0,i=1,2,…,n之下對ai〉0求式(5)的最大值:7/23/202321哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分W(a)=ai-aiajyiyj(xi.xj)（5）若ai*為最優(yōu)解，則w*=∑i=1..nai*yixi（6）即最優(yōu)分類面的權(quán)系數(shù)向量式訓(xùn)練樣本的線性組合。7/23/202322哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分這是一個不等式約束的二次函數(shù)極值問題，存在唯一解，并且解必須滿足(Kuhn-Tucker條件):ai[yi(w*xi+b)-1]=0,i=1..n

（7）顯然，只有支持向量的系數(shù)ai不為0,即只有支持向量影響最終的劃分結(jié)果。

這是為什么？

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

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

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

（8）7/23/202324哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性可分若ai*為最優(yōu)解,求解上述問題后得到的最優(yōu)分類函數(shù)是:f(x)=sgn{(w*·x)+b*}=sgn{ai*yi(xi·x)+b*}其中:sgn()為符號函數(shù),b*是分類的閾值,可以由任意一個支持向量用式(2)求得,或通過兩類中任意一對支持向量取中值求得。對于給定的未知樣本x,只需計算sgn(w?x+b),即可判定x所屬的分類。對于非支持向量ai都為0。7/23/202325哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性不可分對于線性不可分的樣本,希望使誤分類的點數(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)7/23/202326哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心SVM原理之線性不可分在式(9)中,對于給定的常數(shù)C,求出使φ(w,ξ)=(w·w)+C{ξi}（10）取極小值的w,b,這一優(yōu)化問題同樣需要變換為用拉格朗日乘子表示的對偶問題,變換的過程與前面線性可分樣本的對偶問題類似,結(jié)果也幾乎完全相同,只是約束條件略有變化:aiyi=0,(0≤ai≤C,i=1,2,…,n)(11)C反映了在復(fù)雜性和不可分樣本所占比例之間的折中。

7/23/202327哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心支持向量機如果用內(nèi)積K(x,x′)代替最優(yōu)分類面中的點積,就相當于把原特征空間變換到了某一新的特征空間,此時優(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*}

7/23/202328哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心支持向量機算法的其他條件均不變,這就是支持向量機。所以，原問題就轉(zhuǎn)化成了找SV的問題，而求SV的過程就是解一個二次規(guī)劃(有約束的)，二次規(guī)劃無局部極值，只有一個最值，所以SV的求解不會有不收斂或者收斂到局部極小的問題。而VC維又保證了機器的容量，不可能過學(xué)習(xí)(因為機器的結(jié)構(gòu)已經(jīng)固定)具體的求解方法可以參考運籌學(xué)中約束二次規(guī)劃的求解7/23/202329哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心非線性分類面非線性可分的數(shù)據(jù)樣本在高維空間有可能轉(zhuǎn)化為線性可分。在訓(xùn)練問題中，涉及到訓(xùn)練樣本的數(shù)據(jù)計算只有兩個樣本向量點乘的形式使用函數(shù) ,將所有樣本點映射到高為空間，則新的樣本集為設(shè)函數(shù)

內(nèi)核函數(shù)(Kernelfunction)7/23/202330哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心一個能實現(xiàn)非線性關(guān)系到線性關(guān)系變換的實例取：那么7/23/202331哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心核函數(shù)7/23/202332哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心核函數(shù)Mercer條件

對于任意的對稱函數(shù)K(x,x')，它是某個特征空間中的內(nèi)積運算的充分必要條件是，對于任意的φ(x)≠0且∫φ2(x)dx<∞，有∫∫K(x,x')φ(x)φ(x')dxdx'>0

7/23/202333哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心支持向量網(wǎng)絡(luò)7/23/202334哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心通常的內(nèi)核函數(shù)