想让AI更安全可靠，从了解算法的泛化能力开始

在新数据中，深度学习系统执行（泛化）能力如何？其性能如何？要想建立AI系统的信赖度和可靠性，必须估计算法的泛化能力。

我们能信任AI吗？AI是否会像人类酗酒一样毫无顾忌？一但AI启动，是否会毁灭世界？

统计学习理论意义何在？

AI系统必须安全可靠，一旦启动AI，算法才能按预期执行。确保AI算法性能良好是提高其采用度和信任度的必由之路 [5]。

此外，决策人在欧盟委员会发布的《可信赖AI的伦理准则》（《ETHICS GUIDELINES FOR TRUSTWORTHY AI》）中明确规定要了解算法的泛化能力。

然而，模型泛化性（泛化理论）研究领域依然投资不足。目前唯一可继续且可行的标准方法是进行数据拆分、验证集和测试集。然而，尽管在无法量化算法的泛化能力时，在测试（留出）集上进行估计不失明智；但这一过程非常棘手，可能发生数据泄漏的风险，需要另外进行独立性假设（独立性验证的参数单独从留出集中选出），但会与p-hacking 等实践所混淆[20]。

什么是泛化？

数据是由潜在的未知分布D生成的，这是上述工作的关键性假设。统计学习并非直接访问分布，而是假定给出了训练样本S，其中S的每个元素均由D生成，并呈独立同分布。学习算法从函数空间（假设类）H中选择函数（假设h），其中H = {f（x，α）}，α是参数向量。

于是，假设h的泛化误差可定义为：从分布D中选取的样本x的预期误差与经验损失（给定样本S上的损失）之间的差值 [4,11]。

我们的任务是给泛化错误设定上限，看究竟会出现多么严重的泛化错误。

传统方法：模型能力

传统泛化理论中，根据假设类H的复杂度（容量）建立泛化能力模型。简单来说，类的“容量”取决于可以在这个类上拟合良好的数据集的数量。类的容量越大，这个类就越灵活，但也越容易过度拟合。[..]容量控制使用的是更加灵活的模型，以获得良好拟合，那些非常灵活但过度拟合的模型则弃之不用[8]。

如何界定假设类H的复杂性？传统泛化理论概念包括VC维、Rademacher复杂度和PAC-Bayes边界。

VC维和死亡神经元

VC（Vapnik-Chervonenkis）维是一种通过评估函数弯曲程度来衡量函数类的复杂度的一种方式，H类的VC维即可以被H打散的最大样本点数目。如果一组样本点都能被函数打散，无论为一组内所有样本点分配什么样的二进制标签，该类样本都可以将其完美分离。[5]

图1 参数数量激增，但测试误差没有骤增[1]

Zhang等人的实验[7]表明，在现实数据中训练的深网真实的“参数复杂度”目前无人知晓，20多年前巴特利特（Bartlett）的VC计算（#节点数*＃层）只是一个粗略设定的上限[ 2]。

死亡神经元的实验数据表明，当网络足够大，并使用非线性激活函数ReLU时，许多权重为零[13]，这一点可能不足为奇。

那么如何估计模型的VC维呢？

PAC可学习性和Rademacher复杂度

PAC（可能近似正确）可学习性的定义很简单，即存在一种算法，对于每个分布D和Є，δ> 0，找到具有概率1-δ的“Є-最优”假设。每个分布都有一个算法的呼声十分强烈，即Rademacher复杂度反而针对特定但未知的分布D而定义。

基于[23]的Rademacher复杂度的草图推导

简而言之，Rademacher复杂度衡量假设类H的能力，以适应随机±1二进制标签。与VC维相比，Rademacher复杂度取决于分布，可用于任何类别的实值函数（不仅是离散值函数）。

正如Bartlett的VC维计算，Rademacher复杂度缺乏有效的深度学习泛化界限。事实上，实验测试表明，许多神经网络用任意标签完美拟合训练集，于是，我们也希望相应模型H的Rademacher复杂度臻于完美。当然，这只是Rademacher复杂度的一个微不足道的上限，在现实环境中得不到有用的泛化界限[7]。

