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

文章图片
来源：中国计算机学会（ID：ccfvoice)
本文约2400字，建议阅读5分钟
这篇文章尝试用通俗故事的方式讲述一个机器学习理论中重要问题的探索历程。读者或能从中感受到机器学习理论探索的曲折艰辛，体会到理论进展对算法设计的指引意义。
关键词：机器学习AdaBoost间隔理论Boosting学习理论
溯源
1989年，哈佛大学的莱斯利·维利昂特（LeslieValiant ，计算学习理论奠基人、2010年ACM图灵奖得主）和他的学生迈克尔·肯斯（MichaelKearns ，后来担任贝尔实验室人工智能研究部主任）提出了一个公开问题：“弱可学习性是否等价于强可学习性？”
这个问题大致上是说：如果一个机器学习任务存在着比“随机猜测”略好一点的“弱学习算法” ，那么是否就必然存在着准确率任意高（与该问题的理论上限任意接近）的“强学习算法”？
直觉上这个问题的答案大概是“否定”的，因为我们在现实任务中通常很容易找到比随机猜测稍好一点的算法（比方说准确率达到51%）、却很难找到准确率很高的算法（比方说达到95%）。
出人意料的是， 1990年，麻省理工学院的罗伯特·夏柏尔(RobertSchapire)在著名期刊MachineLearning上发表论文，证明这个问题的答案是“YES”！更令人惊讶的是，他的证明是构造性的！
也就是说，夏柏尔给出了一个过程，直接按这个过程进行操作就能将弱学习算法提升成强学习算法。过程的要点是考虑一系列“基学习器” ，让“后来者”重点关注“先行者”容易出错的部分，然后再将这些基学习器结合起来。
遗憾的是，这个过程仅具备理论意义，并非一个能付诸实践的实用算法，因为它要求知道一些实践中难以事先得知的信息，比方说在解决一个问题之前，先要知道这个问题的最优解有多好。
后来夏柏尔到了新泽西的贝尔实验室工作，在这里遇见加州大学圣塔克鲁兹分校毕业的约夫·弗洛恩德(YoavFreund) 。凑巧的是，弗洛恩德曾经研究过多学习器的结合。两人开始合作。终于，他们在1995年欧洲计算学习理论会议（注：该会议已经并入COLT）发表了一个实用算法，完整版于1997年在JournalofComputerandSystemSciences发表。这就是著名的AdaBoost 。夏柏尔和弗洛恩德因这项工作获2003年“哥德尔奖”、2004年“ACM帕里斯·卡内拉基斯(ParisKanellakis)理论与实践奖” 。

文章图片
AdaBoost的算法流程非常简单，用夏柏尔自己的话说，它仅需“十来行代码(just10linesofcode)” 。但这个算法非常有效，并且经修改推广能应用于诸多类型的任务。例如，在人脸识别领域被誉为“第一个实时人脸检测器”、获得2011年龙格-希金斯(Longuet-Higgins)奖的维奥拉-琼斯(Viola-Jones)检测器就是基于AdaBoost研制的。 AdaBoost后来衍生出一个庞大的算法家族，统称Boosting ，是机器学习中“集成学习”的主流代表性技术。即便在当今这个“深度学习时代” ， Boosting仍发挥着重要作用，例如经常在许多数据分析竞赛中打败深度神经网络而夺魁的XGBoost ，就是Boosting家族中GradientBoost算法的一种高效实现。
我们今天的故事就是关于Boosting学习理论的探索。
异象
机器学习界早就知道，没有任何一个算法能“包打天下”（注：著名的“没有免费的午餐”定理，参见周志华《机器学习》，清华大学出版社2016 ， 1.4节）。因此不仅要对算法进行实验测试，更要进行理论分析，因为有了理论上的清楚刻画，才能明白某个机器学习算法何时能奏效、为什么能奏效，而不是纯粹“碰运气” 。