2011年11月24日 星期四

[轉]統計學習那些事


SVM的基本原理普遍表述為,SVM通過非線性變換把原空間映射到高維空間,然後在這個高維空間構造線性分類器,因為在高維空間資料點更容易分開。 甚至有部分學者認為SVM可以克服維數災難(curse of dimensionality)。如果這樣理解SVM的基本原理,我覺得還沒有看到問題的本質。因為這個看法不能解釋下面的事實:SVM在高維空間裡構建 分類器後,為什麼這個分類器不會對原空間的資料集Overfitting呢?要理解SVM的成功,我覺得可以考慮以下幾個方面:第一,SVM求解最優分類 器的時候,使用了L2-norm regularization,這個是控制Overfitting的關鍵。第二,SVM不需要顯式地構建非線性映射,而是通過Kernel trick完成,這樣大大提高運算效率。第三,SVM的優化問題屬於一個二次規劃(Quadratic programming),優化專家們為SVM這個特殊的優化問題設計了很多巧妙的解法,比如SMOSequential minimal optimization)解法。第四,Vapnika的統計學習理論為SVM提供了很好的理論背景(這點不能用來解釋為什麼SVM這麼popular, 因為由理論匯出的boundloose)。於是SVM成功了,火得一塌糊塗!
再說Boosted Trees。它基本的想法是通過對弱分類器的組合來構造一個強分類器。所謂就是比隨機猜要好一點點;就是強啦。這個想法可以追溯到由Leslie Valiant教 授(2010年圖靈獎得主)在80年代提出的probably approximately correct learning (PAC learning) 理論。不過很長一段時間都沒有一個切實可行的辦法來實現這個理想。細節決定成敗,再好的理論也需要有效的演算法來執行。終於功夫不負有 心人, Schapire1996年提出一個有效的演算法真正實現了這個夙願,它的名字叫AdaBoostAdaBoost把多個不同的決策樹用一種非隨機的方 式組合起來,表現出驚人的性能!第一,把決策樹的準確率大大提高,可以與SVM媲美。第二,速度快,且基本不用調參數。第三,幾乎不 Overfitting。我估計當時BreimanFriedman肯定高興壞了,因為眼看著他們提出的CART正在被SVM比下去的時 候,AdaBoost讓決策樹起死回生!Breiman情不自禁地在他的論文裡讚揚AdaBoost是最好的現貨方法(off-the-shelf,即拿下了就可以用的意思)。其實在90年代末的時候,大家對AdaBoost為什麼有如此神奇的性能迷惑不解。1999年,Friedman的一篇技術 報告“Additive logistic regression: a statistical view of boosting”解釋了大部分的疑惑(沒有解釋AdaBoost為什麼不容易Overfitting,這個問題好像至今還沒有定論),即搞清楚了 AdaBoost在優化什麼指標以及如何優化的。基於此,Friedman提出了他的GBMGradient Boosting Machine,也叫MART或者TreeNet)。幾乎在同時,Breiman另闢蹊徑,結合他的Bagging (Bootstrap aggregating) 提出了Random Forest (今天微軟的Kinect裡面就採用了Random Forest,相關論文Real-time Human Pose Recognition in Parts from Single Depth ImagesCVPR2011best paper)。
有一個關於Gradient Boosting細節不得不提。Friedman在做實驗的時候發現,把一棵新生成的決策樹,記為f_m,加到當前模型之前,在這棵決策樹前乘以一個小的 數,即v×f_m(比如v=0.01),再加入到當前模型中,往往大大提高模型的準確度。他把這個叫做“Shrinkage”。接下 來,HastieTibshiraniFriedman進一步發現(我發現大師們都是親自動手寫程式做實驗的),如果把具有Shrinkage Gradient Boosting應用到線性回歸中時,得到的Solution PathLassoSolution Path驚人地相似(如圖所示)!他們把這一結果寫在了ESL的第一版裡,並推測這二者存在著某種緊密的聯繫,但精確的數學關係他們當時也不清楚。 Tibshirani說他們還請教了斯坦福的優化大師(我估計是Stephen Boyd),但還是沒有找到答案。

Lasso & Boosting

