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

有趣的是，统计学习奠基人、支持向量机发明人弗拉基米尔·N.瓦普尼克(VladimirN.Vapnik)在1990年（苏联解体前一年）离开苏联来到新泽西的贝尔实验室工作，夏柏尔和弗洛恩德合作时与瓦普尼克是同事，或许受到了他的影响。
冰封
夏柏尔等人在1998论文结尾说，他们与李奥·布瑞曼(LeoBreiman)进行了“沉痛(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间隔理论体系由此进入“冰封年代” 。研究者纷纷转向其他理论体系，其中最重要的是名著TheElementsofStatisticalLearning作者、斯坦福大学三位大师杰罗姆·弗里德曼(JeromeFriedman)、特莱沃尔·哈斯蒂(TrevorHastie)、罗伯特·提比希阿尼(RobertTibshirani)提出的“统计视角(StatisticalView)”理论。这一派理论也有不少争议，尤其是未能清楚解释AdaBoost为何未发生过拟合。但人们认为至少它“活着”、还可以被改善，而间隔理论体系虽有优美的几何直观解释，但它已经“死了” 。

文章图片
续命
七年后，在2006年国际机器学习大会(ICML)上，在普林斯顿大学任教的夏柏尔与耶鲁大学的学生列夫·芮因(LevReyzin)合作获得了“杰出论文奖” 。获奖论文做了一件事：把布瑞曼1999年的实验重新做一遍。
我们知道， Boosting间隔理论体系除了间隔，必然还会涉及到训练样本数和模型复杂度。要讨论间隔对泛化误差的影响，就必须把训练样本数和模型复杂度“固定”住。前者容易：指定训练样本的个数即可；后者则必须专门处理。
一般认为，决策树模型复杂度由叶结点的数目决定，因此在1999年实验中布瑞曼使用了叶结点数目相同的决策树。芮因和夏柏尔重复了布瑞曼的实验，发现AdaBoost决策树虽然与Arc-gv决策树的叶结点数目相同，但树的层数却更多。因此芮因和夏柏尔推测，这些决策树的复杂度或许不同？