从2019 AI顶会最佳论文，看深度学习的理论基础

2020 年 2 月 4 日 极市平台

加入极市专业CV交流群，与6000+来自腾讯，华为，百度，北大，清华，中科院等名企名校视觉开发者互动交流！更有机会与李开复老师等大牛群内互动！

同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流。关注 极市平台 公众号，回复 加群，立刻申请入群~

如同物理大时代寻求统一的量子力学，深度学习也许也需要一个统一的理论框架。

如果能有一种理论告诉我们什么样的模型架构、运算方式能最好地表示某种数据，什么样的损失函数、迭代方式能最高效地学习到某种能力，什么样的设置又使这种能力能处理各种意外情况。那么，这样的深度学习，乃至机器学习，才是理论基础圆润的大学科。

令人惊喜的是，我们可以看到近来很多前沿研究都越来越系统，越来越有洞见。最明显的是近年举行的 AI 顶会，我们可以看到很多获奖论文都尝试从更基础、更深刻的角度为 DL 打下地基。本文将从 2019 年人工智能顶会的获奖论文出发，为你介绍深度学习的理论基础到底是什么样的，当前又有哪些新发现。

数学基础 ≠ 理论基础

在入门深度学习的过程中，我们经常会听到各种数学名词，线性代数和矩阵微分、概率论与随机过程，似乎要想理解各种模型，首先必须理解这些数学概念。那么这些数学描述不正是深度学习的「理论基础」吗？

这里我们需要明确的是，数学是一种语言、一种工具，使用它描述深度学习并不一定等于构建 DL 的理论基础。这是一种数学基础，而不是整理领域的理论基础。很多深度模型确实都是从数学推导出发，然后得出某些很好的性质，但这只能说明模型是有理论保证的，它们并不能组成深度学习的理论基础。

比如说图卷积网络或变分自编码器，它们最开始都是从数学的角度推导某些性质，后来才根据这样的性质构建整个模型。我们可以说这些模型的理论基础非常坚实，如果我们需要理解它们，同样也需要对应的数学基础。此外，在实际建模时，我们并不一定完全遵循理论推导，可以稍微修改以获得更强的计算效果。

在深度学习中，有很多模型的数学推导都非常优美。也有很多模型从实验与直观概念出发，描述整个学习过程的数学表达。它们都非常重要，但并不能解决深度学习最基本的疑问： 为什么深度模型能够高效学习？为什么深度模型要比浅层模型的性质好？为什么深度学习泛化性也不错 ？

就像上个世纪初发现各种量子现象与解释，物理大时代艰难地寻求统一的「量子力学」。现在深度学习也有各种非常高效的模型，各种惊艳的结构，我们也许也需要一种统一的底层理论框架。

DL 的理论基础知多少

谈到深度学习的理论基础，可能读者首先想到的就是通用近似定理（Universal approximation theorem），其表示拥有无限神经元的单层前馈网络能逼近紧致实数子集上的任意连续函数。通俗来说， 只要神经元足够多，单层前馈神经网络「有潜力」逼近任意复杂的连续函数 。

在 1989 年提出通用近似定理以来，至少我们有了最基本的一个理论基础，即神经网络有潜力解决各种复杂的现实问题。

MIT 教授 Tomaso Poggio 曾在他的系列研究中 [1] 表示深度学习理论研究可以分为三大类：

表征问题（Representation）：为什么深层网络比浅层网络的表达能力更好？
最优化问题（Optimization）：为什么梯度下降能找到很好的极小值解，好的极小值有什么特点？
泛化问题（Generalization）：为什么过参数化仍然能拥有比较好的泛化性，不过拟合？

对于表征问题，我们想要知道深度神经网络这种「复合函数」，它的表达能力到底怎么确定，它的复合机制又是什么样的。我们不再满足于「能拟合任意函数」这样的定性描述，我们希望知道是不是有一种方法能描述 50 层 ResNet、12 层 Transformer 的拟合能力，能不能清楚地了解它们的理论性质与过程。

