浙江高校探討生《人工智能引論》課件徐從富(CongfuXu)PhD,AssociateProfessorEmail:xucongfu@InstituteofArtificialIntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaSeptember11,2003第一稿Oct.16,2006第三次修改稿第八章統計學習理論與SVM

(Chapter8SLT&SVM)書目概述統計學習理論中的基本概念統計學習理論的發展簡況統計學習理論的基本內容支持向量機概述探討現狀參考文獻8.1.1SLT&SVM的地位和作用是統計學習方法的優秀代表有嚴密的數學依據，得到了嚴格的數學證明有力反對——“困難的理論是沒有用的，有用的是簡潔的算法”等錯誤觀點充分表明——“沒有什么比一個好的理論更好用了”等基本的科學原則8.1概述8.1.2SLT&SVM的數學基礎概率論與數理統計泛函分析“ForGodsolovedtheworldthathegavehisoneandonlySon,thatwhoeverbelievesinhimshallnotperishbuthaveeternallife.ForGoddidnotsendhisSonintotheworldtocondemntheworld,buttosavetheworldthroughhim.”

fromJOHN3:16-17NIV

8.1.3

SLT&SVM所堅持的“基本信念”傳統的估計高維函數依靠關系的方法所堅持的信念實際問題中總存在較少數目的一些“強特征”，用它們的簡潔函數（如線性組合）就能較好地靠近未知函數。因此，須要細致地選擇一個低維的特征空間，在這個空間中用常規的統計技術來求解一個靠近。SLT&SVM所堅持的信念實際問題中存在較大數目的一些“弱特征”，它們“奇異的”線性組合可較好地靠近未知的依靠關系。因此，接受什么樣的“弱特征”并不特殊重要，而形成“奇異的”線性組合更為重要。8.1.4SLT&SVM與傳統方法的區分要較好地實現傳統方法，須要人工選擇（構造）一些數目相對較少的“奇異的特征”SVM方法則是自動地選擇（構造）一些數目較少的“奇異的特征”在實際應用中，可通過構造兩層（或多層）SVM來選擇“奇異的特征”SLT&SVM集以下模型于一身：結構風險最小化（SRM）模型數據壓縮模型構造復合特征的一個通用模型在希爾伯特空間中的內積回旋可以看作是構造特征的一種標準途徑。對實際數據的一種模型一個小的支持向量集合可能足以對不同的機器代表整個訓練集。8.2SLT中的基本概念統計方法——從觀測自然現象或者特地支配的試驗所得到的數據去推斷該事務可能的規律性。統計學習理論——在探討小樣本統計估計和預料的過程中發展起來的一種新興理論。【留意】：這里所說的“小樣本”是相對于無窮樣本而言的，故只要樣本數不是無窮，都可稱為小樣本，更嚴格地說，應當稱為“有限樣本”。統計學習理論中的基本概念（續）機器學習主要探討從采集樣本動身得出目前尚不能通過原理分析得到的規律,并利用這些規律對將來數據或無法觀測的數據進行預料。模式識別對表征事務或現象的各種形式(數值、文字及邏輯關系等)信息進行處理和分析,以對事務或現象進行描述、辨別、分類和說明的過程。統計學習理論一種探討有限樣本估計和預料的數學理論8.3統計學習理論的發展簡況學習過程的數學探討F.Rosenblatt于1958,1962年把感知器作為一個學習機器模型統計學習理論的起先Novikoff(1962)證明白關于感知器的第一個定理解決不適定問題的正則化原則的發覺Tikhonov(1963),Ivanov(1962),Phillips(1962)Vanik和Chervonenkis(1968)提出了VC熵和VC維的概念提出了統計學習理論的核心概念得到了關于收斂速度的非漸進界的主要結論SLT的發展簡況(續)Vapnik和Chervonenkis(1974)提出了結構風險最小化（SRM）歸納原則。Vapnik和Chervonenkis(1989)發覺了閱歷風險最小化歸納原則和最大似然方法一樣性的充分必要條件,完成了對閱歷風險最小化歸納推理的分析。90年頭中期,有限樣本狀況下的機器學習理論探討漸漸成熟起來,形成了較完善的理論體系—統計學習理論(StatisticalLearningTheory,簡稱SLT)8.4統計學習理論的基本內容機器學習的基本問題統計學習理論的核心內容8.4.1機器學習的基本問題機器學習問題的表示學習問題的表示產生器(G)，產生隨機向量x屬于Rn,它們是從固定但未知的概率分布函數F(x)中獨立抽取的。訓練器(S)，對每個輸入向量x返回一個輸出值y，產生輸出的依據是同樣固定但未知的條件分布函數F(y|x)。學習機器(LM)，它能夠實現確定的函數集f(x,a)，a屬于A，其中A是參數集合。8.4.2機器學習的基本問題機器學習就是從給定的函數集f(x,)(是參數)中,選擇出能夠最好地靠近訓練器響應的函數。機器學習的目的可以形式化地表示為：依據n個獨立同分布的觀測樣本， 在一組函數中求出一個最優函數對訓練器的響應進行估計,使期望風險最小

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

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

