江苏龙网

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

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


在夏柏尔等人的新理论中 ， AdaBoost的泛化误差界包含一个关于间隔的阈值项θ ， 并且θ出现在分母上；这意味着间隔越大 ， 泛化误差就可能会越小 。 这个理论漂亮地解释了AdaBoost为什么没有发生过拟合：这是因为即便训练误差达到0 ， 间隔仍有可能增大 。 如图4 ， 超平面B已经把两类训练样本点完全分开 ， 其训练误差为0；继续训练可能找到超平面A ， 训练误差仍为0 ， 但是A的间隔比B更大 ， 所以泛化误差可以进一步减小 。
机器之心■周志华：Boosting学习理论的探索——一个跨越30年的故事
本文插图

这项理论在1998年发表 ， 刚好在那一年 ， 多特蒙德大学的托斯腾·约阿希姆斯(Thorsten Joachims)在欧洲机器学习大会上报道了支持向量机在文本分类任务上展现出卓越性能 ， 机器学习领域正式进入“统计学习时代” ， 而“间隔”正是支持向量机的核心概念 。 从间隔的角度来解释AdaBoost的行为 ， 无形中使机器学习的“集成学习”与“统计学习”这两大流派走到了一起 。
有趣的是 ， 统计学习奠基人、支持向量机发明人弗拉基米尔·N.瓦普尼克(Vladimir N. Vapnik)在1990年（苏联解体前一年）离开苏联来到新泽西的贝尔实验室工作 ， 夏柏尔和弗洛恩德合作时与瓦普尼克是同事 ， 或许受到了他的影响 。
冰封
夏柏尔等人在1998论文结尾说 ， 他们与李奥·布瑞曼(Leo Breiman)进行了“沉痛(poignant)”的交流 。 用这个词形容学术交流很少见 。 给他们带来沉痛感的正是被誉为“二十世纪伟大的统计学家”的加州大学伯克利分校的布瑞曼教授 ， 他不仅是统计学领域巨擘 ， 还是机器学习中著名的集成学习方法Bagging和“随机森林”的发明人 。
1999年 ， 布瑞曼的独立署名论文提出了一个新理论 。 这个理论也是基于“间隔”来对AdaBoost进行刻画 ， 但是与夏柏尔等人1998理论不同的是 ， 布瑞曼理论的着眼点是“最小间隔” ， 基于这个间隔物理量 ， 布瑞曼得到了比夏柏尔等人“更紧”的泛化误差界 ， 是Boosting间隔理论体系中一个新的里程碑 。
在学习理论中 ， “更紧的界”通常意味着“更本质的物理量” 。 上一节谈到过 ， “最小间隔”取决于最靠近划分超平面的样本点 ， 而著名的支持向量机就是在努力寻找使得“最小间隔”最大的划分超平面 。 所以 ， 布瑞曼理论揭示出“最小间隔”竟然也是AdaBoost的关键 ， 这使人们感到“醍醐灌顶” 。
到此一切都很美好 ， 只需承认：Boosting间隔理论体系的关键在于“最小间隔”就OK了 。
然而 ， 布瑞曼不仅理论造诣深厚 ， 还是一位热忱的机器学习算法发明者 。 既然证明了“最小间隔”是关键 ， 而AdaBoost跟最小间隔的关联是通过复杂的理论分析才发现的 ， 也就是说 ， AdaBoost并非“直接”优化最小间隔 ， 那么何不发明一个直接优化最小间隔的新型Boosting算法呢？理论上来说这算法应该会比AdaBoost更强大 。
于是 ， 布瑞曼在1999年发明了一个新算法Arc-gv 。 可以从理论上证明 ， 这个算法能够使最小间隔达到最优 。 同时 ， 布瑞曼的大量实验也验证了该算法对应的“最小间隔”总是大于AdaBoost的“最小间隔” 。 然而 ， 实验却显示出Arc-gv的泛化误差大于AdaBoost!
这就奇怪了 。 已经证明了Boosting间隔理论体系的关键是“最小间隔” ， 现在Arc-gv的“最小间隔”无论在理论上还是在实验上都优于AdaBoost ， 那么Arc-gv算法的泛化性能应该更好啊 ， 为什么反倒不如AdaBoost呢？！
证明过程无误 。 这就意味着 ， 把“间隔”作为基石是错误的 。 因此 ， 布瑞曼的工作不啻于宣告了Boosting间隔理论体系的“死刑” 。
Boosting间隔理论体系由此进入“冰封年代” 。 研究者纷纷转向其他理论体系 ， 其中最重要的是名著The Elements of Statistical Learning作者、斯坦福大学三位大师杰罗姆·弗里德曼(Jerome Friedman)、特莱沃尔·哈斯蒂(Trevor Hastie)、罗伯特·提比希阿尼(Robert Tibshirani)提出的“统计视角(Statistical View)”理论 。 这一派理论也有不少争议 ， 尤其是未能清楚解释AdaBoost为何未发生过拟合 。 但人们认为至少它“活着”、还可以被改善 ， 而间隔理论体系虽有优美的几何直观解释 ， 但它已经“死了” 。


推荐阅读


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

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