自适应增强

AdaBoost是最优秀的Boosting算法之一,它能够将比随机猜测略好的弱分类器(weak learner)提升为分类精度高的强分类器(strong learner)。AdaBoost对每一个训练样本都分配一个权重,每次迭代之后都会对权重进行调整,被正确分类的样本权重会被降低,被错误分类的样本权重会被提高。也就是说,如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它被选中的概率就被降低;相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高,更有可能被选中进入下一个训练集中,让后面的弱分类器重点关注之前表现不好的样本上。通过这样的方式,AdaBoost方法能“聚焦于”那些较难分(更富信息)的样本上,从而将多个弱分类器组合为一个强分类器。

简介

AdaBoost是最优秀的Boosting算法之一,它能够将比随机猜测略好的弱分类器(weak learner)提升为分类精度高的强分类器(strong learner)。AdaBoost对每一个训练样本都分配一个权重,每次迭代之后都会对权重进行调整,被正确分类的样本权重会被降低,被错误分类的样本权重会被提高。也就是说,如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它被选中的概率就被降低;相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高,更有可能被选中进入下一个训练集中,让后面的弱分类器重点关注之前表现不好的样本上。通过这样的方式,AdaBoost方法能“聚焦于”那些较难分(更富信息)的样本上,从而将多个弱分类器组合为一个强分类器。

这种组合多个弱分类器来提高分类准确率的思想的数学基础是弱学习定理,Schapire在他1990年发表的论文里证明了若目标是弱可学习的,则目标也是强可学习的。值得注意的是,弱学习定理只是提供了一种理论上的可行性。在实际训练过程中,要想成功将多个弱分类器提升为强分类器,训练样本需要能够满足“正确分类次数大于错误分类次数”这一条件。因此,随机采样抽取训练数据是保证这一方法有效的重要前提。

AdaBoost算法既实用又简单,它的应用热度一直不减,而且学者们也在不断尝试改进这一算法。目前常见的改进算法主要有3种思路:①改进AdaBoost里样本权重的更新公式,比如对权重大小加入阈值限制;②改进训练方法,比如将训练过程中表现不好的弱分类器予以丢弃或替换;③将AdaBoost和其他算法相结合,比如和支持向量机(Support Vector Machine, SVM)组合,得到准确率更高的弱分类器。以AdaBoost及其改进算法为基础的人脸识别系统,是目前人工智能领域最热门的应用之一。

[描述来源: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.

URL: https://dl.acm.org/citation.cfm?id=261549

描述来源:Liao, H. W., & Zhou, D. L. (2012). Review of AdaBoost and its improvement. Jisuanji Xitong Yingyong- Computer Systems and Applications, 21(5), 240-244.

URL:http://en.cnki.com.cn/Article_en/CJFDTOTAL-XTYY201205056.htm

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

URL:http://www.cs.princeton.edu/~schapire/papers/strengthofweak.pdf]

发展历史

AdaBoost这一算法早在1995年就被Freund和Schapire提出,因此他们还获得了2003年的哥德尔奖(Gödel Prize)。AdaBoost实用简单,自从它诞生开始就一直深受学者们的追捧。在此基础上Viola和Jones又提出了积分图像和级联器的概念,结合AdaBoost算法取得了里程碑式的成功。学者们不断致力于对AdaBoost算法进行改进。提出了诸如不对称AdaBoost、FloatBoost等一系列改进算法。Viola和Jones致力于将AdaBoost算法应用在物体识别领域,他们在2001年发表了关于物体识别的两篇经典论文,奠定了AdaBoost算法在物体识别领域的地位。近年来AdaBoost算法被广泛应用在人脸识别领域,同时学者们也在不断尝试改进算法,提出了诸如NAdaBoost、SemiBoost、SEAdaBoost和AdaBoostSVM等衍生算法,他们各有特点,应用在机器学习的各个领域,相信未来能够看到更多基于AdaBoost及其改进思想的新算法。

主要事件

年份事件相关论文
1990Schapire证明了若目标弱可学习,则目标也强可学习,是AdaBoost算法有效性的数学基础Schapire, R. E. (1990). The strength of weak learnability. Machine learning, 5(2), 197-227.
1995Freund和Schapire的论文提出AdaBoost,并将其推广至多元分类情况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.
1998Schapire等人提出边缘理论(Margin Theory),对投票方法作了深入解释Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 26(5), 1651-1686.
1999Breiman提出对最小边缘限制理论(minimum margin bound)的质疑Breiman, L. (1999). Prediction games and arcing algorithms. Neural computation, 11(7), 1493-1517.
2000Friedman等人从统计学的角度解释了AdaBoost算法,奠定了之后一系列的Boosting算法变种,同时也激发了学者们对AdaBoost统计学意义的研究Friedman, J., Hastie, T., & Tibshirani, R. (2000). Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors). The annals of statistics, 28(2), 337-407.
2001Viola和Jones提出利用AdaBoost算法对物体进行识别Viola, P., & Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. In Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on (Vol. 1, pp. I-I). IEEE.
2002Viola和Jones提出非对称的AdaBoost改进方法Viola, P., & Jones, M. (2002). Fast and robust classification using asymmetric adaboost and a detector cascade. In Advances in neural information processing systems (pp. 1311-1318).
2006Reyzin和Schapire提出影响AdaBoost算法的核心是边缘分布(margin distribution),而不是最小边缘(minimum margin)Reyzin, L., & Schapire, R. E. (2006, June). How boosting the margin can also boost classifier complexity. In Proceedings of the 23rd international conference on Machine learning (pp. 753-760). ACM.

发展分析

瓶颈

-与二元分类研究相比,多元分类的AdaBoost理论还不够完善

-AdaBoost方法在有噪声(noise)和异常点(outlier)情况下训练时很容易出现过拟合(over-fitting)

未来发展方向

针对AdaBoost算法当前理论的不足,未来会有更多基于此的改进。上文总结了目前常见的3种改进思路,其中以第三个方向,也就是将其和其他算法相结合的方法开放性最强,机器学习领域的新算法层出不穷,不同的结合点产生不同的效果,也许未来我们会在这一领域看到更有趣、更实用,也更有效的新算法,助力人类走向通用人工智能的道路。

Contributor:KEYU QI

相关人物
Michael Jones
Michael Jones
简介
相关人物