有了表征能力，那也只是具备了拟合潜力，深度学习还需要找到一组足够好的极值点，这就是模型的最优解。不同神经网络的「最优化 Landscape」是什么样的、怎样才能找到这种高维复杂函数的优秀极值点、极值点的各种属性都需要完善的理论支持。

最后就是泛化了，深度模型泛化到未知样本的能力直接决定了它的价值。那么深度模型的泛化边界该怎样确定、什么样的极值点又有更好的泛化性能，很多重要的特性都等我们确定一套理论基准。

总而言之，谈到深度学习理论基础，我们总是少不了听到这些关键词：

19 年顶会关于理论的研究

在 2019 年中，我们会看到人工智能顶会选了很多理论性研究作为最佳或杰出论文。它们并不一定是在架构或算法上做出新的贡献，相反，它们很多都希望从数学及理论的角度理解深度学习，理解它的行为与边界。正因为顶尖研究成果更偏向底层，所以我们会发现它们的阅读难度越来越高。

我们查阅了 2019 年 AI 顶会论文的获奖情况，这里我们确定「顶会」主要是根据 CCF 推荐的 A 类会议（人工智能领域），再加上 CCF 没有收录的 ICLR。我们将获奖论文分为偏模型算法与偏理论研究两部分，其中理论研究可能是关于深度学习的理论研究，也可能是模型算法的理论理解。

统计数据可见附录A：https://www.jiqizhixin.com/articles/2020-01-01-20。

一般偏算法或模型的论文，阅读起来还是非常友好的，论文会介绍直观想法、形式化过程及最终结果。但偏理论的论文会要求很多领域知识，尤其是坚实的数学基础。文章后面会具体介绍几项代表性研究，但现在，我们还是先看看整体都是什么样的。

深度学习的理论基础

DL 的理论基础其实还是比较窄的领域，表征、最优化和泛化三大问题也是最重要与基础的方向。在今年的顶会论文中，NeurIPS 2019 的新方向杰出论文 [2] 就特别关注深度学习的泛化问题。

从理论上来说，目前深度学习大多都根据一致性收敛推导出泛化上界，但 CMU 的研究者表示，这种泛化边界是有问题的。研究者通过一系列实验与理论分析，证明不论一致性收敛边界如何精炼，它都不能被证明可解释泛化性。因此由一致性收敛推出的一大族泛化边界都是有问题的。

在 ICLR 2019 最佳论文 [3] 中，MIT 的研究者提出的 Lottery Ticket Hypothesis 非常有意思，它表示如果某些参数在模型中很重要，那么开始训练之前就是重要的。换而言之，神经网络初始化后就有个子网络，训练这个子网络能获得整个网络相近的性能，这样的子结构可以称为 winning tickets。这种特殊子结构，同样展示了神经网络表征能力的新特性。

除此之外，收敛性分析也有新发现，ICML 最佳论文 [4] 就分析了变分高斯过程的收敛率，并提出了计算更便捷的方式。

模型的理论性理解

在理论基础之外，有更多的偏理论研究关注从理论上理解模型算法，并借此提出新的方案。最显著的是 NeurIPS 2018 年最佳论文 ODENet [5] ，它将残差网络理解为常微分方程，从而拥有新的解决思路。在 2019 年的顶会获奖论文中，即使偏算法类研究成果，也会有一些理论性理解，只不过本文关注理论成分更多的研究。

首先 AAAI 最佳论文 [6] 从迭代算法的角度出发解信息不完美博弈，从而进一步构建更强的智能体。这种将复杂游戏抽象为简单博弈问题，并从博弈论的角度出发构建新算法，具有很优秀的理论属性。

在 NeurIPS 2019 的杰出论文 [7] 中，CMU 的研究者从理论上分析了大型损失函数族，探讨 GAN 的损失函数到底怎么样。同样在 ACL 2019 的杰出论文 [8] 中，研究者认为建立自动文本摘要的理论模型能加深我们对任务的理解，也有助于改进文本摘要系统。为此，港科大等研究者对文本摘要的一些概念进行了严格定义，并提出了理论性建模框架。

