浙江大學SVM(支持向量機)

1、浙江大學研究生浙江大學研究生人工智能引論人工智能引論課件課件徐從富徐從富(Congfu Xu) PhD, Associate Professor Email: Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou 310027, P.R. ChinaSeptember 11, 2003第一稿第一稿Oct. 16, 2006第三次修改稿第三次修改稿第八章 統(tǒng)計學習理論與SVM(Chapter8 SLT & SVM )目錄目錄n概述n統(tǒng)計學習理論中的基

2、本概念n統(tǒng)計學習理論的發(fā)展簡況n統(tǒng)計學習理論的基本內容n支持向量機概述n研究現狀n參考文獻8.1.1 SLT & SVM的地位和作用的地位和作用n是統(tǒng)計學習方法的優(yōu)秀代表n有嚴密的數學依據，得到了嚴格的數學證明n有力反駁 “復雜的理論是沒有用的，有用的是簡單的算法”等錯誤觀點n充分表明 “沒有什么比一個好的理論更實用沒有什么比一個好的理論更實用了了”等基本的科學原則8.1 概述概述8.1.2 SLT & SVM的數學基礎的數學基礎概率論與數理統(tǒng)計泛函分析“For God so loved the world that he gave his one and only Son,

3、that whoever believes in him shall not perish but have eternal life. For God did not send his Son into the world to condemn the world, but to save the world through him.” from JOHN 3:16-17 NIV 8.1.3 SLT&SVM所堅持的“基本信念”傳統(tǒng)的估計高維函數依賴關系的方法所堅持的信傳統(tǒng)的估計高維函數依賴關系的方法所堅持的信念念 實際問題中總存在較少數目的一些“強特征強特征”，用它們的簡單函數（如線

4、性組合）就能較好地逼近未知函數。因此，需要仔細地選擇一個低仔細地選擇一個低維的特征空間維的特征空間，在這個空間中用常規(guī)的統(tǒng)計技術來求解一個逼近。SLT&SVM所堅持的信念所堅持的信念 實際問題中存在較大數目的一些“弱特征弱特征”，它們“巧妙的”線性組合可較好地逼近未知的依賴關系。因此，采用什么樣的“弱特征”并不十分重要，而形成“巧妙的”線性組合更為重要。8.1.4 SLT&SVM與傳統(tǒng)方法的區(qū)別要較好地實現傳統(tǒng)方法傳統(tǒng)方法，需要人工選擇（構造）一些數目相對較少的“巧妙的特征”SVM方法方法則是自動地選擇（構造）一些數目較少的“巧妙的特征”在實際應用中，可通過構造兩層（或多層）構

5、造兩層（或多層）SVM來選擇“巧妙的特征”SLT & SVM集以下模型于一身：結構風險最小化（SRM）模型數據壓縮模型構造復合特征的一個通用模型 在希爾伯特空間中的內積回旋可以 看作是構造特征的一種標準途徑。對實際數據的一種模型 一個小的支持向量集合可能足以對不同的機器代表整個訓練集。8.2 SLT中的基本概念中的基本概念n統(tǒng)計方法統(tǒng)計方法 從觀測自然現象或者專門安排的實驗所得到的數據去推斷該事務可能的規(guī)律性。n統(tǒng)計學習理論統(tǒng)計學習理論 在研究小樣本小樣本統(tǒng)計估計和預測的過程中發(fā)展起來的一種新興理論。【注意注意】：這里所說的“小樣本”是相對于無窮樣本而言的，故只要樣本數不是無窮，都可稱

6、為小樣本，更嚴格地說，應該稱為“有限樣本有限樣本”。統(tǒng)計學習理論中的基本概念（續(xù)）n機器學習機器學習 主要研究從采集樣本出發(fā)得出目前尚不能通過原理分析得到的規(guī)律,并利用這些規(guī)律對未來數據或無法觀測的數據進行預測。n模式識別模式識別 對表征事務或現象的各種形式(數值、文字及邏輯關系等)信息進行處理和分析,以對事務或現象進行描述、辨認、分類和解釋的過程。n統(tǒng)計學習理論統(tǒng)計學習理論 一種研究有限樣本估計和預測的數學理論8.3 統(tǒng)計學習理論的發(fā)展簡況統(tǒng)計學習理論的發(fā)展簡況n學習過程的數學研究F. Rosenblatt于1958,1962年把感知器作為一個學習機器模型n統(tǒng)計學習理論的開始Novikoff

