江苏龙网

  1. 首页 > 资讯 > 科技 > >

机器之心■周志华：Boosting学习理论的探索——一个跨越30年的故事( 五 )


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

剧终
从1998年AdaBoost间隔理论体系萌生 ， 到几经论争跌宕得到2013年结果 ， 经过了15年 。 再经6年得到该结果的定论 。 如果从故事开头的1989年算起 ， 整整经历了30年 。 故事中的一些主要人物如李奥·布瑞曼已经作古 ， 而当年的研究生已成为教授 。 最后 ， 本文不加解释地列出故事中最主要的三个理论结果以志纪念（见图8） 。
机器之心■周志华：Boosting学习理论的探索——一个跨越30年的故事
本文插图
图8 本文提到的最主要的3个理论结果
参考文献
[1]Zhou Z H. Large margin distribution learning[C]// ANNPR 2014.(keynote article)
[2]Zhang T, Zhou Z H. Optimal margin distribution machine[J]. IEEE Transactions on Knowledge and Data Engineering, DOI:10.1109/TKDE.2019.2897662.


推荐阅读


上一篇：「手机中国」DXOMARK即将公布三星S20 Ultra相机得分 会成第一吗

下一篇：『天极网』新iPhone SE真香 但弃“安”投“苹”确实没啥必要