论文阅读笔记：Frequency Bias in Neural

作者: 抄书侠 | 来源:发表于2020-05-28 23:10 被阅读0次

两层非均匀分布神经网络NTK的特征函数

我们开始研究从非均匀分布中采样的两层神经网络的NTK模型。首先关注1D目标函数 $y(x):\mathbb{S}^1\rightarrow \mathbb{R}$ 和分片连续数据分布 $p(x)$ ，我们推到了NTK的特征方程和特征向量。这允许我们证明学习频率为 $\kappa$ 一维函数需要 $O\left(\kappa^{2} / p^{*}\right)$ 次迭代，其中 $p^*$ 表示 $p(x)$ 的最小密度。我们用具有更高维度的函数的实验来补充这些理论推导，这表明在 $\mathbb{S}^{d-1}$ 中学习频率为 $\kappa$ 的函数需要 $O\left(\kappa^2/p^*\right)$ 次迭代。

考虑只有第一层被训练的神经网络，NTK模型被表示为
$k\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)=\frac{1}{4 \pi}\left(\mathbf{x}_{i}^{T} \mathbf{x}_{j}+1\right)\left(\pi-\arccos \left(\mathbf{x}_{i}^{T} \mathbf{x}_{j}\right)\right)\quad (5)$
假设n个训练数据是非均匀采样自圆上分片连续分布 $p(x)$ ， $x\in\mathbb{S}^1$ 。我们然后形成一个 $n\times n$ 的矩阵 $H^p$ 其中元素由采样 $x_i,x_j$ 组成的 $H_{ij}^p=k(x_i,x_j)$ 决定， $k$ 由上式定义。Arrora等人2019研究表明GD的收敛速率取决于 $H^p$ 的特征系统。为了分析特征系统，我们考虑 $H^p$ 的极限情况，即点数趋于无穷的时候。在极限的 $H^p$ 特征系统接近核 $k(x_i,x_j)p(x_j)$ 的特征系统，其中特征方程 $f(x)$ 满足如下方程
$\int_{\mathbb{S}^{1}} k\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) p\left(\mathbf{x}_{j}\right) f\left(\mathbf{x}_{j}\right) d \mathbf{x}_{j}=\lambda f\left(\mathbf{x}_{i}\right)\quad(7)$
这是一个homogeneous Fredholm方程的第二类有着非对称极核 $k(x_i,x_j)p(x_j)$ 。有着实特征值的特征函数的存在性建立在核的对称性基础上。令 $\tilde{k}(x_i,x_j)=p^{1/2}(x_i)k(x_i,x_j)p^{1/2}(x_j)$ 和 $g(x)=p^{1/2}f(x)$ 。在上式乘以 $p^{1/2}(x_i)$ 得到
$\int_{\mathbb{S}^{d}} \tilde{k}\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) g\left(\mathbf{x}_{j}\right) d \mathbf{x}_{j}=\lambda g\left(\mathbf{x}_{i}\right)\quad(8)$
特征方程存在且 $\lambda$ 为实数。
进一步我们使用弧度来参数化单位圆，记 $x,z$ 为任意两个角度。我们因此将(7)表示为
$\int_{x-\pi}^{x+\pi} k(x, z) p(z) f(z) d z=\lambda f(x)\quad(9)$
其中(5)中的核用弧度表示为
$k(x, z)=\frac{1}{4 \pi}(\cos (x-z)+1)(\pi-|x-z|)$
$p(x)$ 和 $f(x)$ 都是以 $2\pi$ 为周期的因此 $x$ 依赖于单位圆。

特征方程的表达式

接下来我们解决(9)并导出特征方程 $f(x)$ 的表达式。我们的推导假设 $p(x)$ 是分段连续的。尽管假设局限在我们的界中，但是试验结果表明当 $p(x)$ 连续变化的时候，特征方程也是连续调制的，和我们的解有一致性。我们总结为：
Proposition 1 令 $p(x)$ 是 $\mathbb{S}^1$ 的分片连续的密度函数。那么(9)中特征方程有如下一般形式
$f(x)=a(p(x)) \cos \left(\frac{q}{Z} \Psi(x)+b(p(x))\right)\quad (11)$
其中 $q$ 是整数， $\Psi(x)=\int_{-\pi}^x\sqrt{p(\tilde{x})}d\tilde{x}$ 且 $Z=\frac{1}{2\pi}\Psi(\pi)$

注意如果 $p(x)=p_j$ 在连通区域 $R_j\subset\mathbb{S}^1$ ，那么(11)能被写成
$f(x)=a_{j} \cos \left(\frac{q \sqrt{p_{j}} x}{Z}+b_{j}\right), \forall x \in R_{j}$

换句话说，在区域 $R_j$ 上，有一个余弦函数，频率与 $\sqrt{p_j}$ 成比例。分片连续分布的特征函数如下所示：

image.png
命题的证明依赖于在补充材料中证明的引理，(9)满足如下二阶常微分方程

