統(tǒng)計學習理論與SVM-課件

浙江大學研究生《人工智能引論》課件第八章統(tǒng)計學習理論與SVM

(Chapter8SLT&SVM)1ppt課件目錄概述統(tǒng)計學習理論中的基本概念統(tǒng)計學習理論的發(fā)展簡況統(tǒng)計學習理論的基本內容支持向量機概述研究現(xiàn)狀參考文獻2ppt課件8.1.1SLT&SVM的地位和作用是統(tǒng)計學習方法的優(yōu)秀代表有嚴密的數(shù)學依據(jù)，得到了嚴格的數(shù)學證明有力反駁——“復雜的理論是沒有用的，有用的是簡單的算法”等錯誤觀點充分表明——“沒有什么比一個好的理論更實用了”等基本的科學原則8.1概述3ppt課件8.1.2SLT&SVM的數(shù)學基礎概率論與數(shù)理統(tǒng)計泛函分析“ForGodsolovedtheworldthathegavehisoneandonlySon,thatwhoeverbelievesinhimshallnotperishbuthaveeternallife.ForGoddidnotsendhisSonintotheworldtocondemntheworld,buttosavetheworldthroughhim.”

fromJOHN3:16-17NIV

4ppt課件8.1.3

SLT&SVM所堅持的“基本信念”傳統(tǒng)的估計高維函數(shù)依賴關系的方法所堅持的信念

實際問題中總存在較少數(shù)目的一些“強特征”，用它們的簡單函數(shù)（如線性組合）就能較好地逼近未知函數(shù)。因此，需要仔細地選擇一個低維的特征空間，在這個空間中用常規(guī)的統(tǒng)計技術來求解一個逼近。SLT&SVM所堅持的信念

實際問題中存在較大數(shù)目的一些“弱特征”，它們“巧妙的”線性組合可較好地逼近未知的依賴關系。因此，采用什么樣的“弱特征”并不十分重要，而形成“巧妙的”線性組合更為重要。5ppt課件8.1.4SLT&SVM與傳統(tǒng)方法的區(qū)別要較好地實現(xiàn)傳統(tǒng)方法，需要人工選擇（構造）一些數(shù)目相對較少的“巧妙的特征”SVM方法則是自動地選擇（構造）一些數(shù)目較少的“巧妙的特征”在實際應用中，可通過構造兩層（或多層）SVM來選擇“巧妙的特征”6ppt課件SLT&SVM集以下模型于一身：結構風險最小化（SRM）模型數(shù)據(jù)壓縮模型構造復合特征的一個通用模型在希爾伯特空間中的內積回旋可以看作是構造特征的一種標準途徑。對實際數(shù)據(jù)的一種模型一個小的支持向量集合可能足以對不同的機器代表整個訓練集。7ppt課件8.2SLT中的基本概念統(tǒng)計方法

——從觀測自然現(xiàn)象或者專門安排的實驗所得到的數(shù)據(jù)去推斷該事務可能的規(guī)律性。統(tǒng)計學習理論

——在研究小樣本統(tǒng)計估計和預測的過程中發(fā)展起來的一種新興理論。【注意】：這里所說的“小樣本”是相對于無窮樣本而言的，故只要樣本數(shù)不是無窮，都可稱為小樣本，更嚴格地說，應該稱為“有限樣本”。8ppt課件統(tǒng)計學習理論中的基本概念（續(xù)）機器學習

主要研究從采集樣本出發(fā)得出目前尚不能通過原理分析得到的規(guī)律,并利用這些規(guī)律對未來數(shù)據(jù)或無法觀測的數(shù)據(jù)進行預測。模式識別

對表征事務或現(xiàn)象的各種形式(數(shù)值、文字及邏輯關系等)信息進行處理和分析,以對事務或現(xiàn)象進行描述、辨認、分類和解釋的過程。統(tǒng)計學習理論

