Ｂｏｏｓｔｉｎｇ算法研究.docVIP

Ｂｏｏｓｔｉｎｇ算法研究 　　摘要：Boosting 算法是近年来在机器学习领域中一种流行的用来提高学习精度的算法。文中以AdaBoost算法为例来介绍Boosting的基本原理。 　　关键词：机器学习；Boosting；泛化误差；分类 　　中图分类号：TP181文献标识码：A文章编号：1009-3044(2008)36-2698-02 　　A Study of Boosting Algorithm 　　LU Gang1, CHEN Yong1, FAN Yong-xin2, HU Cheng1 　　(1.The Artillery Academy of PLA, Hefei 230031, China;2.China Construction Bank Yunnan Branch, Kunming 650021, China) 　　Abstract: Boosting is a general method for improving the accuracy of any given learning algorithm.This short overview paper introduces the boosting algorithm AdaBoost, and explains the underlying theory of boosting. 　　Key words: machine learning; boosting; generalization error; classification 　　1 引言 　　Freund 和 Schapire的AdaBoost算法问世便引起了机器学习和数理统计两大领域的广泛关注。它的思想起源于Valiant提出的PAC ( Probably Approximately Correct)学习模型。Kearns 和Valiant首次提出PAC学习模型中任意给定仅比随机猜测略好的弱学习算法是否可“boosted”为强学习算法。1990年，Schapire构造出一种多项式级的算法，对该问题做了肯定的证明，这是最初的Boosting算法。一年后，Freund提出了一种效率更高的Boosting算法。但是，这两种算法存在共同的实践上的缺陷，那就是都要求事先知道弱学习算法学习正确率的下限。这些早期的Boosting 算法首先被Drucker、Schapire和Simard应用于一次OCR工作中。1995年，Freund和schapire改进了Boosting算法，提出了AdaBoost (Adaptive Boosting)算法，此算法不需要任何关于弱分类器的先验知识，可以非常容易地应用到实际问题中。 　　2 AdaBoost算法 　　在机器学习领域中，AdaBoost算法得到极大的重视。实验结果显示，AdaBoost能显著提高学习精度和泛化能力，已经成为Boosting 系列中的代表算法。之后出现的各种Boosting算法都是在AdaBoost算法的基础之上发展而来的。对AdaBoost算法的研究应用大多集中在分类问题中，近年来也出现了一些在回归问题上的研究。寻找多个识别率不是很高的弱分类算法比寻找一个识别率很高的强分类算法要容易得多，AdaBoost算法的任务就是完成将容易找到的识别率不高的弱分类算法提升为识别率很高的强分类算法，这也是AdaBoost 算法的核心指导思想所在，如果算法完成了这个任务，那么在分类时，只要找到一个比随机猜测略好的弱分类算法，也就是给定一个弱学习算法和训练集，在训练集的不同子集上，多次调用弱学习算法，最终按加权方式联合多次弱学习算法的预测结果就可得到最终学习结果。 　　AdaBoost算法的基本思想是：首先给出任意一个弱学习算法和训练集(x1,y1), (x2, y2 ) ,..., (xm, ym) ,此处,xi∈X, X表示某个域或实例空间，在分类问题中是一个带类别标志的集合,yi∈Y={+1, -1}。初始化时, Adaboost为训练集指定分布为1/m，即每个训练例的权重都相同为1 /m 。接着，调用弱学习算法进行T次迭代，每次迭代后，按照训练结果更新训练集上的分布，对于训练失败的训练例赋予较大的权重，使得下一次迭代更加关注这些训练例，从而得到一个预测函数序列h1,h2,...,ht，每个预测函数ht也赋予一个权重，预测效果好的，相应的权重越大。T次迭代之后，在分类问题中最终的预测函数H采用带权重的投票法产生。单个弱学习器的学习准确率不高，经过运用Boosting算法之后，最终结果准确率将得到提高。每个样本都赋予一个权重, T次迭代，每次迭代后，对分类错误的样本加大权重。 　　离散的AdaBoost算法，给定训练样本集S