傅里叶特征位置编码详解

起因是在做模式识别与机器视觉布置的论文阅读作业中，一篇微软亚洲研究院的文章：Perceiver: General Perception with Iterative Attention，这篇文章本来是将 Transformer 在多模态数据上的应用的，其原理简单来说就是利用交叉注意力迭代地使用低维的 Latent array 提取高维的 Byte array 的信息，然后进行自注意力计算，这样可以解耦层数和输入的维度，从而可以通过增加网络的深度提高模型能力。

「 」 — ・・・・・・・・・

搞懂 Perceiver 基本架构和思想并不难，但是它们论文中关于使用的位置编码这一段倒是看得我一头雾水，什么是傅里叶特征位置编码？抱着这样的疑问，我到互联网上进行搜索，拜读了一些大牛的文章，勉强是懂了一点，这篇文章就记录一下，并梳理一下思路。

MLP 难以学习高频函数，这种现象被称为谱偏差（spectral bias），神经正切核（Neural Tangent kernel —— NTK）理论认为这是因为标准的基于坐标的 MLP 等价于一个具有高速频率衰减特性的核，导致它们不能够学习到具有高频信息的图像和场景。

谱偏差

谱偏差相关的工作可以参考 18 年的一篇论文：On the Spectral Bias of Neural Networks，这篇论文是 2018 年图灵奖得主 Yoshua Bengio 团队的工作。

谱偏差主要描述的内容就是神经网络会优先学习低频信息，难以学习高频信息。例如对于图片来说，神经网络更容易学习到图像整体的颜色、大致轮廓等信息，但对于图像的纹理和边缘细节等信息则难以学习。同时模型对于高频噪声的鲁棒性较差，这一点很好理解，因为模型在学习高频信息时需要对参数进行调整，这部分参数相当敏感。上面提到的论文主要从傅里叶变换的角度从频域上进行了理论和实验上的验证。

谱偏差的存在并非完全是缺点，它也使得神经网络具有更好的泛化能力，缓解了过拟合现象，同时使得网络对于低频噪声的干扰具有鲁棒性。

关于谱偏差产生的原因，学术界目前有很多种说法，并没有一个确切的结论，其中比较有代表性的就是神经正切核理论。

神经正切核

神经正切核是一种核函数，在深入了解她之前，我们首先介绍核函数的概念。

核函数

如果你学过 SVM 的话，应该知道其中就由提到核函数这一概念，具体来说核函数的定义如下：

设 \(\mathcal{X}\) 是输入空间，\(\mathcal{H}\) 是特征空间，若存在一个从 \(\mathcal{X}\) 至 \(\mathcal{H}\) 的映射：

\[\phi(x): \mathcal{X} \rightarrow \mathcal{H}\]

使得对所有的 \(x, z \in \mathcal{X}\) 函数 \(k(x,z)\) 满足

\[k(x,z) = \langle\phi(x),\phi(z)\rangle\]

其中 \(k(x,z)\) 就是核函数，\(\phi(x)\) 是映射函数，\(\langle\phi(x),\phi(z)\rangle\) 表示两者的内积，核函数的作用是特征映射后求内积，但是并不一定要显示地进行映射。

关于核回归，我在之前的博客《从 RNN 到 Transformer》中讲到了 Nadaraya-Watson 核回归模型，感兴趣的同学可以前去查看。核回归的基本思想就是通过向量在特征空间上的距离来对值进行加权，估计某点处的函数值。

梯度流和动力学方程

这一部分可以参考大佬的文章，这里就不详细写了，只挑重点讲。

如果我们把模型更新的步长视为无限小的话，那么参数的更新可以视作一个梯度流

\[\frac{\partial\theta}{\partial t} = - \nabla _\theta L(\theta)\]

其中 \(\theta\) 是模型的参数，\(L\) 是损失函数

我们定义神经网络的输出 \(f(x,\theta)\) 和目标函数 \(f^*(x)\) 之间的偏差 \(u(t,x)=f(x,\theta)-f^*(x)\)，就可以得到描述误差随训练步数变化的方程，也就是网络训练的动力学方程：