一種研究有限樣本估計和預測的數(shù)學理論9ppt課件8.3統(tǒng)計學習理論的發(fā)展簡況學習過程的數(shù)學研究F.Rosenblatt于1958,1962年把感知器作為一個學習機器模型統(tǒng)計學習理論的開始Novikoff(1962)證明了關于感知器的第一個定理解決不適定問題的正則化原則的發(fā)現(xiàn)Tikhonov(1963),Ivanov(1962),Phillips(1962)Vanik和Chervonenkis(1968)提出了VC熵和VC維的概念提出了統(tǒng)計學習理論的核心概念得到了關于收斂速度的非漸進界的主要結論10ppt課件SLT的發(fā)展簡況(續(xù))Vapnik和Chervonenkis(1974)提出了結構風險最小化（SRM）歸納原則。Vapnik和Chervonenkis(1989)發(fā)現(xiàn)了經(jīng)驗風險最小化歸納原則和最大似然方法一致性的充分必要條件,完成了對經(jīng)驗風險最小化歸納推理的分析。90年代中期,有限樣本情況下的機器學習理論研究逐漸成熟起來,形成了較完善的理論體系—統(tǒng)計學習理論(StatisticalLearningTheory,簡稱SLT)11ppt課件8.4統(tǒng)計學習理論的基本內容機器學習的基本問題統(tǒng)計學習理論的核心內容12ppt課件8.4.1機器學習的基本問題機器學習問題的表示13ppt課件學習問題的表示產(chǎn)生器(G)，產(chǎn)生隨機向量x屬于Rn,它們是從固定但未知的概率分布函數(shù)F(x)中獨立抽取的。訓練器(S)，對每個輸入向量x返回一個輸出值y，產(chǎn)生輸出的根據(jù)是同樣固定但未知的條件分布函數(shù)F(y|x)。學習機器(LM)，它能夠實現(xiàn)一定的函數(shù)集f(x,a)，a屬于A，其中A是參數(shù)集合。14ppt課件8.4.2機器學習的基本問題機器學習就是從給定的函數(shù)集f(x,)(是參數(shù))中,選擇出能夠最好地逼近訓練器響應的函數(shù)。機器學習的目的可以形式化地表示為：根據(jù)n個獨立同分布的觀測樣本

，

在一組函數(shù)中求出一個最優(yōu)函數(shù)對訓練器的響應進行估計,使期望風險最小

其中是未知的,對于不同類型的機器學習問題有不同形式的損失函數(shù)。

15ppt課件三類基本的機器學習問題模式識別函數(shù)逼近（回歸估計）概率密度估計【補充說明】：用有限數(shù)量信息解決問題的基本原則——在解決一個給定問題時，要設法避免把解決一個更為一般的問題作為其中間步驟。16ppt課件上述原則意味著，當解決模式識別或回歸估計問題時，必須設法去“直接”尋找待求的函數(shù)，而不是首先估計密度，然后用估計的密度來構造待求的函數(shù)。密度估計是統(tǒng)計學中的一個全能問題，即知道了密度就可以解決各種問題。一般地，估計密度是一個不適定問題(ill-posedproblem)，需要大量觀測才能較好地解決。實際上，需要解決的問題（如決策規(guī)則估計或回歸估計）是很特殊的，通常只需要有某一合理數(shù)量的觀測就可以解決。17ppt課件經(jīng)驗風險最小化原則對于未知的概率分布,最小化風險函數(shù),只有樣本的信息可以利用,這導致了定義的期望風險是無法直接計算和最小化的。根據(jù)概率論中大數(shù)定理,可用算術平均代替數(shù)據(jù)期望,于是定義了經(jīng)驗風險

來逼近期望風險。經(jīng)驗風險最小化(ERM)原則：使用對參數(shù)w求經(jīng)驗風險的最小值代替求期望風險的最小值。18ppt課件經(jīng)驗風險最小化從期望風險最小化到經(jīng)驗風險最小化沒有可靠的依據(jù),只是直觀上合理的想當然。期望風險和經(jīng)驗風險都是w的函數(shù),概率論中的大數(shù)定理只說明了當樣本趨于無窮多時經(jīng)驗風險將在概率意義上趨近于期望風險,并沒有保證兩個風險的w是同一點,更不能保證經(jīng)驗風險能夠趨近于期望風險。即使有辦法使這些條件在樣本數(shù)無窮大時得到保證,也無法認定在這些前提下得到的經(jīng)驗風險最小化方法在樣本數(shù)有限時仍能得到好的結果。19ppt課件復雜性與推廣能力學習機器對未來輸出進行正確預測的能力稱作推廣能力（也稱為“泛化能力”）。在某些情況下,訓練誤差過小反而導致推廣能力的下降,這就是過學習問題。神經(jīng)網(wǎng)絡的過學習問題是經(jīng)驗風險最小化原則失敗的一個典型例子。20ppt課件用三角函數(shù)擬合任意點21ppt課件學習的示例22ppt課件復雜性與推廣能力（續(xù)）在有限樣本情況下，經(jīng)驗風險最小并不一定意味著期望風險最??；學習機器的復雜性不但與所研究的系統(tǒng)有關,而且要和有限的學習樣本相適應；學習精度和推廣性之間似乎是一對不可調和的矛盾,采用復雜的學習機器雖然容易使得學習誤差更小,卻往往喪失推廣性；傳統(tǒng)的解決辦法（例如：采用正則化、模型選擇、噪聲干擾等方法以控制學習機器的復雜度）缺乏堅實的理論基礎。23ppt課件8.5統(tǒng)計學習理論的核心內容SLT被認為是目前針對有限樣本統(tǒng)計估計和預測學習的最佳理論，它從理論上較為系統(tǒng)地研究了經(jīng)驗風險最小化原則成立的條件、有限樣本下經(jīng)驗風險與期望風險的關系及如何利用這些理論找到新的學習原則和方法等問題。SLT的主要內容包括:基于經(jīng)驗風險原則的統(tǒng)計學習過程的一致性理論學習過程收斂速度的非漸進理論控制學習過程的推廣能力的理論構造學習算法的理論24ppt課件VC維(函數(shù)的多樣性)為了研究經(jīng)驗風險最小化函數(shù)集的學習一致收斂速度和推廣性，SLT定義了一些指標來衡量函數(shù)集的性能，其中最重要的就是VC維(Vapnik-ChervonenkisDimension)。VC維：對于一個指示函數(shù)（即只有0和1兩種取值的函數(shù)）集，如果存在h個樣本能夠被函數(shù)集里的函數(shù)按照所有可能的2h種形式分開，則稱函數(shù)集能夠把h個樣本打散，函數(shù)集的VC維就是能夠打散的最大樣本數(shù)目。如果對任意的樣本數(shù)，總有函數(shù)能打散它們，則函數(shù)集的VC維就是無窮大。25ppt課件26ppt課件VC維（續(xù)）一般而言,VC維越大,學習能力就越強,但學習機器也越復雜。目前還沒有通用的關于計算任意函數(shù)集的VC維的理論,只有對一些特殊函數(shù)集的VC維可以準確知道。N維實數(shù)空間中線性分類器和線性實函數(shù)的VC維是n+1。Sin(ax)的VC維為無窮大?！?7ppt課件VC維（續(xù)）

