support vector machine 支持向量機(jī) - search readpudncom

1、Support Vector Machine支持向量機(jī),張鑫2002. 2.1,提綱,SVM的有關(guān)概念介紹SVM問題的數(shù)學(xué)表示和推導(dǎo)簡單的最優(yōu)分類面SVM廣義最優(yōu)分類面 SVM非線性最優(yōu)分類面SVMSVM的分解算法,SVM的描述,SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的模式識別方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，從此迅速的發(fā)展起來，現(xiàn)在已經(jīng)在許多領(lǐng)域（生物信息學(xué)，文本和手寫識別等）都取得了成功

2、的應(yīng)用COLT(Computational Learning Theory),,目標(biāo)：找到一個(gè)超平面，使得它能夠盡可能多的將兩類數(shù)據(jù)點(diǎn)正確的分開，同時(shí)使分開的兩類數(shù)據(jù)點(diǎn)距離分類面最遠(yuǎn)。解決方法：構(gòu)造一個(gè)在約束條件下的優(yōu)化問題，具體的說是一個(gè)受限二次規(guī)劃問題(constrained quadratic programing),求解該問題，得到分類器。,模式識別問題的一般描述,已知：n個(gè)觀測樣本，(x1,y1), (x2,y2)……

3、 (xn,yn)求：最優(yōu)函數(shù)y’= f(x,w)滿足條件：期望風(fēng)險(xiǎn)最小 損失函數(shù),,期望風(fēng)險(xiǎn)R(w)要依賴聯(lián)合概率F(x,y)的信息，實(shí)際問題中無法計(jì)算。一般用經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)代替期望風(fēng)險(xiǎn)R(w),一般模式識別方法的問題,經(jīng)驗(yàn)風(fēng)險(xiǎn)最小不等于期望風(fēng)險(xiǎn)最小，不能保證分類器的推廣能力.經(jīng)驗(yàn)風(fēng)險(xiǎn)只有在樣本數(shù)無窮大趨近于期望風(fēng)險(xiǎn)，需要非常多的樣本才能保證分類器的性能。需要找到經(jīng)驗(yàn)風(fēng)險(xiǎn)最小和推廣能力最大的平衡點(diǎn)。,最優(yōu)分

4、類面,簡單情況：在線性可分的情況下的最優(yōu)分類面（Margine最大）,SVM問題的數(shù)學(xué)表示,已知：n個(gè)觀測樣本，(x1,y1), (x2,y2)…… (xn,yn)目標(biāo)：最優(yōu)分類面 wx-b=0滿足條件：是分類面 經(jīng)驗(yàn)風(fēng)險(xiǎn)最?。ㄥe(cuò)分最少）? 推廣能力最大（空白最大）,分類面方程滿足條件,對(xi,yi) 分類面方程g(x)=wx-b應(yīng)滿足即,空白,空白長度=2x樣本點(diǎn)到直線的距離=2x,SVM問題

5、的數(shù)學(xué)表示,已知：n個(gè)觀測樣本，(x1,y1), (x2,y2)…… (xn,yn)求解：目標(biāo)：最優(yōu)分類面 wx-b=0,廣義最優(yōu)分類面SVM,分類面條件的放寬經(jīng)驗(yàn)風(fēng)險(xiǎn)最小空白最大（不變）,SVM的數(shù)學(xué)表示,已知：n個(gè)觀測樣本，(x1,y1), (x2,y2)…… (xn,yn)求解：目標(biāo)：最優(yōu)分類面 wx-b=0,SVM問題求解,將上述問題表示成拉格朗日乘子式Kuhn-Tucker條件,,得到

6、只要確定?，便可解出w,b,,將上述條件代入L中新的優(yōu)化問題(Quadratic Programing),SVM問題求解,已知：n個(gè)觀測樣本，(x1,y1), (x2,y2)…… (xn,yn)求解根據(jù)?，求得w,b ，得到最優(yōu)分類面,非線性分類面,非線性可分的數(shù)據(jù)樣本在高維空間有可能轉(zhuǎn)化為線性可分。在訓(xùn)練問題中，涉及到訓(xùn)練樣本的數(shù)據(jù)計(jì)算只有兩個(gè)樣本向量點(diǎn)乘的形式使用函數(shù) ,將所有樣本點(diǎn)映射到高

7、為空間，則新的樣本集為設(shè)函數(shù),SVM的一般表示,已知：n個(gè)觀測樣本，(x1,y1), (x2,y2)…… (xn,yn)求解最優(yōu)非線性分類面為,通常的內(nèi)核函數(shù),線性內(nèi)核徑向基函數(shù)內(nèi)核多項(xiàng)式內(nèi)核S形內(nèi)核,多項(xiàng)式內(nèi)核,,SVM的計(jì)算,求解如下問題：D={ yiyjxixj }D的存儲代價(jià)=0.5 x (訓(xùn)練樣本數(shù))2 x 單元存儲空間 0.5 x(7000)2x8=196 x 106 Byte,二次

8、規(guī)劃問題求解,,,SVM的分解算法,Edgar Osuna(Cambridge ,MA)等人在IEEE NNSP’97發(fā)表了An Improved Training Algorithm for Support Vector Machines ,提出了SVM的分解算法,SVM的分解算法,將?向量分成兩個(gè)集合,工作集?B,固定集?N。即每次對?B解決一個(gè)小的二次規(guī)劃問題,保持?N中的值不變每次迭代選擇不同的?B和?N ，每解決一個(gè)小

9、規(guī)模優(yōu)化問題，都在原來的基礎(chǔ)上向最終的解集前進(jìn)一步。每次迭代檢查當(dāng)前結(jié)果，滿足優(yōu)化條件，則找到了優(yōu)化問題的解，算法結(jié)束。,SVM的分解算法,SVM的分解算法,常數(shù)項(xiàng),工作集的大小可以人為指定,相等項(xiàng),SVM的分解算法,Proposition(Build down):moving a variable from B to N leaves the cost function unchanged,and the solution is

10、 feasible in the subproblemProposition(Build up)moving a variable that violates the optimality condition from N to B gives a strict improvement in the cost function when the subproblem is re-optimized,SVM的分解算法,Arbitra

11、rily choose |B| points from the data set.Solve the subproblem defined by the variable in B.While there exist some ?j j?N,such thatreplace any ?i ,i ? B,with ?j and solve the new subproblem.,SVM分解算法的實(shí)例,SVMlight T

12、horsten Joachims (UniversityDortmund ,Informatik, AI-Unit)Make Large-Scale SVM Learning PracticalSMOJohn C. Platt (Microsoft Research)Fast Training of Support Vector Machines using Sequential Minimal Optimizatio