简而言之，引理通过使用一系列(9)的六阶导来证明，以及一些代数运算，得到的六阶常微分方程。假设分片连续可以简化ODE。然后(13)通过限制有周期，但是这个限制能够通过直接预处理数据来提升，而无须改变需要学习的数据。

(13)式有如下一般解：
$f(x)=A e^{i \frac{\Psi(x)}{\sqrt{\pi \lambda}} x}+B e^{-i \frac{\Psi(x)}{\sqrt{\pi \lambda}} x}$
使得 $\Psi$ 的导数为 $\Psi'(x)=\sqrt{p(x)}$ ，造成实特征方程的形式为
$f(x)=a(p(x)) \cos \left(\frac{\Psi(x)}{\sqrt{\pi \lambda}} x+b(p(x))\right)$

在均匀分布里面，由于周期边界条件，存在可数个特征值，能够使用均匀情况下已知的特征值得到
$\lambda=\left\{\begin{array}{ll} Z^{2}\left(\frac{1}{2 \pi^{2}}+\frac{1}{8}\right) & q=0 \\ Z^{2}\left(\frac{1}{\pi^{2}}+\frac{1}{8}\right) & q=1 \\ \frac{Z^{2}\left(q^{2}+1\right)}{\pi^{2}\left(q^{2}-1\right)^{2}} & q \geq 2 \text { even } \\ \frac{Z^{2}}{\pi^{2} q^{2}} & q \geq 2 \text { odd } \end{array}\right.$
$q$ 是整数，对 $q=0$ 有一个特征方程，且对 $q>0$ 有两个特征函数。

振幅和相移是通过要求特征函数处处连续可微确定的。我们对两个邻域显示了补充材料， $j,j+1$ 成立，如果 $p_{i}\leq p_{j+1}$ 那么强度的比值是对不同值 $p_j$ 和 $p_{j+1}$ 有界的:
$1 \leq \frac{a_{j}}{a_{j+1}} \leq \sqrt{\frac{p_{j+1}}{p_{j}}}$

收敛时间

得到了NTK的特征方程和特征向量允许我们预测学习到目标函数需要的迭代步数并且理解由不同密度带来的影响。为了理解这一点，我们考虑目标函数形式为 $g(x)=\cos(\kappa x)$ 其中 $x$ 从 $\mathbb{S}^1$ 的分段连续分布中采样。记为 $R_j\subset\mathbb{S}^1,1\leq j \leq l$ 为连续密度区域。简略说，对每个区域 $R_j$ 我们期望 $g(x)$ 能够和一个特征方程相关的很好(或许还会有另一个，但是会有更小的能量)。当然，最小密度的区域应当和最小特征值的特征函数相对应。特征值取决于区域的目标频率 $\kappa$ 和密度 $p(x)$ ，将会决定收敛的迭代次数。可以总结为如下定理。

定理1令 $p(x)$ 为 $\mathbb{S}^1$ 上分片连续分布。记 $u^{(t)}(x)$ 为GD迭代 $t$ 次时的神经网络预测值。对任意 $\delta>0$ ，达到 $\|g(x)-u^{(t)}(x)\|<\delta$ 迭代 $t$ 的数量为 $\tilde{O}\left(\kappa^{2} / p_{\alpha}^{*}\right)$ ，其中 $p^*$ 表示 $\mathbb{S}^1$ 中 $p(x)$ 的最小密度, $\tilde{O}(\cdot)$ 隐藏了对数项。

由于一下事实，证明该定理很复杂(1)目标函数的频率或许没有准确被表示在核的特征方程中，由于特征方程的离散数目(2)特征方程限制在给定区域 $R_j$ 上不是正交的。这两个特性或许能造成不可忽略的 $g(x)$ 核小特征值的特征方程的相关性。因此，为了证明定理1我们首先检查 $g(x)$ 投影到小特征值对应的特征方程。随后，我们使用界来证明定理的收敛速度。证明提供在补充材料。

高维

导出从较高维中的非均匀分布得出的数据的解析表达式，即在 $S^{d-1},d>2$ 是有挑战性的留给未来工作。然而，模拟实验让我们推测在 $\mathbb{S}^1$ 成立的主要特性在高维也成立，即(1)分段连续分布的特征方程类似于球谐函数的级联斑块(2)这些谐波频率随着密度变化，并随着各自的特征值变小而单调递增(3)学习频率 $k$ 的谐波函数应当要求 $O(k^d/p^*)$ 次迭代。

深度网络

我们接着把我们对NTK模型讨论拓展到深的全连接神经网络。我们首先证明了NTK的特征向量的确刻画了有限宽高度过参数神经网络的GD收敛性质。我们然后实验研究了NTK的特征向量和特征值从均匀和非均匀分布抽样的数据，并显示了纯正弦和谐波目标函数的收敛。

我们开始显示了NTK特征向量刻画了过参数有限宽全连接神经网络的动力学。我们的理论扩展了Arora的定理4.1，

论文阅读笔记：Frequency Bias in Neural

两层非均匀分布神经网络NTK的特征函数

特征方程的表达式

收敛时间

高维

深度网络

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读