support vector machine 支持向量機 - search readpudncom

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

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

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

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

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

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

7、為空間，則新的樣本集為設函數(shù),SVM的一般表示,已知：n個觀測樣本，(x1,y1), (x2,y2)…… (xn,yn)求解最優(yōu)非線性分類面為,通常的內核函數(shù),線性內核徑向基函數(shù)內核多項式內核S形內核,多項式內核,,SVM的計算,求解如下問題：D={ yiyjxixj }D的存儲代價=0.5 x (訓練樣本數(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的分解算法,將?向量分成兩個集合,工作集?B,固定集?N。即每次對?B解決一個小的二次規(guī)劃問題,保持?N中的值不變每次迭代選擇不同的?B和?N ，每解決一個小

9、規(guī)模優(yōu)化問題，都在原來的基礎上向最終的解集前進一步。每次迭代檢查當前結果，滿足優(yōu)化條件，則找到了優(yōu)化問題的解，算法結束。,SVM的分解算法,SVM的分解算法,常數(shù)項,工作集的大小可以人為指定,相等項,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分解算法的實例,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