2009高級人工智能大綱日歷及教案6支持向量機

1、2022/7/101第八章支持向量機 Support Vector Machines 2022/7/102內(nèi)容提要統(tǒng)計學習方法概述學習問題的表示學習過程的泛化能力支持向量機SVM尋優(yōu)算法應用2022/7/103統(tǒng)計學習方法概述 統(tǒng)計方法是從事物的外在數(shù)量上的表現(xiàn)去推斷該事物可能的規(guī)律性?？茖W規(guī)律性的東西一般總是隱藏得比較深，最初總是從其數(shù)量表現(xiàn)上通過統(tǒng)計分析看出一些線索，然后提出一定的假說或?qū)W說，作進一步深入的理論研究。當理論研究 提出一定的結(jié)論時，往往還需要在實踐中加以驗證。就是說，觀測一些自然現(xiàn)象或?qū)ｉT安排的實驗所得資料，是否與理論相符、在多大的程度上相符、偏離可能是朝哪個方向等等問題，都

2、需要用統(tǒng)計分析的方法處理。2022/7/104統(tǒng)計學習方法概述 近百年來，統(tǒng)計學得到極大的發(fā)展。我們可用下面的框架粗略地刻劃統(tǒng)計學發(fā)展的過程：1900-1920 數(shù)據(jù)描述1920-1940 統(tǒng)計模型的曙光1940-1960 數(shù)理統(tǒng)計時代隨機模型假設的挑戰(zhàn)松弛結(jié)構(gòu)模型假設1990-1999 建模復雜的數(shù)據(jù)結(jié)構(gòu)2022/7/105統(tǒng)計學習方法概述 從1960年至1980年間，統(tǒng)計學領域出現(xiàn)了一場革命，要從觀測數(shù)據(jù)對依賴關(guān)系進行估計，只要知道未知依賴關(guān)系所屬的函數(shù)集的某些一般的性質(zhì)就足夠了。引導這一革命的是60年代的四項發(fā)現(xiàn)：Tikhonov, Ivanov 和 Philips 發(fā)現(xiàn)的關(guān)于解決不適定

3、問題的正則化原則；Parzen, Rosenblatt 和Chentsov 發(fā)現(xiàn)的非參數(shù)統(tǒng)計學；Vapnik 和Chervonenkis 發(fā)現(xiàn)的在泛函數(shù)空間的大數(shù)定律，以及它與學習過程的關(guān)系；Kolmogorov, Solomonoff 和Chaitin 發(fā)現(xiàn)的算法復雜性及其與歸納推理的關(guān)系。 這四項發(fā)現(xiàn)也成為人們對學習過程研究的重要基礎。2022/7/106統(tǒng)計學習方法概述 統(tǒng)計學習方法：傳統(tǒng)方法: 統(tǒng)計學在解決機器學習問題中起著基礎性的作用。傳統(tǒng)的統(tǒng)計學所研究的主要是漸近理論，即當樣本趨向于無窮多時的統(tǒng)計性質(zhì)。統(tǒng)計方法主要考慮測試預想的假設和數(shù)據(jù)模型擬合。它依賴于顯式的基本概率模型。 模糊

4、集粗糙集支持向量機2022/7/107統(tǒng)計學習方法概述 統(tǒng)計方法處理過程可以分為三個階段：（1）搜集數(shù)據(jù)：采樣、實驗設計（2）分析數(shù)據(jù)：建模、知識發(fā)現(xiàn)、可視化（3）進行推理：預測、分類 常見的統(tǒng)計方法有: 回歸分析（多元回歸、自回歸等） 判別分析（貝葉斯判別、費歇爾判別、非參數(shù)判別等） 聚類分析（系統(tǒng)聚類、動態(tài)聚類等） 探索性分析（主元分析法、相關(guān)分析法等）等。2022/7/108支持向量機SVM是一種基于統(tǒng)計學習理論的機器學習方法，它是由Boser,Guyon, Vapnik在COLT-92上首次提出，從此迅速發(fā)展起來，目前已經(jīng)在許多智能信息獲取與處理領域都取得了成功的應用。 2022/7/

5、109內(nèi)容提要統(tǒng)計學習方法概述學習問題的表示學習過程的泛化能力支持向量機SVM尋優(yōu)算法應用2022/7/1010函數(shù)估計模型The Function Estimation Model of learning examples:產(chǎn)生器 (G) generates observations x (typically in Rn), independently drawn from some fixed distribution F(x)訓練器Supervisor (S) labels each input x with an output value y according to some fix