來靠近期望風險。閱歷風險最小化(ERM)原則：運用對參數w求閱歷風險的最小值代替求期望風險的最小值。閱歷風險最小化從期望風險最小化到閱歷風險最小化沒有牢靠的依據,只是直觀上合理的想當然。期望風險和閱歷風險都是w的函數,概率論中的大數定理只說明白當樣本趨于無窮多時閱歷風險將在概率意義上趨近于期望風險,并沒有保證兩個風險的w是同一點,更不能保證閱歷風險能夠趨近于期望風險。即使有方法使這些條件在樣本數無窮大時得到保證,也無法認定在這些前提下得到的閱歷風險最小化方法在樣本數有限時仍能得到好的結果。困難性與推廣實力學習機器對將來輸出進行正確預料的實力稱作推廣實力（也稱為“泛化實力”）。在某些狀況下,訓練誤差過小反而導致推廣實力的下降,這就是過學習問題。神經網絡的過學習問題是閱歷風險最小化原則失敗的一個典型例子。用三角函數擬合隨意點學習的示例困難性與推廣實力（續）在有限樣本狀況下，閱歷風險最小并不確定意味著期望風險最小；學習機器的困難性不但與所探討的系統有關,而且要和有限的學習樣本相適應；學習精度和推廣性之間似乎是一對不行調和的沖突,接受困難的學習機器雖然簡潔使得學習誤差更小,卻往往丟失推廣性；傳統的解決方法（例如：接受正則化、模型選擇、噪聲干擾等方法以限制學習機器的困難度）缺乏堅實的理論基礎。8.5統計學習理論的核心內容SLT被認為是目前針對有限樣本統計估計和預料學習的最佳理論，它從理論上較為系統地探討了閱歷風險最小化原則成立的條件、有限樣本下閱歷風險與期望風險的關系及如何利用這些理論找到新的學習原則和方法等問題。SLT的主要內容包括:基于閱歷風險原則的統計學習過程的一樣性理論學習過程收斂速度的非漸進理論限制學習過程的推廣實力的理論構造學習算法的理論VC維(函數的多樣性)為了探討閱歷風險最小化函數集的學習一樣收斂速度和推廣性，SLT定義了一些指標來衡量函數集的性能，其中最重要的就是VC維(Vapnik-ChervonenkisDimension)。VC維：對于一個指示函數（即只有0和1兩種取值的函數）集，假如存在h個樣本能夠被函數集里的函數依據全部可能的2h種形式分開，則稱函數集能夠把h個樣本打散，函數集的VC維就是能夠打散的最大樣本數目。假如對隨意的樣本數，總有函數能打散它們，則函數集的VC維就是無窮大。VC維（續）一般而言,VC維越大,學習實力就越強,但學習機器也越困難。目前還沒有通用的關于計算隨意函數集的VC維的理論,只有對一些特殊函數集的VC維可以精確知道。N維實數空間中線性分類器和線性實函數的VC維是n+1。Sin(ax)的VC維為無窮大。……VC維（續） Openproblem:對于給定的學習函數集,如何用理論或試驗的方法計算其VC維是當前統計學習理論探討中有待解決的一個難點問題。三個里程碑定理推廣性的界SLT系統地探討了閱歷風險和實際風險之間的關系,也即推廣性的界。依據SLT中關于函數集推廣性界的理論,對于指示函數集中全部的函數,閱歷風險和實際風險之間至少以概率滿足如下關系:

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

