自“彩票假设”理论被授予2019 ICLR最佳论文后，该领域又有了哪些新的研究进展？
编译 | Mr Bear
编辑 | 陈大鑫
在人们互相交流和信息传递的过程中，「隐喻」的作用极其重要。在1970年之前，当人们提起「桌面」这个单词，联想到的还都是放满了锅碗瓢勺的桌子。但是当天才计算机大师Alan Kay在 Xerox PARC 实验室设计了现代的 GUI 交互界面之后，桌面这个词可能更多的指代的就是配备各种图形化操作系统的电脑桌面了。
近年来，在深度学习领域，人们将一个新的具有广阔前景的研究领域隐喻为「彩票假说」（LTH）。在本文中，我们会深入探讨该假设，并回顾 Frankle 和 Carbin 在 ICLR 2019 上发表的那篇风光无限的最佳论文 《THE LOTTERY TICKET HYPOTHESIS: FINDING SPARSE, TRAINABLE NEURAL NETWORKS》 。
1
深度学习模型剪枝
对过参数化的神经网络进行剪枝是深度学习领域中经久不衰的问题。其中，最常见的方法是将某些特定的权值设置为零，并且在随后的训练过程中冻结它们（不进行训练）。这种思想比较朴素，实现也很简单，只要将权值 W 和一个二元剪枝掩模 M 按对应元素相乘即可。进行这种干预的动机如下：
通过对过参数化的函数进行正则化处理，使剪枝后的模型具有较强的泛化能力。 能够找出原本庞大网络中性能优越的小型子网络（现有存储条件可满足），从而减少模型前向推理时的内存需求。 减少了模型所需的算力、耗电量、存储和延迟等需求，从而使其能够在移动设备部署。 近年来，随着网络模型的深度越来越深，以上三个问题逐渐受到了人们越来越大的关注。一般来说，优秀的网络剪枝算法必须解决以下 4 个基本问题：
问题 1：应该剪掉怎样的连通结构？
非结构化修剪不考虑剪枝的权值之间的任何关系。另一方面，结构化剪枝则是通过去除整个神经元（权值列）、删除卷积神经网络的卷积核或通道等方式对一组权值进行剪枝。尽管非结构化的剪枝方法往往能在保持较高性能的同时剪掉数量更多的权值，但是这种方法并不一定会真正加速在标准硬件上的计算过程。实际上，这里的关键原因在于密集的计算可以很容易被并行化处理；而剪枝后的网络通常过于「分散」，难以实现并行计算。
除了从结构化角度来对剪枝算法进行分类，我们还能够从局部和全局剪枝的角度进行另一种分类。其中，局部剪枝方法会强制从网络的每一层剪掉一定比例的权值参数。而全局剪枝就没有这个要求了，它只需要将整个网络中 s% 的权重参数剪掉即可。
图 2：深度学习网络剪枝要考虑的因素：剪掉哪些部分、如何剪枝、何时剪枝、剪枝频率如何？
问题 2：如何对有待剪枝的权值参数进行排序？
已经有一些研究人员或多或少使用了启发式方法对网络中的某个权值的重要性进行评估。其中常见并且有效的经验是，网络中权重取值较大的连接或者说神经元对网络的表达能力和函数拟合能力更加重要，剪枝算法应该尽量避免剪掉这些权值。尽管这种经验非常实用，但是从直觉上说，这好像和 L2 权值正则化方法的思想有些矛盾。在 L2 正则化方法中，损失函数会对取值很大的权重进行较大的惩罚，避免网络过度依赖于某些权重或者神经元，从而保证模型的泛化能力。这种对于权值处理的矛盾也催生出了相关的技术，这些技术使用基于梯度的方法或者更高阶的曲率信息来学习剪枝掩模。
问题 3：我们应该多久进行一次剪枝？
基于权值的幅值对其重要性进行评估会在很大程度上受到噪声干扰。我们知道，网络剪枝方法可以分为单次剪枝（One-Shot）和迭代式（Iterative）剪枝。单次剪枝会极大地受到噪声的影响，而迭代式剪枝方法则会好很多，因为它在每次迭代之后只会删除掉少量的权重，然后周而复始地进行其他轮的评估和删除，这就能够在一定程度上减少噪声对于整个剪枝过程的影响。通常，每次迭代的剪枝率大概在 20% 左右，总共需要进行 20~30 轮剪枝迭代（最终仅仅保留 1% 未被剪掉的网络权重）。当然，我们可以设计网络来让修剪后保留的权值参数更多一些（即更保守），但是这会增加算法的训练时间。
问题 4：何时执行剪枝步骤？
具体来说，我们可以在「训练前」、「训练中」和「训练后」三个不同的阶段执行剪枝。其中，在训练收敛后进行剪枝的方法通常会降低模型的泛化能力，所以很多工作需要重新对模型再次进行微调。除了训练后的剪枝，训练中的剪枝方法也很常用，这种方法通常是跟正则化、Dropout、强化分布式表征等思想相关联。然而，从头开始训练一个稀疏的网络几乎是不可能的，所以「训练前」剪枝的方法很少被使用。
2
彩票假设（LTH）及其扩展方法
Frankle & Carbin (2019) — The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
论文链接：
https://openreview.net/forum?id=rJl-b3RcF7
代码链接：
https://github.com/facebookresearch/open_lth
当前有很多研究已经证实，在不显著降低网络性能的前提条件下，一个训练好的稠密的网络能够被剪枝成一个参数量很小的网络。实际上，人们曾在很长的一段时间内认为，从头开始训练一个稀疏的网络几乎是不可能的。这是为什么呢？其实，较小的子网络确实可以近似一个性能良好的函数，但是它与稠密的网络相比，其学习模式（learning dynamics）有很大的差别。
在 Frankle 和 Carbin 与 2019 年发表的「彩票假设」原始论文中，作者首先解释了可能造成这种现象的原因。他们认为在网络剪枝之后，生成的子网络会被随机初始化。但是，如果我们能在生成裁剪网络之后，将子网络的权重重新初始化为它们的原始权重（在剪枝后已经被掩模屏蔽了），那么在经历较少轮的迭代之后，网络就有可能恢复到它在剪枝之前的性能，甚至可能达到更好的性能。这些性能特别优越的子网络就好比在权值初始化彩票游戏中中奖的幸运儿。彩票假设的具体内容如下：
彩票假设：任何随机初始化的稠密的前馈网络都包含具有如下性质的子网络——在独立进行训练时，初始化后的子网络在至多经过与原始网络相同的迭代次数后，能够达到跟原始网络相近的测试准确率。
那么我们如何才能找到这种「中奖网络」呢？Frankle 和 Carbin 在 2019 的论文中提出了迭代幅值剪枝（IMP，iterative magnitude pruning）方法：首先，对初始的稠密网络进行多轮训练，直到模型收敛。然后，我们确定最小的 s% 个权值，并创建一个二值掩模对这些权值进行剪枝。随后，我们使用之前的初始化权值重新训练稀疏化后的网络。在模型收敛后，我们重复该剪枝过程（屏蔽额外的 s 的权值），并使用新一轮剪枝后发现的掩模设置初始化权值。我们重复这个过程，直到达到期望的稀疏程度，或者测试准确率显著下降。
图 3：寻找「中奖网络」的过程
如果 IMP 算法成功执行，它就能找到「中奖网络」，即经过迭代式的剪枝过程后留下的子网络。请注意，我们也可能通过简单的单次剪枝方法实现这一目的，但是当执行额外的计算时，我们可以获得更好的结果（详见原始论文的图 4）。如果我们回顾一下前面提到的网络剪枝中普遍存在的问题，那么 IMP 需要满足以下条件：
图 4：IMP 与网络剪枝的核心问题
下图总结了第一篇 LTH 论文的一些关键的实验结论：
图 5：LTH 的关键性结果。
B 图：IMP 能够在不进行任何超参数调整的前提下，仅使用较少的迭代次数就能找出性能超越未修剪的稠密网络的稀疏子网络（图 B 中不同颜色的曲线代表不同的被剪掉的权值比例）。其中，中奖彩票的初始化和随机重初始化的最终性能之间的差异被称为「彩票效应」（Lottery Ticket Effect）。 图 C 和图 D：为了能够将原始的实验结果扩展到更加复杂的任务和网络架构中（如 CIFAR-10数据集，VGG19 和 Resnet20 等网络），Frankle 和 Carbin 不得不对学习率进行调整，并且引入「热身」规划机制，让模型在预定义的迭代集合内从 0 退火到最终的学习率上。请注意，根据经验，适合于 ResNet 的学习率远远小于适合于 VGG19 的学习率。 上述结论告诉我们什么呢？首先，IMP 算法能够找到一个有利于当前任务的子结构，而且子网络的权值初始化需要通过特殊的学习模式获得。此外，成功的训练并不一定需要过参数化——过参数化可能只能通过排列组合提供一些可用的子网络选项，而这些排列组合是会造成组合爆炸效应的。当前已经有很多后续的工作尝试尝试揭示「中奖网络」与普通网络定性的区别背后的潜在机制。
Frankle et al. (2019) — Stabilizing the Lottery Ticket Hypothesis
论文链接：https://arxiv.org/abs/1903.01611
代码链接：https://github.com/facebookresearch/open_lth
原始的「彩票假设」论文存在的局限性之一是：该研究仅仅局限于小规模的任务，比如 MNIST 和 CIFAR-10。那为了能够将 LTH 扩展到其它更加复杂的任务上，Frankle 和 Carbin 不得不调整学习率的变化策略。
Liu 等人https://arxiv.org/pdf/1810.05270.pdf和Gale 等人（https://arxiv.org/pdf/1902.09574.pdf)）
分别发现，如果我们不调整学习率的话，所训练出来的小网络性能会很差，无法达到和原始的网络相近的性能。既然如此，如果我们将「中奖彩票」的限制放宽松，将会如何呢？
在 Frankle 等人的后续工作（https://arxiv.org/abs/1903.01611）中，他们尝试通过将权值重新设置为经过了较少的 k 轮训练之后得到的权值，而不是网络的初始化权值，从而鲁棒地获得剪枝后的子网络。换而言之，我们在剪枝后不将权值「回放」到第 0 轮迭代时的情况，而是将权值回放到第 k 轮迭代时情况。该工作的形式化定义和图解如下所示：
图 6：带回放机制的彩票假设
由于我们没有对网络进行彻底的训练，只是进行了前 k 步的训练，所以我们找到的这个初始化策略就不能再被叫做「中奖彩票」，它只能算作是一个「接近中奖的彩票」（Matching Ticket）。
图 7：带回放机制的 IMP
这种做法的一些关键性结论如下图所示：执行 IMP 算法时，将剪枝后的网络权重回放为 k>0 的某次迭代后的值是很有效的。它能在仍旧获得和原始网络相近的测试性能的同时，剪掉高达 85% 的权值参数。当算法将 k 设置为500时（如图 8 A 所示），该结论在 CIFAR-10 数据集和 ResNet-20 模型上也成立；当算法将 k 设置为 6 时，该结论也适用于 ImageNet数据集 和 ResNet-50。此时，我们并不需要使用学习率的「热身」操作。
图 8：LTH 关键结论的放缩结果
Renda et al. (2020) — Comparing Rewinding and Fine-tuning in Neural Network Pruning
论文链接：https://arxiv.org/abs/2003.0238
代码链接：https://github.com/lottery-ticket/rewinding-iclr20-public
至此，我们已经讨论过 IMP 是否能够找出一种性能与「中奖网络」相近的网络初始化状态。但是和其它剪枝算法相比，IMP 的剪枝算法流程有何异同呢？在 Renda 等人于 2020 年发表的论文「Comparing Rewinding and Fine-tuning in Neural Network Pruning」（https://arxiv.org/abs/2003.02389）中，他们比较了三种不同的剪枝过程：
1、调优：在剪枝过程结束之后，算法对剩余的权重使用较小的学习率继续进行学习，从而得到最终的权重取值。一般来说，这个较小的学习率也是稠密的原始网络最终的学习率。
2、权值回放：该方法与 Frankle 等人在论文「Stabilizing the Lottery Ticket Hypothesis」中使用的方法对应。在剪枝之后，剩余的神经元权值被重置为第 k 次随机梯度下降迭代后的权值。此后，算法以第 k 次迭代时的权值为起点，使用某种学习率调整策略重新训练权值。此时，权值和学习率的调整策略都会被重置。
3、学习率回放：该方法并未回放权值或将学习率调整策略设置为初始状态，学习率回放使用的是最终未剪枝的权值，并且只将学习率调成策略调整到第 k 轮迭代的状态。
Renda 等人在论文 「Comparing Rewinding and Fine-tuning in Neural Network Pruning」 中对比了上述三种方法在准确率、搜索成本和参数效率三个方面的优劣，并且回答了下面的几个问题：
假设我们可以用无限的算力进行搜索，上述三种模型约简方法最终的准确率和参数效率（剪枝前后的压缩比）的表现和差异将如何？ 给定固定的用于搜索的算力预算时，上述三种模型约简方法最终的准确率和参数效率的表现和差异将如何？ 为了回答上面的问题，作者使用 ResNet 34、ResNet 50、ResNet 56 网络在 GNMT 自然语言处理对比基准上进行了实验，并得到如下的结论：
在算力无限和给定固定算力预算的实验中，使用权值回放并重新训练的性能都明显优于简单的微调并再训练的方法。在结构化和非结构化剪枝的对比实验中，该结论也成立。 学习率回放方法的性能优于权值回放方法。此外，虽然权值回放法在 k=0 时可能效果不好，但将学习率回放到训练过程开始的状态往往是有效的。 在准确率、压缩比和搜索成本效率方面，权值回放 LTH 网络是目前性能最优的对初始网络进行剪枝的模型。 在经过了大规模的实验后，研究人员提出了许多有关深度学习的实验性结论，但问题是：对于我们理解这些高度非线性的系统（深度神经网络）来说，这些结论究竟有什么含义？
3
剖析彩票假设：鲁棒性与学习模式
Zhou et al. (2019) — Deconstructing lottery tickets: Zeros, signs, and the supermask
论文链接：
https://papers.nips.cc/paper/8618-deconstructing-lottery-tickets-zeros-signs-and-the-supermask.pdf
代码链接：
https://github.com/lottery-ticket/rewinding-iclr20-public
决定某个初始网络是否为「中奖网络」的主要因素是什么？也许，这些因素包括：掩模屏蔽的标准（权值的大小）、回放未被屏蔽的权值的方法，以及将权值设置为零并冻结它们的掩模。但是，如果我们改变以上三种因素其中的一个，结果将如何呢？较大的权重会有什么样的影响？使用其它回放策略是否还能够找到中奖网络呢？为什么要把权值设置为零？Zhou 等人在论文「Deconstructing lottery tickets: Zeros, signs, and the supermask」中从以下三个方面对这些问题展开了研究：
对比不同的选择被屏蔽权值的打分方式：保留那些最小的训练后权值；保留初始化时最大或者最小的权值，或者在权值空间中幅值变化最大或最小的权重。 分析如果不将权值回放到初始状态，是否仍然会得到中奖网络：Zhou 等人对比了随机重初始化、重新打乱保留的权值，以及恒定初始化等情况。 将被掩模屏蔽的值固定为初始化的值，而不是将它们设定为 0。 通过大量的实验，作者得出了以下结论：
那些成比例地保留剩余权值与初始状态之间距离的评分标准，会得到与保留「最大权值」的标准相同的性能。 只要在执行回放时将权值的符号保持为初始权值的符号，就可以获得和执行经典的 IMP 方法时获得的相同的中奖网络（请注意：该结论在 Frankle 于 2020 年发表的论文 「The Early Phase of Neural Network Training 」 中无法复现）。 将权值屏蔽为 0 是很重要的。 基于以上结论，作者猜想，利用一些具有先验设定的掩模也可以成为一种训练形式：它只是加速了权值变化的过程，而这些权值其实在优化过程中已经逐渐趋向于 0。有趣的是，使用应用于随机初始化的网络的 IMP 方法获得的掩模（并且没有进行任何额外的训练）所能达到的性能，远远优于随机的掩模，或者随机初始化的网络。所以，我们可以将其看做是一种「超级掩模」，它能够编码一种强归纳偏置。这个发现很让人激动，也许我们可以根本不训练网络权值，只需要找到正确的掩模就能获得很好的模型性能。Zhou 等人在论文 「 Deconstructing lottery tickets: Zeros, signs, and the supermask」 中说明，我们甚至可以通过使掩模可微或使用类似于强化学习的损失函数学习性能优越的掩模。这种思路令人不禁想起 Gaier 和 Ha 于 2019 年发表的「Weight Agnostic Neural Networks」。其中，一个学习到的掩模可以被看做一种连接模式，它对解的正则性进行了编码。通过对权值进行多次采样，从而评价某个掩模，我们实际上使该掩模对于采样的权值具有很强的鲁棒性。
Frankle et al. (2020a) — Linear Mode Connectivity & the Lottery Ticket Hypothesis
Paper | Code
论文链接：https://arxiv.org/abs/1912.05671
代码链接：https://github.com/facebookresearch/open_lth
当我们训练一个神经网络时，往往会对数据的批次进行随机的排序。每个批次会被用来针对网络参数估计损失的梯度。在完整地遍历一次数据集（即一个 epoch）后，这些批次会被打乱重组，然后我们进行下一轮的迭代。我们可以将批次的序列视为噪声的来源，我们可能会在此时将这些噪声带入到训练过程中。由于这个原因，我们得到的最终权值可能差别很大。但是，理想状态下，我们网络的训练过程应该对于这样的噪声十分鲁棒。更正式地说，我们可以考虑某种权值初始化方式，此时我们使用两种不同的批次顺序进行训练，从而得到两组不同的训练后的权值。Frankle 等人在论文 「Linear Mode Connectivity and the Lottery Ticket Hypothesis」 中提出了以下问题：如果我们在这两种通过不同的数据顺序得到的最终的权值设定之间平滑地插值（凸组合），那么验证/测试的准确率将会如何？