機器學(xué)習(xí)：第四章 支持向量機

1、機器學(xué)習(xí)理論與應(yīng)用課件,第四章 支持向量機Support Vector Machine (SVM,4.1 支持向量機原理,4.1.1 機器學(xué)習(xí)的簡單回顧 4.1.2 支持向量機發(fā)展歷史 4.1.2 線性分類器 4.1.3 支持向量機理論 4.1.4 核函數(shù)與支持向量機 4.1.5 支持向量機的應(yīng)用舉例,簡介,支持向量機是機器學(xué)習(xí)領(lǐng)域一個里程碑 什么是支持向量機？ 支持向量是它的核心內(nèi)容，所謂的支持向量就是具有支持作用的一些訓(xùn)練樣本 利用核方法實現(xiàn)非線性擴展 簡單的回顧一下機器學(xué)習(xí)的發(fā)展歷史,回顧(一,感知器是一種早期的神經(jīng)網(wǎng)絡(luò)模型 上個世紀(jì)80年代，神經(jīng)網(wǎng)絡(luò)獲得迅速發(fā)展,提出了BP,Hopef

2、ield等著名網(wǎng)絡(luò)模型 遇到理論與應(yīng)用的瓶頸，實際應(yīng)用中沒有得到預(yù)期的效果,2 感知器模型 感知器是一種早期的神經(jīng)網(wǎng)絡(luò)模型，由美國學(xué)者F.Rosenblatt于1957年提出.感知器中第一次引入了學(xué)習(xí)的概念，對人腦所具備的學(xué)習(xí)功能進行了一定程度的模擬，所以引起了廣泛的關(guān)注。 簡單感知器 它通過采用監(jiān)督學(xué)習(xí)來逐步增強模式劃分的能力，達到所謂學(xué)習(xí)的目的,其結(jié)構(gòu)如下圖所示,基于數(shù)學(xué)函數(shù)表示 感知器處理單元對n個輸入進行加權(quán)和操作v即： 其中，Wi為第i個輸入到處理單元的連接權(quán)值為閾值。 f取階躍函數(shù),BP神經(jīng)網(wǎng)絡(luò)模型,反向傳播(Back propagation)算法：從后向前（反向）逐層“傳播”輸出

3、層的誤差，以間接算出隱層誤差。 可以解決XOR問題，但是模型復(fù)雜 需要樣本足夠多,Hopefield神經(jīng)網(wǎng)絡(luò)模型解決旅行商問題Deep Belief Net,回顧（二,上個世紀(jì)90年代，支持向量機獲得全面發(fā)展，在實際應(yīng)用中，獲得比較滿意的效果 成為機器學(xué)習(xí)領(lǐng)域的標(biāo)準(zhǔn)工具,非線性變換異或問題,異或問題在二維空間線性不可分 變換到三維空間，線性可分，z=x.y,4.1 支持向量機原理,4.1.1 機器學(xué)習(xí)的簡單回顧 4.1.2 支持向量機發(fā)展歷史 4.1.3 線性分類器 4.1.4 支持向量機理論 4.1.5 核函數(shù)與支持向量機 4.1.6 支持向量機的應(yīng)用舉例,4.1.1 支持向量機發(fā)展歷史,1

4、963年，Vapnik在解決模式識別問題時提出了支持向量方法。起決定性作用的那部分樣本為支持向量,即為SVM名字的起源 1971年，Kimeldorf構(gòu)造基于支持向量構(gòu)建核空間的方法 1992年，Vapnik等人開始對支持向量機進行研究。 1995年，Vapnik等人正式提出統(tǒng)計學(xué)習(xí)理論。 結(jié)構(gòu)風(fēng)險理論的發(fā)展過程的回顧,期望風(fēng)險,學(xué)習(xí)到一個假設(shè)H=f(x, w) 作為分類函數(shù),其中w是廣義參數(shù).它對F(X,Y)的期望風(fēng)險R(w)是(即統(tǒng)計學(xué)習(xí)的實際風(fēng)險)： 其中，f(x,w)稱作分類函數(shù)集，w為函數(shù)的廣義參數(shù)。L(y,f(x,w)為由于用f(x,w)對y進行預(yù)測而造成的損失。不同類型的學(xué)習(xí)問題

5、有不同形式的損失函數(shù),而對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)險,ERM的缺點,Empirical Risk Minimization(ERM) 用ERM準(zhǔn)則代替期望風(fēng)險最小化并沒有經(jīng)過充分的理論論證，只是直觀上合理的想當(dāng)然做法 這種思想?yún)s在多年的機器學(xué)習(xí)方法研究中占據(jù)了主要地位。人們多年來將大部分注意力集中到如何更好地最小化經(jīng)驗風(fēng)險上。

6、 而實際上，即使可以假定當(dāng)n趨向于無窮大時經(jīng)驗風(fēng)險也不一定趨近于期望風(fēng)險，在很多問題中的樣本數(shù)目也離無窮大相去甚遠 。 如神經(jīng)網(wǎng)絡(luò) 那么實際風(fēng)險到底是什么呢,h是VC維, n是樣本數(shù),根據(jù)統(tǒng)計學(xué)習(xí)理論中關(guān)于函數(shù)集的推廣性的界的結(jié)論，對于兩類分類問題中的分類函數(shù)集f(x, w)的所有函數(shù)(當(dāng)然也包括使經(jīng)驗風(fēng)險員小的函數(shù))，經(jīng)驗風(fēng)險Remp(w)和實際風(fēng)險R(w)之間至少以不下于1-(01)的概率存在這樣的關(guān)系,實際風(fēng)險 -Vapnic統(tǒng)計學(xué)習(xí)理論,Vapnik-Chervonenkis(VC)維,VC維是對分類函數(shù)能力一種刻畫。 分類函數(shù)集= f(x,w):wW的VC維是能被該分類函數(shù)無錯學(xué)習(xí)的

7、樣本的最大數(shù)量 （2類問題中） 描述了學(xué)習(xí)機器的復(fù)雜性 VC維的估計是有待研究的問題 存在一組就可以,VC dimension,Definition VC dimension of f() is the maximum number of points that can be shattered by f() and is a measure of capacity,一般的學(xué)習(xí)方法(如神經(jīng)網(wǎng)絡(luò))是基于 Remp(w) 最小,滿足對已有訓(xùn)練數(shù)據(jù)的最佳擬和,在理論上可以通過增加算法（如神經(jīng)網(wǎng)絡(luò)）的規(guī)模使得Remp(w) 不斷降低以至為0。 但是,這樣使得算法（神經(jīng)網(wǎng)絡(luò)）的復(fù)雜度增加, VC維h增加

8、,從而(n/h)增大,導(dǎo)致實際風(fēng)險R(w)增加,這就是學(xué)習(xí)算法的過擬合(Overfitting,VC維與經(jīng)驗風(fēng)險,VC維與經(jīng)驗風(fēng)險,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,結(jié)構(gòu)風(fēng)險最小化原則,函數(shù)集Fk=F(x,w);wWk, k=1,2,n F1 F2 Fn VC維

9、：h1h2hn 在使保證風(fēng)險（風(fēng)險的上界）最小的子集中選擇使經(jīng)驗風(fēng)險最小的函數(shù),結(jié)構(gòu)風(fēng)險最小化原則,4.1 支持向量機原理,4.1.1 機器學(xué)習(xí)的簡單回顧 4.1.2 支持向量機發(fā)展歷史 4.1.3 線性分類器 4.1.4 支持向量機理論 4.1.5 核函數(shù)與支持向量機 4.1.6 支持向量機的應(yīng)用舉例,4.1.2 線性分類器,線性分類器解決的問題： 根據(jù)一個帶有類別標(biāo)號的訓(xùn)練集合，通過學(xué)習(xí)一個線性分類面，使得訓(xùn)練集合按照類別進行劃分。 通常轉(zhuǎn)化成一個優(yōu)化問題。 從兩類問題入手,4.1.2 線性分類器,分類面：把一個空間按照類別切分兩部分的平面，在二維空間中，分類面相當(dāng)于一條直線，三維空間中相

10、當(dāng)于一個平面,高維空間為超平面,線性分類面函數(shù)形式為,wT,b是分類面函數(shù)的參數(shù),x是輸入的樣本, wT權(quán)向量,b是偏移量,4.1.2 線性分類器,代入(1,0),(0,1)驗證g0,線性分類面函數(shù),如果,則為xi分類面上的點，反過來也成立,如果w相同，則分類面是平行的，b是一個偏移量,4.1.2 線性分類器,線性分類器學(xué)習(xí)過程：從給定的訓(xùn)練樣本確定wT和b這兩個參數(shù)。 得到參數(shù)以后，就確定了分類面，從而可以對輸入樣本進行分類。 闡述一下各個參數(shù)的性質(zhì),當(dāng)s1和s2都在分類面上時，這表明wT和分類面上任意向量正交，并稱wT為分類面的法向量,wT,幾何解釋：線性分類器的作用就是把輸入樣本在法向量

11、上投影變成一維變量，然后給一個閾值來分類,4.1.2 線性分類器,分類面函數(shù),核心,可視化 表示,如何尋找最優(yōu)的權(quán)向量 ？ 優(yōu)化問題,wT為法向量,Margin最大化分類面,Margin最大化分類面與投影方向,1.什么是Margin,如何定義?平行于分類面的類邊界線之間的距離,類間隔 經(jīng)過一類中距離另外一類距離最近那些點構(gòu)成的面,2.支持向量在wT方向上的投影,由于類邊界線垂直于投影方向，則其投影點之間的距離即為類間距,x1投影之后結(jié)果為,Margin最大化分類面（續(xù)1,尋找投影方向W，使得不同類別樣本在投影以后距離最遠,X1, X2是離得最近那些樣本,Margin最大化分類面（續(xù)2,經(jīng)驗風(fēng)險

12、最小不等于期望風(fēng)險最小，不能保證分類器的推廣能力. 需要找到經(jīng)驗風(fēng)險最小和推廣能力最大的平衡點,4.1 支持向量機原理,4.1.1 機器學(xué)習(xí)的簡單回顧 4.1.2 支持向量機發(fā)展歷史 4.1.3 線性分類器 4.1.4 支持向量機理論 4.1.5 核函數(shù)與支持向量機 4.1.6 支持向量機的應(yīng)用舉例,4.1.3支持向量機理論,SVM從線性可分情況下的分類面發(fā)展而來。 Margin最大化分類面不僅僅要求經(jīng)驗風(fēng)險盡可能的小，且使分類間隔最大。 SVM考慮尋找一個滿足分類要求的分類面。 過兩類樣本中離分類面最近的點且平行于分類面的訓(xùn)練樣本就叫做支持向量,支持向量機理論（續(xù)1,假定訓(xùn)練數(shù)據(jù) 線性分類面

13、函數(shù) 轉(zhuǎn)化成優(yōu)化問題 此時分類間隔等于 使最大間隔等價于使 最小,支持向量機理論（續(xù)2,定義Lagrange函數(shù),輸入的類別與決策具有相同的符號,最優(yōu)分類面問題可以表示成約束優(yōu)化問題,最小化目標(biāo)函數(shù) 約束條件,1629年，Lagrange最初是為了解決沒有不等式約束的最優(yōu)化解 1951年，Kuhn和Tucker進一步把這個方法擴展到具有不等式約束的情況下，而他們理論實際基于Karush的工作。 通過對偶理論簡化約束條件即Karush-Kuhn-Tucker互補條件 完美的解決了支持向量機的優(yōu)化問題,Lagrange函數(shù)優(yōu)化問題的回顧,支持向量機理論（續(xù)3,Lagrange函數(shù),一個簡單的例子,

14、x1 =(0, 0)T, y1 = +1 x2 =(1, 0)T, y2 = +1 x3 =(2, 0)T, y3 = -1 x4 =(0, 2)T, y4 = -1,代入x,y值,思考：當(dāng)數(shù)據(jù)量很大的時候怎么辦,可調(diào)用Matlab中的二次規(guī)劃程序，求得1, 2, 3, 4的值，進而求得w和b的值,代入(3/2,0),(0,3/2)點可以知道,4.1 支持向量機原理,4.1.1 機器學(xué)習(xí)的簡單回顧 4.1.2 支持向量機發(fā)展歷史 4.1.3 線性分類器 4.1.4 支持向量機理論 4.1.5 核函數(shù)與支持向量機 4.1.6 支持向量機的應(yīng)用舉例,4.1.4 核函數(shù)與支持向量機,支持向量機的軟肋

15、假定線性可分 很多情況下，訓(xùn)練數(shù)據(jù)集是線性不可分的，Vapnik等人提出了用廣義分類面（松弛子）來解決這一問題。 非線性變換通過非線性變換將它轉(zhuǎn)化為某個高維空間中的線性問題，在這個高維空間中尋找最優(yōu)分類面,軟間隔,最優(yōu)化問題,SVM問題求解,將上述問題表示成拉格朗日乘子式 Kuhn-Tucker條件,得到 只要確定，便可解出w,b,將上述條件代入L中 新的優(yōu)化問題 (Quadratic Programing,非線性變換,基本思想：選擇非線性映射(X)將x映射到高維特征空間Z，在Z中構(gòu)造最優(yōu)超平面,非線性變換異或問題,異或問題在二維空間線性不可分 變換到三維空間，線性可分，z=x.y,設(shè)訓(xùn)練集

16、，其中 假定可以用 平面上的二次曲線來分劃,現(xiàn)考慮把2維空間 映射到6維空間的變換,上式可將2維空間上二次曲線映射為6維空間上的一個超平面,非線性分類,可見，只要利用變換，把 所在的2維空間的兩類輸入點映射到 所在的6維空間，然后在這個6維空間中，使用線性學(xué)習(xí)機求出分劃超平面,最后得出原空間中的二次曲線,怎樣求6維空間中的分劃超平面？(線性支持向量分類機,非線性分類,高維空間中的最優(yōu)分類面,分類函數(shù)只涉及到訓(xùn)練樣本之間的內(nèi)積運算(xixj),因此,在高維空間中只需進行內(nèi)積運算 , 很難知道變換的形式。內(nèi)積運算可否替代？模糊處理？ 根據(jù)Hibert-Schmidt原理,只要一種運算滿足Merce

17、r條件,就可以作為內(nèi)積使用,非線性支持向量機（1,在最優(yōu)分類面中采用適當(dāng)?shù)膬?nèi)積函數(shù)就可以實現(xiàn)某一非線性變換后的線性分類,而計算復(fù)雜度卻沒有增加,與線性支持向量機的區(qū)別,非線性支持向量機（2,分類面函數(shù)： 優(yōu)化目標(biāo)函數(shù),一些典型的核函數(shù),SVM中不同的內(nèi)積核函數(shù)將形成不同的算法,常用的核函數(shù)有三類： 多項式核函數(shù) 徑向基函數(shù) S形函數(shù),4.1 支持向量機原理,4.1.1 機器學(xué)習(xí)的簡單回顧 4.1.2 支持向量機發(fā)展歷史 4.1.3 線性分類器 4.1.4 支持向量機理論 4.1.5 核函數(shù)與支持向量機 4.1.6 支持向量機的應(yīng)用舉例,4.1.5 支持向量機的應(yīng)用實例,SVM Applicat

18、ions,Pattern recognition Handwritten number,face dection,etc. DNA array expression data analysis Features: expr. levels in diff. conditions Protein classification Features: AA composition,手寫體數(shù)字識別,SVM的主要應(yīng)用于模式識別領(lǐng)域,手寫體數(shù)字識別 具體方法：共10類樣本，每一類訓(xùn)練一個分類器,Handwritten Digits Recognition,手寫體數(shù)字識別,貝爾實驗室對美國郵政手寫數(shù)字庫進行的

19、實驗 該數(shù)據(jù)共包含7291個訓(xùn)練樣本，2007個測試數(shù)據(jù)，輸入數(shù)據(jù)的維數(shù)為16x16維,手寫體數(shù)字識別參考文獻,B.E. Boser, I. M. Guyon, and V.Vapnik, A training algorithm for optimal margin classifiers, in proc. of ACM workshop on Computational Learning Theory, pp.144- 152,1992 C. Cortes and V. Vapnik, Support Vector Networks, Machine Learning, pp.273-2

20、97,1995,Applying SVMs to Face Detection,The SVM face-detection system,1. Rescale the input image several times,2. Cut 19x19 window patterns out of the scaled image,3. Preprocess the window using masking, light correction and histogram equalization,4. Classify the pattern using the SVM,5. If the clas

21、s corresponds to a face, draw a rectangle around the face in the output image,Applying SVMs to Face Detection,Experimental results on static images Set A: 313 high-quality, same number of faces Set B: 23 mixed quality, total of 155 faces,支持向量機免費軟件,Libsvm SVMlight bsvm mySVM MATLAB svm toolbox,Libsvm

22、簡介,Libsvm是臺灣大學(xué)林智仁(Lin Chih-Jen)副教授等開發(fā)設(shè)計的一個簡單、易于使用和快速有效的SVM模式識別與回歸的軟件包 提供了編譯好的可在Windows系列系統(tǒng)的執(zhí)行文件，還提供了源代碼,總結(jié),本節(jié)課主要講述了支持向量機的基本原理 支持向量機的核心思想在于假定了樣本總是可以被簡單的線性分類器進行分類 深刻理解Margin最大化思想 熟悉支持向量機的具體應(yīng)用實例,課下思考,為什么支持向量機會成為統(tǒng)計學(xué)習(xí)領(lǐng)域的里程碑？ 數(shù)據(jù)量很大的時候，如何優(yōu)化支持向量機的目標(biāo)函數(shù)？ 是我們后續(xù)課程需要解決的重點,Vapnik V N. 著，張學(xué)工譯. 統(tǒng)計學(xué)習(xí)理論.人民郵電出版社. Nell

23、o Cristianini, John Shawe-Taylor, 李國正，王猛，曾華軍，支持向量機導(dǎo)論,主要參考文獻,References,Vladimir Vapnik. The Nature of Statistical Learning Theory, Springer, 1995 Andrew W. Moore. cmsc726: SVMs. /awm/tutorials C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):955-974, 1998. http:/ Vladimir Vapnik. Statistical Learning Theory. Wiley-Interscience; 1998 Thorsten Joachims (joachims_01a): A Statistical Lea