廣義最優分類面（續3）Lagrange函數一個簡潔的例子：x1=(0,0),y1=+1x2=(1,0),y2=+1x3=(2,0),y3=-1x4=(0,2),y4=-1可調用Matlab中的二次規劃程序，求得1,2,3,4的值，進而求得w和b的值。8.6.3支持向量機很多狀況下，訓練數據集是線性不行分的，Vapnik等人提出了用廣義分類面（松弛子）來解決這一問題。非線性問題——通過非線性變換將它轉化為某個高維空間中的線性問題，在這個高維空間中找尋最優分類面。高維空間中的最優分類面分類函數只涉及到訓練樣本之間的內積運算(xi·xj) ,因此,在高維空間中只需進行內積運算,這種內積運算可通過定義在原空間中的函數來實現,甚至不必知道變換的形式。SLT指出,依據Hibert-Schmidt原理,只要一種運算滿足Mercer條件,就可以作為內積運用。Mercer條件支持向量機在最優分類面中接受適當的內積函數就可以實現某一非線性變換后的線性分類,而計算困難度卻沒有增加。支持向量機8.6.4核函數SVM中不同的內積核函數將形成不同的算法,主要的核函數有三類：多項式核函數徑向基函數S形函數8.6.5支持向量機實現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-toymySVMMATLABsvmtoolbox支持向量機實現8.7探討現狀應用探討支持向量機探討支持向量機算法探討8.7.1應用探討SVM的應用主要于模式識別領域貝爾試驗室對美國郵政手寫數字庫進行的試驗分類器錯誤率人工表現2.5%決策樹C4.516.2%最好的兩層神經網絡5.9%SVM4.0%SVM與神經網絡（NN）的對比SVM的理論基礎比NN更堅實，更像一門嚴謹的“科學”（三要素：問題的表示、問題的解決、證明）SVM——嚴格的數學推理NN——猛烈依靠于工程技巧推廣實力取決于“閱歷風險值”和“置信范圍值”，NN不能限制兩者中的任何一個。NN設計者用超群的工程技巧彌補了數學上的缺陷——設計特殊的結構，利用啟發式算法，有時能得到出人意料的好結果。“我們必需從一起先就澄清一個觀點，就是假如某事不是科學，它并不確定不好。比如說，愛情就不是科學。因此，假如我們說某事不是科學，并不是說它有什么不對，而只是說它不是科學。”——byR.FeynmanfromTheFeynmanLecturesonPhysics,Addison-Wesley同理，與SVM相比，NN不像一門科學，更像一門工程技巧，但并不意味著它就確定不好！主要應用領域手寫數字識別語音識別人臉識別文本分類8.7.2支持向量機探討如何針對不同的問題選擇不同的核函數照舊是一個懸而未決的問題。標準的SVM對噪聲是不具有魯棒性的,如何選擇合適的目標函數以實現魯棒性是至關重要的。8.7.3支持向量機算法探討支持向量機的本質是解一個二次規劃問題,雖然有一些經典（如對偶方法、內點算法等）,但當訓練集規模很大時,這些算法面臨著維數災難問題。為此,人們提出了很多針對大規模數據集的SVM訓練算法。支持向量機算法探討（續1）思路1：分解子問題塊算法SMO算法(SequentialMinimalOptimization)思路2：序列優化思路3：近鄰SVM支持向量機算法探討（續2）訓練SVM的絕大多數算法都是針對分類問題,只有一小部分算法考慮了回來函數的估計問題。提高算法效率、降低困難度。支持向量機算法探討（續3）SVM增量學習算法的探討超球面SVM算法探討One-classSVM算法……SVM多值分類器算法One-against-the-rest（一對多方法）One-against-one（一對一方法）Multi-classObjectiveFunctions（多類SVM）DecisionDirectedAcyclicGraph,DDAGSVMDecisionTree