\[\begin{aligned} \partial_{t} u(t, \boldsymbol{x}) & =\partial_{t} f(\boldsymbol{x}, \boldsymbol{\theta}) \\ & =\nabla_{\boldsymbol{\theta}} f(\boldsymbol{x}, \boldsymbol{\theta}) \cdot \partial_{t} \boldsymbol{\theta} \\ & =-\nabla_{\boldsymbol{\theta}} f(\boldsymbol{x}, \boldsymbol{\theta}) \cdot \nabla_{\boldsymbol{\theta}} L \\ & =-\nabla_{\boldsymbol{\theta}} f(\boldsymbol{x}, \boldsymbol{\theta}) \cdot \int_{R^{d}} \frac{\partial \mathbf{Loss}}{\partial f\left(\boldsymbol{x}^{\prime}, \boldsymbol{\theta}\right)} \nabla_{\boldsymbol{\theta}} f\left(\boldsymbol{x}^{\prime}, \boldsymbol{\theta}\right) \rho\left(\boldsymbol{x}^{\prime}\right) \mathrm{d} \boldsymbol{x}^{\prime} \\ & =-\int_{R^{d}} \nabla_{\boldsymbol{\theta}} f(\boldsymbol{x}, \boldsymbol{\theta}) \cdot \nabla_{\boldsymbol{\theta}} f\left(\boldsymbol{x}^{\prime}, \boldsymbol{\theta}\right) \frac{\partial \mathbf{Loss}}{\partial f\left(\boldsymbol{x}^{\prime}, \boldsymbol{\theta}\right)}\rho\left(\boldsymbol{x}^{\prime}\right) \mathrm{d} \boldsymbol{x}^{\prime}\\ &=-\int_{R^{d}} \nabla_{\boldsymbol{\theta}} f(\boldsymbol{x}, \boldsymbol{\theta}) \cdot \nabla_{\boldsymbol{\theta}} f\left(\boldsymbol{x}^{\prime}, \boldsymbol{\theta}\right) u_{\rho}\left(\boldsymbol{x}^{\prime}\right) \mathrm{d} \boldsymbol{x}^{\prime} \end{aligned}\]

我们可以从上面的式子中看到，损失随时间的变化与时间本身是无关的。我们定义核函数：

\[K(\boldsymbol{x},\boldsymbol{x}^{\prime})=\nabla_{\boldsymbol{\theta}} f(\boldsymbol{x}, \boldsymbol{\theta}) \cdot \nabla_{\boldsymbol{\theta}} f\left(\boldsymbol{x}^{\prime}, \boldsymbol{\theta}\right)\]

所以上面的动力学方程可以表示为：

\[\partial_{t} u(t, \boldsymbol{x})=-\int_{R^{d}} K(\boldsymbol{x},\boldsymbol{x}^{\prime}) u_{\rho}\left(\boldsymbol{x}^{\prime}\right) \mathrm{d} \boldsymbol{x}^{\prime}\]

为了将其离散化，我们定义下面的几个式子：

\[K(\boldsymbol{x},\mathcal X)=\left[K\left(\boldsymbol{x}, \boldsymbol{x}_{1}\right), \cdots, K\left(\boldsymbol{x}, \boldsymbol{x}_{n}\right)\right]\] \[u(\mathcal X)= {\left[u\left(\boldsymbol{x}_{1}, \cdots, \boldsymbol{x}_{n}\right)\right]}^{T}\] \[u_L(\mathcal X)=[\frac{\partial \mathbf{Loss}}{\partial f\left(\boldsymbol {x_1}, \boldsymbol{\theta}\right)},\cdots, \frac{\partial \mathbf{Loss}}{\partial f\left(\boldsymbol {x_n}, \boldsymbol{\theta}\right)}]^T\]

将这个网络的动力学方程向量化表示为：

\[\partial_{t} u(t,\boldsymbol x)=-K(\boldsymbol x,\mathcal X) u_L(\mathcal X)\]

我们得到的是一个非线性的一阶微分方程，右式中的 \(K(\boldsymbol x,\mathcal X)\) 是由网络参数结构决定的，\(u_L(\mathcal X)\) 是由数据集决定的，当其等于 0 时，训练结束。

在训练的过程中，神经网络的输入就是数据集，所以我们更进一步，考虑任取样例 \(x\) 的情况，则离散形式的动力学方程可以写成：

