深度 | 思考VC维与PAC：如何理解深度神经网络中的泛化理论？

2017 年 12 月 17 日 机器之心

选自offconvex.org

作者：Sanjeev Arora

机器之心编译

参与：Panda

近年来的深度神经网络研究进展往往都重方法而轻理论，但理论研究能够帮助我们更好地理解深度学习成功背后的真正原因，并有望为进一步的研究指明方向。近日，普林斯顿大学计算机科学教授 Sanjeev Arora 发表博文介绍了在深度网络泛化上的理论，机器之心对本文进行了编译介绍。

深度学习的理论还存在诸多神秘之处。近来很多机器学习理论研究者都在关注神秘的泛化（generalization）：为什么训练后的深度网络能在之前并未见过的数据上取得良好的表现，即便它们的自由参数的数量远远超过了数据点的数量（经典的「过拟合」情况）？张驰原等人的论文《理解深度学习需要重新思考泛化（Understanding Deep Learning requires Rethinking Generalization）》为这一难题带来了一些关注。论文地址：https://arxiv.org/abs/1611.03530。他们的主要实验发现是：如果你在带有随机标签的图像上训练一个经典的卷积网络架构（比如 Alexnet），那么你仍然可以在这些训练数据上实现非常高的准确度。（此外，人们认为有助于实现更好的泛化的常见正则化策略其实帮助不大。）不用说，这个训练后的网络之后并不能预测仍未见过的图像的（随机）标签，这就意味着它不能泛化。这篇论文指出将分类器与带有随机标签的数据进行拟合的能力也是机器学习领域内的一种传统方法，该方法被称为 Rademacher 复杂度（后面我们会讨论），因此 Rademacher 复杂度在样本复杂度上并没有有意义的边界。我觉得这篇论文写得很有意思，推荐阅读。该论文获得了 ICLR 2017 最佳论文奖，恭喜作者。

但在 2017 年春季关于理论机器学习的 Simons Institute 课程上，泛化理论专家表达了对这篇论文的不满，尤其是其标题。他们认为相似的问题已经在更简单的模型上得到过广泛的研究了，比如 kernel SVM（核支持向量机）（老实说，这篇论文里也明确提到过）。设计具有很高 Rademacher 复杂度同时又能在真实数据上很好地训练和泛化的支持向量机架构是很简单的。此外，用于解释这种泛化行为的理论也已经得到了发展（而且还适用于 boosting 等相关模型）。在一个相关的说明中，Behnam Neyshabur 及其联合作者的几篇更早期的论文已经提出了与张弛原等人对深度网络的看法相当相似的观点。

但不管这些吐槽抱怨，张弛原等人的论文让人们关注起这个核心的理论难题了，我们应该感到高兴。实际上，在 Simons Institute 课程上的热情讨论者自己也组成了小组来解决这个难题，这带来了多篇论文（其中后两篇出现在了 NIPS' 17 上）：

Dzigaite 和 Roy 的论文《Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data》：https://arxiv.org/abs/1703.11008
Bartlett、Foster 和 Telgarsky 的论文《Spectrally-normalized margin bounds for neural networks》https://arxiv.org/abs/1706.08498
Neyshabur、Bhojapalli、MacAallester 和 Srebro 的论文《A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks》：https://arxiv.org/abs/1707.09564

在解读这些研究结果之前，我先说明一下对张弛原等人论文的标题的部分争议源自一些基本的困惑，即当前的泛化理论是规范性的还是仅仅是描述性的。这些困惑由源自课程和教科书对泛化理论的标准对待方式，我在我的研究生课程上教授最近的进展时也发现了这一点。

规范性理论还是描述性理论

为了阐释两者的差异，假设有一位病人对其医生说：「医生，我晚上常常醒来而且一天都很累。」

医生 1（没有进行任何身体检查）：「哦，你患了失眠症。」

我将这种诊断称为描述性的（descriptive），因为这只是给该病人的问题分配一个标签，而没有给出如何解决该问题的任何见解。与之相反：