所有这些顶尖研究成果，都离不开理论的支持，下面我们从理论基础与理论理解，具体介绍新研究都是什么样的。

有问题的泛化性

什么样的模型泛化性比较好？难道测试集上表现好的模型泛化能力真的好吗？

之前很多模型采用在测试集上的误差作为泛化误差，先不管到底有没有「偷窥」测试数据，这种误差也只是一种经验性的指标。深度学习需要从理论上对学习方法的泛化能力进行分析。我们先看看泛化误差的定义是什么样的：

其实上面的表达式并不复杂，它描述的是，泛化误差应该是模型在所有未知数据上的「平均」预测误差，即所有误差的数学期望。注意，我们是无法获取「所有未知数据」的，因此这只是一个定义。

走向衰落的传统泛化理论

之前的理论研究，主要靠分析泛化误差的概率上界来进行，也就是我们常听到的泛化误差上界。传统机器学习会认为，泛化误差上界是样本容量的函数，当样本数增加时，泛化误差上界趋向于 0；同时，泛化误差上界也是模型能力的函数，模型能力越强，它就越难学习，泛化误差上界就越大。

例如大名鼎鼎的传统理论 VC 维，它通过考虑模型函数族的一致性收敛边界，来探讨函数族的表达能力有多强。在 NeurIPS 2019 新方向杰出论文中，研究者表示这种考虑一致性收敛边界的方法，是行不通的。传统泛化误差大致可以表示为如下：

我们认为，测试误差不能超过训练误差再加上某个边界。这个边界随着训练集的增加而减少，随着模型参数量（depth×width）的增加而增加。

但问题在于，传统泛化误差上界并没有考虑深度神经网络「过参数化」这一神奇的现象。并不是说所有参数对最终的预测是起作用的，深度模型存在着大量冗余参数。因此 depth×width 并不能正确描述深度模型的学习难度，过参数化会让学习变得更简单。

现代泛化理论的革新之路

既然传统泛化理论已经不行了，深度学习研究者也就开始探索新的出路。近来的研究者在思考：「我们能不能确定底层的数据分布、算法如何共同约束深度神经网络，从而构建成一种『简单的』函数族。」因此，通过范数约束函数族，也许我们可以将一致性收敛应用到更简洁与准确的边界：

这一类方法看上去非常不同，但本质上仍是一致性收敛的不同表示。在 CMU 的这篇论文中，他们发现，一致性收敛边界实际上并不能全面解释深度学习的泛化问题，我们应该在一致性收敛之上来讨论泛化边界。

一致性收敛到底有什么问题？

首先我们需要确定，机器学习中的一致收敛性，简单来说就是回答「为什么降低训练损失能降低测试损失」这个问题。如果函数族的经验风险能与总体风险一致地收敛，那么这个问题就是可以学习的。

论文 [2] 一作 Vaishnavh Nagarajan 说：「之前的研究大多数都基于一致性收敛考虑泛化边界，但我们的研究表明这类问题很可能是局限的。」目前 Rademacher Complexity、Covering Numbers 和 PAC-Bayes 等众多前沿泛化边界分析都可能存在问题。

Vaishnavh 表示一致性收敛边界会随着参数量的增长而增大，因此这样的边界对于深度网络来说太大了，而且行为也不像真实泛化边界。但也有可能一致性收敛边界会非常紧致，只不过它并不是原始神经网络的边界，很可能是通过模型压缩等技术精炼的新边界。

为了进一步了解为什么一致收敛性不能提供坚实的理论基础，研究者做了很多实验与推导，并最终发现主要问题体现在两方面。

首先，泛化边界竟然随着训练集的增长而增长，这是非常有问题的。因为按照我们的直观理解，当数据集无穷大时，训练误差和测试误差之间差距应该减少到零。Vaishnavh 说： 「即使我们观察到随着数据集的增加，测试误差是正常减少的，但泛化边界却反常地扩大。」