6、ed distribution F(y|x)學習機Learning Machine (LM) “l(fā)earns” from an i.i.d. （獨立同分布）l-sample of (x,y)-pairs output from G and S, by choosing a function that best approximates S from a parameterised function class f(x,)（預測函數(shù)集）, where is in the parameter set關(guān)鍵概念: F(x,y), an i.i.d. l-sample on F, functions f

7、(x,) and the equivalent representation of each f using its index GSLMxyy2022/7/1011 風險最小化問題損失函數(shù) loss functional (L, Q)the error of a given function on a given example風險函數(shù)risk functional (R)the expected loss of a given function on an example drawn from F(x,y) the (usual concept of) generalisation err

8、or of a given function2022/7/1012學習問題的一般表示學習目標Given an i.i.d. l-sample z1,zl drawn from a fixed distribution F(z)For a function class loss functionals Q(z,), with in We wish to minimise the risk, finding a function *2022/7/1013學習問題的一般表示經(jīng)驗風險最小化歸納原則 (The Empirical Risk Minimization (ERM) Inductive Pri

9、nciple)Define the empirical risk (sample/training error):Define the empirical risk minimiser:ERM approximates Q(z,*) with Q(z,l) the Remp minimiserthat is ERM approximates * with lLeast-squares and Maximum-likelihood are realisations of ERM2022/7/1014學習理論的四個部分1. 學習過程的一致性理論What are (necessary and suf

10、ficient) conditions for consistency (convergence of Remp to R) of a learning process based on the ERM Principle?2.學習過程收斂速度的非漸近理論How fast is the rate of convergence of a learning process?3. 控制學習過程的泛化能力理論How can one control the rate of convergence (the generalization ability) of a learning process?4.

11、構(gòu)造學習算法的理論 How can one construct algorithms that can control the generalization ability?2022/7/1015內(nèi)容提要統(tǒng)計學習方法概述學習問題的表示學習過程的泛化能力支持向量機SVM尋優(yōu)算法應用2022/7/1016結(jié)構(gòu)風險最小化歸納原則 (SRM)ERM is intended for relatively large samples (large l/h)Large l/h induces a small which decreases the the upper bound on riskSmall s

12、amples? Small empirical risk doesnt guarantee anything!we need to minimise both terms of the RHS of the risk boundsThe empirical risk of the chosen An expression depending on the VC dimension of 2022/7/1017結(jié)構(gòu)風險最小化歸納原則 (SRM)The Structural Risk Minimisation (SRM) PrincipleLet S = Q(z,),. An admissible

13、 structure S1S2SnS:For each k, the VC dimension hk of Sk is finite and h1h2hnhSEvery Sk is either is non-negative bounded, or satisfies for some (p,k)2022/7/1018The SRM Principle continuedFor given z1,zl and an admissible structure S1S2Sn S, SRM chooses function Q(z,lk) minimising Remp in Sk for whi

14、ch the guaranteed risk (risk upper-bound) is minimalThus manages the unavoidable trade-off of quality of approximation vs. complexity of approximationS1S2Snhh1hnh*結(jié)構(gòu)風險最小化歸納原則 (SRM)2022/7/1019 Sn S*經(jīng)驗風險Empirical risk置信范圍Confidence interval風險界限Bound on the riskh1h*hnhS1S*Sn結(jié)構(gòu)風險最小化歸納原則 (SRM)2022/7/1020

15、Overfitting and underfittingProblem: how rich class of classifications q(x;) to use.underfittingoverfittinggood fitProblem of generalization: a small emprical risk Remp does not imply small true expected risk R.2022/7/1021內(nèi)容提要統(tǒng)計學習方法概述學習問題的表示學習過程的泛化能力支持向量機SVM尋優(yōu)算法應用2022/7/1022支持向量機 SVMSVMs are learnin

16、g systems that use a hyperplane of linear functionsin a high dimensional feature space Kernel functiontrained with a learning algorithm from optimization theory LagrangeImplements a learning bias derived from statistical learning theory Generalisation SVM is a classifier derived from statistical lea

17、rning theory by Vapnik and Chervonenkis2022/7/1023 線性分類器ayestdenotes +1denotes -1f xf(x,w,b) = sign(w. x - b)How would you classify this data?2022/7/1024線性分類器f xayestdenotes +1denotes -1f(x,w,b) = sign(w. x - b)How would you classify this data?2022/7/1025線性分類器f xayestdenotes +1denotes -1f(x,w,b) = s

