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

我爱计算机 4年前 发在 人工智能, 博客, 机器学习 0

作者：@龙星镖局

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

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

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

ensemble1

用好集成学习有两个关键点：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的工作时，相当轻描淡写，不知道何故，谨慎怀疑他对她是否有误会？【批注1】2005年，Breiman离世，集成学习理论突破的使命交给了后来人。

2005-2015这十年里，集成学习方面的论文陆续有放出，但遗憾的是，个人认为集成学习的理论进展还是非常缓慢。大多工作都是围绕一个特定的算法做分析，始终没有一个大一统的理论站稳脚跟。“理论指导实践”，这是机器学习研究者们渴望已久的灯塔，但它太远太远，以至于我们只能在茫茫迷雾中怀着这份渴望摸索前行。回顾集成学习理论的发展历程，为数不多的有用结论之一可能就是---从bias-variance分解角度分析集成学习方法【批注2】，人们意识到：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中的DT一般是RT，所以预测出来的绝对值本身就有比较意义，而LR能很好利用这个值。这是个非常大的优势，尤其是用到广告竞价排序的场景上。最后需要说明的是，这只是从一个角度来理解嫁接的好处，还有其他方面就不一一展开了。

接着，唠叨几句红红火火的集成半监督学习。我读书时候也是集成半监督技术开始兴盛那会，但坦白讲，虽然它在一些数据集或场景下取得了一定效果，个人一直偏执地不看好这个方向。个人拙见：具体到分类问题上，集成方法要想成功，要依赖的有标记的样本量要大，至少可能是要大于单个算法的。半监督学习技术虽然可取，但没有一定量的标记样本也是瞎折腾。两者都对样本要求如此苛刻，融合在一起岂不是更坏？另一方面，两派人的研究方法论不同，根本不看好融合在一起的集成半监督技术【批注3】。所以即便是co-training这样训练两个学习器的算法，实际预测时也只使用其中一个。然而，随后这方面一系列的工作有理有据，着实给人们上了生动的一课。值得一提的是，我国南大数据挖掘团队对这个领域的发展起到了推动作用，他们先是做了tri-training，co-forest等算法，验证了引入集成对半监督学习的好处。后来又在理论上证明了半监督学习引入集成会带来很大好处。而对集成学习者，他们揭示出引入半监督学习可以不牺牲个体学习器精度就能提升diversity，并设计出UDEED算法。这一系列工作得到了业界高度评价。

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

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

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

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

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

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

主要批注：

  1. 她是模式识别领域的，研究方法论和机器学习有很大差别。Ho主要的贡献是随机子空间，她偶然用了一下决策树，但是从属性子空间的角度去做的，是不是决策树并不重要，而且最关键的是没有用到bootstrap，而bootstrap是bagging和RF的最精华。从Breiman的角度看，Ho是纯属凑巧弄了个和RF看上去长得像的东西，而且这东西里面没有RF最宝贵的部分，当然不会看好。Ho的random subspace是模式识别里面很有效的技术。她自己也更看重这个。
  2. bias-variance分解不是集成学习特有的，1992年German发明后借用过来的。集成学习特有的是error-ambiguity分解。
  3. 集成学习者认为: 只要允许我使用多个学习器，就能把弱学习器提升到足够强，根本不需要什么无标记样本。半监督学习者认为: 只要能让我使用无标记样本，就能把学习器提升到足够强，哪需要什么多学习器。双方各执一词，真是老死不相往来的节奏。

主要后记：

  1. 非常感谢周志华、陈天奇等学者指正了本文中的明显错误，并进行了主要批注。
  2. 因写作仓促，调研不足，难免还有其他错误或不当之处，希望读者继续纠正。
  3. 文中所有言论仅是个人观点，与他人无关。
  4. 本文已授权发布在《我爱计算机》 www.52cs.org

主要参考文献：

  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).
  9. Xinran He, Junfeng Pan, Ou Jin, Tianbing Xu, Bo Liu, Tao Xu, Yanxin Shi, Antoine Atallah, Ralf Herbrich, Stuart Bowers and Joaquin Quinonero Candela,Practical Lessons from Predicting Clicks on Ads at Facebook, ADKDD'14.[PDF]
  10. Z.-H. Zhou. Ensemble Methods: Foundations and Algorithms, Boca Raton, FL: Chapman & Hall/CRC, 2012. (ISBN 978-1-439-830031)
Tags :

留下你的评论