adaboost的一些说明.docVIP

adaboost的一些说明~~~~~~~~~` 2008-11-27 01:14 上学期拿出一部分时间来做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较好,但是没有前者的比较来得明显.文献中记录的.M1算法初始1.获得一组样本(X)和它的分类(Y)和一个分类器(weaklearn).2.赋予平均的权值分布D(i)进入循环:T次1. 赋予弱分类器权值D(i),使用弱分类器获得样本(X)到分类(Y)上的一个映射.(就是把某个X归到某个Y类中去)2. 计算这个映射的误差e.e=各个归类错误的样本权值之和.如果e1/2那么弱分类器训练失败,挑出循环,训练结束(这在二值检测中是不会发生的,而多值的情况就要看分类器够不够强健了)3. 设B = e / ( 1 - e ).用于调整权值.因为e1/2.因此0B14. 如果某样本分类正确,该样本的权值就乘以B让权值变小;如果分类错误,就让该样本的权值乘以B^-1或者不变,这样就让分类正确的样本权值降低,分类错误的样本权值升高,加强了对较难分类样本的分类能力5. 权值均衡化循环结束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. 求每个样本的权值,即每个样本所有不正确的分类的权值和,再求每个样本错误分类的权值,即不正确分类的权值除以该样本的权值.最后将每个样本的权值归一化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 Cascades of Boosted Clas