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

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