"没有免费午餐定理"加强版_风闻

经典的「没有免费午餐定理」表明：如果某种学习算法在某些方面比另一种学习算法更优，则肯定会在其它某些方面弱于另一种学习算法。

也就是说，对于任何一个学习问题，没有最优的算法，只有最合适的算法。

而在这项最新研究中，作者向我们揭示了这一现象背后的数学原理：每个神经网络，都是一个高维向量。

在高维向量空间中，不存在单调的大小比较。如果两个向量A、B是垂直的，则内积为零，通常也反映两者更加不相关，比如作用在物体运动方向的垂直方向的力就不做功。

类似地，如果两个神经网络对应的向量内积为零，则反映它们的相似程度更低。

在拟合第三个向量C，也就是通过数据进行训练和学习时，如果A和C内积更大，则表示A更容易学习C，也反映B更不容易学习C。

另一方面，当A通过训练变得更加接近C时，与C垂直的另一个神经网络D也会因此和A更加不相关，也就是A变得更加难以学习D。

此即本文提出的「没有免费午餐定理」加强版。

利用这个数学描述，我们就可以量化神经网络的泛化能力。

该研究主要基于宽神经网络，而表示神经网络的高维空间的每一个维度，都是由神经正切核的特征向量构成的。

同时，作者也指出，该发现在宽度较小的网络中也成立。在高维空间中，神经网络泛化性的非单调数学关系一览无余。

复杂社会系统本质上也是高维向量，因此比较不同制度的优越性往往会导致自相矛盾的结论。想靠一种模式解决所有的社会问题是痴人说梦，估计只有元宇宙才能满足这种梦想。

长期以来，探寻神经网络泛化性能的量化方法一直是深度学习研究的核心目标。

尽管深度学习在许多任务上取得了巨大的成功，但是从根本上说，我们还无法很好地解释神经网络学习的函数为什么可以很好地泛化到未曾见过的数据上。

从传统的统计学习理论的直觉出发，过参数化的神经网络难以获得如此好的泛化效果，我们也很难得到有用的泛化界。

因此，研究人员试图寻找一种新的方法来解释神经网络的泛化能力。

近日，加州大学伯克利分校的研究者于 Arxiv 上在线发表了一篇题为「NEURAL TANGENT KERNEL EIGENVALUES ACCURATELY PREDICT GENERALIZATION」的论文，指出「神经正切核」的特征值可以准确地预测神经网络的泛化性能。

「神经正切核」是近年来神经网络优化理论研究的热点概念，研究表明：通过梯度下降以无穷小的步长（也称为梯度流）训练的经过适当随机初始化的足够宽的神经网络，等效于使用称为神经正切核（NTK）的核回归预测器。

在本文中，作者指出：通过研究神经网络的神经正切核的特征系统，我们可以预测该神经网络在学习任意函数时的泛化性能。具体而言，作者提出的理论不仅可以准确地预测测试的均方误差，还可以预测学习到的函数的所有一阶和二阶统计量。

此外，通过使用量化给定目标函数的「可学习性」的度量标准，本文作者提出了一种加强版的**「没有免费午餐定理**」****，该定理指出，对于宽的神经网络而言：提升其对于给定目标函数的泛化性能，必定会弱化其对于正交函数的泛化性能。

最后，作者将本文提出的理论与宽度有限（宽度仅为 20）的网络进行对比，发现本文提出的理论在这些宽度较小的网络中也成立，这表明它不仅适用于标准的 NTK，事实上也能正确预测真实神经网络的泛化性能。

论文地址：https://arxiv.org/pdf/2110.03922.pdf

1

问题定义及研究背景

作者首先将上述问题形式化定义为：从第一性原理出发，对于特定的目标函数，我们是否高效地预测给定的神经网络架构利用有限的个训练样本学习到的函数的泛化性能？

该理论不仅可以解释为什么神经网络在某些函数上可以很好地泛化，而且还可以预测出给定的网络架构适合哪些函数，让我们可以从第一性原理出发为给定的问题挑选最合适的架构。

为此，本文作者进行了一系列近似，他们首先将真实的网络近似为理想化的宽度无限的网络，这与核回归是等价的。接着，作者针对核回归的泛化推导出了新的近似结果。这些近似的方程能够准确预测出原始网络的泛化性能。

本文的研究建立在无限宽网络理论的基础之上。该理论表明，随着网络宽度趋于无穷大，根据类似于中心极限定理的结果，常用的神经网络会有非常简单的解析形式。特别是，采用均方误差（MSE）损失的梯度下降训练的足够宽的网络等价于 NTK 核回归模型。利用这一结论，研究者们研究者们通过对核回归的泛化性能分析将相同的结论推广至了有限宽的网络。

Bordelon 等人于 2020 年发表的 ICML 论文「Spectrum dependent learning curves in kernel regression and wide neural networks」指出，当使用 NTK 作为核时，其表达式可以精准地预测学习任意函数的神经网络的 MSE。我们可以认为，当样本被添加到训练集中时，网络会在越来越大的输入空间中泛化得很好。这个可学习函数的子空间的自然基即为 NTK 的特征基，我们根据其特征值的降序来学习特征函数。

具体而言，本文作者首先形式化定义了目标函数的可学习性，该指标具备 MSE 所不具备的一些理想特性。接着，作者使用可学习性来证明了一个加强版的「没有免费午餐定理」，该定理描述了核对正交基下所有函数的归纳偏置的折中。该定理表明，较高的 NTK 本征模更容易学习，且这些本征模之间在给定的训练集大小下的学习能力存在零和竞争。作者进一步证明，对于任何的核或较宽的网络，这一折中必然会使某些函数的泛化性能差于预期。

2

特征值与特征向量

令A为n阶方阵，若存在数λ和非零向量x，使得Ax=λx，则λ称为A的特征值，x为A对应于特征值λ的特征向量。

图 1：特征值与特征向量的定义

简而言之，由于λ为常量，矩阵A并不改变特征向量的方向，只是对特征向量进行了尺度为λ的伸缩变换：

图 2：特征值与特征向量的几何意义

通过在特征向量为基构成的向量空间中将神经网络重新表示，我们得以将不同初始化的神经网络以及学习后的神经网络进行量化对比。

3

神经正切核

一个前馈神经网络可以代表下面的函数：

其中，θ是一个参数向量。令训练样本为x，目标值为y，测试数据点为x’，假设我们以较小的学习率η执行一步梯度下降，MSE 损失为。则参数会以如下所示的方式更新：

我们希望知道对于测试点而言，参数更新的变化有多大。为此，令θ线性变化，我们得到：

其中，我们将神经正切核 K 定义为：

值得注意的是，随着网络宽度区域无穷大，修正项可以忽略不计，且在任意的随机初始化后，在训练的任何时刻都是相同的，这极大简化了对网络训练的分析。可以证明，在对任意数据集上利用 MSE 损失进行无限时长的训练后，网络学习到的函数可以归纳如下：

4

近似核回归的泛化

为了推导核回归的泛化性，我们将问题简化，仅仅观察核的特征基上的学习问题。我们将核看做线性操作，其特征值/向量对满足：