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

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

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

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

5、109內容提要統計學習方法概述學習問題的表示學習過程的泛化能力支持向量機SVM尋優算法應用2022/7/1010函數估計模型The Function Estimation Model of learning examples:產生器 (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) “learns” 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,)（預測函數集）, where is in the parameter set關鍵概念: 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 風險最小化問題損失函數 loss functional (L, Q)the error of a given function on a given example風險函數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學習問題的一般表示經驗風險最小化歸納原則 (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、構造學習算法的理論 How can one construct algorithms that can control the generalization ability?2022/7/1015內容提要統計學習方法概述學習問題的表示學習過程的泛化能力支持向量機SVM尋優算法應用2022/7/1016結構風險最小化歸納原則 (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結構風險最小化歸納原則 (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*結構風險最小化歸納原則 (SRM)2022/7/1019 Sn S*經驗風險Empirical risk置信范圍Confidence interval風險界限Bound on the riskh1h*hnhS1S*Sn結構風險最小化歸納原則 (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內容提要統計學習方法概述學習問題的表示學習過程的泛化能力支持向量機SVM尋優算法應用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維空間內積6維空間內積非線性分類2022/7/1055為此，引進函數有比較(2)和(3)，可以發現這是一個重要的等式，提示6維空間中的內積可以通過計算 中2維空間中的內積 得到。非線性分類2022/7/1056實現

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

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

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

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

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

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

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

30、速索引列表，通過索引列表判斷該訓練樣本向量的核函數列是否在核矩陣中，并確定在哪一列。SVM尋優算法2022/7/1069SVM尋優算法選擇一個訓練集，通過調整核緩沖參數的大小，記錄不同核緩存大小情況下訓練時間，結果如下表：核緩存大小(Mb)訓練樣本數核矩陣迭代次數訓練時間(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算法，有效提高了核矩陣查找和喚入喚出操作的效率。設置核矩陣列參數，通過調節列參數，可以靈活的根據系統運行情況調整訓練的時間和空間開銷，避免因系統空間開銷過大使系統運行效率下降，反而影響訓練速度。SVM尋優算

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

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

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