之所以出现这样的问题，在于之前我们通过参数量来度量模型的复杂度，后来修正方法也是通过权重范数来度量复杂度。但问题在于，权重范数会随着数据集的增加而显著增加，并抵消分母数据集的增长速度。「参数依赖性只是泛化问题的一部分，我们同样要特别关注数据集的依赖性」，Vaishnavh 说。

其次对于第二个问题，研究者们调查了所有泛化边界的理论分析，并表示任何一致性收敛边界，不论它们的推导与应用如何严格，它们都不能解释 SGD 训练的神经网络泛化性问题。正如 Vaishnavh 所说，在深度学习中，不论一致性收敛边界如何精炼，它都不能被证明可解释泛化性。

正如上式所示，即使再精炼，一致性收敛边界可能推导出约等于 1，但真实的泛化差距可能接近于 0。这样的结果是非常虚的，它并起不到什么作用。

Vaishnavh 最后表示，在过参数化的深度学习中，决策边界是异常复杂的。如上所示，决策边界在每一个训练数据点上都可能有一些小的弯曲，这种边界会影响一致性收敛，但并不影响泛化性。因此，也许我们需要数学工具来描述深度神经网络复杂的决策边界，需要在一致性收敛之上的一些理论来讨论深度学习。

有些参数生而不平等

深度学习存在很强的过参数化现象，其参数量远远超过了数据量。而且重要的一点是，并不是所有参数都是平等的，有的参数根本不重要，删掉它们也不会有影响。那么为什么会有权重剪枝这些模型压缩方法呢，在 ICLR 2019 最佳论文 [3] 中，MIT 的研究者从底层机制做出理论假设，并通过实验验证这样的假设。

上面表达的是， 如果神经网络完成了随机初始化，那么它就包含了一个子网络。该子网络从头开始训练相同的迭代次数，就能获得与整体网络相媲美的效果 。这样的假设似乎是反直觉的，因为我们一直有一个概念「剪枝后的子网络从头学习肯定效果要差于整体网络」。

但研究者提出这样的新假设，认为只要完成初始化，有效的子结构，也就是「winning tickets」也就确定了。要想确定这样的假设到底真不正确，当然还是需要实验。

实验做起来

因为模型剪枝天生就构建了一个子网络，因此研究者首先验证了这种子网络是不是有效子结构。研究者发现，固定这样的子网络不变，并重新初始化权重，这样训练出来的结果并不能匹配之前的效果。因此，这也证明了初始化对有效子结构的影响。

假设神经网络存在这样的子结构，那么我们通过四步就能找到它。其核心思想是，既然常规的模型剪枝能在删除大量权重的情况下保持准确率基本不变，那么在那种初始化条件下，它就是有效子结构。如果我们保存之前初始化的结果，并采用剪枝后的子结构，那么是不是就能训练达到很好的效果？

具体而言，对于神经网络 f(x; θ)，θ 为初始化的权重。经过训练并剪枝后，我们重新赋予子结构之前的初始化权重，这可以表示为 f(x; m⊙θ)。其中 m 的维度与θ相等，且每一个元素要么是 0 要么是 1，f(x; m⊙θ) 就代表着经过正确初始化的子网络。现在实验分为四大步：

随机初始化神经网络 f(x; θ_0)，其中θ_0 服从于某个分布 D_0；
迭代训练网络 j 次，并获得最优参数θ_j；
剪裁掉θ_j 中的 p% 的参数，从而获得 Mask m；
恢复初始参数θ_0，并创建有效子结构 f(x; m⊙θ_0)。

通过种实验方式，研究者在 MNIST 中找到了全连接网络的「winning tickets」，在 CIFAR-10 中找到了卷积网络的「winning tickets」。这些子网络只有原网络 10-20% 的参数量，但重新训练能获得相近的效果。

VGG-19 在 CIFAR-10 上的测试效果，从左到右分别是迭代 30K、60K、112K 的结果。选自：arXiv:1803.03635。

如上图所示为横轴表示保留的权重，数轴表示准确度，图例展示的是学习率。每一种颜色的实线表示采用「有效初始化」的子网络，而虚线表示随机初始化。通过绿色实线、绿色虚线以及蓝色实线，我们可以明确地看出来研究者找到了「winning tickets」。

