機器學(xué)習的一個(gè)比較熱門(mén)的方向是統計機器學(xué)習（另外一個(gè)可能是圖模型，按照Jordan的說(shuō)法是統計機器學(xué)習屬于頻率主義，而圖模型屬于貝葉斯主義）， 對于每一個(gè)做統計機器學(xué)習的研究者來(lái)說(shuō)，他們大致可以分為兩類(lèi)：一類(lèi)做統計學(xué)習理論相關(guān)工作，如泛化界、約簡(jiǎn)或一致性；一類(lèi)做優(yōu)化算法，如支持向量機、Boosting等。作為一個(gè)純統計機器學(xué)習的學(xué)者來(lái)說(shuō)，我想這兩塊內容都得了解。優(yōu)化算法的門(mén)檻低點(diǎn)，可能比較容易上手，了解他們并不太難，比如支持向量機本質(zhì)上是求解一個(gè)RKHS上的二次優(yōu)化問(wèn)題，Boosting是函數空間上的梯度下降優(yōu)化問(wèn)題。統計學(xué)習理論的門(mén)檻高點(diǎn)，需要的基礎數學(xué)知識多點(diǎn)，離計算機出生的人比較遠，因而常常使人望而生畏。最近本人對統計學(xué)習理論這塊做了些整理，發(fā)現其實(shí)這塊東西并非如想象的那么難，他們的本質(zhì)無(wú)非是概率集中不等式在機器學(xué)習上的應用，下面以泛化界為例講一下自己對那塊內容的理解。
Talagrand(1996)說(shuō)過(guò): "A random variable that depends(in a "smooth way") on the influence of many independentvariables(But not too much on any of them) is essentially constant". 中文上的意思是，依賴(lài)于許多獨立隨機變量的隨機變量本質(zhì)上是個(gè)常量，舉個(gè)例子，經(jīng)驗風(fēng)險就是一個(gè)依賴(lài)于一個(gè)隨機訓練樣本集合的隨機變量，因而經(jīng)驗風(fēng)險本質(zhì)上應該是個(gè)常量。正因為如此，這個(gè)隨機變量離開(kāi)它均值的概率就以指數形勢衰減，因此這就是泛化界中常見(jiàn)的如下論述：“以1-\sigma的概率，作如下論斷”的由來(lái)。目前使用的各種泛化界分析工具本質(zhì)上正是基于這個(gè)原理，下面介紹下目前主流的三種泛化界分析方法，VC維，R復雜度和穩定性分析。
為了敘述清楚，如一個(gè)游戲開(kāi)始之前需要設置游戲規則一樣，這里簡(jiǎn)單介紹一下機器學(xué)習問(wèn)題設置。統計機器學(xué)習研究的問(wèn)題一般是，給定一堆帶標簽的訓練樣本集合，需要從訓練集合中學(xué)習出一個(gè)預測器來(lái)，對新的樣本進(jìn)行預測，使得預測結果盡可能的接近它的真實(shí)標簽。相應的，對統計機器學(xué)習理論分析，我們需要做如下一些假設：假設訓練樣本集合是從一個(gè)未知但固定的分布中獨立同分布的抽取出來(lái)，學(xué)習的目標是根據這樣一個(gè)樣本集合，從一個(gè)事先給定的分類(lèi)器集合中挑選出一個(gè)分類(lèi)器，使得分類(lèi)器的對從同一個(gè)分布中隨機抽取的樣本在給定的一個(gè)損失評價(jià)下的風(fēng)險最小。一個(gè)需要特別注意的是，在統計學(xué)習泛化界分析時(shí)，分類(lèi)器的風(fēng)險常常被認為是隨機樣本集上的一個(gè)隨機變量，這樣的隨機風(fēng)險集合(以分類(lèi)器為索引)在統計上被叫做經(jīng)驗過(guò)程。
VC維可能是影響最深也是最早提出來(lái)的泛化界分析方法， V是統計機器學(xué)習理論的墊基者Vapnic的名稱(chēng)的縮寫(xiě)，這從名稱(chēng)上就驗證了VC維在統計機器學(xué)習理論的影響力。這塊的分析得先從Hoeffding不等式說(shuō)起，Hoeffding不等式本質(zhì)說(shuō)明一組獨立隨機變量的均值離開(kāi)它的期望的可能性以指數形式衰減。因此，對于任一給定的分類(lèi)器F（F與訓練樣本集合無(wú)關(guān)), F與每個(gè)隨機樣本結合形成了一個(gè)F作用在該隨機變量上的新的隨機變量(取值0，1，即分對與分錯)，這個(gè)隨機變量的期望剛好是F的期望風(fēng)險，N個(gè)這樣隨機變量的均值剛好是F的經(jīng)驗風(fēng)險，因此，我們獲得了F在N個(gè)訓練樣本集合上的經(jīng)驗風(fēng)險偏離F期望風(fēng)險的可能性的概率描述，為敘述方便，以下簡(jiǎn)稱(chēng)經(jīng)驗風(fēng)險偏離F期望風(fēng)險為偏離情況。然而，這樣的概率描述只能針對一個(gè)F，它所起作用的那部分訓練樣本集合上也直接與F相關(guān)，而我們的學(xué)習是從事先給定的函數空間中選擇一個(gè)F，因此我們并不能保證Hoeffding不等式作用的那個(gè)F就是我們選擇出來(lái)的F，即使假設我們沒(méi)看到訓練樣本集合之前，我們已經(jīng)知道選擇哪個(gè)F，我們在推導該F與最優(yōu)F（函數空間里期望風(fēng)險最小的F）之間關(guān)系時(shí)，也需要一個(gè)不隨樣本集合變化的概率描述。因此，我們需要一個(gè)對函數空間中的所有F一致成立的偏離情況的可能性的概率描述，這就是泛化界里常說(shuō)的uniform。當函數空間的勢是個(gè)有限值時(shí)，這種情況比較容易處理，分別對每個(gè)F運用Hoeffinding不等式，所有的偏離可能性的和就是存在一個(gè)F，它的偏離情況超過(guò)一個(gè)給定值的概率的上界。 反過(guò)來(lái)說(shuō)，即是假設空間里的任何函數都以至少一定的概率，偏離情況小于一個(gè)給定值。當函數空間的勢不是一個(gè)有限值時(shí)，上面的處理就遇到了問(wèn)題，因為無(wú)窮個(gè)偏離可能性的和是個(gè)無(wú)窮大的數，這樣的上界就是個(gè)無(wú)意義的事。為了處理這種情況，我們的先驅者注意到了以下兩個(gè)情況：1）假設空間的中所有函數偏離情況的上確界是所有函數偏離情況的上界；2）在任何有限的樣本上（比如N），盡管函數空間的勢是無(wú)窮的，但是它們作用在有限個(gè)樣本的分類(lèi)情況卻是有限的（上界是2^N）。如果我們能夠找到偏離情況的上確界的概率的一個(gè)上界，并且這個(gè)上界能夠以有限個(gè)樣本上的某種概率表達出來(lái)，我們就能解決問(wèn)題。具體的做法是，可以證明偏離情況的上確界的概率的一個(gè)上界是兩個(gè)同樣大小的從同一分布中抽取的訓練樣本集合經(jīng)驗風(fēng)險之差的概率的上確界。然后對后者就可以使用有限假設空間下的Hoeffinding不等式，得出后者偏離情況的概率描述。為了得到比較精確的界的描述，必須刻畫(huà)函數集合在有限樣本上的分類(lèi)情況，這個(gè)分類(lèi)情況對應的術(shù)語(yǔ)叫生長(cháng)函數，它表示N個(gè)樣本被函數空間的函數們分成不同情況的最大值。為了計算生長(cháng)函數，VC維被定義出來(lái)，它描述了函數集合分類(lèi)樣本的能力，具體表現為函數集合能夠任意分類(lèi)的最大樣本個(gè)數。由生長(cháng)函數和VC維定義馬上知道，當樣本的個(gè)數N小于等于VC維時(shí)，生長(cháng)函數的值等于2^N, 否則生長(cháng)函數的值小于2^N。這也說(shuō)明了，一個(gè)有限VC維空間的生長(cháng)函數并非指數增長(cháng)，從而避免了界的無(wú)意義性。Vapnik老前輩已經(jīng)為我們推導出了生長(cháng)函數與VC維的關(guān)系不等式，將他們之間的關(guān)系降到了多項式，因而我們的界從O(1)->O(sqrt(logn/n))。后人在此基礎上又提出了一些改進(jìn)，主要集中在如何讓不等式的界更緊，比如比生長(cháng)函數小的VC熵，對函數能力的更有效描述的覆蓋數，還有對Hoeffding不等式的改進(jìn)版本Bernstein不等式等。VC維這套理論的建立為統計機器學(xué)習的理論鋪下了堅實(shí)的理論基礎，從此機器學(xué)習變得有理可依，也許這就是機器學(xué)習從人工智能中分離出來(lái)的一個(gè)重要因素之一，然而由于VC維的難以計算，還是給具體應用帶來(lái)了不便(目前常用的一個(gè)事實(shí)是，d維超平面集合的VC維是d+1)。
R復雜度的提出，動(dòng)機之一就是克服VC維的的不容易計算。另外一個(gè)原因是某些算法在無(wú)窮維空間里也獲得了很好的經(jīng)驗性能，然而卻不能用VC維解釋。比如RKHS中的函數都是無(wú)窮維的，在此空間得出的用VC維表達的界是平凡的，無(wú)法對實(shí)際算法設計提供指導。與VC維類(lèi)似，R復雜度也是對一個(gè)函數集合能力的描述，它描述了函數集合擬合噪聲的能力，能力越強，R復雜度越大。R復雜度有兩種：一種是期望R復雜度，一種是經(jīng)驗R復雜度，期望R復雜度與經(jīng)驗R復雜度本質(zhì)上也是經(jīng)驗量與期望量之間的關(guān)系，因而也可以用概率集中不等式描述其中的關(guān)系，經(jīng)驗R復雜度因為是給定了N個(gè)樣本的情況，因而更容易計算。與VC維的分析類(lèi)似，R復雜度的分析也是專(zhuān)注于偏離情況的上確界，與VC維不同的是，這兒使用了一個(gè)比Hoeffinding更強大的不等式McDiarmid集中不等式，由Mcdiarmid不等式我們可以得出，偏離情況與期望偏離情況之間的差的概率描述。其中期望偏離情況的分析比較復雜，通過(guò)一些列分析可以得出期望偏離情況的一個(gè)上界，剛好是函數集的R復雜度，由此我們得到了與VC維類(lèi)似的一個(gè)泛化風(fēng)險界，其中生長(cháng)函數被替換成了R復雜度。R復雜度的計算比VC維容易，常?？梢愿鶕恍┎坏仁饺鏑auchy-Schwarz或Jensen不等式求出，另外機器學(xué)習大牛們還提供了一些組合函數的與個(gè)體函數之間R復雜度的關(guān)系的計算公式，因此對于實(shí)際應用更有指導意義，比如我們可以從中推導出著(zhù)名的Margin界。
VC維和R復雜度存在的一個(gè)問(wèn)題是，它們關(guān)心的都是整個(gè)函數空間的擬合能力，而對算法如何搜索函數空間無(wú)關(guān)，實(shí)際上我們并不需要一個(gè)對整個(gè)函數空間都成立的界，我們關(guān)心的只是我們的算法可能搜索到的函數的泛化能力，此外，描述一個(gè)函數空間能力大小的事也不是一件容易的事情。因此，我們需要一個(gè)能夠僅僅對我們算法搜索出來(lái)的解的泛化能力分析的概率表達式子。因此與前面兩種分析方法不一樣的是，穩定性分析關(guān)心的是算法搜索出來(lái)的解的偏離情況的概率描述。穩定性描述的是當訓練樣本集合中的訓練樣本發(fā)生變動(dòng)時(shí)（常常研究一個(gè)變動(dòng)），算法輸出的分類(lèi)器是如何變化的，用的最多是算法的一致穩定性，它表示，當訓練集合中的一個(gè)樣本被替換或者刪掉時(shí)，分類(lèi)器的輸出的函數在定義域上變動(dòng)的最大值，這個(gè)最大值稱(chēng)為穩定數，即對應于兩個(gè)函數之差的無(wú)窮范數。有了這個(gè)工具后，我們對算法輸出的函數的偏移情況與期望偏移情況使用McDiarmid集中不等式，就可以得出偏移情況的一個(gè)上界，在對期望偏移情況分析，可以得出期望偏移情況的一個(gè)用算法穩定數表示的上界，因此我們得到了一個(gè)用穩定數表達的算法輸出的函數期望風(fēng)險的上界。由于我們需要得到一個(gè)有意義的上界，因此穩定數至少應該長(cháng)得像1/N。接下來(lái)穩定性分析關(guān)心的是，如何計算有效的穩定數的問(wèn)題，大牛們已經(jīng)提供了一套在正則化RKHS空間下的算法穩定性的計算公式，可以發(fā)現這個(gè)空間下的算法的確滿(mǎn)足1/N的形式。
統計機器學(xué)習推動(dòng)了機器學(xué)習的發(fā)展，統計學(xué)習理論的建立為統計機器學(xué)習奠定了堅實(shí)的基礎，隨著(zhù)統計機器學(xué)習理論的發(fā)展，相信不久將來(lái)更緊的更容易指導實(shí)踐的界會(huì )被提出來(lái)。想做這塊研究的人需要一定的數學(xué)基礎，然而，做出來(lái)的東西確很少有實(shí)際價(jià)值，因此需要慎重對待。好了，改天有空再寫(xiě)寫(xiě)自己對一致性或約簡(jiǎn)的一些體會(huì )。
本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請
點(diǎn)擊舉報。