18、ign(w. x - b)How would you classify this data?Copyright 2001, 2003, Andrew W. Moore2022/7/1026線性分類器f xayestdenotes +1denotes -1f(x,w,b) = sign(w. x - b)How would you classify this data?Copyright 2001, 2003, Andrew W. Moore2022/7/1027線性分類器f xayestdenotes +1denotes -1f(x,w,b) = sign(w. x - b)How would

19、 you classify this data?Copyright 2001, 2003, Andrew W. Moore2022/7/1028最大間隔f xayestdenotes +1denotes -1f(x,w,b) = sign(w. x - b)The maximum margin linear classifier is the linear classifier with the maximum margin.This is the simplest kind of SVM (Called an LSVM)Linear SVMCopyright 2001, 2003, Andr

20、ew W. Moore2022/7/1029分類超平面Training set: (xi, yi), i=1,2,N; yi+1,-1Hyperplane: wx+b=0This is fully determined by (w,b)2022/7/1030最大間隔According to a theorem from Learning Theory, from all possible linear decision functions the one that maximises the margin of the training set will minimise the genera

21、lisation error.2022/7/1031最大間隔原則Note1: decision functions (w,b) and (cw, cb) are the sameNote2: but margins as measured by the outputs of the function xwx+b are not the same if we take (cw, cb).Definition: geometric margin: the margin given by the canonical decision function, which is when c=1/|w| S

22、trategy: 1) we need to maximise the geometric margin! (cf result from learning theory)2) subject to the constraint that training examples are classified correctly wwx+b=0wx+b0wx+b1wx+b非線性分劃代價：2維空間內(nèi)積6維空間內(nèi)積非線性分類2022/7/1055為此，引進函數(shù)有比較(2)和(3)，可以發(fā)現(xiàn)這是一個重要的等式，提示6維空間中的內(nèi)積可以通過計算 中2維空間中的內(nèi)積 得到。非線性分類2022/7/1056實現(xiàn)

23、非線性分類的思想給定訓練集后，決策函數(shù)僅依賴于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數(shù) ，一旦選定了函數(shù)，就可以求解最優(yōu)化問題得 ，而決策函數(shù)2022/7/1057決策函數(shù)其中實現(xiàn)非線性分類的思想2022/7/1058設 是 中的一個子集。稱定義在 上的函數(shù) 是核函數(shù)(正定核或核)，如果存在著從 到某一個空間 的映射使得其中 表示 中的內(nèi)積核函數(shù)(核或正定核)定義2022/7/1059多項式內(nèi)核徑向基函數(shù)內(nèi)核RBFSigmoind內(nèi)核目前研究最多的核函數(shù)主要有三類：得到q 階多項式分類器每個基函數(shù)中心對應一個支持向量，它們及輸出權(quán)值由算法自動確定包含一

24、個隱層的多層感知器，隱層節(jié)點數(shù)是由算法自動確定核函數(shù)的選擇2022/7/1060多項式內(nèi)核The kind of kernel represents the inner product of two vector(point) in a feature space of dimension.For example2022/7/1061內(nèi)容提要統(tǒng)計學習方法概述學習問題的表示學習過程的泛化能力支持向量機SVM尋優(yōu)算法應用2022/7/1062Edgar Osuna(Cambridge,MA)等人在IEEE NNSP97發(fā)表了An Improved Training Algorithm for Su

25、pport Vector Machines ,提出了SVM的分解算法，即將原問題分解為若干個子問題，按照某種迭代策略，通過反復求解子問題，最終使得結(jié)果收斂于原問題的最優(yōu)解。傳統(tǒng)的利用二次型優(yōu)化技術(shù)解決對偶問題時： 需要計算存儲核函數(shù)矩陣。當樣本點數(shù)較大時，需要很大的存儲空間。例如：當樣本點超過4000時，存儲核函數(shù)矩陣就需要多達128兆內(nèi)存； SVM在二次型尋優(yōu)過程中要進行大量的矩陣運算，通常尋優(yōu)算法占用了算法時間的主要部分。SVM尋優(yōu)算法2022/7/1063考慮去掉Lagrange乘子等于零的訓練樣本不會影響原問題的解，采用一部分樣本構(gòu)成工作樣本集進行訓練，移除其中的非支持向量，并把訓練結(jié)

