Adaboost，最终分类器的助推剂

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。

Boosting，也称为增强学习或提升法，是一种重要的集成学习技术，能够将预测精度仅比随机猜度略高的弱学习器增强为预测精度高的强学习器，这在直接构造强学习器非常困难的情况下，为学习算法的设计提供了一种有效的新思路和新方法。作为一种元算法框架，Boosting几乎可以应用于所有目前流行的机器学习算法以进一步加强原算法的预测精度，应用十分广泛，产生了极大的影响。而AdaBoost正是其中最成功的代表，被评为数据挖掘十大算法之一。在AdaBoost提出至今的十几年间，机器学习领域的诸多知名学者不断投入到算法相关理论的研究中去，扎实的理论为AdaBoost算法的成功应用打下了坚实的基础。AdaBoost的成功不仅仅在于它是一种有效的学习算法，还在于：

1）它让Boosting从最初的猜想变成一种真正具有实用价值的算法；

2）算法采用的一些技巧，如：打破原有样本分布，也为其他统计学习算法的设计带来了重要的启示；

3）相关理论研究成果极大地促进了集成学习的发展。

对adaBoost算法的研究以及应用大多集中于分类问题，同时也出现了一些在回归问题上的应用。就其应用adaBoost系列主要解决了： 两类问题、多类单标签问题、多类多标签问题、大类单标签问题、回归问题。它用全部的训练样本进行学习。

最初的Boosting算法由Schapire于1990年提出，即一种多项式的算法，并进行了实验和理论性的证明。在此之后，Freund研究出一种更高效的Boosting算法。但这两种算法都有共同的不足即需要提前确定弱学习算法识别准确率的下限。Boosting算法可以提升任意给定学习算法的准确度，主要思想是通过一些简单的规则整合得到一个整体，使得该整体具有的性能比任何一个部分都高。其思想受启发于Valiant提出的PAC学习模型。

Valiant认为“学习”是一种不管模式明显清晰或是否存在模式时都能够获得知识的过程，并从计算的角度定义了学习的方法，其包含学习的协议、合理信息采集机制的选择以及可以在适当过程内实现学习概念的分类。PAC学习模型的原理是指在训练样本的基础上，算法的输出能够以概率靠近未知的目标进行学习分类，基本框架涉及样本复杂度和计算复杂度。简而言之，在PAC学习模型中，能够在多项式个时间内和样本获得特定要求的正确率即就是一个好的学习过程。该模型由统计模式识别、决策理论得到的一些简单理论并结合计算复杂理论的方法而得出的学习模型。其中提出了弱学习和强学习的概念。

Adaboost算法已被证明是一种有效而实用的Boosting算法。该算法是Freund和Schapire于1995年对Boosting算法的改进得到的，其算法原理是通过调整样本权重和弱分类器权值，从训练出的弱分类器中筛选出权值系数最小的弱分类器组合成一个最终强分类器。基于训练集训练弱分类器，每次下一个弱分类器都是在样本的不同权值集上训练获得的。每个样本被分类的难易度决定权重，而分类的难易度是经过前面步骤中的分类器的输出估计得到的。

Adaboost算法在样本训练集使用过程中，对其中的关键分类特征集进行多次挑选，逐步训练分量弱分类器，用适当的阈值选择最佳弱分类器，最后将每次迭代训练选出的最佳弱分类器构建为强分类器。其中，级联分类器的设计模式为在尽量保证感兴趣图像输出率的同时，减少非感兴趣图像的输出率，随着迭代次数不断增加，所有的非感兴趣图像样本都不能通过，而感兴趣样本始终保持尽可能通过为止。

算法流程

该算法其实是一个简单的弱分类算法提升过程，这个过程通过不断的训练，可以提高对数据的分类能力。整个过程如下所示：

1． 先通过对N个训练样本的学习得到第一个弱分类器；

2． 将分错的样本和其他的新数据一起构成一个新的N个的训练样本，通过对这个样本的学习得到第二个弱分类器 ；

3． 将1和2都分错了的样本加上其他的新样本构成另一个新的N个的训练样本，通过对这个样本的学习得到第三个弱分类器；

4． 最终经过提升的强分类器。即某个数据被分为哪一类要由各分类器权值决定。

由Adaboost算法的描述过程可知，该算法在实现过程中根据训练集的大小初始化样本权值，使其满足均匀分布，在后续操作中通过公式来改变和规范化算法迭代后样本的权值。样本被错误分类导致权值增大，反之权值相应减小，这表示被错分的训练样本集包括一个更高的权重。这就会使在下轮时训练样本集更注重于难以识别的样本，针对被错分样本的进一步学习来得到下一个弱分类器，直到样本被正确分类。在达到规定的迭代次数或者预期的误差率时，则强分类器构建完成。 

算法特点

Aadboost 算法系统具有较高的检测速率，且不易出现过适应现象。但是该算法在实现过程中为取得更高的检测精度则需要较大的训练样本集，在每次迭代过程中，训练一个弱分类器则对应该样本集中的每一个样本，每个样本具有很多特征，因此从庞大的特征中训练得到最优弱分类器的计算量增大。典型的 Adaboost 算法采用的搜索机制是回溯法，虽然在训练弱分类器时每一次都是由贪心算法来获得局部最佳弱分类器，但是却不能确保选择出来加权后的是整体最佳。在选择具有最小误差的弱分类器之后，对每个样本的权值进行更新，增大错误分类的样本对应的权值，相对地减小被正确分类的样本权重。且执行效果依赖于弱分类器的选择，搜索时间随之增加，故训练过程使得整个系统的所用时间非常大，也因此限制了该算法的广泛应用。另一方面，在算法实现过程中，从检测率和对正样本的误识率两个方面向预期值逐渐逼近来构造级联分类器，迭代训练生成大量的弱分类器后才能实现这一构造过程。由此推出循环逼近的训练分类器需要消耗更多的时间。