转载

机器学习刀光剑影之屠龙刀

机器学习是一个大武林，这里面江湖人士颇多，“发明”出来的算法兵器也是五花八门，浩瀚如海，足够你数上三天两夜了。然而，这些兵器行走江湖能用的不多，真正无敌的更是屈指可数，或许只有屠龙刀倚天剑了。正如江湖传言：武林至尊，宝刀屠龙，号令天下，莫敢不从，倚天不出，谁与争锋? 机器学习中还真有这么一把屠龙刀、一把倚天剑。用上了这两样兵器，保你平平安安创四方，潇潇洒洒走江湖。今天，就先絮叨絮叨这把屠龙刀。

在下以为，集成学习就是这把屠龙刀。为什么集成学习能称为“屠龙刀”呢？因为它立竿见影，好像“刀过竹解”；因为它从不过时，俨然“宝刀未老”。它是一把刀，但不是一把普通的刀；它是一把锋利的刀，一把可以屠龙的刀。集成学习在众多的机器学习/数据挖掘竞赛中往往探囊取物，屡试不爽，像屠龙刀一样当之无愧排行兵器谱第一。

什么是集成学习呢？通俗的讲，就是多算法融合。它的思想相当简单直接，以至于用一句俗语就可以完美概括：三个臭皮匠，顶个诸葛亮。实际操作中，集成学习把大大小小的多种算法融合在一起，共同协作来解决一个问题。这些算法可以是不同的算法，也可以是相同的算法。对于前者，效果一般也不差，但出发点实在过于简单粗暴，简直就是一介武夫，就不过多介绍了。这里着重谈一下如何使用同一个算法进行集成学习（虽然只关注这个话题，但里面很多思想对前者也是适用的）。

机器学习刀光剑影之屠龙刀

用好集成学习有两个关键点：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嫁接在一起，实现了两者的优势互补。刚刚过去的一年，网上近乎疯传的Facebook的那个GBDT+LR的文章，只不过是这个思想的延续，初看下来实在没啥可追捧的。不同意？先别急，这样做的确还有一些其他好处，咱们得换另外一个角度来看GBDT+LR。对比GBDT和DT会发现GBDT较DT有两点好处：1）GBDT本身是集成学习的一种算法，效果可能较DT好；2）GBDT预测出来的绝对值本身就有比较意义，LR能很好利用这个值。这是个非常大的优势，尤其是用到广告竞价排序的场景上。最后需要说明的是，这只是从一个角度来理解嫁接的好处，还有其他方面就不一一展开了。

相信其他常用的集成方法和算法大家都比较熟悉，就不再赘述了。这里着重提一下集成学习成功的关键---要千方百计围绕学习器的差异和强度做文章。这两者有非常密切而又难以描述的关系，其中有对立，也有协同，实际应用中我们要平衡好彼此。瞄准了这个方向，就能事半功倍，才能在正确的道路上越走越远。怎样解决这个关键问题呢？答案就一个字：试。如果非要多说两个字，那就是：试试。如果…你还要我多说吗?呵呵。好吧，不开玩笑了。如果你非想问出个子丑寅卯来，你可能要用好以下技术：完全随机，结合先验的伪随机，选择集成，融合进人为思维等等。最最重要的是，会根据不同问题要调一把好参，如特征相关性太强怎么调随机选取特征的比例，样本噪声太大怎么调随机选取示例的比例，正负比例不平衡时怎么做平衡等等。另外，在实际应用中，还要平衡好性能和效果，做一些工程上的优化，哪些该实时算，哪些可以离线算，哪些可以半实时都要规划好，还要使用好单机资源，多机资源，甚至牺牲效果换性能。这些点都是要注意的，用过才知道。

好了，准备收笔了。做个小结：集成学习方法是机器学习中最最实用的兵器，堪称屠龙刀。但并不是每个人都能用好这把刀，我们都要继续修炼内功，理解数据，用好数据。

末了，希望大家牢记两句话：

1）机器学习的成功依赖数据，系统和算法，缺一不可。

2）人能做的绝不留给机器。

再末了，预告下篇是讲能带你装逼带你飞的倚天剑，敬请期待。

主要参考文献：

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.
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 .
Landwehr, N.; Hall, M.; Frank, E. (2005). "Logistic Model Trees" . Machine Learning 59: 161.
http://deeplearning.stanford.edu/wiki/index.php/UFLDL_Tutorial
Breiman, Leo (2001). "Random Forests". Machine Learning 45 (1): 5–32. doi : 10.1023/A:1010933404324 .
Dietterich, Thomas (2000). "An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization". Machine Learning : 139–157.
Breiman, Leo (1996). "Bagging predictors". Machine Learning 24 (2): 123–140. doi : 10.1007/BF00058655 . CiteSeerX : 10.1.1.121.7654 .
Geoffrey I. Webb (2000). MultiBoosting: A Technique for Combining Boosting and Wagging. Machine Learning. Vol.40(No.2).

正文到此结束