北京大学王立威教授：机器学习理论的回顾与展望（三）

雷锋网［AI科技评论］按：本文根据王立威教授在中国人工智能学会AIDL第二期人工智能前沿讲习班＊机器学习前沿所作报告《机器学习理论：回顾与展望》编辑整理而来，雷锋网在未改变原意的基础上略作了删减。

王立威

王立威，在北京大学教授主要研究领域为机器学习。在包括COLT, NIPS，JMLR, PAMI等权威会议期刊发表论文60余篇。2010年入选 AI’s 10 to Watch，是首位获得该奖项的亚洲学者。2012年获得首届国家自然科学基金优秀青年基金，新世纪优秀人才。任 NIPS 等权威会议 Area Chair，和多家学术期刊编委。以下为王立威教授所做的现场演讲的第三部分，主要阐述了Margin Theory，算法稳定性等相关问题，并对深度学习算法展开了一些讨论。

| Margin Theory介绍

接下来给大家介绍机器学习中第二个比较重要的理论——Margin Theory。

Margin Theory和VC Theory有何区别？

VC Theory和算法关系不大，它刻画的是集合的复杂程度；

Margin Theory则不同，它牵扯到很多算法，后面我介绍的Margin Theory就是完全在刻画算法。所以大家要理解，机器学习理论的发展，是先从刻画一些结构的性质，再逐渐变化到刻画算法本身。

我认为当前，尤其对深度学习来说，最有价值的学习理论一定是在刻画深度学习算法本身的性质。当然你的模型复杂程度也有用，但那可能不是最主要的。

Margin是什么？

Margin Theory大家可能都听说过，像SVM、Boosting这样的方法都包含有Large Margin的概念。它到底是什么含义呢？

Margin Theory在SVM中怎么用大家都比较熟悉了，想象一下：

比如空间中有正负两类点，现在要找一条线把这两类点分开。需要找一种个分法使得这两类点分完了以后，离分类面的间距越大越好，而这个间距就叫Margin。

而对于Boosting来讲，也有类似的概念。我前面也讲到，Boosting就是由许多基本分类器把线性组合起来而得到的一个最终结果。

Margin有什么作用？

比如你组合了100个分类器，你要看这100个分类器里面究竟有多少是把这个数据看成正的点，有多少是看成负的。

• 如果50%判成正的、50%判成负的，实际上这个判别结果对数据就没有Margin，Margin就是0；

• 如果百分之百的判成正的，Margin就非常大。

所以大家可以领会一下，Boosting的Margin实际上体现了这个Boosting所用的基本分类器对数据分类结果的置信度（confidence）。如果百分之百都分成正的这一类，说明这个结果的置信度非常高；如果接近50%，则说明置信度非常低。所以，这个置信度就是用Margin来表示的，它实际上对泛化能力起到了非常重要的影响。

为什么会开始研究Margin Theory？

大家最开始用VC Theory研究Boosting的时候，理论结果肯定是综合越多的基本分类器，泛化效果越差。但实际上实验结果却是，综合了几千个基本分类器之后，泛化性能不仅没有变差，还在不断变好。这看起来就很奇怪，因此也引导人们去思考，不仅要考虑模型的复杂程度，还要考虑算法本身是否也对泛化产生影响。 

从直观上理解：如何用Margin刻画泛化？

Margin既可以对SVM刻画泛化，也可以对Boosting刻画泛化。不过我们先把所有这些理论都忘掉，单纯从直观的角度来思考。

现在大家有这样两种情形大家来比较一下：

• 第一种情形，我现在有一个分类器，它对绝大部分的数据都有一个很大的置信度，要么是全部分成正类，要么全部分成负类。用Margin语言来说，就是对于绝大部分数据Margin都很大；

• 第二种情形，对于绝大部分数据来说Margin都很小，基本上都是只比50%稍微多一点。

这两种分类器虽然差别很大，但是我们假定这两种情况在训练数据上的训练错误率是完全相同的。