医生 2（经过仔细的身体检查后）：「你的鼻窦增生导致睡眠呼吸暂停。移除它可以解决你的问题。」

这样的诊断是规范性的（prescriptive）。

泛化理论：描述性还是规范性？

比如 VC 维、Rademacher 复杂度和 PAC-Bayes 边界等泛化理论概念是为缺乏泛化的基本现象赋予一个描述性标签。对于今天复杂的机器学习模型来说，它们很难计算，更不要说用来指导学习系统的设计了。

想一下如果假设/分类器 h 不能泛化，会意味着什么。假设训练数据是由 m 个样本 S=(x1,y1),(x2,y2),…,(xm,ym) 构成的，这些样本来自于分布 D。损失函数 ℓ描述了假设 h 分类数据点的水平：如果该假设在 x 上不能得到接近的标签 y，那么损失 ℓ(h,(x,y)) 就高；如果接近，则损失就低。（举个例子，回归损失是

，现在我们用表示 S 中样本点的平均损失，用表示在来自分布 D 的样本上的预期损失。如果假设 h 对于随机样本 S 都能得到最小的，并且在全分布上也能实现非常近似的损失，那么这个训练就是泛化的。如果没有得到这样的结果，我们就说：

缺乏泛化：

在实践中，缺乏泛化是通过从 D 中取另一个大小为 m 的样本（「留存集」）S2 来检测的。通过 concentration bounds，h 在这第二个样本上的预期损失近似接近于，让我们可以总结得到：

泛化理论：描述性部分

我们现在讨论 Rademacher 复杂度，本文中的讨论会有所简化。详情可参阅我的课程笔记：https://www.cs.princeton.edu/courses/archive/fall17/cos597A/lecnotes/generalize.pdf。在这里的讨论中，为了方便起见，假设标签和损失是 0 和 1，并且假设泛化能力糟糕的 h 在训练样本 S 上的表现完美但在留存集 S2 上的完全错误，也就是说：

Rademacher 复杂度涉及到下面的思想实验。从 D 中取大小为 2m 的单个样本集，然后将其分成两半，其中一半是 S，另一半是 S2。翻转 S2 中点的标签。现在尝试寻找能最好地描述这些新样本的分类器 C，也就是说最小化

为什么呢？因为翻转点的标签可以将好的分类变成糟糕的分类，或反过来，因此 S2 的损失函数是 1 减去翻转前的损失。如果这个量有很高的概率很小（比如接近于 0），那么我们就说这个分类器的类别的 Rademacher 复杂度高。

但 (3) 式表明 Rademacher 复杂度高的情况是：S、S2 是来自 D 的大小为 m 的随机样本，所以它们的总大小是 2m；当泛化失败时，我们就成功找到了使

非常小的假设 h。

换句话说，继续用医疗的例子类比，医生只需听到「泛化没有发生」就得到结论「Rademacher 复杂度高」。所以我说这个结果是描述性的。

类似地，VC 维边界也是描述性的。如果存在一个大小为 k 的集合使得下面的结果成立，那么 VC 维至少是 k+1。如果我们检查类别中的所有可能的分类器，并且该标签序列中每一个标签都给了样本中的 k 个数据点，那么我们可以找到 0 和 1 构成的所有可能的 2^k 个序列。

如果泛化确实如 (2) 或 (3) 式中那样发生了，那么这就说明对于一些 ϵ>0 而言，VC 维至少是在 ϵm 附近。原因是当将 2m 个数据点随机分割成 S 和 S2 时，存在种分割方式。当泛化错误是 Ω(1) 时，这就说明我们可以使用所有可能的分类器得到 2m 个数据点的个标签。现在可以使用经典的 Sauer 引理（参阅：https://www.cs.princeton.edu/courses/archive/spring14/cos511/scribe_notes/0220.pdf）来证明对于一些常量 ϵ>0，VC 维至少为 ϵm/log m。