Openproblem:

對于給定的學習函數(shù)集,如何用理論或實驗的方法計算其VC維是當前統(tǒng)計學習理論研究中有待解決的一個難點問題。28ppt課件三個里程碑定理29ppt課件推廣性的界SLT系統(tǒng)地研究了經(jīng)驗風險和實際風險之間的關系,也即推廣性的界。根據(jù)SLT中關于函數(shù)集推廣性界的理論,對于指示函數(shù)集中所有的函數(shù),經(jīng)驗風險和實際風險之間至少以概率滿足如下關系:

其中，h是函數(shù)集的VC維,n是樣本數(shù)。30ppt課件推廣性的界（續(xù)1）學習機器的實際風險由兩部分組成:訓練樣本的經(jīng)驗風險置信范圍(同置信水平有關,而且同學習機器的VC維和訓練樣本數(shù)有關。在訓練樣本有限的情況下,學習機器的VC維越高,則置信范圍就越大,導致實際風險與經(jīng)驗風險之間可能的差就越大。31ppt課件推廣性的界（續(xù)2）在設計分類器時,不但要使經(jīng)驗風險最小化,還要使VC維盡量小,從而縮小置信范圍,使期望風險最小。尋找反映學習機器的能力的更好參數(shù)，從而得到更好的界是SLT今后的重要研究方向之一。32ppt課件結構風險最小化傳統(tǒng)機器學習方法中普遍采用的經(jīng)驗風險最小化原則在樣本數(shù)目有限時是不合理的,因此，需要同時最小化經(jīng)驗風險和置信范圍。統(tǒng)計學習理論提出了一種新的策略,即把函數(shù)集構造為一個函數(shù)子集序列,使各個子集按照VC維的大小排列;在每個子集中尋找最小經(jīng)驗風險,在子集間折衷考慮經(jīng)驗風險和置信范圍,取得實際風險的最小。這種思想稱作結構風險最小化(StructuralRiskMinimization)，即SRM準則。33ppt課件結構風險最小化（續(xù)1）34ppt課件結構風險最小化（續(xù)2）實現(xiàn)SRM原則的兩種思路在每個子集中求最小經(jīng)驗風險,然后選擇使最小經(jīng)驗風險和置信范圍之和最小的子集。設計函數(shù)集的某種結構使每個子集中都能取得最小的經(jīng)驗風險,然后只需選擇適當?shù)淖蛹怪眯欧秶钚?則這個子集中使經(jīng)驗風險最小的函數(shù)就是最優(yōu)函數(shù)。支持向量機方法實際上就是這種思路的實現(xiàn)。35ppt課件8.6支持向量機概述支持向量機概述支持向量機理論支持向量機核函數(shù)支持向量機實現(xiàn)36ppt課件8.6.1支持向量機概述1963年，Vapnik在解決模式識別問題時提出了支持向量方法,這種方法從訓練集中選擇一組特征子集,使得對特征子集的劃分等價于對整個數(shù)據(jù)集的劃分,這組特征子集就被稱為支持向量(SV)。1971年，Kimeldorf提出使用線性不等約束重新構造SV的核空間,解決了一部分線性不可分問題。1990年，Grace,Boser和Vapnik等人開始對SVM進行研究。1995年，Vapnik正式提出統(tǒng)計學習理論。37ppt課件8.6.2支持向量機理論SVM從線性可分情況下的最優(yōu)分類面發(fā)展而來。最優(yōu)分類面就是要求分類線不但能將兩類正確分開(訓練錯誤率為0),且使分類間隔最大。SVM考慮尋找一個滿足分類要求的超平面,并且使訓練集中的點距離分類面盡可能的遠,也就是尋找一個分類面使它兩側的空白區(qū)域(margin)最大。過兩類樣本中離分類面最近的點且平行于最優(yōu)分類面的超平面上H1,H2的訓練樣本就叫做支持向量。38ppt課件支持向量機理論（續(xù)1）39ppt課件廣義最優(yōu)分類面40ppt課件廣義最優(yōu)分類面（續(xù)1）假定訓練數(shù)據(jù)可以被一個超平面分開我們進行正歸化此時分類間隔等于使最大間隔最大等價于使最小41ppt課件廣義最優(yōu)分類面（續(xù)2）最優(yōu)分類面問題可以表示成約束優(yōu)化問題MinimizeSubjectto定義Lagrange函數(shù)

