Adaboost.doc

Adaboost.doc,其思想起源于Valiant提出的PAC(ProbablyApproximatelyCorrect)学习模型。Valiant和Kearns提出了弱学习和强学习的概念:,识别准确率很高并能在多项式时间内完成的学习算法称为强学习算法。同时,Valiant和Kearns首次提出了PAC学习模型中弱学习算法和强学习算法的等价性问题,即任意给定仅比随机猜测略好的弱学习算法,是否可以将其提升为强学习算法?如果二者等价,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法,而不必寻找很难获得的强学习算法。1990年,Schapire最先构造出一种多项式级算法,对该问题做了肯定的证明,这就是最初的Boosting算法。一年后,Freund提出了一种效率更高的Boosting算法。但是,这两种算法存在共同的实践上的缺陷,那就是都要求事先知道弱学习算法学习正确的下限。1995年,Freund和Schapire改进了Boosting算法,提出了AdaBoost(AdaptiveBoosting)算法,该算法效率和Freund于1991年提出的Boosting算法几乎相同,但不需要任何关于弱学习器的先验知识,因而更容易应用到实际问题当中。之后,、,在机器学习领域受到了极大的关注。Adaboost是一种迭代算法,其核心思想是针对同一个训练集训练不同的弱分类器(),然后把这些弱分类器集合起来,构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的,它根据每次训练集之中每个样本的分类是否正确,以及上次的总体分类的准确率,来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练,最后将每次训练得到的分类器最后融合起来,作为最后的决策分类器。使用Adaboost分类器可以排除一些不必要的训练数据特征,并将关键放在关键的训练数据上面。在产生单个的基分类器时可用相同的分类算法,也可用不同的分类算法,这些算法一般是不稳定的弱分类算法,如神经网络(BP),决策树()等。,对Adaboost算法的研究以及应用大多集中于人脸识别、行人检测、文本分类等方面的分类器的设计中,近年也出现了一些在回归问题上的应用。就其应用,Adaboost算法主要解决了:两类问题、多类单标签问题、多类多标签问题、大类单标签问题、回归问题。它用全部的训练样本进行学习。,这个过程通过不断的训练,可以提高对数据的分类能力。整个过程如下所示: (1)先通过对个训练样本的学习得到第一个弱分类器; (2)将分错的样本和其他的新数据一起构成一个新的个的训练样本,通过对这个样本的学习得到第二个弱分类器; (3)将1和2都分错了的样本加上其他的新样本构成另一个新的个的训练样本,通过对这个样本的学习得到第三个弱分类器; (4)最终级联得到经过提升的强分类器。即某个数据被分为哪一类要通过弱分类器中的多数表决。