换句话说，理论研究尚未取得有效成果，只能从“炼金术”或一些最佳实践中寻找解决办法。有实践表明：对Rademacher这种复杂学习架构来说，能够真正降低其复杂度的唯一方法是使用训练分类器，并通过留出集检测缺少的泛化。世界上每一位从业者其实无意中已经做到了这一点。张等人的研究（[7]）得出的结论目前在该领域无人超越，获得了认同。

新方法

当今机器学习模型相对复杂，很难用经典的泛化理论进行计算，更不能指导学习系统设计[2]。泛化理论的经典方法只是描述性的，换句话说，如果没有发生泛化，可以通过利用复杂性度量（VC维和Rademacher）进行证明，但没有任何可以规范性原则可以指导实践[ 2]。

此外，实验测试表明，容量接近于无限的假设类可能在实践中运作良好。这不仅适用于深度学习模型，也适用于其他机器学习方法，例如一些带有内核的支持向量机SVM（例如：径向基函数）具有无限的VC维。更简单的线性模型甚至可以欺骗我们，过度参数化线性模型的假设空间可以记忆任何训练数据，并且随着参数的范数任意变大，即使参数任意远离真值参数[12]，该空间也可减少任意接近零（包括零）的训练和测试误差，深度学习极为重视传统的泛化理论方法，哪怕过度参数化很高，或者容量较大（随机标记的数据为零训练误差）[1]，深度网络的一个主要难题还是在于缺少过度拟合。

目前，人们正重新审视复杂度的总体思路。关于深度学习，也出现了许多新颖的泛化方法。

基于范数的容量度量

计算容量度量的途径之一是由间距归一化的权值矩阵的范数度量来查看容量度量。数据样本的输出分类间距是模型分配给正确类别的值减去所有其他类别的最大值的差异。

图2 注意路径范数、从网络输入到输出的所有可能路径的总和、通过每层中的单个神经元[14]

基于范数的测量并不完全依赖模型中的参数数量，因此可能能够更好地表示其容量 的潜力[14]。基于范数的度量可以解释深度神经网络（DNN）的泛化，因为就复杂度而言，在随机标签上训练的模型总是高于在真实标签上训练的模型，由此后者的泛化能力更加有利[14]。

图3 CIFAR10数据上VGG网络（卷积神经网络架构）的不同复杂度度量在所有实验中，学习网络的训练误差均为零。

上图表明这些测量可以解释该泛化，因为随机标签学习模型的复杂度总是高于用真实标签学习模型的复杂度。此外，随着训练集规模的增加[22]，二者复杂度之间的差距也在增加。

与之相关的另一个容量测量是网络的利普希茨常数。利普希茨常数是权值矩阵的谱范数的乘积。谱范数是矩阵的最大奇异值：矩阵可以拉伸一个向量[9]。

利普希茨常数与超额风险相关（测试误差减去训练误差）。然而，尽管风险过高，但这一度量随着时间的推移而增长[4];其增长可以通过利普希茨常数的间距抵消掉，重复抵消可使增长归一化（见图4）

图 4 AlexNet 在 cifar10 上用 SGD 培训 [4]

压缩方法

泛化的基本定理表明，如果训练集具有m个样本，那么定义为训练数据和测试数据误差间差异的泛化误差是sqrt（N'/ m）的量级，其中N'是网络有效参数的数量 [或复杂度度量] [23,24]。

采用具有N个可训练参数的矩阵C，并尝试将其压缩为另一个具有较少参数（N''）的C'和与C大致相同的训练误差。根据泛化基本定理，只要训练样本的数量超过N''，那么C'（压缩网！）就能进行良好的泛化[23,24]。

压缩方法非常具有吸引力。一方面，可以确定DNN的泛化界限。另一方面，能够获得广泛的实践和运营优势：

1. 在生产中使用相对较小（的训练）模型有许多好处，运算速度更快，耗能更低（这一点在移动和嵌入式应用中很重要），并且消耗更少的内存。

2. 最近的研究提出了“彩票假设”的经验证据，随机初始化的密集神经网络包含一个子网络（中奖彩票），该子网被初始化，以便隔离训练。经过训练的子网可以匹配原始网络的测试精度，最多实现相同的迭代次数[16]。采用能够识别获奖门票的训练策略转化为a）更快学习b）更高的测试准确度和c）...;）

