支持向量機及應(yīng)用簡介.ppt

支持向量機介紹,統(tǒng)計學習理論,統(tǒng)計學習理論,統(tǒng)計學習理論是小樣本統(tǒng)計估計和預測學習的最佳理論。 假設(shè)輸出變量Y與輸入變量X之間存在某種對應(yīng)的依賴關(guān)系,即一未知概率分布P(X,Y)，P(X,Y)反映了某種知識。學習問題可以概括為:根據(jù)l個獨立同分布( independently drawn and identically distributed )的觀測樣本train set， (x1,y1),(x2,y2),(xn,yn),支持向量機（SVM）,支持向量機（Support Vector Machine，SVM）是由Boser,Guyon和Vapnik發(fā)明，并首次在計算學習理論（COLT）1992年年會論文中提出。它是繼人工神經(jīng)網(wǎng)絡(luò)后，智能計算領(lǐng)域發(fā)展的又一里程碑。支持向量機以嚴格證明的統(tǒng)計學習理論為基礎(chǔ)，使用核函數(shù)把數(shù)據(jù)從樣本空間映射到高維特征空間，將非線性問題轉(zhuǎn)化為線性可分問題，獲得最優(yōu)解，是一重大的理論創(chuàng)新。支持向量機有嚴密的數(shù)學基礎(chǔ)，訓練結(jié)果只與支持向量有關(guān)，且泛化性強，成為了解決非線性問題的重要工具，因此，受到智能計算領(lǐng)域?qū)W者的廣泛關(guān)注，在模式分類和回歸領(lǐng)域得到了廣泛的應(yīng)用。,機器學習的基本問題和方法,從給定的函數(shù)集中選擇出能夠最好地逼近系統(tǒng)響應(yīng)的函數(shù),有指導機器學習的目的是根據(jù)給定的訓練樣本，求出對某系統(tǒng)輸入輸出之間依賴關(guān)系的估計，使它能夠?qū)ξ粗斎胱鞒霰M可能準確的預測。可以一般地表示為：變量y與x存在一定的未知依賴關(guān)系，即遵循某一未知的聯(lián)合概率F(x,y)（x 和y 之間的確定性關(guān)系可以看作是其特例），有指導機器學習問題就是根據(jù)N個獨立同分布觀測樣本 在一組函數(shù)f (x,w)中求一個最優(yōu)的函數(shù) f (x,w0)對依賴關(guān)系進行估計，使期望風險 最小,期望風險,而對train set上產(chǎn)生的風險Remp(w)被稱為經(jīng)驗風險(學習的訓練誤差):,首先Remp(w)和R(w)都是w的函數(shù)，傳統(tǒng)概率論中的定理只說明了(在一定條件下)當樣本趨于無窮多時Remp(w)將在概率意義上趨近于R(w)，卻沒有保證使Remp(w)最小的點也能夠使R(w) 最小(同步最小)。,經(jīng)驗風險,經(jīng)驗風險最小化準則,因為是由訓練樣本(即經(jīng)驗數(shù)據(jù))定義的，因此稱之為經(jīng)驗風險。用求經(jīng)驗風險的最小值代替求期望風險R (a)的最小值，就是所謂的經(jīng)驗風險最小化(ERM)準則 從期望風險最小化到經(jīng)驗風險最小化的理論依據(jù)是大數(shù)定理，只有當訓練樣本趨近于無窮大的時候，經(jīng)驗風險才趨近于期望風險。即：,過學習Overfitting and underfitting,Problem: how rich class of classifications q(x;) to use.,underfitting,overfitting,good fit,Problem of generalization: a small emprical risk Remp does not imply small true expected risk R.,存在的問題,由于經(jīng)驗風險最小化代替期望風險最小化的理論依據(jù)是大數(shù)定理，實際的機器學習不能滿足訓練樣本趨近于無窮大這一苛刻的要求，致使經(jīng)驗風險最小化準則算法復雜性大與泛化能力差。 例如：基于經(jīng)驗風險最小化準則人工神經(jīng)網(wǎng)絡(luò)研究中，廣大學者總是把注意力集中在如何使更小，但很快便發(fā)現(xiàn)，一味追求訓練誤差小并不是總能達到好的預測效果。,原因,從理論上看，之所以出現(xiàn)過學習現(xiàn)象， 一是因為訓練樣本不充分， 二是機器學習的風險準則不合理。 出現(xiàn)這種現(xiàn)象的原因，就是試圖用一個復雜的模型去擬合有限的樣本，結(jié)果導致喪失了推廣能力。在神經(jīng)網(wǎng)絡(luò)中，如果對于有限的訓練樣本來說網(wǎng)絡(luò)的學習能力過強，足以記住每一個訓練樣本，此時經(jīng)驗風險很快就可以收斂到很小甚至零，但學習機器卻根本無法保證它對未來新的樣本能夠得到好的預測。這就是有限樣本下學習機器的復雜性與推廣性之間的矛盾。因此，關(guān)于學習機器復雜性和推廣能力，得到以下的結(jié)論,結(jié)論,經(jīng)驗風險最小并不一定意味著期望風險最小; 學習機器的復雜性不但與所研究的系統(tǒng)有關(guān)，而且要和有限的學習樣本相適應(yīng)。,VC維反映了函數(shù)集的學習能力，VC維越大則學習機器越復雜(容量越大)。,VC維(Vapnik-Chervonenkis Dimension)。模式識別方法中VC維的直觀定義是：對一個指示函數(shù)集，如果存在h個樣本能夠被函數(shù)集里的函數(shù)按照所有可能的2h種形式分開，則稱函數(shù)集能夠把h個樣本打散。函數(shù)集的VC維就是它能打散的最大樣本數(shù)目h。,VC維,經(jīng)驗風險與VC維關(guān)系,經(jīng)驗風險Remp(a)和實際風險R(a)之間至少以不下于1-(01)的概率存在這樣的關(guān)系:,結(jié)構(gòu)風險最小化歸納原則 (SRM),Sn,S*,經(jīng)驗風險Empirical risk,h1,h*,hn,h,S1,S*,Sn,置信范圍 Confidence interval,風險界限Bound on the risk,實現(xiàn)方法,設(shè)計具有某種結(jié)構(gòu)的函數(shù)集，使每個子集中都能取得最小的經(jīng)驗風險(如使訓練誤差為0)，然后只需選擇適當?shù)淖蛹怪眯欧秶钚。瑒t這個子集中使經(jīng)驗風險最小的函數(shù)就是最優(yōu)函數(shù)。支持向量機就是使用這一思想，實現(xiàn)統(tǒng)計學習理論結(jié)構(gòu)風險最小化準則的典型方法。,支持向量回歸(Regression),回歸問題,線性回歸:給定訓練集(xi,yi),找個線性函數(shù)f(x)=w.x+b,來擬合數(shù)據(jù) 最小二乘法(Least Square) 其中 為回歸誤差. 記 ,則目標函數(shù)可寫為 解為,最小二乘解的不足:數(shù)值穩(wěn)定性問題,增加新數(shù)據(jù)