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

众所周知，以支持向量机为代表的一大类统计学习方法都在试图最大化“最小间隔” ，而这个新理论揭示：若能最大化“平均间隔”同时最小化“间隔方差” ，得到的学习器会更好！于是，笔者的博士生张腾同学（现华中科技大学计算机学院教师）等开始了这方面的探索。 2014年开始的5年里，我们建立起“最优间隔分布学习机(OptimalmarginDistributionMachine,ODM)”这个新的算法族，包括二分类、多分类、聚类、半监督等学习算法，这些受新理论启发的算法工作不属于本文重点，就不赘述了。
定论
2013年的工作引起了很多反响，如在2014年国际人工智能大会(AAAI)上，国际人工智能学会主席、卡内基梅隆大学机器学习系主任曼纽拉·维罗索(ManuelaVeloso)教授的Keynote报告将它作为人工智能领域的重要进展介绍，称其“使间隔理论复兴(renascence)”“为学习算法设计带来了新洞察(newinsight)” 。
然而，笔者仍有隐忧。虽然2013理论相应的泛化误差界在当时是最紧致的，但今后会不会有人基于其他的间隔物理量获得更紧的界，导致我们关于“AdaBoost为何未发生过拟合”的答案和“最大化平均间隔同时最小化间隔方差”的算法指导思想被推翻呢？
六年后，在2019年底的NeurIPS会议上，丹麦奥胡斯大学的阿兰·格洛隆德(AllanGr?nlund)、卡斯柏·拉森(KasperG.Larsen)、莱尔·卡玛(LiorKamma)、亚历山大·马塞厄森(AlexanderMathiasen)与加州大学伯克利分校的杰拉尼·纳尔逊(JelaniNelson)合作发表了一篇论文（见图7）。纳尔逊是美国总统奖和斯隆研究奖得主，拉森在STOC和FOCS曾两获最佳学生论文奖，是理论计算机科学界的新星，卡玛则毕业于以色列魏兹曼研究所这个计算机科学重镇。理论计算机科学家出手机器学习理论问题，是近年来的一个重要趋势。这篇论文最终证明了2013年我们给出的已经几乎是最紧的泛化误差上界，至多再改进一个log因子，并且这个上界已经与下界匹配，理论上不可能有更好的结果！
终于，心安了。

文章图片
剧终
从1998年AdaBoost间隔理论体系萌生，到几经论争跌宕得到2013年结果，经过了15年。再经6年得到该结果的定论。如果从故事开头的1989年算起，整整经历了30年。故事中的一些主要人物如李奥·布瑞曼已经作古，而当年的研究生已成为教授。最后，本文不加解释地列出故事中最主要的三个理论结果以志纪念（见图8）。

文章图片
图8本文提到的最主要的3个理论结果
参考文献
[1]ZhouZH.Largemargindistributionlearning[C]//ANNPR2014.(keynotearticle)
[2]ZhangT,ZhouZH.Optimalmargindistributionmachine[J].IEEETransactionsonKnowledgeandDataEngineering,DOI:10.1109/TKDE.2019.2897662.
[3]Gr?nlundA,KammaL,LarsenKG,etal.Margin-basedgeneralizationlowerboundsforboostedclassifiers[C]//NeurIPS2019.
注：对理论内容感兴趣的读者可以从[1]中找到主要文献；对ODM算法感兴趣的读者可参阅[2]；[3]是“定论”一节谈到的最新工作。
作者简介

文章图片
周志华
CCF会士、常务理事。南京大学教授、计算机系主任、人工智能学院院长、计算机软件新技术国家重点实验室常务副主任。
ACM/AAAS/AAAI/IEEE/IAPRFellow ，欧洲科学院外籍院士。主要研究方向为人工智能、机器学习、数据挖掘。
zhouzh@nju.edu.cn
编辑：于腾凯
校对：林亦霖
—完—
【[品品科技]，一个跨越30年的故事，周志华：Boosting学习理论的探索】关注清华-青岛数据科学研究院官方微信公众平台“AI数据派”及姊妹号“数据派THU”获取更多讲座福利及优质内容。