除了“彩票票据方法”之外，还有很多其他有趣的网络压缩方法。其中一个非常有吸引力的想法受到了TensorNetworks的启发：“Tensor Train”的概念显示了DNN全连接层的权值矩阵，显示出已经很有希望的实证结果[17]。

尽管这种压缩通常需要重新训练压缩网络，但[25]提供了对网络压缩方法的调查，这是基于[23,24]提供的基本定理和压缩的泛化理论的方法所没有考虑到的地方。

结论

为了保证深度学习算法的可靠性，必须得出有效的（紧密的）泛化界限。对这一问题，传统方法（VC维、Rademacher）未能给出答案，而新的方法尚待研究。

参考文献

[0]https://ec.europa.eu/futurium/en/ai-alliance-consultation/guidelines/1#Robustness

[1] Poggio, Tomaso, et al.“Theory of Deep Learning III: explaining the non-overfitting puzzle.” arXivpreprint arXiv:1801.00173 (2017). [link]

[2] Sanjeev Arora,“Generalization Theory and Deep Nets, An introduction” (2017)

[3] Desh Raj, Introduction toLearning Theory — Part 1 [link]

[4] Bartlett, Peter L., DylanJ. Foster, and Matus J. Telgarsky. “Spectrally-normalized margin bounds forneural networks.” Advances in Neural Information Processing Systems. 2017.

[5] Growing pains — 2018Global CEO Outlook

[6] Jordan Boyd-Graber,Classification: Rademacher Complexity, Machine Learning, Lecture 6.

[7] Zhang, Chiyuan, et al.“Understanding deep learning requires rethinking generalization.” arXivpreprint arXiv:1611.03530 (2016).

[8] Cosma Rohilla Shalizi,Undergraduate Capacity Control, 2012, [link]

[9] Yoshida, Yuichi, andTakeru Miyato. “Spectral norm regularization for improving the generalizabilityof deep learning.” arXiv preprint arXiv:1705.10941 (2017).

[10] Boyd, S., EE263 Lecturenotes (2015), Singular Value Decomposition.

[11] Shawe-Taylor, J. andRivasplata, O., “Statistical Learning Theory: A Hitchhiker’s Guide”, 2012.

[12] Kawaguchi, Kenji, LesliePack Kaelbling, and Yoshua Bengio. “Generalization in deep learning.” arXivpreprint arXiv:1710.05468 (2017).

[13] Vidal, Rene, et al.“Mathematics of deep learning.” arXiv preprint arXiv:1712.04741 (2017).

[14] Jakubovitz, Daniel, RajaGiryes, and Miguel RD Rodrigues. “Generalization error in deep learning.” arXivpreprint arXiv:1808.01174 (2018).

[15] Rob Schapire, COS 511:Theoretical Machine Learning Lecture Notes, Lecture 09.

[16] Frankle, Jonathan, andMichael Carbin. “The lottery ticket hypothesis: Finding sparse, trainableneural networks.” arXiv preprint arXiv:1803.03635 (2018).

[17] Novikov, Alexander, etal. “Tensorizing neural networks.” Advances in neural information processingsystems. 2015.

[18] Zhou, Hattie, et al.“Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask”. UberEngineering blog post. 2019.

[20] Bagnall, Alexander, and GordonStewart. “Certifying the True Error: Machine Learning in Coq with VerifiedGeneralization Guarantees.” (2019).

[21] Neyshabur, Behnam, RyotaTomioka, and Nathan Srebro. “Norm-based capacity control in neural networks.”Conference on Learning Theory. 2015.

[22] Neyshabur, Behnam, et al.“Exploring generalization in deep learning.” Advances in Neural InformationProcessing Systems. 2017.

[23] Belkin, Mikhail, et al.“Reconciling modern machine learning and the bias-variance trade-off.” arXivpreprint arXiv:1812.11118(2018).

[23] Bhaskara, CS 5966/6966:Theory of Machine Learning, Lecture 6

[23] Arora, Sanjeev, et al.“Stronger generalization bounds for deep nets via a compression approach.”arXiv preprint arXiv:1802.05296 (2018).

[24] Arora, Sanjeev, Provinggeneralization of deep nets via compression (2018) .

[25] Cheng, Yu, et al. “Asurvey of model compression and acceleration for deep neural networks.” arXivpreprint arXiv:1710.09282 (2017).