研究者表示，这一系列实验都证明了神经网络确实存在高效的子结构，它虽然只是一个假设，但对于进一步的理论研究非常有帮助，尤其是关于最优化与泛化性的理论研究。

硬核的损失函数分析

如果你认为上面那种理论理解在数学上不够优美，那么顶会获奖论文还有一系列严格的数学论证。在 NeurIPS 2019 中，有一篇获奖论文 [7] 分析了名为 Besov IPM 的损失函数族，该函数族包括 L_p 范数距离、总变分距离、Wasserstein 距离、Kolmogorov-Smirnov 距离等众多损失函数。

对于这么一大帮损失函数，研究者分析了它们的上下界，明确了损失函数的选择以及数据假设的相互作用，它们如何决定极小极大过程的最优收敛率。

对于 GAN 来说，如果生成器与判别器函数分别表示为 F 与 P，那么整个 GAN 就可以视为概率分布估计：

如上表达式描述的是，GAN 的这种概率分布估计，可以针对经验分布 P_n tilde 直接最小化经验 IPM 风险。经过一系列复杂的数学分析，研究者得出了三个主要结论：

1. 证明了 IPM 损失函数下分布估计的极小极大收敛率，其下界与上界都是什么样的（定理 4 与定理 5）。对于 IPM 损失函数来说，生成分布

与判别分布

都属于 Besov 空间。研究者的收敛上界主要通过 Donoho[9] 等研究者提出的 wavelet-thresholding 估计器得出，结果显示最优收敛率比之前了解的损失范围要更广。具体而言，如果 M(F, P) 表示极小极大风险，那么对于

有：

2. 定理 7 表明，对于 p』_d ≥ p_g 和 σ_g ≥ D/p_g，在「线性估计器」这一大类概率分布估计器中，没有估计器的收敛率快于：

这种「线性估计器」包括经验分布、核密度估计和最近提出来的正交系列估计器。上面表达式描述的下界表明，在很多情况下，线性估计器都只能实现次优收敛率。

3. 经过正则化后，GAN 可以通过有限大小的生成器与判别器实现极小极大收敛率。作为分离 GAN 与其它非参工具的首批理论结果，它可能可以帮助解释为什么 GAN 在高维数据上能获得这么大的成功。

最后，不论是深度学习真正的理论基础，还是从理论出发构建新方法、新模型，至少在 2019 年的 AI 顶会中，我们很高兴能看到各种前沿研究都在拜托「启发式」的新发现，反而更系统地关注它们的立足基础。也许这些新发现，最终能带领我们构建一个系统的领域、一个成熟的学科。

参考文献：

[1]Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization, arXiv:1908.09375

[2]Uniform convergence may be unable to explain generalization in deep learning, arXiv:1902.04742

[3]The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks, arXiv:1803.03635

[4]Rates of Convergence for Sparse Variational Gaussian Process Regression, arXiv:1903.03571

[5]Neural Ordinary Differential Equations, arXiv:1806.07366

[6]Solving Imperfect-Information Games via Discounted Regret Minimization, arXiv:1809.04040

[7]Nonparametric density estimation & convergence of GANs under Besov IPM losses, arXiv:1902.03511

[8]A Simple Theoretical Model of Importance for Summarization, arXiv:1801.08991

[9]Density estimation by wavelet thresholding, David L Donoho et al.

-END-

*延伸阅读

PS：新年假期，极市将为大家分享计算机视觉顶会 ICCV 2019 大会现场报告系列视频，欢迎前往B站【极市平台】观看，春节也学习，极市不断更，快来打卡点赞吧~

https://www.bilibili.com/video/av83518299

添加极市小助手微信（ID : cv-mart），备注：研究方向-姓名-学校/公司-城市（如：目标检测-小极-北大-深圳），即可申请加入目标检测、目标跟踪、人脸、工业检测、医学影像、三维&SLAM、图像分割等极市技术交流群，更有每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流，一起来让思想之光照的更远吧~