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

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

王立威

王立威，在北京大学教授主要研究领域为机器学习。在包括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就是一个很典型的例子。但是不要着急，我们慢慢的深入研究它、理解它，我相信对深度学习是一样的，应该在不久的将来，我们从理论上会对深度学习有一个更深刻的认识。

| 算法稳定性

我们接下来谈谈第三个比较重要的学习理论，叫Algorithmic Stability（算法稳定性）。

算法稳定性是什么？

刚刚我们谈到了机器学习理论的发展，从最开始几乎不关心算法，只考虑模型的复杂度，慢慢到Margin，实际上已经和算法有关，而Algorithmic Stability其实完全就是探讨算法性质，我这个算法究竟具备了一个什么样的特点，从而导致我们能够有一个好的泛化能力。

什么叫做Algorithmic Stability呢？我们还是从比较宏观的角度来考虑，细节大家回去以后自己去看。简而言之，怎样的算法是stable的？它的核心是说，当算法用一个训练数据集可以训练出一个结果，假如我的训练数据集有1万个数据，我把其中9999个都保持不变，就把其中的1个数据换成一个新的，那么这个时候你的学习算法学出来的分类器会不会有一个显著的变化？如果没有显著的变化，那么这个学习算法是stable的。如果有显著变化，我们说这个算法是不stable的。

Algorithmic Stability，就是从定量的角度上来刻画以下的关系：当换掉其中一个训练数据时，算法学出来的结果会有多大的改变。

稳定的算法会有更好的泛化能力

大家觉得，是比较stable的算法会有更好的泛化能力呢，还是说一个不stable的算法有比较好的泛化能力呢？从直觉上思考一下，显然是stable的算法有很好的泛化能力。

我还拿最开始的“胡克定律”来说明。如果是一个线性的模型，训练数据更换一个，其实这条直线不会有显著的变化；如果我有100个数据，用99阶多项式来匹配这100个数据，假如把这100个数据换掉一个，我相信新的99阶多项式可能就会发生重大的改变。所以大家要从新的角度，也就是算法的稳定性来刻画。

算法稳定性理论是一个很定量的描述：如果我的算法具有一个什么样的程度的稳定性，那么算法的生成范围就能有什么样的表征，我们就能给出一个数学领域的严谨描述，一个定量的刻画。具体的内容我就跳过去了。

SVM与SGD，算法稳定性如何？

我在讲这个算法稳定性比较新的内容之前，先说一说一些很传统的算法，有一些是稳定性很好的。

举个例子，SVM的稳定性很好。SVM可以从数学上证明，如果换掉其中的一个训练数据，其实你得到的结果通常发生的改变是比较小的，是1/√n的级别，n是数据的量。如果改变一个数据只是1/√n级别的变化，那么它的算法稳定性很好。什么样的算法稳定性很不好呢？比如说以前有一个算法叫决策树（decision tree），假如换掉其中一个数据，有可能决策树就完全变掉了。

所以从这个算法说回今天我们最常用的方法上。今天大家很多人都在用深度学习（Deep Learning），训练深度学习，大家是用什么样的算法在训练Deep Learning呢？最常用的算法就是SGD（随机梯度下降）。我们来问问大家，SGD这个算法究竟是一个stable的算法还是一个不stable的算法？你从直觉上先想一下，梯度下降（GD）是在当前求它的梯度，沿梯度下降的方向走一小步。由于我求GD很费劲，所以我们从随机角度入手，对某一个数据点求一个梯度，这就是一个SGD。

SGD这个算法有没有稳定性呢？这是2016年去年的一个结果（上图），SGD这个算法具有一定的稳定性，如果你在一个convex function上用SGD它的稳定性相当好。通常大家都知道，深度学习的损失函数是非凸的,而仍然可以证明SGD是具有一定的稳定性的，虽然在理论上可能暂时还证明不出来它具有非常高的稳定性，但是它能有一个还不错的稳定性，在实际中它是不是有稳定性？我认为如果是做研究的老师、同学们其实可以去思考这个问题，这个如果做深度学习是一个比较重要的成果。

深度学习算法

接下来我们可以简单地总结一下深度学习算法。很多深度学习做应用的人会觉得，传统的机器学习理论无法解释今天深度学习的成功，因为今天的深度学习在很多方法跟传统的机器学习理论看上去是矛盾的。

我举个例子，今天大家用的这个深度学习的网络，它的VC Dimension是多少？数学上可以证明，如果用全连接的网络，它的VC Dimension基本上就是它的编的数目，可是今天我们用的网络，通常编的数目是我们训练数据要高一个数量级，编的数目就是我们参数的个数，所以实际上我们是在一个什么样的模型中间去学习呢？是在一个VC Dimension大概是10倍于训练数据的空间在做，这跟我们之前提到，你的训练数据 10倍于VC Dimension的空间做，是不一样的。在VC Dimension是训练数据10倍的情况下，如果你用training error最小化这样的简单的算法，是不能指望得到任何好的成果的。所以从我个人的角度来看，深度学习之所以能在VC Dimension是数据量的10倍的复杂度的模型里学习，并且能够取得成功，极大地依赖于SGD的算法。