42ppt課件廣義最優(yōu)分類面（續(xù)3）Lagrange函數(shù)43ppt課件一個簡單的例子：x1=(0,0),y1=+1x2=(1,0),y2=+1x3=(2,0),y3=-1x4=(0,2),y4=-1可調用Matlab中的二次規(guī)劃程序，求得1,2,3,4的值，進而求得w和b的值。44ppt課件45ppt課件8.6.3支持向量機很多情況下，訓練數(shù)據(jù)集是線性不可分的，Vapnik等人提出了用廣義分類面（松弛子）來解決這一問題。非線性問題——通過非線性變換將它轉化為某個高維空間中的線性問題，在這個高維空間中尋找最優(yōu)分類面。46ppt課件高維空間中的最優(yōu)分類面分類函數(shù)只涉及到訓練樣本之間的內積運算(xi·xj) ,因此,在高維空間中只需進行內積運算,這種內積運算可通過定義在原空間中的函數(shù)來實現(xiàn),甚至不必知道變換的形式。SLT指出,根據(jù)Hibert-Schmidt原理,只要一種運算滿足Mercer條件,就可以作為內積使用。47ppt課件Mercer條件48ppt課件支持向量機在最優(yōu)分類面中采用適當?shù)膬确e函數(shù)就可以實現(xiàn)某一非線性變換后的線性分類,而計算復雜度卻沒有增加。49ppt課件支持向量機50ppt課件8.6.4核函數(shù)SVM中不同的內積核函數(shù)將形成不同的算法,主要的核函數(shù)有三類：多項式核函數(shù)徑向基函數(shù)S形函數(shù)51ppt課件8.6.5支持向量機實現(xiàn)SVMlight -2.private:/usr/local/binsvm_learn,svm_classifybsvm -2.private:/usr/local/binsvm-train,svm-classify,svm-scalelibsvm -2.private:/usr/local/binsvm-train,svm-predict,svm-scale,svm-toymySVMMATLABsvmtoolbox52ppt課件支持向量機實現(xiàn)53ppt課件8.7研究現(xiàn)狀應用研究支持向量機研究支持向量機算法研究54ppt課件8.7.1應用研究SVM的應用主要于模式識別領域貝爾實驗室對美國郵政手寫數(shù)字庫進行的實驗分類器錯誤率人工表現(xiàn)2.5%決策樹C4.516.2%最好的兩層神經(jīng)網(wǎng)絡5.9%SVM4.0%55ppt課件SVM與神經(jīng)網(wǎng)絡（NN）的對比SVM的理論基礎比NN更堅實，更像一門嚴謹?shù)摹翱茖W”（三要素：問題的表示、問題的解決、證明）SVM——嚴格的數(shù)學推理NN——強烈依賴于工程技巧推廣能力取決于“經(jīng)驗風險值”和“置信范圍值”，NN不能控制兩者中的任何一個。NN設計者用高超的工程技巧彌補了數(shù)學上的缺陷——設計特殊的結構，利用啟發(fā)式算法，有時能得到出人意料的好結果。56ppt課件“我們必須從一開始就澄清一個觀點，就是如果某事不是科學，它并不一定不好。比如說，愛情就不是科學。因此，如果我們說某事不是科學，并不是說它有什么不對，而只是說它不是科學?！?/p>

——

by

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