提升算法

Boosting是一种主要用于减少偏差的机器学习集成元算法,也是监督学习的一个变化,是一种将弱学习器转换为强学习器的机器学习算法家族。 Boosting是基于Kearns和Valiant(1988,1989)提出的问题:一组弱学习器能创造一个强大的学习器吗?一个弱的学习器被定义为一个分类器,它与真实的分类只有轻微的相关性(它可以比随机猜测更好地标注示例)。相反,强大的学习器是一个与真实分类任意相关的分类器。

来源:Wikipedia
简介

Boosting是一种能够将弱学习器转化为强学习器,从而提升各种学习算法的方法。理论上,boosting可以显著减小弱学习器的偏差,这些弱学习器的效果只是稍微优于随机猜测,比如小决策树——数据加权模型。然后Boosting在运行时将更多的权重赋值给早期训练中错误最多的数据集,通过结合加权多数投票(分类)或加权求和(回归)以产生最终预测。Boosting的每个模型都是单独运行,每个模型决定下一个模型要关注的特征,最后在不偏向任何模型的前提下聚合输出结果。

其中,最广泛使用的 boosting 算法是 AdaBoost,如下图所示,它首先对第一个基础分类器使用全部相等的权重进行训练。在随后的 boosting 训练中,增加错误分类的数据点的系数权重,同时减少正确分类的数据点的系数权重,用这些新的权重值来继续运行模型和数据。

梯度boosting树(Gradient Tree Boosting)是boosting使用任意可微分损失函数的推广。它可以用于回归和分类问题。梯度Boosting以顺序的方式构建模型。在每一步,给定当前的模型,决策树通过最小化损失函数更新模型。回归和分类算法在使用的损失函数的类型上有所不同。

[描述来源:机器之心;URL:https://www.jiqizhixin.com/articles/2017-08-28-3]

[描述来源:机器之心;URL:https://www.jiqizhixin.com/articles/2017-11-25-2]

[描述来源:论文;URL:http://www.public.asu.edu/~jye02/CLASSES/Fall-2005/PAPERS/boosting-icml.pdf]

发展历史

描述

1988年Kearns和1989年Valiant分别提出的弱学习的概念,引发了关于“能否用一组弱学习器创造一个强学习器”这一问题的讨论。1990年Schapire对这一问题给出了肯定的回答。之后Freund和Schapire提出了AdaBoost,该算法被广泛使用,他们还凭借Adaboost获得了计算机领域富有盛名的哥德尔奖。除了Adaboost之外,还有其他一些boosting算法,如Linear Programming Boosting (LPBoost),梯度boosting树,BrownBoost, Xgboost,LogitBoost等。

主要事件

年份

事件

相关论文/Reference

1990

Schapire对弱学习转化成强学习的方法进行了描述,即boosting的原始表达。

Schapire, R. E. (1990). The strength of weak learnability. Machine learning, 5(2), 197-227.

1995

Freund和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.

1996

Freund和Schapire对Adaboost进行了实验论证

Freund, Y., & Schapire, R. E. (1996, July). Experiments with a new boosting algorithm. In Icml (Vol. 96, pp. 148-156).

2001

Freund提出了BrownBoost算法

Freund, Y. (2001). An adaptive version of the boost by majority algorithm. Machine learning, 43(3), 293-318.

2002

提出梯度boosting树,是boosting使用任意可微分损失函数的推广

Friedman, J. H. (2002). Stochastic gradient boosting. Computational Statistics & Data Analysis, 38(4), 367-378.

2016

提出一种可缩放的端对端的boosting树系统,称为Xgboost

Chen, 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.

发展分析

瓶颈

由于boost方法对于不同的样本在抽样时赋予了不同的权重,使得后面的模型更加关注于被错误分类的样本,因此此方法可能对被错误分类的噪声数据(outlier)敏感,加大这些数据的权重会干扰后面学习器的学习效果。

未来发展方向

Boosting在模式识别、计算机视觉领域仍将继续发挥重要作用。

Contributor: Yueqin Li

相关人物
罗伯特·夏皮尔
罗伯特·夏皮尔
美国计算机科学家,美国国家工程院、美国国家科学院院士,曾任普林斯顿大学计算机科学系David M. Siegel '83教授,现就职于微软研究院纽约办公室。他主要研究理论和应用机器学习。 1995 年他与Yoav Freund发明了AdaBoost算法,并因此获得 2003 年哥德尔奖。
周志华
周志华
周志华分别于1996年6月、1998年6月和2000年12月于 南京大学计算机科学与技术系获学士、硕士和博士学位。主要从事人工智能、机器学习、数据挖掘 等领域的研究工作。主持多项科研课题,出版《机器学习》(2016)与《Ensemble Methods: Foundations and Algorithms》(2012),在一流国际期刊和顶级国际会议发表论文百余篇,被引用三万余次。
陈天奇
陈天奇
陈天奇,华盛顿大学计算机系博士生,此前毕业于上海交通大学ACM班,研究方向为大规模机器学习。陈天奇曾获得KDD CUP 2012 Track 1第一名,并开发了SVDFeature,XGBoost,cxxnet等著名机器学习工具,是最大开源分布式机器学习项目DMLC的发起人之一。
简介
相关人物