返回论文笔记资料库
arXiv 2021ICLR 2022模型合并论文笔记

Permutation Invariance

大胆假设

原始论文

The Role of Permutation Invariance in Linear Mode Connectivity of Neural Networks

论文作者

Rahim Entezari · Hanie Sedghi · Olga Saukh · Behnam Neyshabur

发表版本
ICLR 2022会议
arXiv 首次提交
arXiv:2110.06296
引用此论文 · BibTeX

引用信息对应所链接的论文版本,作者为原论文作者。

@misc{modelmergingpermutationinvariance2021,
  title = {{The Role of Permutation Invariance in Linear Mode Connectivity of Neural Networks}},
  author = {Rahim Entezari and Hanie Sedghi and Olga Saukh and Behnam Neyshabur},
  year = {2021},
  eprint = {2110.06296},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.06296}
}
本页内容

损失地形的研究,在 2018 年前后告诉我们一件奇怪的事。

两个从不同随机初始化训练出来的网络,中间可以找到一条弯曲的低损失路径;可是直接连一条直线,损失还是会在中间冲高。弯路走得通,直线却过不去。

TU Graz 与 Google 的 Entezari、Sedghi、Saukh 与 Neyshabur 想到一个可能的原因。神经网络的隐藏单元没有固定顺序,把同一层的神经元换个位置,网络算出来的函数完全一样,参数向量却变成另一个点。两个网络在直线上撞墙,也许只是因为它们的神经元「排错了位置」。

他们把这个想法写成一个猜想,并且直接承认它很大胆。

定义问题

障碍怎么量

令 L(θ)L(\theta) 是网络在某组参数下的损失(例如训练误差)。两组参数 θ1\theta_1、θ2\theta_2 之间的线性插值障碍定义为

B(θ1,θ2)=sup⁡α∈[0,1][L(αθ1+(1−α)θ2)]−[αL(θ1)+(1−α)L(θ2)]B(\theta_1,\theta_2) = \sup_{\alpha\in[0,1]}\Big[L\big(\alpha\theta_1+(1-\alpha)\theta_2\big)\Big] - \Big[\alpha L(\theta_1)+(1-\alpha)L(\theta_2)\Big]

第一项是插值模型的损失,第二项是两端损失的线性插值。两者相减,量的是「比直线预期多出来的那一截」。

这和 Frankle 等人的定义略有不同。Frankle 用两端损失的平均 0.5L(θ1)+0.5L(θ2)0.5L(\theta_1)+0.5L(\theta_2) 当基准;两端损失相等时两种定义一样,不相等时,这个版本不会把「损失从一端线性变到另一端」也算成障碍。

B≈0B\approx0 时,就说两个网络线性模式连通(linear mode connectivity, LMC)。作者在实验中发现,只在 α=12\alpha=\tfrac12 量一次,和取整条路径的上确界差距小于 10−410^{-4},所以之后的图都只报中点的值。

先看障碍跟什么有关

在提出猜想前,作者先做了一轮普查。架构有单层 MLP、两层卷积的 Shallow CNN、VGG 与 ResNet,数据集有 MNIST、SVHN、CIFAR-10、CIFAR-100。每个设置训练 10 个不同种子的模型,取 5 组随机配对测量训练误差的障碍。

  1. 宽度:障碍先随宽度上升,到了某个宽度又开始下降,形状很像 double descent。作者对照测试误差,发现障碍的峰值大约落在模型刚好能拟合训练数据的宽度。简单的数据集(MNIST、SVHN)比 CIFAR 更早开始下降。
  2. 深度:MLP 和 Shallow CNN 固定每层宽度 2102^{10},每多加一层,障碍就明显变高。VGG 和 ResNet 的障碍一直卡在很高的位置,不随宽度改变。
  3. 任务难度:MLP 在 MNIST 上的障碍只有 0.0174,到 CIFAR-100 是 0.7965;Shallow CNN 从 0.0161 到 0.4861。浅层网络的障碍和测试误差高度正相关。ResNet18 和 VGG16 在四个数据集上都在 0.84 到 0.99 之间,测试误差低,障碍却很高。

普查的结论是,宽可以降低障碍,深会提高障碍。这些现象需要一个解释。

解决问题

两种不变性

一个网络经过某种变换后,表示的函数不变,就说网络对这个变换具有不变性。常见的有两种。

第一种是 ReLU 的正齐次性。把某个神经元的输入权重乘上 c>0c>0、输出权重除以 cc,函数不变。作者认为这种不变性不重要,因为 SGD 的隐式偏好会让各层权重的大小趋于平衡,收敛到特定的缩放方式。

