关于Boosting算法的一点思考

早上起床看到朋友圈很多同学在转发南大周志华老师的这篇文章 《Boosting学习理论的探索 —— 一个跨越30年的故事》，文章主要是讨论了过去多年来对Adaboost理论分析的一系列工作与思路。周老师文章写得挺好的。我这里斗胆给一些自己的看法。

我一直认为boosting系列的算法是统计学习方法非常有意思的一个家族：发展至今已经有了相对完善的理论体系;参数往往不需要多少调优就可以在绝大多数场景下得到很强的一个baseline（往往需要做深度学习的同行花非常大的力气才有可能超越）;更有意思的是可以感受到boosting这一系列方法与其他机器学习方法有着很不一样的看待问题的思维，这种思维带来了大量对学习方法的insight。当然还有其他有趣的地方，这里就不再赘述了。

当然，boosting也有明显的缺点。最大的缺点之一就是boosting无法做online learning，而这在许多场景（如广告，推荐等）中是至关重要的。这个缺点也是为什么facebook当年要在gbdt后面接一个logistic regression的原因。还有一个明显缺点是gbdt在极大规模且稀疏的特征集（同样是推荐、广告中常见的情况）上会有明显的性能下降，甚至有时候不如粗暴的logistics。这个原因有很多，这里就不展开讲了（留作习题给有余力的读者）。不过瑕不掩瑜，boosting方法无疑问是机器学习史上的一颗明珠。

出于对boosting的喜欢与看重，我在蔡老师的新机器学习课程中也专门增加了这部分的作业，主要是让同学们去实现一个Adaboost，并探索为何多层的决策树以及其他强学习器作为Adaboost的基学习器的效果会不如直接用decision stump。这个探索实际上就对应了这篇文章中提到的icml paper以及其他一些相应工作的结论。除此以外，出于对gbdt的偏爱，我还出了一个证明题，让同学们探索并证明Adaboost与gbdt的关系。注意这个问题在李航的《统计学习方法》中有提到，但是他给出的论断是错误的或者至少是不完整的。那么正确的结论是什么呢？（同样留作习题）

再斗胆发表一些与周老师文章不同的观点。首先，我想学术界早期并没有认为Adaboost不会过拟合。Adaboost自然是会过拟合的，只是这个过拟合会来得比较晚一些，有时候要在训练误差达到很低之后很久才会过拟合。但是只要基学习器的数量设置得够多，这个过拟合是很容易观察到的。我出的作业里也有这一部分的设计。而gbdt的过拟合之容易就更不必去提了，为此xgboost中设计了大约有几十种缓解过拟合的方式（我的作业里同样要求同学对其中最常用的几个进行实现与讨论）。adaboost中有意思的现象是为何这个过拟合会来得比其它学习方法更晚，而这个原因也在周老师的文章中提到了，这里就不再赘述。另外我觉得文中对布瑞曼（Breiman）的工作的讨论有失公平。Beriman的Arc-gv效果不如adaboost，并不能说明间隔（margin）作为boost学习基石是错误的;恰恰相反，后人的所有研究都证明margin是一个非常正确关键且深刻的insight。Arc-gv不work的原因除了icml那篇paper中提到的实验setting问题以外，还有一个重要原因是最小间隔min-margin推出来的bound太松了（学过统计学习理论的同学应该都懂），这其实也是adaboost第一个理论分析的结论不能解释adaboost特殊现象的原因。而后人的工作（包括周老师自己的）本质上就是在追寻基于其他与margin相关的统计/物理量的更紧的bound的证明。当然，我想周老师也是为了追求文章的浅显易懂与跌宕起伏的感觉，所以才故意这么去写。不过我这里还是补充几句，以免一些刚入行的同学真的误解了。

最后，我们能从这个故事中学到什么呢？这个跨越30年的故事是有其研究主线的。我想其中最值得关注的是：1. adaboost中有趣的现象引起大家的思考与探索 2. 漂亮的min-margin导出的Arc-gv不work推动着大家思考原因，并探寻其他基于margin更紧的bound。这给我们一些启示。1. 研究/工程中碰到的奇异现象往往可能包含着重要的insight，往往是很好的问题，也许会带来很好的研究。2. 绝大多数人的研究不是孤立的，而是对已有工作中存在问题的思考与探索解决。

另外很有意思的一点是，周老师果然是不放过任何diss deep learning的机会：“因此不仅要对算法进行实验测试，更要进行理论分析，因为有了理论上的清楚刻画，才能明白某个机器学习算法何时能奏效、为什么能奏效，而不是纯粹“碰运气” ”。至于这个观点是否正确，我想大家也可以有自己的思考。实际上现在有巨大量的实验科学（包括深度学习），我想只要实验做得够完善，效果又确实出众，那么很多时候就是可以抓老鼠的好猫。就算没有对应理论，从实验中也可以大致知道什么时候work、why work，而不是“纯粹碰运气”。当然，对理论的追求也是合理且必要的，只是也许没必要“万般为下品，唯有理论高吧”。

最后的最后，有同学提到了dl research的现状，我也分享一下自己对现在这方面的看法。首先，不管是黑猫白猫，能抓到老鼠就是好猫：dl确实有诸多缺点，但毫无疑问它也是有极大的价值的，是ml史上的里程碑之一。其次，改善鱼龙混杂的research现状需要大家共同努力。倒不是说反对大家灌水，我觉得灌水也是有一些价值的，而且大家都要吃饭的嘛。不过我还是希望大家尽量不发有造假实验结果的文章;尽量不发为了中paper而故意给出误导甚至是错误claim的文章;不要为了增加自己文章的“novelty”而故意不去cite。然后大家当reviewer的时候也可以认真一些，同时尽量拒绝别人来走关系…我作为reviewer也承诺会认真对待每一篇paper。再次，鱼龙混杂的现状更需要大家有critical thinking的能力。最后，追寻真理的道路是漫长又充满艰难险阻的，往往需要一代人甚至几代人的努力。dl或者说ml research的现状不算特别令人满意，但我相信这只是暂时的，我们终会走过这个时期，迎来更光明的未来。引用周老师文章中提到的Beriman那篇论文中的一句话作为收尾：So if the F-S explanation is only a partial answer, then where are we? 我想目前所有的dl research最多都是个partial answer。Where are we? We are still on the road. 共勉。