Adaboost算法的前世今生.docx

Adaboost 算法的前世今生转载▼标签：itAdaboost 算法的前世今生引言众所周知，模式识别的方法可以按照参与识别特征的属性来区分，可以分为两大类：一、使 用定量特征（可度量）如物体长度、宽度等，来描述的各种模式，这一类主要是指决策理论， 有匹配、统计、神经网络等方法；二、使用定性特征如特征结构、排列顺序等，来描绘的各 种模式，这一类主要是指结构判别，主要有串和树的匹配等方法模式识别的完整的流程顺序是：传感器——分割组织——特征提取——分类器——后处理 其中分类器的设计部分，可以使用的理论有很多，目前主要包括：基于统计理论的方法（贝 叶斯理论）、线性判别函数、神经网络的方法、随机方法（对于复杂的问题）、非度量方法（定 性结构特征） 分类器得到的模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的类标号因此， 训练算法的主要目标就是要建立具有很好的泛化能力模型，即建立能够准确地预测未知样本 类标号的模型通常我们用“方差”和“偏差”来测量学习算法与给定分类问题的“匹配”和“校准”程度 “偏差”度量的是匹配的“准确性”和“质量”：一个高的偏差意味着一个坏的匹配，“方差” 度量的是匹配的“精确性”和“特定性”：一个高的方差意味着一个弱的匹配。

研究表明，使用重采样技术可以提高分类器的准确率，而 boosting 算法就是涉及分类器设计 中的重采样技术其思想内涵在于：从给定的数据集中抽取多个数据子集，使得有可能计算 任意统计量的值及其范围说道 boosting，不得不说 Arcing （adaptive reweighting and combining ） 自适应的权值重置和 组合：重新使用和选择数据，以期达到改善分类器性能的目的最简单的 arcing 版本就是 bagging 算法Bagging 一个多分类器系统bagging 算法的基本思想:给定一个弱学习算法，和一个训练集；单个弱学习算法准确率不高；将该学习算法使用多次， 得出预测函数序列，进行投票，最后结果准确率将得到提高步骤1：从大小为n的原始数据集D中，分别独立随机的抽取n'个数据（n'

Bagging 和 boosting 的区别训练集：预测函数准确性使用要求Bagging随机选 择，各轮 训练集相 互独立没有权重;可以并行 生成在有些数据集中， boosting 会 引起退 化要求“不稳定”的分 类方法Boosting各轮训练 集并不独 立，它的 选择与前 轮的学习 结果有关有权重;只能顺序生 成在大多数数据集中， boosting的准确性 比 bagging 高要求“不稳定”的分 类方法训练集的小变动能 够使得分类模型显 著变动Bagging是一个纯粹的降低相关度的方法，如果树的节点具有很高的相关性，bagging就会 有好的结果早期的 AdaBoost 在第二步的时候采用重采样方法，即使某些样本权重增加 这种方法与bagging存在某种关联它也是Boost的成功之处中降低相关度方面的重要部分 AdaBoost在第二步中如果使用加权的tree-growing算法，而不是重采样算法，效果会更好 可以使用stumps作为弱分类器最初的boosting算法1989年Kearns and Valiant研究了 PAC学习模型中弱学习算法和强学习算法两者间的等价问 题，即任意给定仅仅比随机猜测稍好（准确率大于 0.5）的弱学习算法，是否可以被提升为强 学习算法？若两者等价，则我们只需寻找一个比随机猜测稍好的弱学习算法，然后将其提升 为强学习算法，从而不必费很大力气去直接寻找强学习算法。

就此问题， Schapire 于 1990 年首次给出了肯定的答案他主持这样一个观点：任一弱学习算法可以通过加强提升到一个 任意正确率的强学习算法，并通过构造一种多项式级的算法来实现这一加强过程，这就是最 初的 Boosting 算法的原型主要思想是，根据已有的训练样本集设计一个分类器，要求其准确率要比平均性能好，然后 依次顺序加入多个分量分类器系统，最后形成一个总体分类器以一个二类问题举例步骤1：从大小为n的原始样本集D中随机选取n1个样本点（不放回），组成样本集D1 根据 D1 训练出第一个分类器 C1步骤2：构造第二个样本集D2,它是根据C1最富信息的那些样本点组成的在最后产生的 D2集合中将有一半的样本被C1正确分类，而另一半的样本被C1错误分类步骤3：继续构造第三个样本集D3，方法：在D中剩余的样本中选取样本点，并且用C1 和C2进行分类，如果C1和C2判决结果不同，那么就把样本加入D3，否则就忽略这个样 本然后用D3训练新分类器C3步骤4：用这3个分类器对新样本x进行分类，如果C1和C2的判决结果相同，则表为一 类，不同则表为另一类Boosting方法有许多不同的变形，其中最流行的一种就是adaboost。