7、(1962)證明了關于感知器的第一個定理n解決不適定問題的正則化原則的發(fā)現Tikhonov(1963), Ivanov(1962), Phillips(1962)nVanik和Chervonenkis(1968)提出了VC熵熵和VC維維的概念提出了統(tǒng)計學習理論的核心概念得到了關于收斂速度的非漸進界的主要結論SLTSLT的發(fā)展簡況的發(fā)展簡況( (續(xù)續(xù)) )Vapnik和Chervonenkis(1974)提出了結構風結構風險最小化（險最小化（SRM）歸納原則歸納原則。Vapnik和Chervonenkis(1989)發(fā)現了經驗風險最小化歸納原則和最大似然方法一致性的充分必要條件,完成了對經驗風險

8、最小化歸納推理的分析。90年代中期,有限樣本情況下的機器學習理論研究逐漸成熟起來,形成了較完善的理論體系統(tǒng)計學習理論(Statistical Learning Theory,簡稱SLT)8.4 統(tǒng)計學習理論的基本內容統(tǒng)計學習理論的基本內容n機器學習的基本問題n統(tǒng)計學習理論的核心內容8.4.1 機器學習的基本問題機器學習的基本問題n機器學習問題的表示GLMSX Xyy學習問題的表示學習問題的表示n產生器(G)，產生隨機向量x屬于Rn ,它們是從固定但未知的概率分布函數F(x)中獨立抽取的。n訓練器(S)，對每個輸入向量x返回一個輸出值y，產生輸出的根據是同樣固定但未知的條件分布函數 F(y|x)

