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

文章图片
希望训练样本多，这容易理解。为什么希望模型复杂度小呢？这是由于机器学习中存在“过拟合” ，简单地说，如果对训练数据学得“太好了” ，反而可能会犯错误。例如图2 ，在学习“树叶”时，如果学习器错误地认为没有锯齿就不是树叶，这就过拟合了。一般认为，产生过拟合的重要原因之一，就是由于模型过于复杂，导致学得“过度”了、学到了本不该学的训练样本的“特性”而非样本总体的“共性” 。

文章图片
显然，夏柏尔和弗洛恩德在1997年的理论蕴义与机器学习领域的常识一致，因此很容易得到大家认可。
然而， AdaBoost在实践中却呈现出一个奇异的现象：它似乎没有发生过拟合！
如图3所示，在训练误差到达0之后继续训练，虽然模型复杂度在增大，但泛化误差却仍会继续下降。
科学发现中有一个基本方法论：若有多个理论假设符合实验观察，则选取最简洁的。这就是所谓“奥卡姆剃刀(Ocama’srazor)准则” 。这个准则在众多学科史上都发挥了重要作用。然而如果审视AdaBoost的行为，却可以发现它是如此与众不同。
如图3中，训练到第10轮和第1000轮时形成的假设（集成学习器）都与“实验观察”（训练数据）一致，前者仅包含10个基学习器、后者包含1000个基学习器。显然，根据奥卡姆剃刀应该选取前者，但实际上后者却更好。

文章图片
也就是说， AdaBoost的行为表现不仅违背了机器学习领域的常识，从更广大的视角看，甚至违背了科学基本准则！
因此，弄清AdaBoost奇异现象背后的道理，不仅能满足我们的好奇心，还可能揭开机器学习中以前不知道的某种秘密，进而为算法设计打开一扇新门。 “AdaBoost为何未发生过拟合？”作为Boosting最关键、最引人入胜的基础理论问题，吸引了诸多知名学者投入其中。
惊蛰
夏柏尔和弗洛恩德很快意识到1997理论中的问题。 1998年，他们与后来领导伯克利著名的西蒙斯计算理论研究所的彼得·巴特莱特(PeterBartlett)和李伟上(WeeSunLee)合作发表了一个新的基于“间隔(margin)”的理论。
“间隔”是机器学习中一个非常重要的概念。大致来说，如图4所示，假定我们用一个划分超平面把不同类别的样本分开，那么某个样本点与超平面的“距离”就是这个样本点相对该超平面的“间隔” 。考虑所有样本点相对这个超平面的“最小间隔” ，就定义出了“超平面的间隔” 。机器学习中著名的支持向量机SVM就是通过优化技术来求解出间隔最大的划分超平面，换一个角度看，就是试图使样本点相对超平面的“最小间隔”尽可能大。
在夏柏尔等人的新理论中， AdaBoost的泛化误差界包含一个关于间隔的阈值项θ ，并且θ出现在分母上；这意味着间隔越大，泛化误差就可能会越小。这个理论漂亮地解释了AdaBoost为什么没有发生过拟合：这是因为即便训练误差达到0 ，间隔仍有可能增大。如图4 ，超平面B已经把两类训练样本点完全分开，其训练误差为0；继续训练可能找到超平面A ，训练误差仍为0 ，但是A的间隔比B更大，所以泛化误差可以进一步减小。

文章图片
这项理论在1998年发表，刚好在那一年，多特蒙德大学的托斯腾·约阿希姆斯(ThorstenJoachims)在欧洲机器学习大会上报道了支持向量机在文本分类任务上展现出卓越性能，机器学习领域正式进入“统计学习时代” ，而“间隔”正是支持向量机的核心概念。从间隔的角度来解释AdaBoost的行为，无形中使机器学习的“集成学习”与“统计学习”这两大流派走到了一起。