26、果對剩余樣本進行檢驗，將不符合KKT條件的樣本與本次結(jié)果的支持向量合并成為一個新的工作集。然后重新訓練，如此重復獲得最優(yōu)結(jié)果。例如：基于這種思路的 算法。根據(jù)子問題的劃分和迭代策略的不同，大致分為：塊算法(Chunking Algorithm)：SVM尋優(yōu)算法2022/7/1064SMO使用了塊與分解技術(shù)，而SMO算法則將分解算法思想推向極致，每次迭代僅優(yōu)化兩個點的最小子集，其威力在于兩個數(shù)據(jù)點的優(yōu)化問題可以獲得解析解，從而不需要將二次規(guī)劃優(yōu)化算法作為算法一部分。盡管需要更多的迭代才收斂，但每個迭代需要很少的操作，因此算法在整體上的速度有數(shù)量級的提高。另外，算法其他的特征是沒有矩陣操作，不需要

27、在內(nèi)存中存儲核矩陣。塊算法(Chunking Algorithm)：SVM尋優(yōu)算法2022/7/1065SMO算法每次迭代時，在可行的區(qū)域內(nèi)選擇兩點，最大化目標函數(shù)，從而優(yōu)化兩個點的最小子集。無論何時，當一個乘子被更新時，調(diào)整另一個乘子來保證線性約束條件成立，保證解不離開可行區(qū)域。每步SMO選擇兩個參數(shù)優(yōu)化，其他參數(shù)固定，可以獲得解析解。盡管需要更多的迭代才收斂，但每個迭代需要很少的操作，因此算法在整體上的速度有數(shù)量級的提高。另外，算法其他的特征是沒有矩陣操作，不需要在內(nèi)存中存儲核矩陣。SVM尋優(yōu)算法2022/7/1066SVM尋優(yōu)算法類別名稱測試樣本數(shù)錯誤分類數(shù)準確度（%）政治146497.

28、26軍事830100經(jīng)濟137397.81法律32293.75農(nóng)業(yè)106298.11體育90198.89衛(wèi)生34197.06工業(yè)87297.70科技111298.20交通40197.50生活91198.90宗教30100天氣24291.67合計9842197.872022/7/1067SMO算法核緩存算法SMO算法在每次迭代只選擇兩個樣本向量優(yōu)化目標函數(shù)，不需要核矩陣。雖然沒有核矩陣操作，但仍需要計算被選向量和訓練集中所有樣本向量的核函數(shù)，計算次數(shù)為2n（n為訓練集中的樣本數(shù)）。如果訓練集中的樣本選取有誤，在噪聲比較多的情況下，收斂會很慢，迭代次數(shù)很多，則核函數(shù)的計算量也是非?？捎^的，SMO

29、算法的優(yōu)點就完成失去了。同時，考慮到文本分類的文本向量一般維數(shù)比較大，核函數(shù)的計算將會非常耗時，尤其在高價多項式核和高斯核等核函數(shù)的計算中表現(xiàn)更加明顯。SVM尋優(yōu)算法2022/7/1068SMO算法核緩存算法在內(nèi)存中為SMO算法核函數(shù)開辟n行m列的核矩陣空間。其中：n為訓練集中的樣本數(shù)；m是為可調(diào)節(jié)參數(shù)，根據(jù)實際的內(nèi)存大小進行調(diào)整，每列存放訓練集中某個樣本向量與訓練集中所有樣本向量的核函數(shù)計算結(jié)果列表。在核矩陣列頭生成m個節(jié)點的雙向循環(huán)鏈表隊列，每個節(jié)點指向核矩陣的列，通過雙向循環(huán)鏈表隊列實現(xiàn)核矩陣中的核函數(shù)列喚入喚出操作。同時，為了實現(xiàn)樣本向量的核函數(shù)列的快速查找，為每個訓練樣本向量設計了快

30、速索引列表，通過索引列表判斷該訓練樣本向量的核函數(shù)列是否在核矩陣中，并確定在哪一列。SVM尋優(yōu)算法2022/7/1069SVM尋優(yōu)算法選擇一個訓練集，通過調(diào)整核緩沖參數(shù)的大小，記錄不同核緩存大小情況下訓練時間，結(jié)果如下表：核緩存大小(Mb)訓練樣本數(shù)核矩陣迭代次數(shù)訓練時間(M:S)156245624*23407267:061056245624*233407263:502056245624*466407262:413056245624*699407261:564056245624*932407261:295056245624*1165407261:236056245624*1398407261:

