集成学习

集成学习是指使用多种兼容的学习算法/模型来执行单个任务的技术,目的是为了得到更佳的预测表现。集成学习的主要方法可归类为三大类: 堆叠(Stacking)、提升(Boosting) 和 装袋(Bagging/bootstrapaggregating)。其中最流行的方法包括随机森林、梯度提升、AdaBoost、梯度提升决策树(GBDT)和XGBoost。

来源:机器之心
简介

集成学习是指使用多种兼容的学习算法/模型来执行单个任务的技术,目的是为了得到更佳的预测表现。集成学习的主要方法可归类为三大类: 堆叠(Stacking)、提升(Boosting) 和 装袋(Bootstrap aggregating)。

  1. Bootstrap aggregating 简称为 Bagging。我们先来介绍下bootstrap,boostrap是一种简单的统计技巧,如果对一个model的parameter我们可以有一个unbiased estimation,我们还想得到这些parameter的variance。我们就可以从data distribution中sample 出一个empirical data distribution,从而得到这个data distribution的variance,简而言之就是sample data with replacement。(proof详见 http://www.wikiwand.com/en/Glivenko–Cantelli_theorem)Bagging就是我们用这些sample data来训练多个model,代替了用原本的data set来训练一个单一的model,最终做prediction的时候,我们averaging多个model的prediction来得到最终的prediction。
    1. Bagging的好处在于便于reduce overfit
    2. 当原始的data set数据量巨大的时候,sample 一个小的data set可以提升效率
    3. 虽然bagging 减少了variance,但bagging不能reduce bias
  2. 堆叠(Stacking)是一种用于最小化一个或多个泛化器的泛化误差率的方法。它通过推导泛化器相对于所提供的学习集的偏差来发挥其作用。这个推导的过程包括:在第二层中将第一层的原始泛化器对部分学习集的猜测进行泛化,以及尝试对学习集的剩余部分进行猜测,并且输出正确的结果。当与多个泛化器一起使用时,堆叠泛化可以被看作是一个交叉验证的复杂版本,利用比交叉验证更为复杂的策略来组合各个泛化器。当与单个泛化器一起使用时,堆叠泛化是一种用于估计(然后纠正)泛化器的错误的方法,该泛化器已经在特定学习集上进行了训练并被询问了特定问题。
  3. Boosting 是一种能够将弱学习器转化为强学习器,从而提升各种学习算法的方法。理论上,boosting 可以显著减小弱学习器的偏差,这些弱学习器的效果只是稍微优于随机猜测,比如小决策树——数据加权模型。然后Boosting在运行时将更多的权重赋值给早期训练中错误最多的数据集,通过结合加权多数投票(分类)或加权求和(回归)以产生最终预测。Boosting的每个模型都是单独运行,每个模型决定下一个模型要关注的特征,最后在不偏向任何模型的前提下聚合输出结果。

在这些集成技术中最流行的方法包括随机森林、梯度提升、AdaBoost、梯度提升决策树(GBDT)和 XGBoost。Random Forest是一个结合了decision tree + bagging + out of bag trick的technique。我们可以从原始data set bootstrap N个 size 和原始data set相同的data set,然后用out of bag trick来训练N个 classifiers (decision tree) 也就是用没被选到data set的data来训练当前的classifer,最后我们averaging out N 个classifers 的prediction 来获得最终的prediction。Random forest的好处在于decision tree 很容易overfit,结合了bagging可以减少overfit。

[描述来源:Russell, S. J., & Norvig, P. (2010). Artificial Intelligence (A Modern Approach). 及其他词条]

发展历史

1979年,Dasarathy 提出集成系统(ensemble system)的思想,并使用线性分类器和最近邻居(NN)分类器组成的复合系统作为其组成部分的例子来说明这些概念。同年,Bootstrap由 Bradley Efron发表在他的论文"Bootstrap methods: another look at the jackknife"中。因其通用性和简便性,bootstrapping在各种机器学习算法中具有很强的实用性。

1988年Kearns和1989年Valiant分别提出的弱学习的概念,引发了关于“能否用一组弱学习器创造一个强学习器”这一问题的讨论。1990年Schapire对这一问题给出了肯定的回答,并开发出boosting。并在几年之后和Freund提出了AdaBoost,该算法被广泛使用,他们还凭借Adaboost获得了计算机领域富有盛名的哥德尔奖。

1990年,Hansen提出了几种提高神经网络在分类任务上的性能和训练的方法,并使用交叉验证优化网络参数和体系结构。他证明了集成系统的方差缩减(variance reduction)性质,而这可以提升神经网络的表现。

堆叠泛化由Wolpert在1992年首次提出,堆叠通常能获得比任何单个的训练模型更好的性能。

1995年,Tin  Kam Ho 提出了集成学习中最广为人知的算法——随机决策森林,并在几年后由Leo Breiman将随机森林方法进行系统的阐述,随机森林方法正式成为数据挖掘分类算法的重要组成部分。

1996年,Breiman 开发出 Bagging 预测器,并对其原理和训练进行了详细描述。他提出回归和分类的一个关键问题是预测方法的不稳定性——如果扰乱训练集,那么可能会导致构建的预测变量发生重大变化,而Bagging 可以提高准确性。

2010年,Kalal等人提出P-N学习。他们证明通过处理结构化的未标记数据可以显着提高二元分类器的性能,并提出了一种新的范例,用于从标记和未标记的例子中训练一个二元分类器,称之为P-N学习。他们还在学习中用Bootstrapping提升分类器的性能。其他的近期研究有使用堆叠方式构建深度网络结构,XGBoost的提出等。

我们将集成学习归在了应用阶段,因为人工智能领域很多特定应用(比如推荐系统)都已经将集成学习整合到了它们已有的生产算法中;但它仍然还处在早期多数(early majority)阶段,还没有社会影响。从 IEEE(电气和电子工程师协会)和谷歌趋势的搜索结果来看,不仅公众对集成学习的兴趣相对较低,学术界也对此并不热情。

主要事件

年份事件相关论文/Reference
1979Dasarathy 提出集成系统(ensemble system)的思想Dasarathy, B. V. and Sheela, B. V. (1979). A composite classifier system design: Concepts and methodology. Proceedings of the IEEE. 67(5): 708-713.
1979Efron在论文中提出了bootstrapEfron, B. (1979). Bootstrap Methods: Another Look at the Jackknife. The Annals of Statistics, 7(1), 1-26.
1990Hansen 证明了集成系统的方差缩减(variance reduction)性质,而这可以提升神经网络的表现Hansen, L. K. and Salamon, P. (1990). Neural network ensembles. IEEE Transactions on Pattern Analysis and Machine Intelligence. 12(10): 993-1001.
1990Schapire 开发出 BoostingSchapire, R. E. (1990). The strength of weak learnability. Machine learning, 5(2), 197-227.
1992David Wolpert 研究出了堆叠泛化(Stacking /Stacked  Generalization)Wolpert, D. H. (1992). Stacked generalization. Neural networks, 5(2), 241-259.
1995Tin  Kam Ho 提出了随机决策森林Ho, Tin Kam (1995). Random Decision Forests (PDF). Proceedings of the 3rd International Conference on Document Analysis and Recognition, Montreal, QC, 14–16 August 1995. pp. 278–282.
1995Freund和Schapire提出了AdaBoost,该算法在之后成为最广泛使用的boosting算法Freund, Y., & Schapire, R. E. (1995, March). A desicion-theoretic generalization of on-line learning and an application to boosting. In European conference on computational learning theory (pp. 23-37). Springer, Berlin, Heidelberg.
1996Breiman 开发出 Bagging 预测器Breiman, L. (1996). Bagging predictors. Machine Learning. 24(2): 123–140.
1996Freund和Schapire对Adaboost进行了实验论证Freund, Y., & Schapire, R. E. (1996, July). Experiments with a new boosting algorithm. In Icml (Vol. 96, pp. 148-156).
2010在Pn学习中用Bootstrapping提升分类器的性能Kalal, Z., Matas, J., & Mikolajczyk, K. (2010, June). Pn learning: Bootstrapping binary classifiers by structural constraints. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on (pp. 49-56). IEEE.
2012用堆叠方式构建深度网络结构Deng, L., Yu, D., & Platt, J. (2012, March). Scalable stacking and learning for building deep architectures. In Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on (pp. 2133-2136). IEEE.
2016陈天奇(Tianqi Chen)开发出 XGBoostChen, T., & Guestrin, C. (2016, August). Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining (pp. 785-794). ACM.

 发展分析

瓶颈

集成学习最大的问题是需要训练多个模型,很耗时,而且成本高。另外分别来说,boosting对于不同的样本在抽样时赋予了不同的权重,使得后面的模型更加关注于被错误分类的样本, 因此此方法可能对被错误分类的噪声数据(outlier)敏感,加大这些数据的权重会干扰后面学习器的学习效果;Bootstrapping不提供通用的有限样本保证,它的运用基于很多统计学假设,因此假设的成立与否会影响采样的准确性;stacking需要解决的难点则是如何确定最佳的hyperparameters的问题。

未来发展方向

bagging 和 boosting都使用了bootstrapping,而使用bootstrapping对计算能力的要求很高,因此需要对现在的计算能力进行提升,从而扩大集成学习的应用领域。另外,随着AutoML的开发,可以使用AutoML来确定stacking中的超参数取值。

Contributor: Yuanyuan Li

相关人物
托马斯 ·G· 迪特里克
托马斯 ·G· 迪特里克
Thomas G. Dietterich 是俄勒冈州立大学计算机科学荣誉教授。他是机器学习领域的创始人之一。他曾担任机器学习的执行编辑,并帮助共同创建了机器学习研究期刊。为了回应媒体对人工智能危害的关注,Dietterich 已被引用到广泛的媒体渠道,包括国家公共广播电台,商业内幕,微软研究院,CNET 和华尔街日报。
大卫·沃尔伯特
大卫·沃尔伯特
美国数学家、物理学家和计算机科学家。他是圣达菲研究所的教授。他与Macerday一起提出了“没有免费的午餐”(NFL)定理,发展了最优化理论。
约阿夫·弗罗因德
约阿夫·弗罗因德
加州大学圣地亚哥分校的计算机科学教授,主要研究机器学习、计算学习理论、概率论、信息论、统计和模式识别,以及机器学习算法在大数据、计算机视觉、人机交互和在线教育中的应用。他最出名的是工作是开发了AdaBoost算法,并因此荣获 2003 年哥德尔奖。著作:Boosting: Foundations and Algorithm。
Tin Kam Ho
Tin Kam Ho
纽约州立大学布法罗分校的计算机科学博士,IEEE fellow、IAPR fellow、IBM Watson的计算机科学家,贡献领域包括机器学习、数据挖掘和分类等。因在1995年引入随机决策森林及在集成学习和数据复杂性分析方面的开创性工作而闻名于世。
邓力
邓力
邓力,本科毕业于中国科学技术大学,随后在威斯康星大学麦迪逊分校获的硕士和博士学位。曾任微软人工智能首席科学家。邓力2009 年就同 Geoffrey Hinton 教授合作,首次提出并将深度神经网络应用到大规模语言识别中,显著提高了机器对语音的识别率,极大推动了人机交互领域的发展与进步。2017年5月,他加入了市值300亿美元的对冲基金Citadel并担任首席人工智能官。
Lars Kai Hansen
Lars Kai Hansen
Belur V. Dasarathy
Belur V. Dasarathy
俞栋
俞栋
俞栋,语音识别与深度学习领域的专家,现任腾讯AI Lab(人工智能实验室)副主任。俞栋曾在语音识别领域出版了两本专著并发表过大量论文,也是60项专利的发明人及深度学习开源软件CNTK的发起人和主要作者之一。
莱奥·布雷曼
莱奥·布雷曼
1928-2005,加州大学伯克利分校的杰出统计学家、美国国家科学院的成员。他的工作有助于弥合统计学和计算机科学之间的差距,特别是在机器学习领域。他最重要的贡献是在分类和回归树方面的工作。
简介
相关人物