这个名词是“adaptive boosting”的缩写这个方法允许设计者不断的加入新的“弱分类器”直到达到某个预定的 最小错误率1995 年 Freund and Schapire 提出 AdaBoost 算法1996 年 Yoav Freund在 Experiments with a New Boosting Algorithm中提出了 AdaBoost.M1 和 AdaBoost.M2两种算法其中，AdaBoost.M1是我们通常所说的 Discrete AdaBoost:而 AdaBoost.M2 是 M1 的泛化形式该文的一个结论是:当弱分类器算法使用简单的分类方法 时， boosting 的效果明显地统一地比 bagging 要好当弱分类器算法使用 C4.5 时， boosting 比 bagging 较好，但是没有前者的比较来得明显AdaBoost.M1 Discrete AdaBoost：初始版本1. 获得一组样本(X)和它的分类(Y)和一个分类器(weaklearn).2. 赋予平均的权值分布 D(i)进入循环:T次1. 赋予弱分类器权值D(i)，使用弱分类器获得样本(X)到分类(Y)上的一个映射.(就是把某个X 归到某个Y类中去)2. 计算这个映射的误差e，e-各个归类错误的样本权值之和•如果e>1/2那么弱分类器训练失 败，跳出循环，训练结束(这在二值检测中是不会发生的，而多值的情况就要看分类器够不够强健了)3. 设beta B = e / ( 1 - e ).用于调整权值.因为e<1/2.因此OvBvl4. 如果某样本分类正确，该样本的权值就乘以 B 让权值变小;如果分类错误，就让该样本的权 值乘以BA-1或者不变,这样就让分类正确的样本权值降低，分类错误的样本权值升高，加强了 对较难分类样本的分类能力5. 权值均衡化循环结束1.最终的分类器是,当一个X进入时，遍历所有Y,寻找使(h(x)=y的情况下,log(1/B)之和)最大 者即是输出分类y书上版本具体算法：每个样本都赋予一个权重，T次迭代，每次迭代后，对分类错误的样本加大权重，使得下一 次的迭代更加关注这些样本。

输入:(X1,Y1), (X2,Y2),„(Xn,Yn)XiuX, YiUY={+1,-1}初始化权值:D1(i)=1/nFor t=1,„,T在Dt下训练，得到弱的假设ht: X->{-1,+1},错误率:E t=Z Dt(i) [ht(Xi)MYi]选择a t=1/2 ln ( (1- E t)/ E t ),更改权值:if ht(Xi)MYi , Dt+1(i)=Dt(i)* e a t /Ztif ht(Xi)=Yi , Dt+1(i)=Dt(i)* e -a t /Zt输出:H(X)=sign( £ a tht(X))带图版本(程序版本)：初始赋予每个样本相等的权重1/N ；For t = 1, 2, „ , T Do学习得到分类法Ct； 计算该分类法的错误率EtEt=所有被错误分类的样本的权重和；B t= Et/ (1 - Et)根据错误率更新样本的权重；正确分类的样本： Wnew= Wold* p t 错误分类的样本： Wnew= Wold调整使得权重和为 1；每个分类法Ct的投票价值为log [ 1 / P t ]最大错误率问题：将Y t=l/2-Et ;Freund and Schapire 证明: 最大错误率为:即训练错误率随Y t的增大呈指数级的减小. 最大总误差:m : 样本个数 d : VC 维T : 训练轮数Pr: 对训练集的经验概率如果T值太大‘Boosting会导致过适应(overfit) 《模式分类》386页AdaBoost.M2 是 M1 的泛化形式.M2 的流程是1•获得一组样本(X)和它的分类(Y)和一个分类器(weaklearn).2•对于某个样本Xi将它的分类归为一个正确分类Yi和其他不正确分类Yb3. 样本权值进行如下分布首先每个样本分到1/m的权值，然后每个不正确分类分到(1/m)/Yb 的个数。

也就是说样本权值是分到了每个不正确的分类上进入循环1. 求每个样本的权值,即每个样本所有不正确的分类的权值和 ,再求每个样本错误分类的权 值,即不正确分类的权值除以该样本的权值.最后将每个样本的权值归一化2. 将样本权值和某样本的不正确分类的权值输入到weaklearn，获得弱分类器的输出为各个 分类的可能值3. 计算伪错误率:4. 更新权值退出循环1999 年，ROBERT E. SCHAPIRE 和 YORAM SINGER,于 Machine Learning 发表论文： Improved Boosting Algorithms Using Confidence-rated Predictions提出了更具一般性的 AdaBoost 形式提出了自信率以改善 AdaBoost 的性能并提出了解决多标签问题的 AdaBoost.MH和AdaBoost.MR算法，其中AdaBoost.MH算法的一种形式又被称为Real Boost 算法事实上：Discrete AdaBoost是指，弱分类器的输出值限定在{-1,+1},和与之相应的权 值调整，强分类器生成的AdaBoost算法；Real AdaBoost是指，弱分类器输出一个可能度， 该值的范围是整个R,和与之相应的权值调整，强分类器生成的AdaBoost算法。

事实上，Discrete到Real的转变体现了古典集合到模糊集合转变的思想至于Gentle AdaBoost考虑到(AdaBoost对”不像”的正样本权值调整很高，而导致了分类器的 效率下降)，而产生的变种算法它较少地强调难以分类的样本 Rainer Lienhart， Alexander Kuranov, Vadim Pisarevsky 在论文 Empirical Analysis of Detection Ca。