後來Tibshirani找到自己的恩師EfronTibshirani“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 the Lasso.”我就不逐字逐句翻譯了,大意是:Efron獨自擺平了這個問題,與此同時發明了“Least angle regression (LAR)”Efron結論是LassoBoosting的確有很緊密的數學聯繫,它們都可以通過修改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:],有中文翻譯為套索,個人覺得這個翻譯不好,太遠離它本來的含義,不如就用 LassoTibshrani自己說他的Lasso是受到BreimanNon-Negative GarroteNNG)的啟發。 LassoNNG的兩步合併為一步,即L1-norm regularizationLasso的巨大優勢在於它所構造的模型是Sparse的,因為它會自動地選擇很少一部分變數構造模型。現在,Lasso 已經家喻戶曉了,但是Lasso出生後的頭兩年卻很少有人問津。後來Tibshirani自己回憶時說,可能是由下面幾個原因造成的:1. 速度問題:當時電腦求解Lasso的速度太慢;2. 理解問題:大家對Lasso模型的性質理解不夠(直到EfronLAR出來後大家才搞明白);3. 需求問題:當時還沒有遇到太多高維資料分析的問題,對Sparsity的需求似乎不足。Lasso的遭遇似乎在闡釋我們已經熟知的一些道理: 1.千里馬常有,而伯樂不常有(沒有EfronLARLasso可能很難有這麼大的影響力)。2.時勢造英雄(高維資料分析的問題越來越多,比如 Bioinformatics領域)。3.金子總是會閃光的。
LARLasso L1-norm regularization)和Boosting真正的聯繫起來,如同打通了任督二脈(數學細節可以參考本人的一個小結[1], 當然最好還是親自拜讀Efron的原著)。LAR結束了一個晦澀的時代:在LAR之前,有關Sparsity的模型幾乎都是一個黑箱,它們的數學性質(更 不要談古典的幾何性質了)幾乎都是缺失。LAR開啟了一個光明的時代:有關Sparsity的好文章如雨後春筍般地湧現,比如CandesTao Dantzig Selector。伯克利大學的Bin Yu教授稱“Lasso, Boosting and Dantzig are three cousins”。近年來興起的Compressed sensingCandes & Tao, Donoho)也與LAR一脈相承,只是更加強調L1-norm regularization其他方面的數學性質,比如Exact Recovery。我覺得這是一個問題的多個方面,Lasso關注的是構建模型的準確性,Compressed sensing關注的是變數選擇的準確性。由此引起的關於Sparsity的研究,猶如黃河氾濫,一發不可收拾。比如Low-rank 逼近是把L1-norm從向量到矩陣的自然推廣(現在流行的使用者推薦系統用到的Collaborative filtering的數學原理源於此)。有興趣的童鞋可以參考我個人的小結[2]
還必須提到的是演算法問題。我個人覺得,一個好的模型,如果沒有一個快速準確的演算法作為支撐的話,它最後可能什麼也不是。看看Lasso頭幾年的冷遇 就知道了。LAR的成功除了它漂亮的幾何性質之外,還有它的快速演算法。LAR的演算法複雜度相當於最小二乘法的複雜度,這幾乎已經把Lasso問題的求解推 向極致。這一記錄在2007年被FriedmanCoordinate DescentCD)刷新,至今沒人打破。Hastie教授趣稱這個為“FFTFriedman + Fortran + Tricks。因為CDGeneralized Lasso問題並不能一網打盡,許多凸優化解法應運而生,如Gradient Projection Proximal methodsADMM (Alternating Direction Method of Multipliers) (Split) Bregman methodsNesterov’s method (一階梯度法中最優的收斂速度,Candes 的很多套裝軟體都根據這個方法設計) 等等。哪個方法更好呢?這個就像問誰的武功天下第一一樣。我只能回答王重陽以後再也沒有天下第一了,東邪西毒南帝北丐,他們各有各的所長,有的功夫 是這個人擅長一些,而另外幾門功夫又是另一個人更擅長一些。有關L1的演算法可能還會大量湧現,正如優化大師Stephen Boyd所說(2010928日):“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 JangANFIS等等;3.結果的可解釋性;4.利用各種不同形式的資訊。
下面我談談自己的看法,第一,通用逼近性能當然是一個好的性質,它表明模糊系統是很flexible的,但flexible的結構太多了,比如神經 網路。問題往往不在flexible,而在太flexible導致overfitting。就如同SVM一樣,沒有L2-norm regularization,實踐中的性能就會變得很差。第二,快速演算法,這是好的方法必備的,SVMBoostingRandom Forest的演算法都很快,而且可以直接用到高維,這一點上,我沒有看到模糊系統的優勢。第三,可解釋性:模糊系統對低維資料(比如2-4維)的確具有好 的解釋性(因為IF-THEN規則的前提和結論都很簡潔),但這個時候其它工具也可以做得到,比如Gradient BoostingRandom Forests(很多例子可以在ESL這本書裡看到)。第四,充分的利用各種資訊。立新老師指的是IF-THEN規則可以比較自由靈活的加入先驗知識,並 在他的書裡面詳細給出實例。遺憾的是,這些例子都在處理低維空間的問題。如何用IF-THEN規則解構高維空間呢?我個人看不到它們特殊的優勢。然而,在 統計學習裡,利用不同的先驗知識處理高維空間的例子比比皆是,比如Sparsitygroup-structuresmoothness等等。現在舉 一個Gradient Boosting  machineGBM,也叫MART)的例子來說明我的觀點。根據LassoBoosting的關係,可以知道GBM已經用到了Sparsity的性 質(L1-norm regularization)。GBM有兩個參數可以反映我們的先驗知識。第一個參數是深度(depth),控制每棵決策樹的深度 。如果深度為1,即樹樁結構(Stump),表明GBM將採用加法模型(Generalized Additive model),即不考慮變數之間的互動式作用(Interaction);如果深度大於1,則考慮互動式作用。因為互動式作用在非線性建模中比較重要,如 異或(XOR)問題,沒有考慮互動式作用將失敗得很慘,所以這個參數設置反映了對非線性建模的先驗。第二個參數是Shrinkage的大小。假設深度選取 是合理的,在雜訊比較小的時候,沒有Shrinkage會比較好;雜訊比較大的時候,有Shrinkage會好一些。實踐中,使用GBM對高維資料分析, 試錯法(Trial and error)很容易使用,因為就這兩個參數(通常depth=34;實際資料的雜訊往往比較大,推薦設置Shrinkage=0.01)。模型構建好之 後,GBM會告訴你哪些變數是重要的,變數之間的互動式作用如何等等,這樣模型的結果也是比較容易理解。Random Forests也有相似的功能。好了,最後借Hastie教授的一幅圖來總結一下,無疑,GBMMART)是他們的最愛,也是我的最愛。

Characteristics of some statistical models


沒有留言: