雷锋网［AI科技评论］按：本文根据王立威教授在中国人工智能学会AIDL第二期人工智能前沿讲习班＊机器学习前沿所作报告《机器学习理论：回顾与展望》编辑整理而来，雷锋网在未改变原意的基础上略作了删减。
王立威
王立威，在北京大学教授主要研究领域为机器学习。在包括COLT, NIPS，JMLR, PAMI等权威会议期刊发表论文60余篇。2010年入选 AI’s 10 to Watch，是首位获得该奖项的亚洲学者。2012年获得首届国家自然科学基金优秀青年基金，新世纪优秀人才。任 NIPS 等权威会议 Area Chair，和多家学术期刊编委。以下为王立威教授所做的现场演讲的第四部分，主要覆盖Algorithmic Stability的介绍。
我们接下来谈谈第三个比较重要的学习理论，叫Algorithmic Stability（算法稳定性）。
刚刚我们谈到了机器学习理论的发展，从最开始几乎不关心算法，只考虑模型的复杂度，慢慢到Margin，实际上已经和算法有关，而Algorithmic Stability其实完全就是探讨算法性质，我这个算法究竟具备了一个什么样的特点，从而导致我们能够有一个好的泛化能力。
什么叫做Algorithmic Stability呢？我们还是从比较宏观的角度来考虑，细节大家回去以后自己去看。简而言之，怎样的算法是stable的？它的核心是说，当算法用一个训练数据集可以训练出一个结果，假如我的训练数据集有1万个数据，我把其中9999个都保持不变，就把其中的1个数据换成一个新的，那么这个时候你的学习算法学出来的分类器会不会有一个显著的变化？如果没有显著的变化，那么这个学习算法是stable的。如果有显著变化，我们说这个算法是不stable的。
Algorithmic Stability，就是从定量的角度上来刻画以下的关系：当换掉其中一个训练数据时，算法学出来的结果会有多大的改变。
大家觉得，是比较stable的算法会有更好的泛化能力呢，还是说一个不stable的算法有比较好的泛化能力呢？从直觉上思考一下，显然是stable的算法有很好的泛化能力。
我还拿最开始的“胡克定律”来说明。如果是一个线性的模型，训练数据更换一个，其实这条直线不会有显著的变化；如果我有100个数据，用99阶多项式来匹配这100个数据，假如把这100个数据换掉一个，我相信新的99阶多项式可能就会发生重大的改变。所以大家要从新的角度，也就是算法的稳定性来刻画。
算法稳定性理论是一个很定量的描述：如果我的算法具有一个什么样的程度的稳定性，那么算法的生成范围就能有什么样的表征，我们就能给出一个数学领域的严谨描述，一个定量的刻画。具体的内容我就跳过去了。
我在讲这个算法稳定性比较新的内容之前，先说一说一些很传统的算法，有一些是稳定性很好的。
举个例子，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,设计出更好的学习算法，也许有一天,深度学习可能不是最好的方法，甚至被淘汰了，我认为这完全是有可能的，但是还会有新的更好的方法。
我的报告就到这里。谢谢大家！
关于王教授及其他教授的主题报告，敬请期待雷锋网的后续报道。
正在生成分享图...
我在思考中