31、087056245624*1631407261:058056245624*1864407261:049056245624*2097407261:0710056245624*2330407261:3725056245624*5624407261:122022/7/1070通過引入核緩存機制，有效的改進了SMO算法，提高了文本分類的訓練速度。在核緩存機制中采用簡單的hash查找算法和隊列FILO算法，有效提高了核矩陣查找和喚入喚出操作的效率。設置核矩陣列參數(shù)，通過調(diào)節(jié)列參數(shù)，可以靈活的根據(jù)系統(tǒng)運行情況調(diào)整訓練的時間和空間開銷，避免因系統(tǒng)空間開銷過大使系統(tǒng)運行效率下降，反而影響訓練速度。SVM尋優(yōu)算

32、法2022/7/1071活動向量集選擇算法 當訓練樣本數(shù)非常大的時候，如果系統(tǒng)能夠提供的核緩沖大小很有限，那么能夠同時保存在核緩沖中訓練樣本的核函數(shù)數(shù)目在訓練樣本數(shù)中所占比例將非常的小。在訓練過程中，訓練樣本在核緩沖中的核函數(shù)命中率將顯著下降，導致核緩沖中的核函數(shù)被頻繁的喚入喚出，而每執(zhí)行一次喚入喚出操作將引起系統(tǒng)重新計算訓練樣本的核函數(shù)，核緩存的作用被很大程度的削弱了。如果出現(xiàn)這樣的情況，要么增加系統(tǒng)的存儲空間；要么減少訓練樣本數(shù)，才能提高系統(tǒng)的訓練速度。為解決訓練樣本數(shù)多，系統(tǒng)內(nèi)存空間小的矛盾，本文通過活動向量集選擇算法，比較好地解決了這個問題。 SVM尋優(yōu)算法2022/7/1072活動向

33、量集選擇算法 算法的主要思想是：定期檢查訓練樣本集，在收斂前預先確定訓練樣本集中一些邊界上的點（alpha=0，或者alpha=C）是否以后不再被啟發(fā)式選擇，或者不再被判定為最有可能違例，如果存在這樣的點，將它們從訓練樣本集中剔除出去，減少參加訓練的樣本數(shù)。該算法基于如下的認識：經(jīng)過多次迭代后，如果樣本的拉格朗日乘子一直為0，該點被當前估計的支持向量集所確定的超平面區(qū)分得很開，即使以后支持向量集發(fā)生變化，該點也不會是最靠近超平面的點，則可以確定該樣本不是支持向量；經(jīng)過多次迭代后，如果樣本的拉格朗日乘子一直為非常大的C常數(shù)，即使以后支持向量集發(fā)生變化，該點也不會遠離超平面，則可以確定該樣本是上邊

34、界處的支持向量SVM尋優(yōu)算法2022/7/1073活動向量集選擇算法 這樣就可以在SMO算法收斂前，提前將邊界上的點從訓練樣本集中剔除，逐漸縮小參加訓練的活動樣本集，從而減少SMO算法對核緩存空間的要求，提高訓練速度。訓練開始前，訓練活動集樣本初始化為全部訓練樣本。每經(jīng)過一定次數(shù)的迭代（比如迭代1000次），如果算法還沒有收斂，應檢查活動集中的向量，檢查是否有訓練樣本可以不參加迭代運算。檢查完當前活動向量集中所有樣本后，產(chǎn)生了新的活動向量集。如果新的活動向量集的樣本數(shù)減少一成以上（含一成），則可以收縮當前活動向量集，用新的活動向量集替換當前活動向量集。當活動向量集的樣本數(shù)減少到一定的程度，對核緩存空間的要求不是很大的時候，繼續(xù)減少訓練樣本對訓練速度的提高就非常有限了，這時就沒有必要再減少訓練樣本了。SVM尋優(yōu)算法2022/7/1074將工作樣本集的大小固定在算法速度可以容忍的限度內(nèi)，迭代過程選擇一種合適的換入換出策略，將剩余樣本中的一部分與工作樣本集中的樣本進行等量交換，即使支持向量的個數(shù)超過工作樣本集的大小，也不改變工作樣本集的規(guī)模，而只對支持向量中的一部分進行優(yōu)化。例如: 算法2. 固定工作樣本集 (Osuna et al.)：SVM尋優(yōu)算法2022/7/1075內(nèi)容提要統(tǒng)計學習方法概述學習問題的表示學習過程的