初始
1.获得一组样本(X)和它的分类(Y)和一个分类器(weaklearn).
2.赋予平均的权值分布D(i)
进入循环:T次
1. 赋予弱分类器权值D(i),使用弱分类器获得样本(X)到分类(Y)上的一个映射.(就是把某个X归到某个Y类中去)
2. 计算这个映射的误差e.e=各个归类错误的样本权值之和.如果e>1/2那么弱分类器训练失败,挑出循环,训练结束(这在二值检测中是不会发生的,而多值的情况就要看分类器够不够强健了)
3. 设B = e / ( 1 - e ).用于调整权值.因为e<1/2.因此0<B<1
4. 如果某样本分类正确,该样本的权值就乘以B让权值变小;如果分类错误,就让该样本的权值乘以B^-1或者不变,这样就让分类正确的样本权值降低,分类错误的样本权值升高,加强了对较难分类样本的分类能力
5. 权值均衡化
循环结束
1. 最终的分类器是,当一个X进入时,遍历所有Y,寻找使(h(x)=y的情况下,log(1/B)之和)最大者即是输出分类y
M2相比于M1的改进是允许弱分类器输出多个分类结果,并输出这几个分类结果的可能性(注意,这里不是概率)
.M2的流程是
1.获得一组样本(X)和它的分类(Y)和一个分类器(weaklearn).
2.对于某个样本Xi将它的分类归为一个正确分类Yi和其他不正确分类Yb
3.样本权值进行如下分布首先每个样本分到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 Classifiers for Rapid Object Detection中提出在stump弱分类器(即每个弱分类器使用一个特征进行分类)上进行的对比试验中,Gentle的结果明显好于Real和Discrete.大牛已经做出试验了,我就不怀疑它了.
和上篇论文流程大体相同.作者还讨论了alpha(t)的取法:
算法去看文章吧...这里不能直接贴图
文献中记录的AdaBoost.MH算法
算法的运算流程:
1. 得到一组样本(m个)和样本相应的分类,这个分类是由K个是和否的标签组成.某一个样本可以有多个是标签.
2. 均分权值:1/mk
进入循环:
1. 由弱分类器获得各样本针对各标签的是或否结果(给出离散值或连续值)
2. 获得alpha（t）
3. 调整权值.大概是,弱分类器判断l标签的是或否,若判断正确乘以1,错误乘以-1,再乘以 ,然后blablabla…
4. 权值归一化
跳出循环
输出强分类器
1998年Jerome Friedman & Trevor Hastie & Robert Tibshirani发表文章Additive Logistic Regression: a Statistical View of Boosting
一些重要的结论:
Bagging是一个纯粹的降低相关度的方法,如果树的节点具有很高的相关性,bagging就会有好的结果
1.早期的AdaBoost在第二步的时候采用重采样方法,即使某些样本权重增加.这种方法与bagging存在某种关联,它也是Boost的成功之处中降低相关度方面的重要部分.
2.在第二步中如果使用加权的tree-growing算法,而不是重采样算法,效果会更好. This removes the randomization component essential in bagging
3.使用stumps作为弱分类器
Logit和Gentle算法的提出过程大致是这样的
1. 验证Boosting algorithms是一种拟合一个additive logistic regression model(加性的逻辑回归模型)的阶段式估计过程.它有最优一个指数判据,这个判据由第二定理与二项式对数似然判据是等价的.
2. 作者证明Discrete是使用adaptive Newton updates拟合一个additive logistic regression 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年代兴起的逻辑回归的寻优方法中提炼出了LogitBoost(我终于找到logitBoost的logic了)
自适应的牛顿法,拟合加性logistic回归模型
1. 获得样本,(x,y)序列.将分类y*=(y+1)/2
2. 设置初值,F(x)=0,p(xi)=1/2
进入循环
1. 依式计算zi,wi.
2. 通过加权最小二乘的方式拟合函数fm(x).由zi拟合xi,权重为wi
3. 更新F(x),p(x)
退出循环
输出分类器sign[F(x)].
作者提出,logitAdaBoost在每一轮中都使Ee^(-y(F(x)+f(x)))最优,会使训练样本的代表性下降,于是提出了Gentle AdaBoost(牛顿步长法)
第二部分 人脸检测
2001年,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 using a finite quantity of training data.);此外在Integral提出以后,基于特征的系统的运算速度高于基于像素的系统
