機器學習刀光劍影 之 屠龍刀

機器學習是一個大武林，這里面江湖人士頗多，“發明”出來的算法兵器也是五花八門，浩瀚如海，足夠你數上三天兩夜了。然而，這些兵器行走江湖能用的不多，真正無敵的更是屈指可數，或許只有屠龍刀倚天劍了。正如江湖傳言： 武林至尊 ，寶刀屠龍， 號令天下 ，莫敢不從，倚天不出，誰與爭鋒? 機器學習中還真有這么一把屠龍刀、一把倚天劍。用上了這兩樣兵器，保你平平安安創四方，瀟瀟灑灑走江湖。今天，就先絮叨絮叨這把屠龍刀。

在下以為，集成學習就是這把屠龍刀。為什么集成學習能稱為“屠龍刀”呢？因為它立竿見影，好像“刀過竹解”；因為它從不過時，儼然“寶刀未老”。 它是一把刀，但不是一把普通的刀；它是一把鋒利的刀，一把可以屠龍的刀。集成學習在眾多的機器學習/數據挖掘競賽中往往探囊取物，屢試不爽，像屠龍刀一樣 當之無愧排行兵器譜第一。

什么是集成學習呢？通俗的講，就是多算法融合。它的思想相當簡單直接，以至于用一句俗語就可以完美概括：三個臭皮匠，頂個諸葛亮。實際操作中，集 成學習把大大小小的多種算法融合在一起，共同協作來解決一個問題。這些算法可以是不同的算法，也可以是相同的算法。對于前者，效果一般也不差，但出發點實 在過于簡單粗暴，簡直就是一介武夫，就不過多介紹了。這里著重談一下如何使用同一個算法進行集成學習（雖然只關注這個話題，但里面很多思想對前者也是適用 的）。

用好集成學習有兩個關鍵點：1）怎么訓練每個算法？2）怎么融合每個算法？圍繞這兩個關鍵點，有很多方法提出來，極具代表性就是大家熟知的 bagging和boosting方法，其中Bagging和boosting也是當今兩大殺器RF（Random Forests）和GBDT（Gradient Boosting Decision Tree）之所以成功的主要秘訣。注意，這里我用的是“方法”，而 不是“算法”，個人以為“方法”比“算法”更高一層，更抽象些，更具有普適性。

集成學習是典型的實踐驅動的研究方向，它一開始先在實踐中證明有效，而后才有學者從理論上進行各種分析，這是非常不同于大名鼎鼎的 SVM（Support Vector Machine）的。SVM是先有理論，然后基于理論指導實現了算法。這是機器學習研究中少有的理論指導的創新案列。直到如今，它還是部分學者用來看清工 業界發明的算法的主要證據之一。為了證明我的觀點，我們就回顧下集成學習中最主流的RF的發展歷程。1995年，AT&T bell實驗室的韓國女學者Ho Tin Kam最早提出了RF，那個時候還不叫Random Forests, 而叫RDF（Random Decision Forest），她主要是采用Random Subspace的思想使用DT（Decision Tree）來構建Forest。隨后的幾年里，又有一批人相繼提出了大大小小的一些類似或改進的工作，但都還不足以載入史冊。歷史的年輪不知不覺來到了 2001年，統計學家Breiman已開始在機器學習界站穩腳跟。他在RDF基礎上又引入了Bagging技術，并提出了沿用至今的Random Forests。雖然老人家在那篇后來被引用幾千次的文章里進行了“理論”分析，并給出了一個看似不錯的誤差上界，但其實那個公式只是個中看不中用的數學 符號，沒有太多的指導意義。而且，老人家在回顧Ho的工作時，相當輕描淡寫，不知道何故，謹慎懷疑他對她是否有誤會？2005年，Breiman離世，集 成學習理論突破的使命交給了后來人。

2005-2015這十年里，集成學習方面的論文陸續有放出，但遺憾的是，個人認為集成學習的理論進展還是非常緩慢。“理論指導實踐”，這是機器 學習研究者們渴望已久的燈塔，但它太遠太遠，以至于我們只能在茫茫迷霧中懷著這份渴望摸索前行。回顧集成學習理論的發展歷程，為數不多的有用結論之一可能 就是---從bias-variance分解角度分析集成學習方法，人們意識到：Bagging主要減小了variance，而Boosting主要減小 了bias，而這種差異直接推動結合Bagging和Boosting的MultiBoosting的誕生。值得一提的是，我國學者在集成學習領域并不落 后，以南大周志華教授為代表的學者的一系列工作走在了世界前列，如選擇集成技術、集成聚類技術等等。周志華老師還最早將Ensemble Learning翻譯為“集成學習”，是國內這一領域的先行者。

近年來，除了上面的這些方法外，還有一些新方法涌現出來，這里就特別討論下個人認為比較有創意而且很實用的方法，我稱之為“嫁接法”。據百度百科 的說法--所謂嫁接，是指植物的人工營養繁殖方法之一。即把一種植物的枝或芽，嫁接到另一種植物的莖或根上，使接在一起的兩個部分長成一個完整的植株。把 這個概念遷移到集成學習領域，就是把一個算法嫁接到另外一個算法上，從而形成一個新的完整的算法。為什么要這么做呢？因為嫁接后有好處啊。回想一下當下我 們吃的各種水果，不少都是嫁接后的產物。不嚴格說來，袁隆平的雜交水稻也是一種高級的嫁接產物。嫁接后的水稻抗病害，易種植，產量還高。同樣，把兩種算法 嫁接在一起，也能達到類似的好效果。

算法嫁接之后為什么會好呢？回答這個問題得從一個基礎問題講起。以分類算法為例，所有算法大致分為線性和非線性兩類，線性算法如LR，NB，ME 之類；非線性算法如DT，RF，NN之流。一般來說，線性算法訓練和預測的效率較高，但效果較差，而且非常依賴人的知識。如廣告CTR預估中常用的LR算 法，要想達到一定的效果，需要人工或半人工的進行龐大的特征工程--進行特征的變換組合等預處理工作。有過LR使用經驗的同學一定對這個過程刻骨銘心，沒 有一定年限的積累是做不好線性模型的。而非線性算法如DT，理論上是能自動地做這些繁瑣工作的（雖然效果不一定好）。如果能借助這些算法減少人的工作，豈 不大快人心？沒錯，LMT(Logistic Model Tree ) 應運而生，它把LR和DT嫁接在一起，實現了兩者的優勢互補。剛剛過去的一年，網上近乎瘋傳的非死book的那個GBDT+LR的文章，只不過是這個 思想的延續，初看下來實在沒啥可追捧的。不同意？先別急，這樣做的確還有一些其他好處，咱們得換另外一個角度來看GBDT+LR。對比GBDT和DT會發 現GBDT較DT有兩點好處：1）GBDT本身是集成學習的一種算法，效果可能較DT好；2）GBDT預測出來的絕對值本身就有比較意義，LR能很好利用 這個值。這是個非常大的優勢，尤其是用到廣告競價排序的場景上。最后需要說明的是，這只是從一個角度來理解嫁接的好處，還有其他方面就不一一展開了。

相信其他常用的集成方法和算法大家都比較熟悉，就不再贅述了。這里著重提一下集成學習成功的關鍵---要千方百計圍繞學習器的差異和強度做文章。 這兩者有非常密切而又難以描述的關系，其中有對立，也有協同，實際應用中我們要平衡好彼此。瞄準了這個方向，就能事半功倍，才能在正確的道路上越走越遠。 怎樣解決這個關鍵問題呢？答案就一個字：試。如果非要多說兩個字，那就是：試試。如果…你還要我多說嗎?呵呵。好吧，不開玩笑了。如果你非想問出個子丑寅 卯來，你可能要用好以下技術：完全隨機，結合先驗的偽隨機，選擇集成，融合進人為思維等等。最最重要的是，會根據不同問題要調一把好參，如特征相關性太強 怎么調隨機選取特征的比例，樣本噪聲太大怎么調隨機選取示例的比例，正負比例不平衡時怎么做平衡等等。另外，在實際應用中，還要平衡好性能和效果，做一些 工程上的優化，哪些該實時算，哪些可以離線算，哪些可以半實時都要規劃好，還要使用好單機資源，多機資源，甚至犧牲效果換性能。這些點都是要注意的，用過 才知道。

好了，準備收筆了。做個小結：集成學習方法是機器學習中最最實用的兵器，堪稱屠龍刀。但并不是每個人都能用好這把刀，我們都要繼續修煉內功，理解數據，用好數據。

末了，希望大家牢記兩句話：

1）機器學習的成功依賴數據，系統和算法，缺一不可。

2）人能做的絕不留給機器。

再末了，預告下篇是講能帶你裝逼帶你飛的倚天劍，敬請期待。

主要參考文獻：

1. Ho, Tin Kam (1995).  Random Decision Forest . Proceedings of the 3rd International Conference on Document Analysis and Recognition, Montreal, QC, 14–16 August 1995. pp. 278–282.
2. Ho, Tin Kam (1998).  "The Random Subspace Method for Constructing Decision Forests" . IEEE Transactions on Pattern Analysis and Machine Intelligence 20 (8): 832–844.  doi : 10.1109/34.709601 .
3. Landwehr, N.; Hall, M.; Frank, E. (2005).  "Logistic Model Trees" . Machine Learning 59: 161.
4. http://deeplearning.stanford.edu/wiki/index.php/UFLDL_Tutorial
5.   Breiman, Leo  (2001). "Random Forests".  Machine Learning  45 (1): 5–32.  doi : 10.1023/A:1010933404324 .
6. Dietterich, Thomas (2000). "An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization".  Machine Learning : 139–157.
7. Breiman, Leo  (1996). "Bagging predictors".  Machine Learning  24 (2): 123–140.  doi : 10.1007/BF00058655 .  CiteSeerX :  10.1.1.121.7654 .
8. Geoffrey I. Webb (2000). MultiBoosting: A Technique for Combining Boosting and Wagging. Machine Learning. Vol.40(No.2).