关于AdaBoost有效性的分析

开篇：润墨网以专业的文秘视角，为您筛选了一篇关于AdaBoost有效性的分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘要】本文分析了adaboost的概念，Bagging方法训练集选取方法，接着，本文重点分析了AdaBoost有效性，随后，分析了AdaBoost训练误差，最后，本文简单阐述了集成学习算法构造及AdaBoost算法推广。

【关键词】；有效性；分析

中图分类号： TP311 文献标识码： A 文章编号：

一、前言

Adaboost作为一种迭代算法，其使用的领域也是很广的，因此，分析其有效性具有很强的现实意义。提高Adaboost有效性是我们进一步使用Adaboost的前提，因此，对于Adaboost有效性的分析需要深入开展。

二、Adaboost概述

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用adaboost分类器可以排除一些不必要的训练数据特征，并将关键放在关键的训练数据上面。

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

三、Bagging方法训练集选取方法

比起AdaBoost,研究和使用Bagging少得多,究其原因是缺乏选取训练集St的规律.前面已经在算法流程上对二者进行了统一,参照AdaBoost有效性分析,可对Bagging制定训练集的选取策略.仿照AdaBoost权值调整是确保下一轮训练输出ht+1(x)与ht(x)的正确(错误)分类样本有充分的交叉,在Bagging中,可把整个样本集S分成两个子集Sa,Sb,在其中一个子集上通过弱学习算法得到分类器ht(x)后,下一轮从ht(x)正确分类集和错误分类集中各取一半构成新的训练子集,则就确保了前后相邻两次训练得到的弱分类器的正确分类样本交叉,类似AdaBoost,还需要考虑被正确分类和被错误分类累计次数.

四、AdaBoost有效性分析

从前面弱学习算法提升为强学习算法的图示分析以及简化形式弱学习定理的证明可见，被正确分类的样本，其分布的均匀性是非常重要的，否则，如果集中在固定的一些样本上，则另一些样本将始终满足不了“正确分类次数大于错误分类次数”这一条件，最终的分类器错误率将难于降低．

实际上，各弱分类器是基于不同的训练集(或者不同权重的训练集)通过训练而得，因此，此处的均匀性要求也就是对训练算法的“不稳定”要求，即常说的“不稳定”学习算法．当不同的样本或样本权值调整后，新得到的弱分类器的正确分类样本集要有大的变化，才有可能保证正确分类样本分布的随机均匀性．让不同的弱分类器满足正确分类样本在整个样本集上分布的均匀性，是多个弱分类器提升为强分类器的保证条件．

反过来，只要能够采取一定的策略，确保不同的弱分类器正确分类样本分布的均匀性，并满足肚收敛或大于一个大于零的常数，就一定可以得到高精度的强分类器．AdaBoost之所以是一个效率较高的方法，且不易出现过配现象，其权值调整策略的真正目的正是保证不同弱分类器正确分类样本分布的均匀性。

1 、AdaBoost的权值调整分析

换句话说，与的正确与错误分类样本必须交义，这是保证正确分类样本实例的随机性和在样本集S中分布均匀性的一种措施，不允许偏向某些固定样本.随着T增加，被正确分类次数越少的样本权值将越大，从而聚焦到这些错分次数多的样本上，其目的也是让每个样本有相等的机会

被正确分类.由前面的弱学习算法提升为强学习算法的图示分析也可以看出，只有儿乎每个样本被正确分类的机会尽量相等，随着T的增大，才能保证每个样本被正确分类的次数多于一半.A daBoost中权重调整真正目的正是为此.

2、 AdaBoost使用的错误率分析

对AdaBoost的有效性还有一点需要解释就是其使用的错误率，在AdaBoost中， ，其并非真正的错误率 ，不能保证，太多的肯定无法实现由弱分类器提升为强分类器.但正如前面分析指出的,我们并不要求每个弱

分类器的错误率都小于1/2, 只要μ=大于或收敛到一个大于零的常数即可.在下面定理的支撑下,AdaBoost使用εt的合理性就得到保证:

定理3.在AdaBoost中, 与是概率相等的.

五、训练误差分析

记，由于弱分类器的错误率总是比随机猜测（随机猜测的分类器的错误率为0.5），所以，则训练误差为：

。

记，则。

证明：

1、对进行迭代展开

令

。

由于是一个分布，

所以：

所以。

训练误差为

。

所以，为训练误差的上界。

相当于损失函数取，则经验风险/测试误差为，使该经验风险最小的估计为。该风险称为指数风险。

*当样本分对时，，所以，是一个较小的正数。

当样本分错时，，所以。

所以将变为，相当于对上述两种错误率都放大了，这样不等式成立。

证明；

问题：给定弱分类器的集合：，确定弱分类器及其权重。

具体实现时，首先选一个错误率最小的弱分类器，然后确定其权重，所以是一个贪心算法。（相当于对，前向逐步递增特征选择，后面再详细描述）

，因为

即为分类正确的样本的集合，为分类错误的样本的集合。

，两边同乘以

正确率=，错误率=，

所以

所以。

当很小时，很大，即错误率很小的弱分类器的权重很大。

训练误差

令，由于弱分类器的错误率总是比随机猜测（随机猜测的分类器的错误率为0.5），所以，

所以

（不等式可利用在处Taylor展开得到）

令，即为所有中最小的一个。

则训练误差的上界为：

。

所以，当，即训练误差的上界随T的增加指数减小。

AdaBoost相当于最大贝叶斯后验

，

当损失函数取时，则上述表达式为经验风险，当样本很多时，样本均值趋近于期望，即期望风险/测试误差为，

， （表示的概率密度函数）

我们目标是风险最小的，即

所以

所以

，

为最大贝叶斯后验。上面证明了收敛性，最后的强分类器收敛于最大后验概率。

AdaBoost相当于前向逐步递增加法建模

，可视为基展开，其中为基函数，为对应基函数的权重。对基展开，通常是给定基函数，一次联合求出所有的基函数中的参数及其权重（如用最小二乘法或极大似然估计方法）。

而AdaBoost为一个逐步递增的方式增加基函数，并计算其权重，不调整已添加的基函数中的参数及其权重。假设第步的模型为：，当损失函数取时，则第T步新增加的基函数及其权重要使得训练误差/经验风险最小，即

，

，

其中。因为每个不依赖于，所以可以看作是应用于每个观测的权值，该权值依赖于，所以，每个样本的权值随每次迭代改变。

六、集成学习算法构造及AdaBoost算法推广

集成学习算法构造力方法

由前面分析，可以按照下面两个条件来完成一般集成学习算法的构造:

（一）多个分类器按照某种规则集成为一个分类器，使集成分类器好于单个分类器;

（二)新增分类器按照同样规则参与集成，可以降低训练错误率。

对条件1（一)AdaBoost算法采取了加权线性组合，线性组合体现了分类器参与集成不分先后。如果分类器集成分先后，就需要引入非线性组合。决策树就是典型的非线性组合，如判别函数 就等同于决策树:根分类器为h,，被h，分为1类和一1类后的第2层分类器分别为h2和h3。

对条件（二)AdaBoost算法采取了调整样本分布的办法，即调整样本权值，赋予被错分次数多的样本较大权值，让新分类器尽量正确分类这些样本。按照上述构造力一法，从推广AdaBoost算法角度，可以构造一些新集成学习算法。

七、结束语

通过本文的分析和研究，我们总结出Adaboost的使用范围在不断的扩大，同时Adaboost有效性的分析也是进一步拓展Adaboost使用范围，以及提高Adaboost使用效果的必由之路。

参考文献

[1] 武勃,黄畅,艾海舟,劳世竑.基于连续Adaboost算法的多视角人脸检测[J]. 计算机研究与发展. 2005(09)

[2] 燕继坤,郑辉,王艳,曾立君.基于可信度的投票法[J]. 计算机学报. 2005(08)

[3] 沈学华,周志华,吴建鑫,陈兆乾.Boosting和Bagging综述[J]. 计算机工程与应用. 2000(12)