训练错误率只能表示把数据分对还是分错了，而置信度实际上则代表了具体分类值的大小。大家想想，在训练错误率完全相同的前提下，是置信度大的更可能有强泛化能力，还是说置信度小的可能性更大？即使从非常直觉的角度，不用通过任何理论你也能知道，一定是置信度大的泛化能力更大。Margin Theory就是把刚才那个很直观的想法建立在精确的数学基础上，再用严密的语言给表述出来。

对数学很感兴趣的同学可以去看里面数学具体的证明；如果对这个没有兴趣的，就理解我刚才讲的。就是说对于分类结果，千万不要只看训练错误率这么一个简单的数字，你要关注Margin。Margin代表了置信度，而置信度对泛化能力有相当重大的作用。

我和周志华老师一起合作过很多工作，特别是在解释Boosting这方面。这大概是将近十年前做的工作。后来周老师和他的学生又做了很多更深入、更精致的一些工作。所以如果大家感兴趣的话可以参阅一下这方面的论文。

| 对Margin Theory的总结

VC Theory是宏观的，它是对问题的一种最简单的表述，只考虑算法对每个数据判对还是判错和模型的复杂程度，用这两点来刻画泛化。

而Margin Theory告诉大家要更关注算法的信息，算法会输出很多置信度方面的信息。

其实在今天的深度学习里面，同样有这个问题: 深度学习最后输出的不光是对错，而是输出了一个实数值，这个值本身含有一定的信息量，这个值的大小在某种程度上其实也反映了置信度的大小。作为研究内容大家可以去探讨一下，这个值对于深度学习的泛化能力有什么样作用。

从Boosting发展历程中，收获了什么启发？

刚才我们讲了Margin Theory对SVM、对Boosting都是适用的，大家还可以探讨一下两者之间的关系。

下面是一个关于Boosting针对具体的Margin理论给出的数学的表达式，这个表达式比较复杂的，最初是由Boosting的提出者Freund和Schapire提出来的。这个里面其实还有很多的故事。

简单说一下这里面的故事。

Boosting其实很有趣，大家如果回顾一下机器学习的发展历史，你会发现历史总是在不断重复的发生。大概在1995、1996年，人们提出了adaBoost算法。这个算法提出来之后大家觉得，怎么这么简单的一个组合就能大幅度提升性能了呢？这看起来就像魔术，像今天的深度学习一样。它的方法其实就是把基本的分类器组合起来。现在没有人能够解释为什么深度学习在实际中就是有这么好的效果，而当年adaBoost算法刚刚出来的时候也是如此。不过很快，adaBoost的提出者Freund和Schapire他们两个人就给出了理论Margin Theory，从数学上证明其原因是Boosting能够得到一个分类器，而它的Margin很大。

但是不久之后，随机森林和bagging的提出者Leo Breiman又提出一个理论，叫Minimum Margin。这个理论在定量方面做得更好，但是在实验结果上却和理论恰好相反——理论上更好的Boosting算法，反倒没有理论上不太好的Boosting算法的实验结果表现得好。所以大家能理解了，这个时候的实验结果和理论预测是完全矛盾的，那到底应该是相信实验还是相信理论呢？这时我们就必须本着实事求是的精神，百分之百的尊重实验结果：肯定是理论上出了什么问题。所以Breiman得出一个结论：Margin Theory肯定是有极大问题的，它不能解释实际的现象。

很多年以后，通过学者们，包括我和周志华老师，在这方面做的一些研究，我们发现这个理论其实并没有问题，问题在于之前的理论在定量的意义上没有做到最好。你把定量做的更加深入、更加精细之后，就会发现Margin的理论和试验观测就统一了。所以Boosting发展历程的故事对我个人的一个启发是，其实有的时候算法的提出是会比理论超前的，adaBoosting就是一个很典型的例子。但是不要着急，我们慢慢的深入研究它、理解它，我相信对深度学习是一样的，应该在不久的将来，我们从理论上会对深度学习有一个更深刻的认识。

关于王教授及其他教授的主题报告，敬请期待雷锋网的后续报道。