\[\partial_{t} u(\mathcal X)=-K(\mathcal X,\mathcal X) u_L(\mathcal X)\]

其中 \(K(\mathcal X,\mathcal X)\) 被称为 Gram Matrix，并且有

\[K_{i_1,i_2}=K(\boldsymbol x_{i_1},\boldsymbol x_{i_2})=\nabla_{\boldsymbol{\theta}} f(\boldsymbol x_{i_1}, \boldsymbol{\theta}) \cdot \nabla_{\boldsymbol{\theta}} f\left(\boldsymbol x_{i_2}, \boldsymbol{\theta}\right)\]

它是神经网络的输出在数据集上关于参数的梯度的外积，假设数据集的大小为 N，则其维度为 \(N*N\)，并且该矩阵是正定矩阵。

无限宽假设下的模型近似

我们假设神经网络隐藏层是无限宽的，则根据强大数定律（？）可以认为 K 趋近于常数矩阵 G，于是 NTK 就是一个不随时间变化的常数矩阵，此时我们可以认为神经网络训练的结果就是使用 NTK 进行核回归的结果。

当 G 矩阵的所有特征值都非负时，该线性微分方程组指数收敛。

谱偏差产生的原因

神经正切核（NTK）理论为解释深度神经网络的谱偏差（即偏向于优先学习低频信息）提供了一个强有力的理论框架。其核心思想在于 NTK 的特征值谱。

以下是 NTK 理论解释谱偏差的几个关键点：

