第八章高級人工智能

1、第八章 高級人工智能史忠植中國科學院計算技術研究所支持向量機 Support Vector Machines2022/7/181Chap8 SVM Zhongzhi Shi內容提要統(tǒng)計學習方法概述統(tǒng)計學習問題學習過程的泛化能力支持向量機SVM尋優(yōu)算法應用2022/7/182Chap8 SVM Zhongzhi Shi統(tǒng)計學習方法概述 統(tǒng)計方法是從事物的外在數量上的表現去推斷該事物可能的規(guī)律性。科學規(guī)律性的東西一般總是隱藏得比較深，最初總是從其數量表現上通過統(tǒng)計分析看出一些線索，然后提出一定的假說或學說，作進一步深入的理論研究。當理論研究 提出一定的結論時，往往還需要在實踐中加以驗證。就是說，觀

2、測一些自然現象或專門安排的實驗所得資料，是否與理論相符、在多大的程度上相符、偏離可能是朝哪個方向等等問題，都需要用統(tǒng)計分析的方法處理。2022/7/183Chap8 SVM Zhongzhi Shi統(tǒng)計學習方法概述 近百年來，統(tǒng)計學得到極大的發(fā)展。我們可用下面的框架粗略地刻劃統(tǒng)計學發(fā)展的過程：1900-1920 數據描述1920-1940 統(tǒng)計模型的曙光1940-1960 數理統(tǒng)計時代隨機模型假設的挑戰(zhàn)松弛結構模型假設1990-1999 建模復雜的數據結構2022/7/184Chap8 SVM Zhongzhi Shi統(tǒng)計學習方法概述 從1960年至1980年間，統(tǒng)計學領域出現了一場革命，要從

3、觀測數據對依賴關系進行估計，只要知道未知依賴關系所屬的函數集的某些一般的性質就足夠了。引導這一革命的是60年代的四項發(fā)現：Tikhonov, Ivanov 和 Philips 發(fā)現的關于解決不適定問題的正則化原則；Parzen, Rosenblatt 和Chentsov 發(fā)現的非參數統(tǒng)計學；Vapnik 和Chervonenkis 發(fā)現的在泛函數空間的大數定律，以及它與學習過程的關系；Kolmogorov, Solomonoff 和Chaitin 發(fā)現的算法復雜性及其與歸納推理的關系。 這四項發(fā)現也成為人們對學習過程研究的重要基礎。2022/7/185Chap8 SVM Zhongzhi Sh

4、i統(tǒng)計學習方法概述 統(tǒng)計學習方法：傳統(tǒng)方法: 統(tǒng)計學在解決機器學習問題中起著基礎性的作用。傳統(tǒng)的統(tǒng)計學所研究的主要是漸近理論，即當樣本趨向于無窮多時的統(tǒng)計性質。統(tǒng)計方法主要考慮測試預想的假設和數據模型擬合。它依賴于顯式的基本概率模型。 模糊集粗糙集支持向量機2022/7/186Chap8 SVM Zhongzhi Shi統(tǒng)計學習方法概述 統(tǒng)計方法處理過程可以分為三個階段：（1）搜集數據：采樣、實驗設計（2）分析數據：建模、知識發(fā)現、可視化（3）進行推理：預測、分類 常見的統(tǒng)計方法有: 回歸分析（多元回歸、自回歸等） 判別分析（貝葉斯判別、費歇爾判別、非參數判別等） 聚類分析（系統(tǒng)聚類、動態(tài)聚類

5、等） 探索性分析（主元分析法、相關分析法等）等。2022/7/187Chap8 SVM Zhongzhi Shi支持向量機SVM是一種基于統(tǒng)計學習理論的機器學習方法，它是由Boser,Guyon, Vapnik在COLT-92上首次提出，從此迅速發(fā)展起來Vapnik V N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag, New York Vapnik V N. 1998. Statistical Learning Theory. Wiley-Interscience Publication, John Wi

