統(tǒng)計學習StatisticalLearning

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

2、得到極大的發(fā)展。我們可用下面的框架粗略地刻劃統(tǒng)計學發(fā)展的過程：1900-1920 數據描述1920-1940 統(tǒng)計模型的曙光1940-1960 數理統(tǒng)計時代隨機模型假設的挑戰(zhàn)松弛結構模型假設1990-1999 建模復雜的數據結構統(tǒng)計學習方法概述 從1960年至1980年間，統(tǒng)計學領域出現了一場革命，要從觀測數據對依賴關系進行估計，只要知道未知依賴關系所屬的函數集的某些一般的性質就足夠了。引導這一革命的是60年代的四項發(fā)現：Tikhonov, Ivanov 和 Philips 發(fā)現的關于解決不適定問題的正則化原則；Parzen, Rosenblatt 和Chentsov 發(fā)現的非參數統(tǒng)計學；Va

3、pnik 和Chervonenkis 發(fā)現的在泛函數空間的大數定律，以及它與學習過程的關系；Kolmogorov, Solomonoff 和Chaitin 發(fā)現的算法復雜性及其與歸納推理的關系。 這四項發(fā)現也成為人們對學習過程研究的重要基礎。統(tǒng)計學習方法概述 統(tǒng)計學習方法：傳統(tǒng)方法: 統(tǒng)計學在解決機器學習問題中起著基礎性的作用。傳統(tǒng)的統(tǒng)計學所研究的主要是漸近理論，即當樣本趨向于無窮多時的統(tǒng)計性質。統(tǒng)計方法主要考慮測試預想的假設和數據模型擬合。它依賴于顯式的基本概率模型。 模糊集粗糙集支持向量機2022/7/256統(tǒng)計學習方法概述 統(tǒng)計方法處理過程可以分為三個階段：（1）搜集數據：采樣、實驗設計

4、（2）分析數據：建模、知識發(fā)現、可視化（3）進行推理：預測、分類 常見的統(tǒng)計方法有: 回歸分析（多元回歸、自回歸等） 判別分析（貝葉斯判別、費歇爾判別、非參數判別等） 聚類分析（系統(tǒng)聚類、動態(tài)聚類等） 探索性分析（主元分析法、相關分析法等）等。2022/7/257支持向量機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

5、. 1998. Statistical Learning Theory. Wiley-Interscience Publication, John Wiley&Sons, Inc目前已經在許多智能信息獲取與處理領域都取得了成功的應用。 2022/7/258學習問題研究的四個階段Rosenblatt 感知器（60年代）。學習理論基礎的創(chuàng)立（60-70年代） 經驗風險最小，算法復雜性神經網絡（80年代） PAC回到起點（90年代） 多層感知器2022/7/259統(tǒng)計學習理論統(tǒng)計學習理論是小樣本統(tǒng)計估計和預測學習的最佳理論。假設輸出變量Y與輸入變量X之間存在某種對應的依賴關系,即一未知概率分布P(X

6、,Y)，P(X,Y)反映了某種知識。學習問題可以概括為:根據l個獨立同分布( independently drawn and identically distributed )的觀測樣本train set， (x1,y1),(x2,y2),(xn,yn)2022/7/2510函數估計模型學習樣本的函數:產生器 (G) 產生隨機向量x Rn, 它們是從固定但未知的概率分布函數F(x)中獨立抽取的。訓練器Supervisor (S) 對每個輸入向量x 返回一個輸出值y，產生輸出的根據是同樣固定 但未知的條件分布函數 F(y|x)學習機Learning Machine (LM) 它能夠實現一定的函數

