rambo

Adaboost

周末没上微博,今天一来,发现微博上大家对adaboost进行了热烈的讨论。

讨论源于@老师木 这个神人抛了三个问题,无数大牛争相回答。这三个问题是:
1,adaboost不易过拟合的神话。2,adaboost人脸检测器好用的本质原因,3,真的要求每个弱分类器准确率不低于50%。
关于第一个和第二个问题,包括@ICT山世光  @南大周志华 两位大牛在内的很多同学都给了回答。
其中,第二个问题的答案没有太多的争议,全面讲就是三点,1,基于积分图像和haar特征的特征快速计算;2,基于cascade的结构,克服了样本不均衡的问题,同时使得快速计算成为可能;3,基于特征选择和boosting弱分类器集成算法,得到不太差的检测结果。后续的很多改进工作基本上都是围绕这三点进行的改进。在viola的工作之前,人脸检测的准确率已经比较高,在cmu-mit库上有80%多的检测率,只是检测速度太慢,在几秒量级,无法实用。viola工作的主要贡献是使得人脸检测可以实时处理,从而促进人脸检测的实际使用。从检测效果上看,早期工作中,Schneiderman的基于beyesian和小波的方法是效果最好的,基于nn和svm的方法和adaboost的方法效果也基本相当,或者说稍好。所以,检测率并不是viola的卖点,adaboost受追捧也不是因为其效果好。
关于第一个问题,adaboost首先是存在过拟合的,我觉得不能说adaboost不存在过拟合的问题,只是表现得不是特别严重(比如没有决策树恶化的那么厉害)。在实践中,adaboost的泛化性能远没有svm好。因此,在不需要处理大量feature(比如不需要进行特征选择),对运行速度要求不是特别高(非线性svm的使用速度很慢),对模型大小要求不是很高(svm的非线性模型在feature维度高时模型往往很大)等情况下,建议先考虑svm。adaboost能得到的结论是不断增加弱分类器,训练误差的上界会不断下降,这个是能直接推导得到的结论。adaboost不会过拟合这是个伪命题,肯定是无法证明的。而“adaboost不易过拟合”,这似乎又是一个无法证伪也无法证明的问题,因为这不是一个严谨的结论,无法证明。而adaboost的各种版本中,我知道的泛化能力最好的应该是gentle adaboost,因为其权重更新过程比较gentle,直观理解gentle的求优过程,自然会使得泛化更好。
关于第一个问题,@ICT山世光刚刚指出的“为什么VJ的人脸检测算法过拟合出现晚?直觉上有两个原因: 一是弱分类器非常简单,即使很多融合也不易过拟合,但如果弱分类器太强,则易过拟合;二是就人脸检测而言,实践上训练数据通常极丰富,过拟合更好。”,我深表赞同。这一点上我理解还可以进一步讨论,就是因为adaboost是一个加权弱分类器级联结构,前面的弱分类器是在整体样本上效果较好的,这些弱分类器本身不容易过拟合(可以理解为弱分类少,结构简单,还没有到过拟合的程度),处理了大部分样本的分类问题,而后续不断增加的弱分类器,重点处理的是那些权重大被分错的样本,他们即使过拟合,是对前面被错分样本的过拟合,整体上,还是由前面先选出来的弱分类器保证了整体的泛化能力。此外,每个弱分类器的权重是和加权错误率成反比的,因此,一般后续的弱分类器权重会小,其决定作用的就是前面的弱分类器了。但是如果不断选择更多的弱分类器,后面的弱分类器越来越多时,过拟合就变得不可避免了。
关于第三个问题,老师木说到@heavenfireray 和他想谈的话题之一比较类似(我猜测指的是这一段:“想到我之前一篇文章(aaai)上的构造的toy数据形状,可以构造四个在全局样本上准确率低于31%的基分类器,而ensamble后准确率高于99%。 当然那篇文章跟adaboost无关,是自己弄的一套分片线性模型,但是那四个基分类器搬到adaboost上也完全适用。”)。我猜测,其实这里他玩了一个文字游戏。因为,在adaboost推导过程中,在权重更新时,有个错误率,当错误率超过50%时,模型不再收敛,所以,从表面上看,必须要求被选择作为最优弱分类器的分类错误率不超过50%。但是,细细一想,这里的错误来说是加权错误率,也就是说,这个弱分类器不需要保证在全局数据上错误率不超过50%,只要保证加权错误率不超过50%即可。也正因为这个原因@heavenfireray才能构造全局错误率高于50%,但是集成后能达到99%的分类器。
所以说,adaboost的魂在于其样本权重更新(样本权重模拟了概率分布)和弱分类器加权组合。其样本权重更新保证了前面的弱分类器重点处理普遍情况,而后续的分类器重点处理疑难杂症,最终,弱分类器加权组合保证了前面的普遍情况弱分类器会有更大的权重。这其实有先抓总体,再抓特例的分而治之的思想。
难免有错,供大家讨论批评。
同时,十分期待@老师木 有更惊艳的观点。
http://blog.sina.com.cn/s/blog_6ae183910101chcg.html