1. NTK 的特征分解：
   • 像任何正定核函数一样，NTK \(\Theta(x, x')\) 也可以进行特征分解。这意味着我们可以找到一组正交的特征函数（或本征函数）\(\phi_k(x)\) 和对应的特征值 \(\lambda_k\)： \(\int \Theta(x, x') \phi_k(x') dx' = \lambda_k \phi_k(x)\)
   • 这些特征函数 \(\phi_k(x)\) 构成了函数空间中的一个基。任何目标函数 \(f^*(x)\) 都可以被分解为这些特征函数的线性组合：\(f^*(x) = \sum_k c_k \phi_k(x)\)。
   • 神经网络在训练过程中，会试图拟合目标函数 \(f^*(x)\) 的各个特征函数分量。
2. 特征值与学习速度：
   • NTK理论的关键结论是，神经网络在梯度下降训练过程中，学习每个特征函数分量 \(\phi_k(x)\) 的速度与其对应的特征值 \(\lambda_k\) 成正比。 更大的特征值意味着更快的收敛速度。
   • 这是因为在梯度流方程中，\(\frac{d f(x; t)}{dt}\) 的变化方向和速度受 \(\Theta(x, x_i)\) 的影响。在特征空间中，这可以被视为每个特征函数方向上的误差衰减速度与对应特征值相关。
3. NTK 特征值谱的“衰减”特性与频率：
   • 对于许多常见的神经网络架构（特别是全连接网络和使用ReLU等激活函数），以及常见的输入数据分布（如均匀分布在超球面或超立方体上），研究发现 NTK 的特征值谱随着特征函数频率的增加而快速衰减。
   • 换句话说，与低频函数（例如，变化缓慢、平滑的函数，对应于傅里叶分解中的低频分量）对应的 NTK 特征值通常较大。
   • 而与高频函数（例如，变化迅速、有尖锐细节的函数）对应的 NTK 特征值则非常小。
4. 解释谱偏差：
   • 由于低频特征函数对应着更大的 NTK 特征值，因此在梯度下降训练过程中，网络会优先且更快地学习这些低频成分。
   • 高频特征函数由于其对应的 NTK 特征值很小，所以它们的学习速度会非常慢，甚至可能在有限的训练时间内无法被充分学习。
   • 这种现象就解释了为什么神经网络会表现出“谱偏差”：它们本质上被偏向于学习低频信息，这是因为 NTK 的内在结构决定了对不同频率分量的学习效率不同。

总结来说，NTK 理论解释谱偏差的核心逻辑链条是：

神经网络训练 \(\xrightarrow{\text{NTK 理论}}\) 类似核回归 \(\xrightarrow{\text{核的特征分解}}\) 不同特征函数分量有不同特征值 \(\xrightarrow{\text{NTK 特征值谱特性}}\) 低频特征函数对应大特征值 \(\xrightarrow{\text{学习速度与特征值正相关}}\) 低频信息优先且更快被学习 \(\implies\) 谱偏差。

理解这一点对于设计更有效的神经网络架构（例如，通过改变激活函数或引入傅里叶特征来改变 NTK 的谱），或者理解神经网络在不同任务上的泛化行为都非常重要。

参考文献

Understanding the Neural Tangent Kernel

深度学习理论之Neural Tangent Kernel第一讲：介绍和文献总结

Neural Tangent Kernel （NTK）基础推导

这里列出的参考文献其实很多我自己都没有看，只是在搜集资料时看到的，如果后续想深入了解的话，可以参考一下

傅里叶特征

前面我们花了大量篇幅讲解什么是谱偏差，以及介绍了其产生的一种解释——神经正切核理论。在实际计算 NTK 的的时候，我们往往通过先对向量做内积，再计算梯度（即内积和梯度计算交换顺序）的方式进行。综合上面的论述，这里我们只需要考虑两点：

1. 神经网络的最终效果可以使用核回归估算，而核回归衡量的是两个输入之间的距离
2. 核回归衡量的两个输入之间的距离是由这两个向量之间的内积结果决定的

为了能够让神经网络更好地学习到高频信息，首先我们需要引入平移不变性的概念。什么是平移不变性的，就是神经网络的学习只与输入的相对位置关系有关系，例如我的输入是 (1, A),(2, B),(3, C) 以及 (11, A),(12, B),(13, C)，我希望神经网络接受根据这些输入学习到的结果是一致的。

为了实现这样平移不变性，我们可以建立如下的位置编码：

\[\gamma (v)=[a_1\cos(2\pi b_1 v), a_1\sin(2\pi b_1 v),\ldots, a_m\cos(2\pi b_m v),a_m\sin(2\pi b_m v)]^T.\]

其中 \(a_i\) 是系数，\(b\in R^{m \times 2}\) 是一个投影矩阵，输入是二维坐标 \(v\in [0,1)^d\)，位置编码的长度为 2m

由于 NTK 只取决于输入之间的内积，而任意两个位置编码之间的内积结果为

\[\gamma(v_1)^T\gamma(v_2)=[a_1^2\cos(2\pi b_1^T(v_1-v_2))+\ldots]\]

可以看到上式完全取决于两个输入之间的相对距离 \(v_1 - v_2\)，所以神经网络的结果只取决于输入的相对距离，具有平移不变性。

当 MLP 满足了平移不变性之后，我们就能够手动调整 NTK 的带宽了，从而调整神经网络对不同频率信息的学习能力，提高 MLP 学习高频信息的能力。

那么我们该如何调整 NTK 的带宽呢？根据上面的表达式，我们可以通过调整 b 的值实现，并且如果我们令 \(b_j = j\) 的话，就有下面的式子：

\[\gamma(v_1)^T\gamma(v_2)=\sum_{j=1}^{m} a_j^2\cos(2\pi j(v_1-v_2))\]

上面的这个式子和离散傅里叶变换的式子接近，式中 \(j\) 较大的项就表示 NTK 的高频分量，通过修改前面的系数 \(a_j\) 来手动调整 NTK 的频域特征。位置编码其实就是在模拟傅里叶变换，所以作者把她成为傅里叶特征。

傅里叶特征的长度要和输入的值一样，但由于正余弦函数的参数对应，所以实际上 m 的值只要一半即可。但即便是这样，也会导致 m 的值过大，带来很多计算负担，例如一个 256 * 256 的图像，就需要 256 * 128 个频率。有没有什么方法可以避免使用如此多的频率，只关注需要关注的部分呢？有的兄弟，有的。

之前的研究 Random features for large-scale kernel machines 表明，我们不需要密集地采样傅里叶特征，稀疏地采样同样可行。具体来说，我们可以从某个具体的分布中采样，实验表明结果和采样的分布类型无关，主要和分布的标准差有关，因为其决定了傅里叶特征的带宽，也决定了网络拟合高频信息的能力。

总结

这一部分的研究内容很理论，有一大堆公式推导，似乎有很多应用数学领域的研究者在做，不得不佩服研究者的数学功底之深厚，从这种视角来解释神经网络真是太精妙了！