本文译自：http://www.offconvex.org/2018/02/17/generalization2/
译者：欧长坤
正如我们在博客上之前讨论的那样，深度学习有着太多秘密没有被理论解释。最近，许多 ML 理论学者开始对泛化之谜感兴趣：尽管这些网络拥有这比样本的数量更多的参数（经典的过拟合机制）但是为什么训练好的深度网络依然在新数据集上的表现如此优秀？Zhang 等人的《理解深度学习必须重新思考泛化性》一文成功将人们的注意力吸引到了这一富有挑战的问题上。他们的主要实验发现是，如果采用经典的卷积网络体系结构，比如 Alexnet，并在带有随机标签的图像上对其进行训练，那么仍然可以在训练数据上获得非常高的精度（此外，通常的 Regularization 策略则被认为能够提升泛化能力，但没有非常明显的帮助）。显然，训练过的网络是没有办法一直对新图片持续预测随机标签的，也就是说泛化能力不好。而这篇论文表明，在传统机器学习中， Rademacher 复杂度作为描述将分类器与带有随机标签的数据相匹配的工具，但其对样本复杂度并没有任何有意义的限制。我发现这篇论文写得很有意思，尽管这里已经介绍了这篇论文的核心部分，但我还是推荐阅读一下原文，并同时祝贺作者在 ICLR2017 上获得最佳论文奖。
但是，如果我没有在 Simons Institute 2017 年春季学期 做关于 ML 理论的报告，那就是我就太大意了。泛化理论的专家们对这篇论文——尤其是这篇论文的标题感到不满。他们认为，类似的问题已经在更简单的模型（例如 Kernel SVMs）的背景下做过广泛的研究了（说句公道话，那篇论文其实提到了这点），设计具有高 Rademacher 复杂度并在实际数据上训练后的结果表示泛化能力很好的 SVM 架构非常简单。更有甚者还发展了一些理论来解释这种泛化行为（以及类似于 boosting 的相关模型）。于此相关的是，一些 Behnam Neyshabur 及其合著者的几篇早期论文（这篇论文详细介绍了 Behnam 的论文）提出了与 Zhang 等人非常相似的关于深度网络的观点。
无论如何，我们都应该为 Zhang 等人的这篇论文来带的对核心理论关注度感到高兴。确实，Simons 学期学者们非常有激情的讨论自己的小组如何对付这一挑战：这些结果由 [Dzigaite, Roy](Dzigaite and Roy)、Bartlett, Foster 和 Telgarsky 和 Neyshabur, Bhojapalli, MacAallester, Srebro 近期公布。
在详细分析这些结果之前，我先介绍一些由 Zhang 等人论文产生的争议，这些争议是由于目前繁华理论是否是规范性或仅仅是描述性的基础性误解。这些误解来自于课堂里或者课本里关于泛化理论的标准处理手段，正如我在我毕业讨论班上发现的那样。
描述型理论 vs 规范型理论
为了展示他们的不同之处，考虑一个患者对他的主治医生说：『医生，我晚上经常很亢奋，但白天却困得不行』。
医生1（没有任何物理诊断）：『哦，你失眠了』
我将这样的诊断称之为描述型（descriptive），因为它仅仅只是把标签对应到了患者的问题上，而没有给出任何关于如何解决这个问题的看法。相反：
医生2（进行物理诊断之后）：『你的鼻窦导致睡眠时呼吸停止，移除它就可以解决问题。』
这样的诊断就是规范型（prescriptive）的。
描述型还是规范型？
VC 维、Rademacher 复杂性 和 PAC-Bayes 界这些泛化理论的概念都是对泛化能力较差的基本现象给与了规范型的标签。对于当下复杂的 ML 模型而言，它们都难以计算，更不用说作为设计学习系统的指导方针了。
回顾一下一个假设/分类器 $h$ 泛化能力较差的实际意义是什么。假设具有 $m$ 个样本的训练集 $S={(x_1, x_2), …, (x_m, y_m)}$ 服从分布 $D$. 考损失函 $\ell$ 则描述假设 $h$ 对一个数据点的分类好坏程度：$\ell(h, (x,y))$ 较大时，表明假设没有正确的在 $x$ 上产生 $y$，反之则表明有（举个例子，回归问题的损失是 $(h(x)-y)^2$）。现在，令$\Delta_s(h)$ 表示$S$ 上的平均损失，而 $\Delta_D(h)$ 表示分布 $D$ 中样本的期望损失。如果假设 $h$ 在 $S$ 的随机样本下最小化 $\Delta_s(h)$ ，同时在完整分布下获得了非常相似且较低的损失 $\Delta_D(h)$，我们就称训练过程完成了泛化。当泛化失败时，我们有：
泛化不足：$\Delta_S(h) \ll \Delta_{D}(h) $ ………… (1)
在实践中，泛化不足由 $D$ 中大小为 $m$ 的第二类样本进行检查（验证集）$S_2$。而在第二类样本上，$h$ 的期望损失接近于 $\Delta_D(h)$，于是：
$\Delta_S(h) - \Delta_{S_2}(h) \ll 0 $ ………… (2)
描述型泛化理论
我们来简单谈谈 Rademacher 复杂度（或参见我的讲稿）。为了方便起见，我们假设标签和损失为 0 或 1，并且假设泛化能力较差的假设 $h$ 在训练样本 $S$ 上的预测性能很好，同时在测试集 $S_2$ 上的预测完全错误，即：
$\Delta_S(h)-\Delta_{S_2}(h)\approx-1$ …………(3)
Rademacher 复杂度则考虑了如下想法的实验：从 $D$ 中取大小为 $2m$ 的单一样本，并分割为相等的两部分，其中第一部分称为 $S$，第二部分称为 $S_2$。然后翻转$S_2$中的标签（比如-1变成1，1变成-1）并尝试寻找描述新样本最好的分类器 $C$，即意味着最小化 $\Delta_S(h)+1-\Delta_{S_2}(h)$。
翻转一个样本的标签就意味着将最好的分类情况转换为了最坏的情况，反之亦然。正是由于这样， $S_2$ 的损失函数为 1 减之原先损失 $\Delta_{S_2}(h)$，如果这个值很小（比如接近于 0）的概率很大，我们就说分类器具有很高的 Rademacher 复杂度。
但是，公式（3）就暗含了 Rademacher 复杂度很高的情况：这是因为 $D$ 中大小为 $m$ 的随机样本 $S, S_2$ 总大小为 $2m$，当泛化不足时，我成功找到了假设 $h$ 使得 $\Delta_S(h)+1-\Delta_{S_2}(h)$ 非常小。
沿用刚才医疗的例子，换句话说，医生只需了解到『泛化还没发生』就能得出『Rademacher 复杂度很高』的结论。这也就是我称这个结果为描述型的原因。
VC 维的界也是描述型的。VC 维定义为：对于大小为 $k$ 的集合，考虑假设空间中所有可能的分类器，如果标签的序列中每一个标签都给出了样本中的 $k$ 个数据点，那么我们可以找到 0 和 1 构成的所有可能的 $2^k$ 个序列，则 VC 维至少为 $k+1$。
如果泛化如同（2）（3）那样不足，则对于给定的 $\epsilon >0$， VC 维约为 $\epsilon m$。因为对于 $2m$ 个数据点随机分隔为 $S$ 和 $S_2$ 时，存在 $2^{2m}$ 中分隔方法。当泛化误差为 $\Omega(1)$ 时，说明我们可以使用所有可能的分类器得到 $2m$ 个数据点的 $2^{\Omega(m)}$ 个标签。根据 Sauer 引理（见这个主题的讲稿），我们有对于给定的 $\epsilon > 0$，VC 维至少为 $\frac{\epsilon m}{\log{m}}$。
同样的，我们有医生只需了解到『泛化在大小为 $m$ 的样本时尚未开始』，则能够得出结论『VC 维大于 $\Omega(m)$』。
类似的，我们还可以证明 PAC-Bayes 给出的界也是描述型的，细节请看我的课堂讲稿。
为什么学生们会糊涂地认为泛化理论中的这种工具能够提供某种强有力的技术来指导他们设计机器学习算法呢？
答案是，可能是因为讲稿和书本里面的标准展示总是假设我们具有很强的计算能力，并能够计算 VC 维和 Rademacher 复杂度，从而能够得出训练所泛化样本的有意义界。然而这对于以前那些简单的分类器来说是可能的，但对现在我们这种具有百万级变量的分类器（以及反向传播之类的非凸优化技术的组合）来说，太复杂了。
真正的降低复杂学习架构下的 Radmacher 复杂度所提供界的唯一方法是通过训练分类器并通过检验测试集的泛化能力的下降来完成。世界上所有的从业者都这么做了，并且 Zhang 等人获得荣誉也进一步强调了目前的理论在这方面没有任何帮助。
迈向规范型泛化理论
类比现代医学来说，我们可以看到医生至少需要做一次身体检查才能有一个较为规范的诊断。新论文的作者也只管的掌握了这一点，并师徒确定现实生活中深度网络的属性，这能获得更好的泛化能力。这种分析（与『间隔』相关）在十几年前对简单的两层网络进行过，而难点在于寻找类似的多层网络。Bartlett et al. 和 Neyshabur et al. 深入研究了深度网络权重矩阵的稳定秩。这些可以看作是在神经网络文献中被讨论了多年的『flat minimum』的实例。我将介绍我对于这些成果的一些看法和之后的文章中谈到的一些改进。注意，这些方法还没有给出训练有问题的网络所需数据的数量的任何非平凡界。
Dziugaite 和 Roy 走了稍稍不同的路。他们从 McAllester 在 1999年 PAC-Bayes 界出发，得出如果算法在假设集的先验分布为 $P$ 那么在假设集上的每个后验分布 $Q$ （取决于数据），根据 $Q$ 选取的分类器的平均泛化误差上界为：
$E_{h\sim Q}[L_D(h)] - E_{h\sim Q}[L_S(h)] \leq \sqrt{\frac{D(Q||P)+\ln{m/\delta}}{2(m-1)}}$
其中 $D()$ 为 KL 散度。这使得泛化误差的上界（明确的说，在一定数量样本保证下的上界）能够像 Langford 和 Caruana’s 之前的论文所描述的那样进行处理，其中 $P$ 是均匀高斯分布，而 $Q$ 是训练后具有噪声的深度网络（也就是我们想要解释的泛化）。具体来说，如果 $w_{ij}$ 是 ${i,j}$ 的训练后和网络的边权，那么 $Q$ 则由加权高斯噪声 $\eta_{ij}$ 与权 $w_{ij}$ 之和组成。因此，由 $Q$ 产生的随机分类器就是训练好的网络的噪声版本。关键想法是：使用非凸优化来选择 $\eta_{ij}$ 的方差，以平衡两个竞争条件：（1）从 $Q$ 中得出的平均分类器的训练误差不比原始网络多得多（同样，这是最小界的『flatness』的优化后的结果）（2）上述表达式右侧竟可能的小。假设（1）和（2）可以适当的有界，那么来自 $Q$ 的平均分类器对于新数据的泛化能力会非常好。（注意，这种方法只能证明已经训练的分类器的噪声版本的泛化能力）。
将该方法在 MNIST 上使用简单的全连接神经网络，可以证明该方法在 MNIST 数据集上的错误率为 27%（而实际错误率比这个错误率小了 两到三个百分点）。即论文标题所保证的非空泛化界（non-vacuous generalization bounds）。我觉得最有意思的是，他利用非凸优化的方法（利用上面找到的合适的噪声分布 $Q$）来解释关于非凸优化的一个元问题，即深度学习不会过拟合的原因！