9、。n學習機器(LM)，它能夠實現一定的函數集f(x, a)，a屬于A，其中A是參數集合。8.4.2 機器學習的基本問題機器學習的基本問題n機器學習就是從給定的函數集f(x x,)(是參數)中,選擇出能夠最好地逼近訓練器響應的函數。n機器學習的目的可以形式化地表示為：根據n個獨立同分布的觀測樣本 ，在一組函數 中求出一個最優(yōu)函數 對訓練器的響應進行估計,使期望風險最小 其中 是未知的,對于不同類型的機器學習問題有不同形式的損失函數。 1122( ,),(,),(,)nnx yxyxy ( , )f x0 ( , )f x( , )P x y( )( , ( , )( , )RL y f xdP

10、x y三類基本的機器學習問題三類基本的機器學習問題n模式識別n函數逼近（回歸估計）n概率密度估計【補充說明】：用有限數量信息解決問題的基基本原則本原則 在解決一個給定問題時，要設法在解決一個給定問題時，要設法避免把解決一個更為一般的問題作為其中間避免把解決一個更為一般的問題作為其中間步驟步驟。上述原則意味著，當解決模式識別或回歸估計問題時，必須設法去必須設法去“直接直接”尋找待求的函數尋找待求的函數，而不是不是首先估計密度，然后用估計的密度來構造待求的函數。密度估計密度估計是統(tǒng)計學中的一個全能問題，即知道了密度就可以解決各種問題。一般地，估計密度是一個不適定問題(ill-posed probl

11、em)，需要大量觀測才能較好地解決。實際上，需要解決的問題（如決策規(guī)則估計或回歸估計）是很特殊的，通常只需要有某一合理數通常只需要有某一合理數量的觀測就可以解決量的觀測就可以解決。經驗風險最小化原則經驗風險最小化原則n對于未知的概率分布,最小化風險函數, 只有樣本的信息可以利用,這導致了定義的期望風險是無法直接計算和最小化的。n根據概率論中大數定理,可用算術平均代替數據期望,于是定義了經驗風險 來逼近期望風險。n經驗風險最小化(ERM)原則：使用對參數w求經驗風險 的最小值代替求期望風險 的最小值。11( )(,( ,)nempiiiRwL yf x wn( )empRw()R w經驗風險最小

12、化經驗風險最小化n從期望風險最小化到經驗風險最小化沒有可靠的依據,只是直觀上合理的想當然。期望風險和經驗風險都是w的函數,概率論中的大數定理只說明了當樣本趨于無窮多時經驗風險將在概率意義上趨近于期望風險,并沒有保證兩個風險的w是同一點,更不能保證經驗風險能夠趨近于期望風險。即使有辦法使這些條件在樣本數無窮大時得到保證, 也無法認定在這些前提下得到的經驗風險最小化方法在樣本數有限時仍能得到好的結果。復雜性與推廣能力復雜性與推廣能力n學習機器對未來輸出進行正確預測的能力稱作推推廣能力（廣能力（也稱為“泛化能力泛化能力”）。）。n在某些情況下,訓練誤差過小反而導致推廣能力的下降,這就是過學習過學習問

13、題。n神經網絡的過學習問題是經驗風險最小化原則失敗的一個典型例子。用三角函數擬合任意點用三角函數擬合任意點學習的示例學習的示例復雜性與推廣能力（續(xù)）復雜性與推廣能力（續(xù)）n在有限樣本情況下，經驗風險最小并不一定意味著期望風險最??；學習機器的復雜性不但與所研究的系統(tǒng)有關,而且要和有限的學習樣本相適應；學習精度和推廣性之間似乎是一對不可調和的學習精度和推廣性之間似乎是一對不可調和的矛盾矛盾, ,采用復雜的學習機器雖然容易使得學習采用復雜的學習機器雖然容易使得學習誤差更小誤差更小, ,卻往往喪失推廣性；卻往往喪失推廣性；傳統(tǒng)的解決辦法（例如：采用正則化、模型選擇、噪聲干擾等方法以控制學習機器的復雜度

14、）缺乏堅實的理論基礎。8.5 統(tǒng)計學習理論的核心內容統(tǒng)計學習理論的核心內容nSLT被認為是目前針對有限樣本統(tǒng)計估計和預測學習的最佳理論，它從理論上較為系統(tǒng)地研究了經驗風險最小化原則成立的條件、有限樣本下經驗風險與期望風險的關系及如何利用這些理論找到新的學習原則和方法等問題。nSLT的主要內容包括:基于經驗風險原則的統(tǒng)計學習過程的一致性理論學習過程收斂速度的非漸進理論控制學習過程的推廣能力的理論構造學習算法的理論VC維維(函數的多樣性函數的多樣性)n為了研究經驗風險最小化函數集的學習一致收斂速度和推廣性，SLT定義了一些指標來衡量函數集的性能，其中最重要的就是VC維(Vapnik-Chervon

15、enkis Dimension)。nVC維維：對于一個指示函數（即只有0和1兩種取值的函數）集，如果存在h個樣本能夠被函數集里的函數按照所有可能的2h種形式分開，則稱函數集能夠把h個樣本打散，函數集的VC維就是能夠打散的最大樣本數目。n如果對任意的樣本數，總有函數能打散它們，則函數集的VC維就是無窮大。VC維（續(xù)）維（續(xù)）n一般而言,VC維越大, 學習能力就越強,但學習機器也越復雜。n目前還沒有通用的關于計算任意函數集的VC維的理論,只有對一些特殊函數集的VC維可以準確知道。nN維實數空間中線性分類器和線性實函數的VC維是n+1。nSin(ax)的VC維為無窮大。nVCVC維（續(xù)）維（續(xù)） O

16、pen problem: 對于給定的學習函數集,如何用理論或實驗的方法計算其VC維是當前統(tǒng)計學習理論研究中有待解決的一個難點問題。三個里程碑定理三個里程碑定理( )()(VC)lim0( )lim0( )lim0 xannxxH nnHnnG nn收斂的充分 必要 條件熵快收斂速度的充分條件 與概率測度無關的快收斂充要條件推廣性的界nSLT系統(tǒng)地研究了經驗風險和實際風險之間的關系,也即推廣性的界。n根據SLT中關于函數集推廣性界的理論,對于指示函數集中所有的函數,經驗風險 和實際風險 之間至少以概率 滿足如下關系: 其中，h是函數集的VC維,n是樣本數。( )empRw()R w1(ln(2

17、/ ) 1) ln( /4)( )( )emphn hRRn 推廣性的界（續(xù)1）n學習機器的實際風險由兩部分組成:訓練樣本的經驗風險置信范圍(同置信水平 有關,而且同學習機器的VC維和訓練樣本數有關。n在訓練樣本有限的情況下,學習機器的VC維越高,則置信范圍就越大,導致實際風險與經驗風險之間可能的差就越大。(ln(2 / ) 1) ln( /4)( )( )emphn hRRn ( )( )()empnRRh 1推廣性的界（續(xù)2）n在設計分類器時, 不但要使經驗風險最小化,還要使VC維盡量小,從而縮小置信范圍,使期望風險最小。n尋找反映學習機器的能力的更好參數，從而得到更好的界是SLT今后的重

18、要研究方向之一。結構風險最小化n傳統(tǒng)機器學習方法中普遍采用的經驗風險最小化原則在樣本數目有限時是不合理的,因此，需要同時最小化經驗風險和置信范圍。n統(tǒng)計學習理論提出了一種新的策略,即把函數集構造為一個函數子集序列,使各個子集按照VC維的大小排列;在每個子集中尋找最小經驗風險,在子集間折衷考慮經驗風險和置信范圍,取得實際風險的最小。這種思想稱作結構風險最小化(Structural Risk Minimization)，即SRM準則。結構風險最小化（續(xù)1）結構風險最小化（續(xù)2）n實現SRM原則的兩種思路在每個子集中求最小經驗風險,然后選擇使最小經驗風險和置信范圍之和最小的子集。設計函數集的某種結構

19、使每個子集中都能取得最小的經驗風險,然后只需選擇適當的子集使置信范圍最小,則這個子集中使經驗風險最小的函數就是最優(yōu)函數。支持向量機方法實際上就是這種思路的實現。8.6 支持向量機概述n支持向量機概述n支持向量機理論n支持向量機n核函數n支持向量機實現8.6.1 支持向量機概述支持向量機概述n1963年，Vapnik在解決模式識別問題時提出了支持向量方法,這種方法從訓練集中選擇一組特征子集,使得對特征子集的劃分等價于對整個數據集的劃分,這組特征子集就被稱為支持向量(SV)。n1971年，Kimeldorf提出使用線性不等約束重新構造SV的核空間,解決了一部分線性不可分問題。n1990年，Grac

20、e,Boser和Vapnik等人開始對SVM進行研究。n1995年，Vapnik正式提出統(tǒng)計學習理論。8.6.2 支持向量機理論支持向量機理論nSVM從線性可分情況下的最優(yōu)分類面發(fā)展而來。n最優(yōu)分類面就是要求分類線不但能將兩類正確分開(訓練錯誤率為0),且使分類間隔最大。nSVM考慮尋找一個滿足分類要求的超平面,并且使訓練集中的點距離分類面盡可能的遠,也就是尋找一個分類面使它兩側的空白區(qū)域(margin)最大。n過兩類樣本中離分類面最近的點且平行于最優(yōu)分類面的超平面上H1,H2的訓練樣本就叫做支持向量。支持向量機理論（續(xù)1）廣義最優(yōu)分類面廣義最優(yōu)分類面（續(xù)1）n假定訓練數據n可以被一個超平面分

21、開n我們進行正歸化n此時分類間隔等于n使最大間隔最大等價于使 最小() 1,1,.,iiyw xbilRbRwbxwN, 0).(11( ,),.,( ,), 1, 1nllx yx yxR y 2w2w廣義最優(yōu)分類面（續(xù)2）n最優(yōu)分類面問題可以表示成約束優(yōu)化問題MinimizeSubject ton定義Lagrange函數211( )()22()1,1,.,iiwww wyw xbilliiiibwxywbwL1221) 1)(),(廣義最優(yōu)分類面（續(xù)3）nLagrange函數liiiibwxywbwL1221) 1)(),(0),(0),(bwLwbwLbiiliiiliixywya110

22、liiiiliiiililjijijijiibxxyxfyandlixxyyW1111,21)(sgn()(0,.,1, 0)()(一個簡單的例子：4x3x2x1x2221234223341( ) ()(444)2Qx1 =(0, 0), y1 = +1x2 =(1, 0), y2 = +1x3 =(2, 0), y3 = -1x4 =(0, 2), y4 = -1可調用Matlab中的二次規(guī)劃程序，求得1, 2, 3, 4的值，進而求得w和b的值。 123412013 / 41 / 41120312002144231113,02224()3220wbgxxx 8.6.3 支持向量機支持向量機

23、n很多情況下，訓練數據集是線性不可分的，Vapnik等人提出了用廣義分類面（松弛子）來解決這一問題。n非線性問題通過非線性變換將它轉化為某個高維空間中的線性問題，在這個高維空間中尋找最優(yōu)分類面。高維空間中的最優(yōu)分類面n分類函數只涉及到訓練樣本之間的內積運算(xixj) ,因此,在高維空間中只需進行內積運算,這種內積運算可通過定義在原空間中的函數來實現, 甚至不必知道變換的形式。nSLT指出,根據Hibert-Schmidt原理,只要一種運算滿足Mercer條件,就可以作為內積使用。Mercer條件2( , ),( )0( ),) ( ) ( )0K x xxx dxKxxx dxdx對于任意的

24、對稱函數它是某個特征空間中的內積運算的充要條件是,對于任意的且有(x,支持向量機n在最優(yōu)分類面中采用適當的內積函數就可以實現某一非線性變換后的線性分類,而計算復雜度卻沒有增加。支持向量機8.6.4 核函數核函數nSVM中不同的內積核函數將形成不同的算法,主要的核函數有三類：n多項式核函數n徑向基函數nS形函數8.6.5 支持向量機實現支持向量機實現SVMlight - 2.private:/usr/local/binsvm_learn, svm_classifybsvm - 2.private:/usr/local/binsvm-train, svm-classify, svm-scaleli

25、bsvm - 2.private:/usr/local/binsvm-train, svm-predict, svm-scale, svm-toymySVMMATLAB svm toolbox支持向量機實現8.7 8.7 研究現狀研究現狀n應用研究n支持向量機研究n支持向量機算法研究8.7.1 應用研究應用研究nSVM的應用主要于模式識別領域n貝爾實驗室對美國郵政手寫數字庫進行的實驗分類器錯誤率人工表現2.5%決策樹C4.516.2%最好的兩層神經網絡5.9%SVM4.0%SVM與神經網絡（NN）的對比SVM的理論基礎比NN更堅實，更像一門嚴謹的“科學科學”（三要素：問題的表示、問題的解決、證

26、明）SVM 嚴格的數學推理NN 強烈依賴于工程技巧推廣能力推廣能力取決于“經驗風險值”和“置信范圍值”，NN不能控制兩者中的任何一個。NN設計者用高超的工程技巧彌補了數學上的缺陷設計特殊的結構，利用啟發(fā)式算法，有時能得到出人意料的好結果?！拔覀儽仨殢囊婚_始就澄清一個觀點，就是如果某事不是科學，它并不一定不好。比如說，愛情就不是科學。因此，如果我們說某事不是科學，并不是如果我們說某事不是科學，并不是說它有什么不對，而只是說它不是科學說它有什么不對，而只是說它不是科學?！?by R. Feynman from The Feynman Lectures on Physics, Addison-Wes

27、ley同理，與SVM相比，NN不像一門科學，更像一門工程技巧，但并不意味著它就一定不好！主要應用領域n手寫數字識別n語音識別n人臉識別n文本分類8.7.2 支持向量機研究支持向量機研究n如何針對不同的問題選擇不同的核函數仍然是一個懸而未決的問題。n標準的SVM對噪聲是不具有魯棒性的,如何選擇合適的目標函數以實現魯棒性是至關重要的。8.7.3 支持向量機算法研究支持向量機算法研究n支持向量機的本質是解一個二次規(guī)劃問題,雖然有一些經典（如對偶方法、內點算法等）,但當訓練集規(guī)模很大時,這些算法面臨著維數災難問題。為此,人們提出了許多針對大規(guī)模數據集的SVM訓練算法。支持向量機算法研究（續(xù)1）n思路1：分解子問題塊算法SMO算法(Sequential Minimal Optimization)n思路2：序列優(yōu)化n思路3：近鄰SVM支持向量機算法研究（續(xù)2）n訓練SVM的絕大多數算法都是針對分類問題,只有一小部分算法考慮了回歸函數的估計問題。n提高算法效率、降低復雜度。支持向量機算法研究（續(xù)3）nSVM增量學習算法的研究n超球面SVM算法研究One-class SVM算法nSVM多值分類器算法One-against-the-rest（一對多方法