第二种是排列不变性。把第 ii 层的隐藏单元重新排列,参数变成

Wi  →  Pi Wi Pi−1⊤W_i \;\to\; P_i\,W_i\,P_{i-1}^{\top}

其中 PiP_i 是排列矩阵,输入层与输出层不排列。PiP_i 调换这一层输出的顺序,Pi−1⊤P_{i-1}^{\top} 把前一层的排列抵消回来。对 SGD 来说,每一种排列出现的概率都一样,所以排列对损失地形的影响值得认真看。

用一个单隐藏层网络来确认这件事。隐藏层有 hh 个单元,把第一层权重的行、偏置,以及第二层权重的列,用同一个排列一起重排:

python
def permute(params, p):
    W1, b1, W2, b2 = params        # W1: [h, d], b1: [h], W2: [10, h], b2: [10]
    return [W1[p], b1[p], W2[:, p], b2]

在本文后面的小实验中,对宽度 16、64、256 的网络各做一次随机排列,torch.allclose 比较排列前后在整个数据集上的输出,三次都返回 True。函数一模一样,但在参数空间里,它们是相隔很远的两个点。

宽度 hh 的一层就有 h!h! 种排法。同一个函数,在参数空间里有天文数字般的分身。

猜想

作者的猜想用大白话来说是这样的:

大多数 SGD 的解都属于一个集合 SS;只要对 SS 里的元素做适当的排列,任两个元素之间的线性插值都没有障碍。

正式版本加上了宽度条件。存在某个宽度 hh,只要网络够宽,就存在一个解集合 SS 与一个指定排列的函数 QQ,让 SS 里任两个解在排列后的障碍近似为零,而且 SGD 的解有很高的概率落在 SS 里。

如果猜想成立,损失地形上看起来分隔的许多盆地,其实只是同一个盆地被排列复制出来的分身。

理论:只证得了最简单的情况

作者证明了一个很受限的版本。对一个单隐藏层、ReLU 的全连接网络 f(x)=v⊤σ(Ux)f(x)=v^\top\sigma(Ux),在随机初始化时,权重从指定的均匀分布采样,以高概率存在一个排列,让两个网络插值后的输出和两端输出的插值之间,误差只有

O~ ⁣(h−12d+4)\tilde O\!\left(h^{-\frac{1}{2d+4}}\right)

hh 是隐藏单元数、dd 是输入维度。够宽时,误差趋近于零。

这个定理只谈初始化,不谈训练后的网络。指数里的 2d+42d+4 也说明,输入维度越高,需要的宽度增加得非常快。作者自己说,更复杂的证明也许能延伸到 NTK 范围,但留给未来。

实验:排列空间太大,换个方式验证

直接验证要搜索排列,但排列的数量随宽度阶乘增长。作者试过暴力搜索,单隐藏层 MLP 最多只能做到 16 个神经元,那已经是 16!≈2×101316!\approx2\times10^{13} 种排列。

就算用更聪明的搜索算法,失败时也无法分辨是算法不够强,还是根本不存在那样的排列。

作者换了一个角度。给定一个 SGD 解 θ1\theta_1,把它所有的排列收集起来,形成一个集合

S′={ P(θ1,π)  ∣  π∈P }S' = \{\,P(\theta_1,\pi)\;\big|\;\pi \in \mathcal{P}\,\}

S′S' 一定满足猜想,因为里面每个元素都是 θ1\theta_1 的分身,把排列反转回去,障碍就是零。论文称 S′S' 为「我们的模型」,真实的 SGD 解集合 SS 则称为「真实世界」。

接下来只要检查 SS 和 S′S' 的行为是否一样。如果一个独立训练的解 θ2\theta_2 和 θ1\theta_1 之间的障碍,跟 θ1\theta_1 和「θ1\theta_1 的随机排列」之间的障碍,在各种宽度、深度、数据集下都差不多,那么「θ2\theta_2 其实就是 θ1\theta_1 的某个排列,再加上一点小扰动」就是一个合理的解释。

自己跑一次看看

这个论证可以在很小的规模上重现。

下图是本文另外做的小实验,不是论文的结果。数据是 sklearn 内置的 8×8 手写数字(1,797 张),模型是单隐藏层 ReLU MLP,用不同种子训练两个模型 A 和 B,训练损失都在 0.001 左右。接着比较三种线性插值:A 到 B、A 到「随机排列后的 A」,以及 A 到「对齐后的 B」。

