《adaboost的一些说明》由会员分享，可在线阅读，更多相关《adaboost的一些说明（9页珍藏版）》请在金锄头文库上搜索。
1、adaboost的一些说明2008-11-27 01:14上学期拿出一部分时间来做adaboost，做的时候做了一些笔记。论坛上也有一些正在读程序研究算法的人。我就把这份粗糙的笔记拿出来与大家分享一下吧。肯定有错误的地方，也有不妥当的地方，大家不要太相信我 还有这个地方不能贴公式，不能贴图片，还有我很懒，就挑了几幅重要的贴了，其他的大家去看文章吧 排版不好看，也许写得也不明白，大家多包涵，希望大家可以完善这个文档。让后来者少走些弯路。 不用发论坛消息问我，发在这里让更多人看见，更多人解答，然后也可以让更多的人知道，更好些第一部分:算法的产生1996 年 Yoav Freund 在 Experi
2、ments with a New Boosting Algorithm 中提出了 AdaBoost.M1 和 AdaBoost.M2 两种算法.其中，AdaBoost.Ml是我们通常所说的Discrete AdaBoost;而AdaBoost.M2是Ml的泛化形式.该文的一个结论是：当弱分类器算法使用简单的分类方法时boosting的效果明显地统一地比bagging要好.当弱分类器算法使用C4.5时boosting比bagging较好，但是没有前者的比较来得明显.文献中记录的.Ml算法初始1. 获得一组样本(X)和它的分类(Y)和一个分类器(weaklearn).2. 赋予平均的权值分布D(i
3、)进入循环:T次1赋予弱分类器权值D(i),使用弱分类器获得样本(X)到分类(Y)上的一个映射(就是把某个X归到某个Y类中去)2. 计算这个映射的误差e.e=各个归类错误的样本权值之和.如果e1/2那么弱分类器训练失败，挑出循环训练结束(这在二值检测中是不会发生的 而多值的情况就要看分类器够不够强健了)3. 设B = e / ( 1 - e ).用于调整权值.因为e1/2.因此0B14. 如果某样本分类正确，该样本的权值就乘以B让权值变小;如果分类错误，就让该样本的权值乘以B-l或者不变，这样就让分类正确的样本权值降低 分类错误的样本权值升高 加强了对较难分类样本的分类能力5. 权值均衡化循环
4、结束1. 最终的分类器是,当一个X进入时，遍历所有Y,寻找使(h(x)=y的情况下,log(1/B)之和)最大者即是输出分类yM2 相比于 M1 的改进是允许弱分类器输出多个分类结果， 并输出这几个分类结果的可能性(注意， 这里不是概率).M2 的流程是1. 获得一组样本(X)和它的分类(Y)和一个分类器(weaklearn).2. 对于某个样本 Xi 将它的分类归为一个正确分类 Yi 和其他不正确分类 Yb3. 样本权值进行如下分布首先每个样本分到1/m的权值，然后每个不正确分类分到(1/m)/Yb的个数.也就是说样本权值是分到了每个不正确的分类上进入循环1. 求每个样本的权值， 即每个样本
5、所有不正确的分类的权值和， 再求每个样本错误分类的权值， 即不正确分类的权值除以该样本的权值. 最后将每个样本的权值归一化2. 将样本权值和某样本的不正确分类的权值输入到weaklearn,获得弱分类器的输出为各个分类的可能值3. 计算伪错误率:公式见上4. 更新权值退出循环最终的强分类器: 图贴不出来了.1999 年, ROBERT E. SCHAPIRE 和 YORAM SINGER, 于 Machine Learning 发表论文:Improved Boosting Algorithms Using Confidence-rated Predictions. 提出了更具一般性的 AdaB
6、oost 形式.提出了自信率以改善AdaBoost的性能.并提出了解决多标签问题的AdaBoost.MH和AdaBoost.MR算法，其中 AdaBoost.MH 算法的一种形式又被称为 Real Boost 算法.事实上:Discrete AdaBoost是指，弱分类器的输出值限定在-1,+1,和与之相应的权值调整，强分类器生成的AdaBoost算法；Real AdaBoost是指，弱分类器输出一个可能度，该值的范围是整个R,和与之相应的权值调整，强分类器生成的AdaBoost算法。 事实上， Discrete 到 Real 的转变体现了古典集合到模糊集合转变的思想至于Gentle AdaB
7、oost.考虑到（AdaBoost对”不像”的正样本权值调整很高，而导致了分类器的效率下降），而产生的变种算法. 它较少地强调难以分类的样本.Rainer Lienhart, Alexander Kuranov, Vadim Pisarevsky 在论文 Empirical Analysis of Detection Cascades of Boosted Classifiers for Rapid Object Detection中提出在stump弱分类器（即每个弱分类器使用一个特征进行分类）上进行的对比试验中，Gentle的结果明显好于Real和Discrete.大牛已经做出试验了，我就不
8、怀疑它了.和上篇论文流程大体相同作者还讨论了 alpha（t）的取法：算法去看文章吧. 这里不能直接贴图文献中记录的 AdaBoost.MH 算法算法的运算流程:1. 得到一组样本（m个）和样本相应的分类,这个分类是由K个是和否的标签组成.某一个样本可以有多个是标签.2. 均分权值：l/mk进入循环:1. 由弱分类器获得各样本针对各标签的是或否结果（给出离散值或连续值）2. 获得 alpha（t）3. 调整权值大概是,弱分类器判断l标签的是或否，若判断正确乘以1,错误乘以-1,再乘以，然后blablabla4. 权值归一化跳出循环输出强分类器1998 年 Jerome Friedman & T
9、revor Hastie & Robert Tibshirani 发表文章 Additive Logistic Regression: a Statistical View of Boostin 一些重要的结论:Bagging是一个纯粹的降低相关度的方法，如果树的节点具有很高的相关性,bagging就会有好的结果1. 早期的AdaBoost在第二步的时候采用重采样方法，即使某些样本权重增加.这种方法与bagging存在某种关联，它也是 Boost 的成功之处中降低相关度方面的重要部分.2. 在第二步中如果使用加权的 tree-growing 算法,而不是重采样算法,效果会更好.This rem
10、oves the randomization component essential in bagging3. 使用 stumps 作为弱分类器Logit 和 Gentle 算法的提出过程大致是这样的1. 验证Boosting algorithms是一种拟合一个additive logistic regression model(加性的逻辑回归模型)的阶段式估计过程. 它有最优一个指数判据,这个判据由第二定理与二项式对数似然判据是等价的.2. 作者证明 Discrete 是使用 adaptive Newton updates 拟合一个 additive logistic regression
11、model 来最小化 Ee(-yF(x)的过程， 其中F(x)=求和fm(x),而fm(x)就是各层分类器的结果3. 作者证明 Real 是使用层级最优的方法来拟合一个 additive logistic regression model.4. 作者说明了为什么要选择Ee(-yF(x)作为目标：因为大家都用这个5. 作者证明了当(blabla 一个很复杂的公式，贴不出来)时Ee(-yF(x)最小6. 作者证明了每次权值更新以后,最近一次训练出的弱分类器错误率为50%.7. 作者证明了对于最优的F(x),样本的分类乘以权值的和应该为0.于是作者用80年代兴起的逻辑回归的寻优方法中提炼出了 Log
12、itBoost(我终于找到logitBoost的logic 了)自适应的牛顿法, 拟合加性 logistic 回归模型1. 获得样本，(x,y)序列.将分类y*=(y+l)/22. 设置初值,F(x)=0,p(xi)=l/2进入循环1. 依式计算 zi,wi.2. 通过加权最小二乘的方式拟合函数fm(x).由zi拟合xi,权重为wi3. 更新 F(x),p(x)退出循环输出分类器 signF(x).作者提出，logitAdaBoost在每一轮中都使Ee(-y(F(x)+f(x)最优,会使训练样本的代表性下降，于是提出了 Gentle AdaBoost(牛顿步长法)第二部分 人脸检测2001 年
13、，Paul Viola & Michael Jones 在 ACCEPTED CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION 发表文章：Rapid Object Detection using a Boosted Cascade of Simple Features文章的主要结论：1. Haar特征的提出使AdaBoost进行人脸检测成为可能作者说明使用Haar特征而不是像素点的原因是：特征能包含某些特别领域的信息(encode ad-hoc domain knowledge that is difficult to learn us
14、ing a finite quantity of training data.);此外在Integral提出以后,基于特征的系统的运算速度高于基于像素的系统2. 用于快速Haar特征运算的Integral Image的提出：极大地提高了训练速度和检测速度3. 用于物体检测的AdaBoost方法的提出:Haar特征作为弱分类器判据与Adaboost结合到了一起4. Cascade级联方式的提出：极大地提高了 AdaBoost的检测速度实在是一篇很 NB 的文章,每一个贡献都掷地有声 2002 年, Rainer Lienhart and Jochen Maydt 在 IEEE ICIP 上发表文
15、章An Extended Set of Haar-like Features for Rapid Object Detection.1. 提出了扩展的 Haar 特征,并证明了新的 Haar 特征集提高了检测的能力2. 提出了一种针对已训练完成的AdaBoost的修整程序2002 年, Rainer Lienhart & Alexander Kuranov & Vadim Pisarevsky 在 MRL Technical Report 上发表Empirical Analysis of Detection Cascades of Boosted Classifiers for Rapid Object Detection.1. 提出了训练时进行样本丰富化2. 指出：logitBoost could not be used due to convergence problem on later stages in the cascade training.3. 通过试验得出结论,在人脸检测上 Gentle AdaBoost 的效果要好于 Discrete 和 Real2004 年，Bo WU & Haizhou AI & Chang HUANG & Shihong LAO 在 Computer Soc