因此，再次类比一下，医生只需听到「泛化没有在样本大小为 m 的情况下实现」就得到结论「VC 维高于Ω(m/logm)」。

我们也可以类似地证明 PAC-Bayes 边界也是描述性的，你可以在我的课程笔记中看到：http://www.cs.princeton.edu/courses/archive/fall17/cos597A/lecnotes/generalize.pdf

为什么学生搞不清楚，认为这样的泛化理论工具能为机器学习算法的设计提供一些强有力的技术呢？

答案：也许是因为教学笔记和教科书中的标准演示就像是在假设我们在计算上是万能的——好像我们可以计算 VC 维和 Rademacher 复杂度并因此能在可实现泛化的训练所需的样本规模上达到有意义的边界。尽管之前在使用简单的分类器的时候也许能办到，但现在我们的复杂分类器具有数以百万计的变量，而且这些变量还是反向传播等非凸优化技术的产物。为了降低这种复杂学习架构的 Rademacher 复杂度的边界，实际上唯一的方法是在训练分类器后通过留存集检测泛化的缺乏。这一领域的每个实践者都在这样做（却没有意识到），张弛原等人强调了现在的理论毫无助益，这一点值得称赞。

寻找规范性泛化理论：新论文

在我们的医学类比中，我们看到医生至少需要做一次身体检查才能得到规范性的诊断。这些新论文的作者也直观地把握住了这一点并且试图确定可能实现更好泛化的真实神经网络的性质。几十年前有人在简单的 2 层网络上进行过这样的分析（与「边际（margin）」相关），其中的难点是寻找与多层网络的类比。Bartlett 等人和 Neyshabur 等人都深入研究了深度网络的层的权重举证的稳定秩（stable rank）。这些可被看作是「flat minimum」的一个实例，多年来神经网络方面的文献一直在讨论这个问题。我将在未来的文章中给出我对这些结果的理解和一些改进。注意，这些方法目前还未给出任何有关训练网络所需数据点数量的不寻常的边界。

Dziugaite 和 Roy 选择了稍有不同的方向。他们的工作始于 McAllester 的 1999 PAC-Bayes 边界，也即：如果该算法在假设上的先验分布是 P，那么对于在该假设上的每个后验分布 Q（可能取决于数据），根据 Q 所选择的平均分类器的泛化误差的上界如下，其中 D() 表示 KL 散度：

这使得可以通过 Langford 和 Caruana 之前的论文（(Not) Bounding the True Error）中类似的过程为泛化误差设置上界，其中 P 是均匀高斯，Q 是训练后的深度网络的有噪声版本（我们想要解释它的泛化）。具体来说，如果 w_ij 是该训练后网络中边 i,j 的权重，那么为权重 w_ij 增加高斯噪声 η_ij 就构成了 Q。因此根据 Q 所得到的随机分类器不过是该训练后网络的一个有噪声版本而已。现在我们看到关键了：使用非凸优化来寻找 η_ij 的方差的一个选择，使之能在两个不相容的指标上找到平衡：（a）源自 Q 的平均分类器的训练误差不比原来的训练后的网络多很多（同样，这是通过优化找到的极小值的「平坦度」的量化）；（b）上面表达式的右边尽可能小。假设（a）和（b）都可以适当地确定边界，那么源自 Q 的平均分类器可以在未曾见过的数据上表现得相当好。（注意这种方法只是证明了训练后的分类器的有噪声版本的泛化能力。）

将这种方法应用到在 MNIST 数据集上训练的简单全连接神经网络上，他们可以证明这种方法可在 MNIST 上实现 17% 的误差（实际误差要低得多，在 2% 到 3% 之间）。他们的论文也由此得名，承诺有非空虚（nonvacuous）的泛化边界。对于这个结果，我觉得最有意思的是它使用了非凸优化的能力（在上面被用来寻找一个合适的噪声分布 Q）来阐释有关非凸优化的一个元问题，即深度学习不过拟合的原因是什么。