把統計方法引入機器學習領域，作為機器學習的一個方法論，取得了顯著的成果。AI到底是不是一個完備性問題值得探讨，而模糊邏輯為探索語義完備性的應用範圍開辟了一個好的方向，統計機器學習方法對規則的提取與模糊邏輯表象相似，統計機器學習方法妄圖使用優良資料來表示規則，并使用動态資料描述規則的動态性，使模型成為動态模型，不斷提高準确率和應用範圍。
原文連結：http://www.cvchina.info/2011/07/08/%E7%BB%9F%E8%AE%A1%E5%AD%A6%E4%B9%A0%E9%82%A3%E4%BA%9B%E4%BA%8B/
統計機器學習那些事
香港科技大學 電子與計算機工程系 [email protected]
在港科大拿到PhD，做的是Bioinformatics方面的東西。Bio---informatics 這個領域很亂，從業者水準參差不齊，但随着相關技術（比如Microarray, Genotyping）的進步，這個領域一直風風光光。因為我大學是學計算機電子技術方面的，對這些技術本身并沒有多大的興趣，支援我一路走過來的一個重要原因是我感受到統計學習(Statistical
learning)的魅力。正如大學時代看過的一本網絡小說《悟空傳》所寫的：“你不覺得天邊的晚霞很美嗎？隻有看着她，我才能堅持向西走。”
注解：Genotyping平台是2003年2月成立的平台,它目前正在承擔“國際人類基因組3号和21号染色體單體型圖的建構建構”的項目；Microarray-- 生物基因組計劃,微矩陣方法。
離校前閑來無事，覺得應該把自己的一些感受寫下來，和更多的愛好者分享。
先介紹一下我是如何發現這個領域的。我大學學自動化，大四時接觸到一點智能控制的東西，比如模糊系統，神經網絡。研究所學生階段除了做點小硬體和小軟體，主要的時間花在研究模糊系統上。一個偶然的機會，發現了王立新老師的《模糊系統與模糊控制教材》。我至今依然認為這是有關模糊系統的最好的書，邏輯性非常強。它解答了我當年的很多困惑，然而真正令我心潮澎湃的是這本書的序言，讀起來有一種“飛”的感覺。後來我終于有機會來到港科大，成為立新老師的PhD學生，時長一年半（因為立新老師離開港科大投身産業界了）。立新老師對我的指導很少，總結起來可能就一句話：“你應該去看一下Breiman
和Friedman的文章。”立新老師在我心目中的位置是高高在上的，于是我就忠實地執行了他的話。那一年半的時間裡，我幾乎把他們的文章看了好幾遍。開始不怎麼懂，後來才慢慢懂了，甚至有些癡迷。于是，我把與他們經常合作的一些學者的大部分文章也拿來看了，當時很傻很天真，就是瞎看，後來才知道他們的鼎鼎大名，Hastie, Tibshirani, Efron等。文章看得差不多了，就反複看他們的那本書“The Elements of Statistical learning”（以下簡稱ESL）。說實話，不容易看明白，也沒有人指導，我隻好把文章和書一起反複看，就這樣來來回回折騰。比如為看懂Efron的“Least
angle regression”，我一個人前前後後折騰了一年時間（個人資質太差）。當時國内還有人翻譯了這本書（2006年），把名字翻譯為“統計學習基礎”。我的神啦，這也叫“基礎”！還要不要人學啊！難道絕世武功真的要練三五十年？其實正确的翻譯應該叫“精要”。在我看來，這本書所記載的是絕世武功的要義，強調的是整體的了解，聯系和把握，絕世武功的細節在他們的文章裡。
由于篇幅有限，我就以Lasso 和 Boosting為主線講講自己的體會。故事還得從90年代說起。我覺得90年代是這個領域發展的一個黃金年代，因為兩種絕世武功都在這個時候橫空出世，他們是SVM和Boosted Trees。
先說SVM。大家對SVM的基本原理普遍表述為，SVM通過非線性變換把原空間映射到高維空間，然後在這個高維空間構造線性分類器，因為在高維空間資料點更容易分開。甚至有部分學者認為SVM可以克服維數災難(curse of dimensionality)。如果這樣了解SVM的基本原理，我覺得還沒有看到問題的本質。因為這個看法不能解釋下面的事實：SVM在高維空間裡建構分類器後，為什麼這個分類器不會對原空間的資料集Overfitting呢？
要了解SVM的成功，我覺得可以考慮以下幾個方面：
第一，SVM求解最優分類器的時候，使用了L2-norm regularization( 歐氏距離就可以了嗎？非得用傳說中的 範數.....)，這個是控制Overfitting的關鍵。
第二，SVM不需要顯式地建構非線性映射，而是通過Kernel trick完成，這樣大大提高運算效率。
第三，SVM的優化問題屬于一個二次規劃（Quadratic programming），優化專家們為SVM這個特殊的優化問題設計了很多巧妙的解法，比如SMO（Sequential minimal optimization）解法。
第四， Vapnika的統計學習理論為SVM提供了很好的理論背景（ 這點不能用來解釋為什麼SVM這麼popular，因為由理論導出的bound太loose）。于是SVM成功了，火得一塌糊塗！
再說Boosted Trees。它基本的想法是通過對弱分類器的組合來構造一個強分類器。所謂“弱”就是比随機猜要好一點點；“強”就是強啦。這個想法可以追溯到由Leslie Valiant教授（2010年圖靈獎得主）在80年代提出的probably approximately correct learning (PAC
learning) 理論。不過很長一段時間都沒有一個切實可行的辦法來實作這個理想。細節決定成敗，再好的理論也需要有效的算法來執行。終于功夫不負有心人， Schapire在1996年提出一個有效的算法真正實作了這個夙願，它的名字AdaBoost。
AdaBoost把多個不同的決策樹用一種非随機的方式組合起來，表現出驚人的性能！第一，把決策樹的準确率大大提高，可以與SVM媲美。第二，速度快，且基本不用調參數。第三，幾乎不Overfitting。我估計當時Breiman和Friedman肯定高興壞了，因為眼看着他們提出的CART正在被SVM比下去的時候，AdaBoost讓決策樹起死回生！Breiman情不自禁地在他的論文裡贊揚AdaBoost是最好的現貨方法（off-the-shelf，即“拿下了就可以用”的意思）。其實在90年代末的時候，大家對AdaBoost為什麼有如此神奇的性能迷惑不解。1999年，Friedman的一篇技術報告“Additive
logistic regression: a statistical view of
boosting”解釋了大部分的疑惑（沒有解釋AdaBoost為什麼不容易Overfitting，這個問題好像至今還沒有定論），即搞清楚了AdaBoost在優化什麼名額以及如何優化的。基于此，Friedman提出了他的GBM（Gradient
Boosting Machine，也叫MART或者TreeNet）。幾乎在同時，Breiman另辟蹊徑，結合他的Bagging (Bootstrap aggregating) 提出了Random Forest （今天微軟的Kinect裡面就采用了Random Forest，相關論文Real-time Human Pose Recognition in Parts from Single Depth Images(注：不小心發現，這篇論文是現在我正在拜讀的一篇！)
是CVPR2011的best paper）。
有一個關于Gradient Boosting細節不得不提。Friedman在做實驗的時候發現，把一棵新生成的決策樹，記為f_m，加到目前模型之前，在這棵決策樹前乘以一個小的數，即v×f_m（比如v=0.01），再加入到目前模型中，往往大大提高模型的準确度。他把這個叫做“Shrinkage”。接下來，Hastie，Tibshirani和Friedman進一步發現（我發現大師們都是親自動手寫程式做實驗的），如果把具有Shrinkage的Gradient
Boosting應用到線性回歸中時，得到的Solution Path與Lasso的Solution Path驚人地相似(如圖所示)！他們把這一結果寫在了ESL的第一版裡，并推測這二者存在着某種緊密的聯系，但精确的數學關系他們當時也不清楚。Tibshirani說他們還請教了斯坦福的優化大師（我估計是Stephen Boyd），但還是沒有找到答案。
後來Tibshirani找到自己的恩師Efron。Tibshirani在“The Science of Bradley Efron”這本書的序言裡寫道，“He sat down and pretty much single-handedly solved the problem. Along the way, he developed a new algorithm,
‘least angle regression,’ which is interesting in its own right, and sheds great statistical insight on theLasso.”我就不逐字逐句翻譯了，大意是：Efron獨自擺平了這個問題，與此同時發明了“Least
angle regression (LAR)”。Efron結論是Lasso和Boosting的确有很緊密的數學聯系，它們都可以通過修改LAR得到。更令人驚歎的是LAR具有非常明确的幾何意義。于是，Tibshirani在序言中還有一句，“In this work, Brad shows his great mathematical power–not the twentieth century, abstract kind of math, but the old-fashioned kind:
geometric insight and analysis.”讀Prof Efron的文章，可以感受到古典幾何學與現代統計學的結合之美（推薦大家讀讀Efron教授2010年的一本新書Large-Scale Inference，希望以後有機會再寫寫這方面的體會）！總之，Efron的這篇文章是現代統計學的裡程碑，它結束了一個時代，開啟了另一個時代。
（這裡，想補充說明一下Lasso的身世，它的全稱是The Least Absolute Shrinkage and Selection Operator，讀音不是[‘læso]而是[læ’su:]，有中文翻譯為“套索”，個人覺得這個翻譯不好，太遠離它本來的含義，不如就用Lasso。Tibshrani自己說他的Lasso是受到Breiman的Non-Negative Garrote（NNG）的啟發。
Lasso把NNG的兩步合并為一步，即L1-norm regularization。Lasso的巨大優勢在于它所構造的模型是Sparse的，因為它會自動地選擇很少一部分變量構造模型。現在，Lasso已經家喻戶曉了，但是Lasso出生後的頭兩年卻很少有人問津。後來Tibshirani自己回憶時說，可能是由下面幾個原因造成的：1. 速度問題：當時計算機求解Lasso的速度太慢；2. 了解問題：大家對Lasso模型的性質了解不夠（直到Efron的LAR出來後大家才搞明白）；3. 需求問題：當時還沒有遇到太多高維資料分析的問題，對Sparsity的需求似乎不足。Lasso的遭遇似乎在闡釋我們已經熟知的一些道理：
1.千裡馬常有，而伯樂不常有（沒有Efron的LAR，Lasso可能很難有這麼大的影響力）。2.時勢造英雄（高維資料分析的問題越來越多，比如Bioinformatics領域）。3.金子總是會閃光的。）
LAR把Lasso （L1-norm regularization）和Boosting真正的聯系起來，如同打通了任督二脈（數學細節可以參考本人的一個小結[1]，當然最好還是親自拜讀Efron的原著）。LAR結束了一個晦澀的時代：在LAR之前，有關Sparsity的模型幾乎都是一個黑箱，它們的數學性質（更不要談古典的幾何性質了）幾乎都是缺失。LAR開啟了一個光明的時代：有關Sparsity
的好文章如雨後春筍般地湧現，比如Candes和Tao的Dantzig Selector。伯克利大學的Bin Yu教授稱“Lasso, Boosting and Dantzig are three cousins”。近年來興起的Compressed sensing（Candes & Tao, Donoho）也與LAR一脈相承，隻是更加強調L1-norm regularization其他方面的數學性質，比如Exact Recovery。我覺得這是一個問題的多個方面，Lasso關注的是構模組化型的準确性，Compressed
sensing關注的是變量選擇的準确性。由此引起的關于Sparsity的研究，猶如黃河泛濫，一發不可收拾。比如Low-rank 逼近是把L1-norm從向量到矩陣的自然推廣（現在流行的“使用者推薦系統”用到的Collaborative filtering的數學原理源于此）。有興趣的童鞋可以參考我個人的小結[2]。
還必須提到的是算法問題。我個人覺得，一個好的模型，如果沒有一個快速準确的算法作為支撐的話，它最後可能什麼也不是。看看Lasso頭幾年的冷遇就知道了。LAR的成功除了它漂亮的幾何性質之外，還有它的快速算法。LAR的算法複雜度相當于最小二乘法的複雜度，這幾乎已經把Lasso問題的求解推向極緻。這一記錄在2007年被Friedman的Coordinate Descent（CD）重新整理，至今沒人打破。Hastie教授趣稱這個為“FFT（Friedman
+ Fortran + Tricks）”。因為CD對Generalized Lasso問題并不能一網打盡，許多凸優化解法應運而生，如Gradient Projection， Proximal methods，ADMM (Alternating Direction Method of Multipliers)， (Split) Bregman methods，Nesterov’s method (一階梯度法中最優的收斂速度，Candes 的很多軟體包都根據這個方法設計) 等等。哪個方法更好呢？這個就像問“誰的武功天下第一”一樣。我隻能回答“王重陽以後再也沒有天下第一了，東邪西毒南帝北丐，他們各有各的所長，有的功夫是這個人擅長一些，而另外幾門功夫又是另一個人更擅長一些”。有關L1的算法可能還會大量湧現，正如優化大師Stephen
Boyd所說（2010年9月28日）：“God knows the last thing we need is another algorithm for the Lasso.”
最後我想以讨論“模糊系統”和“統計學習”來結尾。這個話題非常具有争議，我就冒天下之大不諱吧，談一談我這幾年的學習體會。記得十年前，立新老師曾經寫過一篇文章《模糊系統：挑戰與機遇并存——十年研究之感悟》，發表在2001年《自動化學報》上。我2005年看到的時候，敬仰之情，猶如滔滔江水。立新老師曾經有這麼一句話：“If a method works well in practice,
there must be some theoretical reasons for its success.”2005年的時候，我開始問自己什麼使模糊系統的成功？立新老師認為有如下幾個原因：1.模糊系統的通用逼近性能（Universal Approximator）；2.模糊系統快速的構造算法，比如他自己的WM方法，Roger Jang的ANFIS等等；3.結果的可解釋性；4.利用各種不同形式的資訊。
下面我談談自己的看法， 第一，通用逼近性能當然是一個好的性質，它表明模糊系統是很flexible的，但flexible的結構太多了，比如神經網絡。問題往往不在flexible，而在太flexible導緻overfitting。就如同SVM一樣，沒有L2-norm
regularization，實踐中的性能就會變得很差。 第二，快速算法，這是好的方法必備的，SVM，Boosting，Random Forest的算法都很快，而且可以直接用到高維，這一點上，我沒有看到模糊系統的優勢。
第三，可解釋性：模糊系統對低維資料（比如2-4維）的确具有好的解釋性（因為IF-THEN規則的前提和結論都很簡潔），但這個時候其它工具也可以做得到，比如Gradient Boosting和Random Forests（很多例子可以在ESL這本書裡看到）。 第四，充分的利用各種資訊。立新老師指的是IF-THEN規則可以比較自由靈活的加入先驗知識，并在他的書裡面詳細給出執行個體。遺憾的是，這些例子都在處理低維空間的問題。如何用IF-THEN規則解構高維空間呢？我個人看不到它們特殊的優勢。然而，在統計學習裡，利用不同的先驗知識處理高維空間的例子比比皆是，比如Sparsity，group-structure，smoothness等等。現在舉一個Gradient
Boosting machine（GBM，也叫MART）的例子來說明我的觀點。根據Lasso和Boosting的關系，可以知道GBM已經用到了Sparsity的性質（L1-norm regularization）。GBM有兩個參數可以反映我們的先驗知識。第一個參數是深度（depth），控制每棵決策樹的深度 。如果深度為1，即樹樁結構（Stump），表明GBM将采用加法模型（Generalized Additive model），即不考慮變量之間的互動式作用（Interaction）；如果深度大于1，則考慮互動式作用。因為互動式作用在非線性模組化中比較重要，如異或（XOR）問題，沒有考慮互動式作用将失敗得很慘，是以這個參數設定反映了對非線性模組化的先驗。第二個參數是Shrinkage的大小。假設深度選取是合理的，在噪聲比較小的時候，沒有Shrinkage會比較好；噪聲比較大的時候，有Shrinkage會好一些。實踐中，使用GBM對高維資料分析，試錯法（Trial
and error）很容易使用，因為就這兩個參數（通常depth=3～4；實際資料的噪聲往往比較大，推薦設定Shrinkage=0.01）。模型建構好之後，GBM會告訴你哪些變量是重要的，變量之間的互動式作用如何等等，這樣模型的結果也是比較容易了解。Random Forests也有相似的功能。好了，最後借Hastie教授的一幅圖來總結一下，無疑，GBM（MART）是他們的最愛，也是我的最愛。
結束語
問：世間是否此山最高，或者另有高處比天高？
答： 在世間自有山比此山更高，Open-mind要比天高。
[1]
http://ihome.ust.hk/~eeyang/lars_Lasso_boost.pdf
[2]
http://ihome.ust.hk/~eeyang/Learning_from_sparsity.pdf
分類:新聞标簽:bioinformatics,boosted
trees,boosting,lasso,svm,統計學習
評論 (33)Trackbacks (0)發表評論Trackback
-
cvchina
2011年7月8日10:06 |#1
回複 |引用
好文！大家幫忙轉一下。
-
biometrics
2011年7月8日11:12 |#2
回複 |引用
Nice job! Very knowledgeable.
-
suzhy
2011年7月8日11:32 |#3
回複 |引用
好文，對目前的模式識别方法作了趨勢判斷
-
匿名
2011年7月8日11:50 |#4
回複 |引用
寫的好！我在讀the element of statistical leanring的時候也前前後後弄了一年。
-
Alex
2011年7月8日11:53 |#5
回複 |引用
Efron是斯坦福大學統計系的老系主任，斯坦福大學統計系能成就全美絕對第一的地位，Efron應該功勞非常大。Efron當年推出了統計裡面裡程碑式的成就Bootstrap，是名滿天下的大牛啊，而且帶領出了斯坦福大學統計系N位大牛教授，桃李滿天下！如今仍然老當益壯，提出了Least angle regression，真是牛上加牛！
對于SVM方法，我個人覺得它最牛的東西是最大間隔超平面，也就是線性核，其次才是非線性核。當然非線性核的方法引發了其它一系列的新方法，什麼kernel pca, kernel lda, kernel ica, kernel matching pursuit之類的，絕對是成果豐碩。對于AdaBoost為什麼不容易Overfitting，早已經有一些人指出是因為它能夠達到近似的最大間隔，也就是說Boosting能得到近似SVM的結果，是以不容易Overfitting。我覺得算是一個能說服人的說法吧。Boosting相對于SVM有它自己的優勢，例如具有on-line的特性等。總之，我覺得machine
learning這個領域已經基本成熟，實際應用已經基本沒問題，目前工業界的重點應該是并行化實作方面，實作海量資料的大規模機器學習系統。cv就截然不同，離成熟還很遙遠，我覺得難點就是表達的問題，也可以說是特征提取的問題吧。
-
匿名
2011年7月8日13:47 |#6
回複 |引用
@Alex很感謝如此專業的評論，共鳴中。補充兩點：1.
Efron教授的代表作是Bootstrap，斯坦福統計系網站上有如下解釋，我覺得可以幫助大家了解：”Bootstrap” means that one available sample gives rise to many others by resampling (a concept reminiscent of pulling yourself up by your own bootstrap)。近年來，Efron教授更加關注Large-Scale Inference，這裡也有很多故事，比如Jame-Stein
Estimator(被Efron教授稱為”the single most striking result of post-World War II statistical theory”) 與FDR的聯系，以及FDR與Lasso的聯系。由于篇幅有限，沒有展開，希望以後有機會整理出來與大家分享。2. 有關Boosting，我當時省略了最近的進展，如Equilibrium Margin（A Refined Margin Analysis for Boosting Algorithms via Equilibrium
Margin， JMLR，2011），這個領域的研究還在進行，目前沒有定論。
-
永遠的幻想
2011年7月8日13:50 |#7
回複 |引用
哈哈，我讀EoSL的心得，可惜爛尾中
http://www.ccthere.com/article/3030613