[品品科技]，一个跨越30年的故事，周志华：Boosting学习理论的探索( 四 ) 来源：中国计算机学会（ID：ccfvoice)

这个发现并不容易，因为这些决策树的高度差并不大。例如，在各自使用300棵决策树时， AdaBoost决策树平均高度约为10.5 ，仅比Arc-gv决策树高了约1层。从大量实验数据中观察到这么小的差别，需要相当敏锐的观察力。

文章图片
芮因和夏柏尔用仅包含2个叶结点的单层决策树（亦称“决策树桩”）作为基学习器重新做了实验。他们发现，虽然Arc-gv的最小间隔始终大于AdaBoost ，但是若考虑样本总体，则AdaBoost的间隔比Arc-gv更大一些。例如从图6中可以看到AdaBoost的曲线更“靠右” ，这意味着有更多的样本点取得较大的间隔值。于是芮因和夏柏尔断言， “最小间隔”并非Boosting间隔理论体系的关键，重要的是间隔的总体分布。他们猜测，或许“间隔均值”或“间隔中位数”是关键物理量，但并未给出理论证明。
一般读者今天看这篇论文或许会感到很诧异：它既没有提出新理论，也没有提出新算法，也没有新应用，这个“三无”论文居然获得了ICML杰出论文奖？
这项工作的意义必须放到Boosting理论探索的整体图景中去考察：它显示出布瑞曼对Boosting间隔理论体系的致命打击，至少其中的实验部分并未“实锤”！
那么，芮因和夏柏尔的工作使Boosting间隔理论体系“活过来了”吗？还没有。因为布瑞曼的主要攻击来自于他的理论结果，实验起的是“验证”作用。因此， Boosting间隔理论体系想逃生，就必须有新理论，基于“最小间隔”之外的间隔物理量证明出比布瑞曼更紧的泛化误差界。
磨砺
2008年，北京大学的王立威博士、封举富教授、杨成同学和后来担任日本RIKEN人工智能研究中心主任的杉山将(MasashiSugiyama)与笔者合作，在COLT会议发表了一篇论文。这篇论文提出了“均衡间隔”的概念，并且基于它证明出一个比布瑞曼更紧的泛化误差界。由于“均衡间隔”不同于最小间隔，因此不少学者以为Boosting理论问题解决了。
然而，笔者心有不安。一方面，在“均衡间隔”理论证明过程中用到的信息与夏柏尔和布瑞曼有所不同，相应的结果未必能直接比较；另一方面，更重要的是， “均衡间隔”是从数学上“强行”定义出来的一个概念，我们说不清它的直观物理含义是什么。
回顾笔者研究Boosting理论问题的初心，是希望通过弄清楚“AdaBoost为何未发生过拟合”来为新的机器学习算法设计获得启发。如果新理论的关键概念缺乏直观物理含义，那么就很难启发算法设计了。因此，笔者继续思考着。
2008年，南开大学组合数学中心的高尉同学（现南京大学人工智能学院副教授）跟笔者联系攻读博士学位，被笔者拽进了AdaBoost问题。当时估计一年应能解决。然而困难超过预期，三年下来仅基于一个走偏的小结果发表了一篇会议论文。博士生毕竟有毕业文章压力，感觉“走投无路”了。笔者内心也很惶惑，但还是必须斗志高昂地鼓劲。幸好笔者手上还有另一个重要理论问题，高尉在这个问题上发表了一篇颇有影响的COLT文章，稍缓解压力，能够继续前行。
几经磨砺，终于在2013年我们在ArtificialIntelligence发表了一个新理论，相应的泛化误差界比夏柏尔和布瑞曼的更紧，这确证了“最小间隔”并非Boosting间隔理论体系的关键物理量。有意思的是，以往认为应该存在“某个”关键的间隔物理量，而我们的新理论揭示出：应该使得“平均间隔”最大化、同时使“间隔方差”最小化，也就是说，关键物理量并非一个，而是两个！
AdaBoost为何未发生过拟合？为何在训练误差达到0之后继续训练仍能获得更好的泛化性能？新理论给出了答案：因为AdaBoost在训练过程中随着轮数的增加，不仅使平均间隔增大，还同时使间隔方差变小。同时，这也意味着AdaBoost最终仍有可能发生过拟合，只不过很迟——当平均间隔已无法再增大、间隔方差也无法进一步减小时。