如果大家设计了一个优化算法，我给你一个数据，给你一个参数个数为训练数据量10倍的网络，而且你找到了全局最优解，我可以负责任地告诉大家，你最后的效果一定是很差的。所以我们今天的深度学习我认为之所以能做好，正是由于它没有找到全局最优解，如果真的能找到，这个性能就坏掉了，或者说必须换成小的网络才有可能。所以SGD这个算法启发大家的一点是，如果从做研究的角度讲，还有没有更好地满足前面讲的方法？

我再谈一点可能跟应用结合更紧密的方面。如果有做深度学习这种实验经验的老师、同学们，不知道大家是怎么做的，反正我的一些学生的经验是这样的：毫无疑问，深度学习的训练是最困难的，经常会发生以下几个现象中的一个或者多个。

• 第一，过拟合。我一训练，training error很快下降了，但是一测试发现，测试数据集和训练数据集的差别巨大，什么原因呢？由于深度学习通常用的网络或者模型是非常复杂的，所以你一旦要在整个模型中找到一个training loss非常低的点，或者说你SGD在走的这条路径当中，实际上算法稳定性是有一定概率意义的，可能你这次走坏了，没走好，实际上stability就不存在了，这是第一种现象。在今天的深度学习中，过拟合还是一个非常常见的现象。
• 第二种，training loss的问题。你训练很长时间就是不降下来，这是什么原因呢？我个人认为，这个原因就是，SGD由于是随机的，实在是没有找到一个loss，能够下降到可接受的点，比如说在很平坦的区域就卡在那儿了，大家看到有很多做深度学习应用的研究者，比如Bengio，给了很多这样的报告，经常出现训练不下降了，是因为你可能陷在一个很平坦的区域，在很大的一个领域里面你的training loss几乎没有什么变化，这个结论是不是真的对？我认为还不一定完全正确，还需要有更多的研究。
• 还有其他一些现象，比如不同的超参数得到的训练结果差异非常大，大家知道深度学习里面有很多超参数要去调，你的这个数不一样，训练的结果完全不一样，所以这些都可以从理论学习的层面去研究，不仅研究，而且希望能够对大家未来能够有一切指导性，就是我如何能够设计这个算法，使其达到最终比较好的目的。如果从学术的角度来讲，这应该也是一个很值得探讨的问题，从应用的角度来讲，对于提高我们训练的效率是很有价值的。

大家可能都知道，如果你是一个做深度学习经验丰富的研究者，和一个刚入门的人，对于同样的问题，即使你拿到同样的代码，其实你想调出同样的结果，需要花的时间差异是巨大的，所以这些方面是很值得深入探讨的一些问题。

关于算法稳定性和SGD具体的算法，为什么它具有稳定性，我想数学上就不用太多讲了，大家可以再思考一下。现在SGD有很多不同优化的算法，你能不能从算法稳定性的角度去想一想，这几种不同的方法谁的stability更好，谁的更差？

其实我认为还是有点区别的，你如果对这些有一个认识，可能不是说直接帮助你解决问题，但它会帮助你加快在训练速度，变成一个很有经验的研究者。还有前面谈到的drop out，从stability的角度探讨一下，它能否对泛化起作用？实际上也是有可能的，我们完全有可能从很多种不同的角度去看待这个问题。

| 关于深度学习算法的一些讨论

最后谈一个学术界很多人都在讨论，特别是深度学习的学术界，大概大家都知道深度学习有三位最有影响的研究者，Hinton、LeCun和Bengio，现在也在研究所谓的深度学习 loss surface。也就是说，我们的目标是想优化学习一个网络，那学习网络过程其实就是在试图将损失最小化，那么我们能不能把loss这个函数，当然是非常非常高维的函数，（你有多少个参数，函数就是多少），我能不能分析一下在这个高维空间中我这个loss function到底长什么样？

有很多人写论文证明loss surface对于深度网络是没有坏的local minima，比如去年的一篇NIPS的oral paper。但是大家特别是做研究的想一想，其实你稍微思考一下应该能明白，这是根本不可能的，显然结论是不正确的。

很简单的例子：你这个网络的最优点，在整个空间里面的数目是非常之大的，因为网络它有很高的对称性。比如说我这样一个网络，我的参数设置是最优，我把这些参数随便做一个置换(permutation)，也是最优，具有这样性质的非凸函数，存在局部极小值。所以loss surface这里面可研究的内容很多，没有现在大家想象的这么简单。

那么，如果大家想做研究开发新的方法，前面我们讲了，一个是现在遇到问题是防止过拟合，还有一种情况是走到一个地方很平坦不下降了，你遇到这种地方怎么让它尽快的跑出来，能够让它下降。

这是从算法稳定性的角度介绍一下我个人认为可以去研究的一些点，对深度学习和泛化、机器学习理论，觉得有趣的点可以研究。

最后总结一下，我觉得我们必须得坦率地承认，我们的学习理论目前为止对深度学习有一个很好的解释，过去的VC理论、Margin Theory，还有算法稳定性等等都不能很完美地解释，虽然算法稳定性我认为有一部分解释了，但是我们应该采取的态度，至少从我的角度来看，不是说就认为学习理论就没有意义了，我觉得还是有意义的，它一定在经过进过更深入研究以后能够帮助我们更好地产生insight,设计出更好的学习算法，也许有一天,深度学习可能不是最好的方法，甚至被淘汰了，我认为这完全是有可能的，但是还会有新的更好的方法。

我的报告就到这里。谢谢大家！

关于王教授及其他教授的主题报告，敬请期待A科技评论的后续报道。