7、集f(x,)， ， 其中是參數的集合。GSLMxyy關鍵概念: 學習的問題就是從給定的函數集f(x,)， 中選擇出能夠最好地逼近訓練器響應的函數。這種選擇是基于訓練集的，訓練集由根據聯合分布F(x,y)=F(x)F(y|x)抽取出的l個獨立同分布（i.i.d）觀測 (x1,y1), (x2,y2), ,(xn,yn) 組成2022/7/2511期望風險 學習到一個假設H=f(x, w) 作為預測函數,其中w是廣義參數.它對F(X,Y)的期望風險R(w)是(即統(tǒng)計學習的實際風險)： 其中，f(x,w)稱作預測函數集，w為函數的廣義參數。f(x,w)可以表示任何函數集。L(y,f(x,w)為由于用

8、f(x,w)對y進行預測而造成的損失。不同類型的學習問題有不同形式的損失函數。 2022/7/2512 而對train set上產生的風險Remp(w)被稱為經驗風險(學習的訓練誤差): 首先Remp(w)和R(w)都是w的函數，傳統(tǒng)概率論中的定理只說明了(在一定條件下)當樣本趨于無窮多時Remp(w)將在概率意義上趨近于R(w)，卻沒有保證使Remp(w)最小的點也能夠使R(w) 最小(同步最小)。經驗風險2022/7/2513 根據統(tǒng)計學習理論中關于函數集的推廣性的界的結論，對于兩類分類問題中的指示函數集f(x, w)的所有函數(當然也包括使經驗風險員小的函數)，經驗風險Remp(w)和實

9、際風險R(w)之間至少以不下于1-(01)的概率存在這樣的關系: 經驗風險2022/7/2514 h是函數H=f(x, w)的VC維, l是樣本數. VC維(Vapnik-Chervonenkis Dimension)。模式識別方法中VC維的直觀定義是：對一個指示函數集，如果存在h個樣本能夠被函數集里的函數按照所有可能的2h種形式分開，則稱函數集能夠把h個樣本打散。函數集的VC維就是它能打散的最大樣本數目h。VC維2022/7/2515 一般的學習方法(如神經網絡)是基于 Remp(w) 最小,滿足對已有訓練數據的最佳擬和,在理論上可以通過增加算法（如神經網絡）的規(guī)模使得Remp(w) 不斷降

10、低以至為0。 但是,這樣使得算法（神經網絡）的復雜度增加, VC維h增加,從而(h/l)增大,導致實際風險R(w)增加,這就是學習算法的過擬合(Overfitting). 過學習2022/7/2516過學習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 ex

11、pected risk R.2022/7/2517學習理論的四個部分1. 學習過程的一致性理論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

12、rate of convergence (the generalization ability) of a learning process?4. 構造學習算法的理論 How can one construct algorithms that can control the generalization ability?2022/7/2518結構風險最小化歸納原則 (SRM)ERM is intended for relatively large samples (large l/h)Large l/h induces a small which decreases the the upper

13、 bound on riskSmall samples? 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/2519結構風險最小化歸納原則 (SRM)The Structural Risk Minimisation (SRM) PrincipleLet S =

14、Q(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/2520The SRM Principle continuedFor given z1,zl and an admissible structure S1S2Sn S, SRM chooses function Q(z,lk) minimisi

15、ng 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/2521 Sn S*經驗風險Empirical risk置信范圍Confidence interval風險界限Bound on the riskh1h*hnhS1S*Sn結構風險最小化

16、歸納原則 (SRM)2022/7/2522支持向量機 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 bias derived from statistical learning theory Generalisation SV

17、M is a classifier derived from statistical learning theory by Vapnik and Chervonenkis2022/7/2523 線性分類器ayestf xf(x,w,b) = sign(w. x - b)denotes +1denotes -1How would you classify this data?2022/7/2524線性分類器f xayestdenotes +1denotes -1f(x,w,b) = sign(w. x - b)How would you classify this data?2022/7/252

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

19、+1denotes -1f(x,w,b) = sign(w. x - b)How would you classify this data?Copyright 2001, 2003, Andrew W. Moore2022/7/2528最大間隔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 (Calle

20、d an LSVM)Linear SVMCopyright 2001, 2003, Andrew W. Moore2022/7/2529分類超平面Training set: (xi, yi), i=1,2,N; yi+1,-1Hyperplane: wx+b=0This is fully determined by (w,b)2022/7/2530最大間隔According to a theorem from Learning Theory, from all possible linear decision functions the one that maximises the margi

21、n of the training set will minimise the generalisation error.2022/7/2531最大間隔原則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 canoni

22、cal decision function, which is when c=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/2556為此，引進函數有比較(2)和(3)，可以發(fā)現這是一個重要的等式，提示

23、6維空間中的內積可以通過計算 中2維空間中的內積 得到。非線性分類2022/7/2557實現非線性分類的思想給定訓練集后，決策函數僅依賴于而不需要再考慮非線性變換如果想用其它的非線性分劃辦法，則可以考慮選擇其它形式的函數 ，一旦選定了函數，就可以求解最優(yōu)化問題得 ，而決策函數2022/7/2558決策函數其中實現非線性分類的思想2022/7/2559設 是 中的一個子集。稱定義在 上的函數 是核函數(正定核或核)，如果存在著從 到某一個空間 的映射使得其中 表示 中的內積核函數(核或正定核)定義2022/7/2560多項式內核徑向基函數內核RBFSigmoind內核目前研究最多的核函數主要有三

24、類：得到q 階多項式分類器每個基函數中心對應一個支持向量，它們及輸出權值由算法自動確定包含一個隱層的多層感知器，隱層節(jié)點數是由算法自動確定核函數的選擇2022/7/2561多項式內核The kind of kernel represents the inner product of two vector(point) in a feature space of dimension.For example2022/7/2562Edgar Osuna(Cambridge,MA)等人在IEEE NNSP97發(fā)表了An Improved Training Algorithm for Support V

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

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

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

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

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

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

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

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

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

34、SVM尋優(yōu)算法2022/7/2573活動向量集選擇算法 這樣就可以在SMO算法收斂前，提前將邊界上的點從訓練樣本集中剔除，逐漸縮小參加訓練的活動樣本集，從而減少SMO算法對核緩存空間的要求，提高訓練速度。訓練開始前，訓練活動集樣本初始化為全部訓練樣本。每經過一定次數的迭代（比如迭代1000次），如果算法還沒有收斂，應檢查活動集中的向量，檢查是否有訓練樣本可以不參加迭代運算。檢查完當前活動向量集中所有樣本后，產生了新的活動向量集。如果新的活動向量集的樣本數減少一成以上（含一成），則可以收縮當前活動向量集，用新的活動向量集替換當前活動向量集。當活動向量集的樣本數減少到一定的程度，對核緩存空間的要求

35、不是很大的時候，繼續(xù)減少訓練樣本對訓練速度的提高就非常有限了，這時就沒有必要再減少訓練樣本了。SVM尋優(yōu)算法2022/7/2574將工作樣本集的大小固定在算法速度可以容忍的限度內，迭代過程選擇一種合適的換入換出策略，將剩余樣本中的一部分與工作樣本集中的樣本進行等量交換，即使支持向量的個數超過工作樣本集的大小，也不改變工作樣本集的規(guī)模，而只對支持向量中的一部分進行優(yōu)化。例如: 算法2. 固定工作樣本集 (Osuna et al.)：SVM尋優(yōu)算法2022/7/2575單隱層的前饋神經網絡（Single-hidden Layer Feedforward Neural networks, SLFN）

36、因為結構簡單并且具有一致的逼近能力，成為了ANN模型中研究的熱點。傳統(tǒng)的SLFN普遍采用梯度下降算法來訓練，其收斂速度慢，網絡中所有的參數都要經過多次迭代求得，通常花費時間要幾小時幾天甚至更長，有時甚至還會陷入局部最優(yōu)解。為了解決以上問題，黃廣斌（G.B.Huang）等人于2004年提出了一種新型的SLFN算法，被稱為極限學習機（Extreme Learning Machine，ELM）。該算法不依賴于輸入權值和隱單元偏置的選擇，可以進行隨機賦值，然后通過合適的激活函數得到隱含層的輸出矩陣，網絡的輸出權值可由解析直接求得。整個算法中所有參數的確定無需迭代，無需微調，因此與傳統(tǒng)的訓練方法如BP算

37、法相比，其學習速度更快，泛化性能更好。極限學習機2022/7/2576泛化SLFN(single-hidden layer feedforward network)SLFN:適合任何分段連續(xù)函數輸出函數: 隱含層輸出函數： 輸出函數不必一定是： Sigmoid: RBF:77新的學習理論學習不伴隨遞歸調解：給定任意一個分段連續(xù)函數g，如果連續(xù)目標函數f(x)能被近似通過SLFN中的隱藏節(jié)點，但是SLFN中隱藏節(jié)點的值不需要被調解；所有隱藏節(jié)點的值被隨機產生不需要對訓練的數據有任何了解，這就是，任何連續(xù)目標函數f和任何隨機產生的序列 只要 能滿足最小化：78統(tǒng)一學習平臺適合任何連續(xù)分段函數對于N

38、個任意不同的樣本在SLFN中有L個隱藏節(jié)點和輸出函數并且SLFN被數學建模為： ：隱藏節(jié)點參數 ：鏈接隱含層節(jié)點與輸出層節(jié)點的權值79極限學習機數學建模：H是神經網絡的隱含層輸出矩陣，H的第i列是第i個隱含節(jié)點的輸出其中:80極限學習機學習三步驟：假設一個給定的訓練集隱藏節(jié)點輸出函數 ，隱藏節(jié)點數目L 隨機產生隱藏節(jié)點參數:計算隱藏層輸出矩陣H計算輸出權值其中：81極限學習機特性：需要的數學簡單學習速度快隱藏節(jié)點 和 不僅獨立于訓練數據也獨立于彼此不像那些在產生隱含節(jié)點之前一定要先觀察訓練數據，ELM可以在觀察訓練數據之前產生隱含節(jié)點ELM適合所有有界分段連續(xù)的激活函數ELM看起來比SVM和神

39、經網絡更簡單82極限學習機變種輸出函數：1 Ridge regression theory based on ELM在計算輸出權值 時，加入 到的對角線中：或者83極限學習機變種2 Kernel based on ELM隱含層輸出矩陣（h（x）有時對使用者未知，定義了kernel 矩陣：84SVM applicationsPattern recognitionFeatures: words countsDNA array expression data analysisFeatures: expr. levels in diff. conditionsProtein classificationFeatures: AA composition2022/7/2585Handwritten Digits Recognition2022/7/2586Applying SVMs to Face DetectionThe SVM face-detection system1. Rescale the i