Adaboost 基本简介

Adaptive Boosting Algorithm目 录一、Adaboost（Adaptive Boosting）历史2二、Adaboost算法基本原理2三、AdaBoost算法的优点4四、AdaBoost算法的缺点4五、AdaBoost算法的应用4六、AdaBoost改进4七、总结5一、Adaboost（Adaptive Boosting）历史Adaboost的前身的Boosting算法。Boosting是一种提高任意给定学习算法准确度的方法。它的思想起源于Valiant提出的PAC(Probably Approximately Correct)学习模型。Valiant和Kearns提出了弱学习和强学习的概念,识别错误率小于1/2,也即准确率仅比随机猜测略高的学习算法称为弱学习算法;识别准确率很高并能在多项式时间内完成的学习算法称为强学习算法。同时,Valiant和Kearns首次提出了PAC学习模型中弱学习算法和强学习算法的等价性问题，即任意给定仅比随机猜测略好的弱学习算法,是否可以将其提升为强学习算法?如果二者等价,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法,而不必寻找很难获得的强学习算法。1990年, Schapire最先构造出一种多项式级的算法,对该问题做了肯定的证明,这就是最初的Boosting算法。一年后,Freund提出了一种效率更高的Boosting算法。但是,这两种算法存在共同的实践上的缺陷,那就是都要求事先知道弱学习算法学习正确率的下限。1995年, Freund和schapire改进了Boosting算法,提出了AdaBoost(Adaptive Boosting)算法5,该算法效率和Freund于1991年提出的Boosting算法几乎相同,但不需要任何关于弱学习器的先验知识,因而更容易应用到实际问题当中。之后,Freund和schapire进一步提出了改变Boosting投票权重的AdaBoost.M1,AdaBoost.M2等算法,在机器学习领域受到了极大的关注。二、Adaboost算法基本原理 Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用Adaboost分类器可以排除一些不必要的训练数据特征，并将关键放在关键的训练数据上面。AdaBoost算法中不同的训练集是通过调整每个样本对应的权重来实现的。开始时，每个样本对应的权重是相同的，即其中 n 为样本个数，在此样本分布下训练出一弱分类器。对于分类错误的样本，加大其对应的权重；而对于分类正确的样本，降低其权重，这样分错的样本就被突出出来，从而得到一个新的样本分布。在新的样本分布下，再次对弱分类器进行训练，得到弱分类器。依次类推，经过 T 次循环，得到 T 个弱分类器，把这 T 个弱分类器按一定的权重叠加（boost）起来，得到最终想要的强分类器。算法步骤设输入的n个训练样本为:(x1,y1)，(x2,y2)，.(xn,yn)，其中xi是输入的训练样本，yi0,1分别表示正样本和负样本，具体步骤如下：（1） 初始化每个样本的权重wi,iD(i);（第一次迭代都初始化为1/n）(2)对每个t=1,., T(T为弱分类器的个数)把权重归一化为一个概率分布（上面这个公式，就是把所有样本的权重求和后，算出每个样本权重占总权重的比例）对每个特征f，训练一个弱分类器计算对应所有特征的弱分类器的加权错误率选取最佳的弱分类器(拥有最小错误率)：即根据上式，选出加权错误率最低的那个弱分类器作为第t次循环得到的分类器。得到第t次循环的分类器后，就需要再重新调整各个样本的权重上式中，如果第i个样本被第t循环得到的分类器分类正确的话，否则为0，以上的操作重复T循环后，得到最后的强分类器，对输入的样本x，我们的分类结果为：三、AdaBoost算法的优点1、 训练的错误率上界：随着迭代次数的增加，会逐渐下降2、 AdaBoost算法即使训练次数很多，也不会出现过拟合的问题3、 AdaBoost提供的只是框架，可以使用各种方法构建子分类器4、 简单，不用做特征筛选四、AdaBoost算法的缺点AdaBoost的训练过程中，每次迭代都会对那些分类错误的样本进行加权，当多个这样的样本多次被分类错误以后，它们的权重过大，进而左右误差的计算和分类器的挑选，使分类器的精确度下降。这就是非常典型的“退化问题”。这些样本往往都是靠近分类边界的样本，称为临界样本。临界样本使得训练的“退化问题”加威，但也是提升分类器精确度的必需品。在人脸检测问题中，现实中人脸的数目要远远小于非人脸数，负样本的范围非常广，样本集往往无法精确表示，正负样本的数量差距很大，分类器会关注大容量样本，导致分类器不能较好地完成区分小类样本的目的。“数据不平衡问题也是AdaBoost的一个典型难题五、AdaBoost算法的应用近年来人工智能技术发展日益成熟，人脸检测问题是其中的一个研究热点，在几十年的研究过程中，许多研究者提出了有效的检测方法。1995年Freund和Schipare提出的AdaBoost算法是第一个实时的人脸检测算法，与以前的方法相比，AdaBoost算法在速度上取得了非常大的成功。AdaBoost算法目前主要用于如上面说的目标识别和上面说的人脸检测领域，如汽车识别，驾驶员眨眼识别等。六、AdaBoost改进根据查看论文，共有几大改进方向1. 权值更新方法的改进如Viola和Jones提出的非对称AdaBoost方法，AsymBoost在正负样本出现误检时给出不同的权值更新方法，增大正样本的比重，减少负样本的比重，以期使样本重心达到平衡。此外还有类似的改进算法，如Allende提出的RADA算法，NAdaBoost算法等。2. 训练方法的改进 AdaBoost应用不广，训练时间太长是原因之一。对此有Stan等人提出的FloatBoost算法，Baumann等人提出的SEAdaBoost算法，Merler等人提出的AdaBoost的并行计算方法P-AdaBoost算法等。3. 多算法结合的改进4. 综合方法的改进七、总结总的来说，AdaBoost算法的研究改进方面集中在以下方面：1、 针对AdaBoost算法本身过拟合和鲁棒性不强的问题（原本AdaBoost算法的优点之一就是不会出现过拟合现象，论文还写了这么句话，不知是有不同意思，还是论文作者写错了的原因）2、 针对AdaBoost算法训练耗时、