关于adaboost的一些浅见

àì夳堔傛蜴生んèń 2022-08-20 15:22 181阅读 0赞

周末没上微博，今天一来，发现微博上大家对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的魂在于其样本权重更新（样本权重模拟了概率分布）和弱分类器加权组合。其样本权重更新保证了前面的弱分类器重点处理普遍情况，而后续的分类器重点处理疑难杂症，最终，弱分类器加权组合保证了前面的普遍情况弱分类器会有更大的权重。这其实有先抓总体，再抓特例的分而治之的思想。

难免有错，供大家讨论批评。

同时，十分期待@老师木有更惊艳的观点。