江苏龙网

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

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


机器之心■周志华：Boosting学习理论的探索——一个跨越30年的故事
本文插图

续命
七年后 ， 在2006年国际机器学习大会(ICML)上 ， 在普林斯顿大学任教的夏柏尔与耶鲁大学的学生列夫·芮因(Lev Reyzin)合作获得了“杰出论文奖” 。 获奖论文做了一件事：把布瑞曼 1999年的实验重新做一遍 。
我们知道 ， Boosting间隔理论体系除了间隔 ， 必然还会涉及到训练样本数和模型复杂度 。 要讨论间隔对泛化误差的影响 ， 就必须把训练样本数和模型复杂度“固定”住 。 前者容易：指定训练样本的个数即可；后者则必须专门处理 。
一般认为 ， 决策树模型复杂度由叶结点的数目决定 ， 因此在1999年实验中布瑞曼使用了叶结点数目相同的决策树 。 芮因和夏柏尔重复了布瑞曼的实验 ， 发现AdaBoost决策树虽然与Arc-gv决策树的叶结点数目相同 ， 但树的层数却更多 。 因此芮因和夏柏尔推测 ， 这些决策树的复杂度或许不同？
这个发现并不容易 ， 因为这些决策树的高度差并不大 。 例如 ， 在各自使用300棵决策树时 ， AdaBoost决策树平均高度约为10.5 ， 仅比Arc-gv决策树高了约1层 。 从大量实验数据中观察到这么小的差别 ， 需要相当敏锐的观察力 。
机器之心■周志华：Boosting学习理论的探索——一个跨越30年的故事
本文插图

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


推荐阅读


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

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