6、ley&Sons, Inc目前已經在許多智能信息獲取與處理領域都取得了成功的應用。 2022/7/188Chap8 SVM Zhongzhi Shi統(tǒng)計學習理論統(tǒng)計學習理論是小樣本統(tǒng)計估計和預測學習的最佳理論。假設輸出變量Y與輸入變量X之間存在某種對應的依賴關系,即一未知概率分布P(X,Y)，P(X,Y)反映了某種知識。學習問題可以概括為:根據l個獨立同分布( independently drawn and identically distributed )的觀測樣本train set， (x1,y1),(x2,y2),(xn,yn) 2022/7/189Chap8 SVM Zhongzhi

7、Shi函數估計模型學習樣本的函數:產生器 (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 fixed distribution F(y|x)學習機Learning Machine (LM) “l(fā)earns” from an i.i.d. l-sample of (x,y)-pairs o

8、utput 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(x,) and the equivalent representation of each f using its index GSLMxyy2022/7/1810Chap8 SVM Zhongzhi Shi期望風險

9、學習到一個假設H=f(x, w) 作為預測函數,其中w是廣義參數.它對F(X,Y)的期望風險R(w)是(即統(tǒng)計學習的實際風險)： 其中，f(x,w)稱作預測函數集，w為函數的廣義參數。f(x,w)可以表示任何函數集。L(y,f(x,w)為由于用f(x,w)對y進行預測而造成的損失。不同類型的學習問題有不同形式的損失函數。 2022/7/1811Chap8 SVM Zhongzhi Shi 而對train set上產生的風險Remp(w)被稱為經驗風險(學習的訓練誤差): 首先Remp(w)和R(w)都是w的函數，傳統(tǒng)概率論中的定理只說明了(在一定條件下)當樣本趨于無窮多時Remp(w)將在概率

10、意義上趨近于R(w)，卻沒有保證使Remp(w)最小的點也能夠使R(w) 最小(同步最小)。經驗風險2022/7/1812Chap8 SVM Zhongzhi Shi 根據統(tǒng)計學習理論中關于函數集的推廣性的界的結論，對于兩類分類問題中的指示函數集f(x, w)的所有函數(當然也包括使經驗風險員小的函數)，經驗風險Remp(w)和實際風險R(w)之間至少以不下于1-(01)的概率存在這樣的關系: 經驗風險2022/7/1813Chap8 SVM Zhongzhi Shi h是函數H=f(x, w)的VC維, l是樣本數. VC維(Vapnik-Chervonenkis Dimension)。模式

11、識別方法中VC維的直觀定義是：對一個指示函數集，如果存在h個樣本能夠被函數集里的函數按照所有可能的2h種形式分開，則稱函數集能夠把h個樣本打散。函數集的VC維就是它能打散的最大樣本數目h。VC維2022/7/1814Chap8 SVM Zhongzhi Shi 一般的學習方法(如神經網絡)是基于 Remp(w) 最小,滿足對已有訓練數據的最佳擬和,在理論上可以通過增加算法（如神經網絡）的規(guī)模使得Remp(w) 不斷降低以至為0。 但是,這樣使得算法（神經網絡）的復雜度增加, VC維h增加,從而(h/l)增大,導致實際風險R(w)增加,這就是學習算法的過擬合(Overfitting). 過學習2

12、022/7/1815Chap8 SVM Zhongzhi Shi過學習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/1816Chap8 SVM Zhongzhi Shi學習理論的四個部分1. 學習過程的一致性理

13、論What are (necessary and sufficient) 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 abilit

14、y) of a learning process?4. 構造學習算法的理論 How can one construct algorithms that can control the generalization ability?2022/7/1817Chap8 SVM Zhongzhi Shi結構風險最小化歸納原則 (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 samp

15、les? 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/1818Chap8 SVM Zhongzhi Shi結構風險最小化歸納原則 (SRM)The Structural Risk Minimisation (SRM) PrincipleLet S = Q(

16、z,),. An admissible 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/1819Chap8 SVM Zhongzhi ShiThe SRM Principle continuedFor given z1,zl and an admissible structure S1S2Sn S, SRM chooses funct

17、ion Q(z,lk) minimising Remp in Sk for which the guaranteed risk (risk upper-bound) is minimalThus manages the unavoidable trade-off of quality of approximation vs. complexity of approximationS1S2Snhh1hnh*結構風險最小化歸納原則 (SRM)2022/7/1820Chap8 SVM Zhongzhi Shi Sn S*經驗風險Empirical risk置信范圍Confidence interva

18、l風險界限Bound on the riskh1h*hnhS1S*Sn結構風險最小化歸納原則 (SRM)2022/7/1821Chap8 SVM Zhongzhi Shi支持向量機 SVMSVMs are learning 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

19、 bias derived from statistical learning theory Generalisation SVM is a classifier derived from statistical learning theory by Vapnik and Chervonenkis2022/7/1822Chap8 SVM Zhongzhi Shi 線性分類器ayestf xf(x,w,b) = sign(w. x - b)denotes +1denotes -1How would you classify this data?2022/7/1823Chap8 SVM Zhong

20、zhi Shi線性分類器f xayestdenotes +1denotes -1f(x,w,b) = sign(w. x - b)How would you classify this data?2022/7/1824Chap8 SVM Zhongzhi Shi線性分類器f xayestdenotes +1denotes -1f(x,w,b) = sign(w. x - b)How would you classify this data?Copyright 2001, 2003, Andrew W. Moore2022/7/1825Chap8 SVM Zhongzhi Shi線性分類器f x

21、ayestdenotes +1denotes -1f(x,w,b) = sign(w. x - b)How would you classify this data?Copyright 2001, 2003, Andrew W. Moore2022/7/1826Chap8 SVM Zhongzhi Shi線性分類器f xayestdenotes +1denotes -1f(x,w,b) = sign(w. x - b)How would you classify this data?Copyright 2001, 2003, Andrew W. Moore2022/7/1827Chap8 SV

22、M Zhongzhi Shi最大間隔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, Andrew W. Moore2022/7/1828Chap8 SVM Zhongzhi Shi分類超平面Training

23、set: (xi, yi), i=1,2,N; yi+1,-1Hyperplane: wx+b=0This is fully determined by (w,b)2022/7/1829Chap8 SVM Zhongzhi Shi最大間隔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 generalisation error

24、.2022/7/1830Chap8 SVM Zhongzhi Shi最大間隔原則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

25、=1/|w| Strategy: 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/1855Chap8 SVM Zhongzhi Shi為此，引進函數有比較(2)和(3)，可以發(fā)現這是一個重要的等式，提示6維空間中的內積可以通過計算 中

26、2維空間中的內積 得到。非線性分類2022/7/1856Chap8 SVM Zhongzhi Shi實現非線性分類的思想給定訓練集后，決策函數僅依賴于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數 ，一旦選定了函數，就可以求解最優(yōu)化問題得 ，而決策函數2022/7/1857Chap8 SVM Zhongzhi Shi決策函數其中實現非線性分類的思想2022/7/1858Chap8 SVM Zhongzhi Shi設 是 中的一個子集。稱定義在 上的函數 是核函數(正定核或核)，如果存在著從 到某一個空間 的映射使得其中 表示 中的內積核函數(核或正定核)定義

27、2022/7/1859Chap8 SVM Zhongzhi Shi多項式內核徑向基函數內核RBFSigmoind內核目前研究最多的核函數主要有三類：得到q 階多項式分類器每個基函數中心對應一個支持向量，它們及輸出權值由算法自動確定包含一個隱層的多層感知器，隱層節(jié)點數是由算法自動確定核函數的選擇2022/7/1860Chap8 SVM Zhongzhi Shi多項式內核The kind of kernel represents the inner product of two vector(point) in a feature space of dimension.For example202

28、2/7/1861Chap8 SVM Zhongzhi ShiEdgar Osuna(Cambridge,MA)等人在IEEE NNSP97發(fā)表了An Improved Training Algorithm for Support Vector Machines ,提出了SVM的分解算法，即將原問題分解為若干個子問題，按照某種迭代策略，通過反復求解子問題，最終使得結果收斂于原問題的最優(yōu)解。傳統(tǒng)的利用二次型優(yōu)化技術解決對偶問題時： 需要計算存儲核函數矩陣。當樣本點數較大時，需要很大的存儲空間。例如：當樣本點超過4000時，存儲核函數矩陣就需要多達128兆內存； SVM在二次型尋優(yōu)過程中要進行大量的

29、矩陣運算，通常尋優(yōu)算法占用了算法時間的主要部分。SVM尋優(yōu)算法2022/7/1862Chap8 SVM Zhongzhi Shi考慮去掉Lagrange乘子等于零的訓練樣本不會影響原問題的解，采用一部分樣本構成工作樣本集進行訓練，移除其中的非支持向量，并把訓練結果對剩余樣本進行檢驗，將不符合KKT條件的樣本與本次結果的支持向量合并成為一個新的工作集。然后重新訓練，如此重復獲得最優(yōu)結果。例如：基于這種思路的 算法。根據子問題的劃分和迭代策略的不同，大致分為：塊算法(Chunking Algorithm)：SVM尋優(yōu)算法2022/7/1863Chap8 SVM Zhongzhi ShiSMO使用了

30、塊與分解技術，而SMO算法則將分解算法思想推向極致，每次迭代僅優(yōu)化兩個點的最小子集，其威力在于兩個數據點的優(yōu)化問題可以獲得解析解，從而不需要將二次規(guī)劃優(yōu)化算法作為算法一部分。盡管需要更多的迭代才收斂，但每個迭代需要很少的操作，因此算法在整體上的速度有數量級的提高。另外，算法其他的特征是沒有矩陣操作，不需要在內存中存儲核矩陣。塊算法(Chunking Algorithm)：SVM尋優(yōu)算法2022/7/1864Chap8 SVM Zhongzhi ShiSMO算法每次迭代時，在可行的區(qū)域內選擇兩點，最大化目標函數，從而優(yōu)化兩個點的最小子集。無論何時，當一個乘子被更新時，調整另一個乘子來保證線性約束

31、條件成立，保證解不離開可行區(qū)域。每步SMO選擇兩個參數優(yōu)化，其他參數固定，可以獲得解析解。盡管需要更多的迭代才收斂，但每個迭代需要很少的操作，因此算法在整體上的速度有數量級的提高。另外，算法其他的特征是沒有矩陣操作，不需要在內存中存儲核矩陣。SVM尋優(yōu)算法2022/7/1865Chap8 SVM Zhongzhi ShiSVM尋優(yōu)算法類別名稱測試樣本數錯誤分類數準確度（%）政治146497.26軍事830100經濟137397.81法律32293.75農業(yè)106298.11體育90198.89衛(wèi)生34197.06工業(yè)87297.70科技111298.20交通40197.50生活91198.90

32、宗教30100天氣24291.67合計9842197.872022/7/1866Chap8 SVM Zhongzhi ShiSMO算法核緩存算法SMO算法在每次迭代只選擇兩個樣本向量優(yōu)化目標函數，不需要核矩陣。雖然沒有核矩陣操作，但仍需要計算被選向量和訓練集中所有樣本向量的核函數，計算次數為2n（n為訓練集中的樣本數）。如果訓練集中的樣本選取有誤，在噪聲比較多的情況下，收斂會很慢，迭代次數很多，則核函數的計算量也是非?？捎^的，SMO 算法的優(yōu)點就完成失去了。同時，考慮到文本分類的文本向量一般維數比較大，核函數的計算將會非常耗時，尤其在高價多項式核和高斯核等核函數的計算中表現更加明顯。SVM尋優(yōu)

33、算法2022/7/1867Chap8 SVM Zhongzhi ShiSMO算法核緩存算法在內存中為SMO算法核函數開辟n行m列的核矩陣空間。其中：n為訓練集中的樣本數；m是為可調節(jié)參數，根據實際的內存大小進行調整，每列存放訓練集中某個樣本向量與訓練集中所有樣本向量的核函數計算結果列表。在核矩陣列頭生成m個節(jié)點的雙向循環(huán)鏈表隊列，每個節(jié)點指向核矩陣的列，通過雙向循環(huán)鏈表隊列實現核矩陣中的核函數列喚入喚出操作。同時，為了實現樣本向量的核函數列的快速查找，為每個訓練樣本向量設計了快速索引列表，通過索引列表判斷該訓練樣本向量的核函數列是否在核矩陣中，并確定在哪一列。SVM尋優(yōu)算法2022/7/186

34、8Chap8 SVM Zhongzhi ShiSVM尋優(yōu)算法選擇一個訓練集，通過調整核緩沖參數的大小，記錄不同核緩存大小情況下訓練時間，結果如下表：核緩存大小(Mb)訓練樣本數核矩陣迭代次數訓練時間(M:S)156245624*23407267:061056245624*233407263:502056245624*466407262:413056245624*699407261:564056245624*932407261:295056245624*1165407261:236056245624*1398407261:087056245624*1631407261:058056245624*

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

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

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

38、量集發(fā)生變化，該點也不會遠離超平面，則可以確定該樣本是上邊界處的支持向量SVM尋優(yōu)算法2022/7/1872Chap8 SVM Zhongzhi Shi活動向量集選擇算法 這樣就可以在SMO算法收斂前，提前將邊界上的點從訓練樣本集中剔除，逐漸縮小參加訓練的活動樣本集，從而減少SMO算法對核緩存空間的要求，提高訓練速度。訓練開始前，訓練活動集樣本初始化為全部訓練樣本。每經過一定次數的迭代（比如迭代1000次），如果算法還沒有收斂，應檢查活動集中的向量，檢查是否有訓練樣本可以不參加迭代運算。檢查完當前活動向量集中所有樣本后，產生了新的活動向量集。如果新的活動向量集的樣本數減少一成以上（含一成），則

39、可以收縮當前活動向量集，用新的活動向量集替換當前活動向量集。當活動向量集的樣本數減少到一定的程度，對核緩存空間的要求不是很大的時候，繼續(xù)減少訓練樣本對訓練速度的提高就非常有限了，這時就沒有必要再減少訓練樣本了。SVM尋優(yōu)算法2022/7/1873Chap8 SVM Zhongzhi Shi將工作樣本集的大小固定在算法速度可以容忍的限度內，迭代過程選擇一種合適的換入換出策略，將剩余樣本中的一部分與工作樣本集中的樣本進行等量交換，即使支持向量的個數超過工作樣本集的大小，也不改變工作樣本集的規(guī)模，而只對支持向量中的一部分進行優(yōu)化。例如: 算法2. 固定工作樣本集 (Osuna et al.)：SVM

40、尋優(yōu)算法2022/7/1874Chap8 SVM Zhongzhi ShiSVM applicationsPattern recognitionFeatures: words countsDNA array expression data analysisFeatures: expr. levels in diff. conditionsProtein classificationFeatures: AA composition2022/7/1875Chap8 SVM Zhongzhi ShiHandwritten Digits Recognition2022/7/1876Chap8 SVM Zhongzhi ShiApplying SVMs to Face DetectionThe SVM face-detection system1. Rescale the input image several times2. Cut 19x19 window patterns out of the scaled image3. Preprocess the window using mask