統(tǒng)計學習那些事
2. 關于Lasso與Boosting
由于篇幅有限，我就以Lasso和Boosting為主線講講自己的體會。故事還得從90年代說起。我覺得90年代是這個領域發(fā)展的一個黃金年代，因為兩種絕世武功都在這個時候橫空出世，他們是SVM和Boosted Trees。
先說SVM。大家對SVM的基本原理普遍表述為，SVM通過非線性變換把原空間映射到高維空間，然后在這個高維空間構造線性分類器，因為在高維空間數(shù)據(jù)點更容易分開。甚至有部分學者認為SVM可以克服維數(shù)災難(curse of dimensionality)。如果這樣理解SVM的基本原理，我覺得還沒有看到問題的本質。因為這個看法不能解釋下面的事實：SVM在高維空間里構建分類器后，為什么這個分類器不會對原空間的數(shù)據(jù)集Overfitting呢?要理解SVM的成功，我覺得可以考慮以下幾個方面：第一，SVM求解最優(yōu)分類器的時候，使用了L2-norm regularization，這個是控制Overfitting的關鍵。第二，SVM不需要顯式地構建非線性映射，而是通過Kernel trick完成，這樣大大提高運算效率。第三，SVM的優(yōu)化問題屬于一個二次規(guī)劃(Quadratic programming)，優(yōu)化專家們?yōu)镾VM這個特殊的優(yōu)化問題設計了很多巧妙的解法，比如SMO(Sequential minimal optimization)解法。第四，Vapnika的統(tǒng)計學習理論為SVM提供了很好的理論背景(這點不能用來解釋為什么SVM這么popular，因為由理論導出的bound太loose)。于是SVM成功了，火得一塌糊涂!
再說Boosted Trees。它基本的想法是通過對弱分類器的組合來構造一個強分類器。所謂“弱”就是比隨機猜要好一點點;“強”就是強啦。這個想法可以追溯到由Leslie Valiant教授(2010年圖靈獎得主)在80年代提出的probably approximately correct learning (PAC learning) 理論。不過很長一段時間都沒有一個切實可行的辦法來實現(xiàn)這個理想。細節(jié)決定成敗，再好的理論也需要有效的算法來執(zhí)行。終于功夫不負有心人， Schapire在1996年提出一個有效的算法真正實現(xiàn)了這個夙愿，它的名字叫AdaBoost。AdaBoost把多個不同的決策樹用一種非隨機的方式組合起來，表現(xiàn)出驚人的性能!第一，把決策樹的準確率大大提高，可以與SVM媲美。第二，速度快，且基本不用調(diào)參數(shù)。第三，幾乎不Overfitting。我估計當時Breiman和Friedman肯定高興壞了，因為眼看著他們提出的CART正在被SVM比下去的時候，AdaBoost讓決策樹起死回生!Breiman情不自禁地在他的論文里贊揚AdaBoost是最好的現(xiàn)貨方法(off-the-shelf，即“拿下了就可以用”的意思)。其實在90年代末的時候，大家對AdaBoost為什么有如此神奇的性能迷惑不解。1999年，F(xiàn)riedman的一篇技術報告“Additive logistic regression: a statistical view of boosting”解釋了大部分的疑惑(沒有解釋AdaBoost為什么不容易Overfitting，這個問題好像至今還沒有定論)，即搞清楚了AdaBoost在優(yōu)化什么指標以及如何優(yōu)化的?；诖?，F(xiàn)riedman提出了他的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)。