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