本文整理的教学图:两张线性插值的训练损失曲线,左图隐藏层宽度 16,右图宽度 256。红色实线是 A 到 B,橙色虚线是 A 到随机排列后的 A,两者在中段都隆起成相近的山峰,宽度 16 时障碍分别是 0.458 与 0.557,宽度 256 时是 0.043 与 0.046。蓝绿色实线是 A 到对齐后的 B,障碍降到 0.196 与 0.002。
本文整理:sklearn digits 上的单隐藏层 MLP 小实验,障碍按上文定义计算,取 21 个插值点。

先看红线和橙线。A 和 B 是各自训练出来的模型,A 和排列后的 A 是同一个函数,两条曲线的山峰却差不多高。论文的核心观察就是这个,独立训练造成的障碍,和「纯粹换座位」造成的障碍,高度相近。

蓝绿线是另外加的。把 B 的隐藏单元按照激活值的相关性,用匈牙利算法一对一配到 A 上,再做插值。宽度 16 时障碍从 0.458 降到 0.196,宽度 256 时从 0.043 降到 0.002。这种对齐方法来自后续研究,不是这篇论文用的搜索法;放在这里,是让你看到「排对位置」实际上能做到什么程度。

另外,宽度 64 时三个障碍分别是 0.094、0.070、0.006。宽度越大,障碍越低,对齐之后也越接近零,和论文普查的趋势一致。

论文的证据

回到论文。作者在 MLP 和 Shallow CNN 上比较 SS 与 S′S',在各种宽度、深度与数据集下,两者的障碍曲线几乎重叠。

接着加入搜索。作者用模拟退火(simulated annealing)找排列,这是旅行商问题常用的近似算法。有两个版本:

  • SA1:直接最小化五个解两两之间的平均障碍。
  • SA2:先把排列后的解平均成一个模型,最小化这个平均模型的训练误差。

两者效果差不多,SA2 便宜很多,之后只用 SA2。但它在五个解同时对齐的设置下,几乎降不了障碍。

作者因此缩小搜索空间,只拿两个解,固定 θ2\theta_2,只排列 θ1\theta_1。这样一来,MNIST 和 SVHN 上的 MLP 与 Shallow CNN 障碍都明显下降,单层 MLP 在 MNIST 上甚至对所有宽度都降到零。更重要的是,搜索前后,SS 和 S′S' 的障碍仍然几乎一样。搜索在 S′S' 上成功的地方,在 SS 上也成功;在 S′S' 上失败的地方,在 SS 上也失败。

全部实验加起来训练了三千多个网络,作者把它们画成一张密度图,「真实世界」与「我们的模型」的障碍大致沿着对角线分布。

讨论

这篇论文的论证方式很有意思。它没有证明猜想,而是设计一组「如果猜想是错的,应该会看到差异」的实验,结果没有看到差异。作者用的字眼也很谨慎,说这些尝试「没能推翻」猜想。

但证据的强弱要分开看。

最有说服力的是浅层网络。MLP 和 Shallow CNN 上,SS 与 S′S' 在搜索前后都很像,搜索也真的能在简单数据集上把障碍降到零。

深层网络的证据比较弱。VGG 和 ResNet 的障碍在 SS 和 S′S' 上都很高,模拟退火在两边都找不到能降低障碍的排列。「两边都失败」和猜想相容,但也无法区分是搜索算法太弱,还是深层网络根本有其他障碍。作者也承认,搜索空间的大小是这篇最大的限制,而且所有实验都只有图像识别。

S′S' 的论证本身也有一个隐含前提。SS 和 S′S' 在「直接插值的障碍」与「搜索后的障碍」上相似,不保证两者在「最佳排列下的障碍」上也相似;后者才是猜想真正在讲的事。

后续研究补上了深层网络这一块。Git Re-Basin 改用权重匹配,在把宽度放大很多倍的 ResNet 上,第一次让 CIFAR-10 上两个独立训练的模型做到零障碍;它也构造了一个非 SGD 解的反例,说明猜想里「SGD 的解」这个限定词不能省略。下一篇要看的 REPAIR,则找到深层网络对齐后仍有障碍的另一个原因,问题出在插值后激活值的方差。

结论

这篇论文提出一个简单的想法:损失地形上很多看似不同的盆地,可能只是同一个盆地的排列分身。

它的理论只覆盖单隐藏层、随机初始化的情况;实验则用「拿一个解的排列,模拟独立训练的解」这个巧妙的替代,在浅层网络上给出相当一致的支持。

想亲手感受这件事,不需要大模型。训练两个小 MLP,随便打乱其中一个的隐藏单元,把它跟原本的自己做插值,你会看到一座和两个独立模型之间差不多高的山。