机器之心原创
作者：朱梓豪
编辑：Haojin Yang

神经网络剪枝技术可以极大的减少网络的参数，并降低存储要求，和提高推理的计算性能。而且目前这方面最好的方法通常能保持很高的准确性。因此对通过修剪产生的稀疏架构的研究是一个很重要的方向。本选题的思路是对以下两篇论文做深度解读，一探当今最好的剪枝方法的究竟。
深度神经网络已经在计算机视觉领域取得了巨大的成功，如 AlexNet、VGG 等。这些模型动辄就有上亿的参数，传统的 CPU 对如此庞大的网络一筹莫展，只有具有高计算能力的 GPU 才能相对快速的训练神经网络。如 2012 年 ImageNet 比赛中夺冠的 AlexNet 模型使用了 5 个卷积层和 3 个全连接层的 6000 万参数的网络，即使使用当时顶级的 K40 来训练整个模型，仍需要花费两到三天时间。卷积层的出现解决了全连接层的参数规模问题，但叠加若干个卷积层后，模型的训练开销仍然很大。
现在有了性能更强的 GPU，计算一个更深的神经网络、参数更多的神经网络根本不成问题。但事实上并不是每个人都是人手几张卡的，对于具有更多层和节点的神经网络，减少其存储和计算成本变得至关重要。并且，随着移动设备和可穿戴设备的普及，如何让这些模型在计算能力并不强的移动端也能很好地应用，也成为亟待解决的问题。因此越来越多的研究者开始研究神经网络模型压缩。
综合现有的模型压缩方法，它们主要分为四类：参数剪枝和共享（parameter pruning and sharing）、低秩分解（low-rank factorization）、转移和紧凑卷积核（transferred/compact convolutional filters）、知识蒸馏（knowledge distillation）[1]。
本篇文章主要解读神经网络剪枝方面的两篇论文，第一篇《The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks》是 MIT 团队发表在 ICLR'19 上的，提出了彩票假设：密集、随机初始化的前馈网络包含子网络（「中奖彩票」），当独立训练时，这些子网络能够在相似的迭代次数内达到与原始网络相当的测试准确率，此文荣获了最佳论文奖。第二篇《Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask》是 Uber AI 团队对彩票假设的深度解构。
论文1：The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
原文链接：https://arxiv.org/abs/1803.03635
介绍
训练机器学习模型是数据科学领域计算成本最高的方面之一。数十年来，研究人员已经提出上百种方法来改进机器学习模型的训练过程，这些方法都基于一个公理假设，即训练应该覆盖整个模型。最近，来自 MIT 的研究人员发表了一篇论文来挑战这一假设，提出了一种更简单的通过关注子网络来训练神经网络的方法，MIT 研究员起了一个很容易记住的名字——「彩票假设」（Lottery Ticker Hypothesis）。
机器学习的训练过程，是数据科学家在理论与现实之间面临的妥协之一。通常情况下，对于特定问题而言，由于训练成本的限制，理想的神经网络架构不能完全实现。一般而言，神经网络最初的训练需要大量的数据集和昂贵的计算成本，其结果得到一个隐藏层之间充满复杂连接的庞大的神经网络结构。这种结构往往需要经过优化技术，移除某些连接来调整模型的大小。数十年来困扰研究者的一个问题是我们是否真的需要这样的庞大的神经网络结构。很明显，如果我们连接网络中的每个神经元，可以解决特定的问题，但可能因为高昂的成本而被迫止步。难道我们不能从更小、更精简的网络开始训练吗？这就是彩票假设的本质。
以博彩来类比，训练机器学习模型就相当于通过购买每一张可能的彩票来获得中奖彩票。但是如果我们知道中奖彩票长什么样子，那么是不是就可以更聪明地来选择彩票？在机器学习模型中，训练过程得到的巨大的神经网络结构相当于一大袋彩票。在初始训练之后，模型需要进行优化，例如剪枝，删除网络中不必要的权重，从而在不牺牲性能的情况下减小模型的大小。这就相当于在袋子中寻找中奖彩票，然后扔掉剩下的彩票。通常情况下，经过剪枝后的网络结构要比原始的小 90% 左右。那么问题来了，如果网络结构可以缩小，那么为了提高训练效率为什么不一开始就训练这个更小的网络呢？然而，已经有许多实验证明了，如果从头开始训练剪枝后的网络，得到的准确率要比原始网络低很多。
MIT 的彩票假设背后的思想是，一个大型的神经网络包含一个小的子网络，如果一开始就训练，那么会得到和原始网络相似的准确率。
彩票假设
文章中对彩票假设的正式定义为：一个随机初始化的密集神经网络包含一个初始化的子网络，在单独训练时，最多经过相同的迭代次数，可以达到和原始网络一样的测试准确率。
我们将一个复杂网络的所有参数当做奖池，上述一组子参数对应的子网络就是中奖彩票。
更正式的，考虑一个密集的前馈神经网络 f(x;θ)，其中初始化参数 θ=θ_0~D_θ，当在训练集上用随机梯度下降时，f 可以在 j 次迭代后达到损失 l 和准确率 a。此外，考虑对参数θ作用一个 01 掩模 m∈{0,1}^|θ|，在相同的数据集上训练 f(x;m⊙θ), f 在 j' 次迭代后达到损失 l' 和准确率 a'。彩票假设指出存在 m, 使得 j』<=j (训练时间更快), a』>=a (准确率更高), ||m||_0 << |θ| (更少的参数)。
如何找到中奖彩票
如果彩票假设是正确的，那么下一个问题就是如何设计一种策略来找出中奖彩票。作者提出一种通过迭代找到中奖彩票的方法：
1. 随机初始化一个复杂神经网络 
2. 训练这个网络 j 次直到收敛
3. 剪掉部分权重参数
4. 将剩下的子网络用第 1 步的权重进行初始化，创建中奖彩票
5. 为了评估第 4 步得到的子网络是否是中奖彩票，训练子网络，比较准确率
上述过程可以进行一次或者多次，在只有一次剪枝时，网络训练一次，p% 的权重被剪掉。论文中迭代进行 n 次剪枝，每一次剪掉 p^(1/n)% 的权重。
实验分析
作者分别在针对 MNIST 的全连接神经网络和针对 CIFAR10 的卷积神经网络上做了大量实验。这里以 MNIST 实验为例：
Pm 代表网络还剩下多少的参数。从图 3 可以观察到，不同剪枝率的子网络的性能不一样，当 Pm>21.2% 时，Pm 越小，即剪枝的参数越多，准确率越高，当 Pm<21.1% 时，Pm 越小，准确率会下降。中奖彩票要比原始网络收敛的更快，同时具有更高的准确率和泛化能力。
由图 4 可以观察到，迭代剪枝要比 oneshot 剪枝更快找到中奖彩票，而且在子网络规模较小的情况下依然可以达到较高的准确率。为了衡量中奖彩票中初始化的重要性，作者保留了中奖彩票的结构然后使用随机初始化重新训练。与中奖彩票不同的是，重新初始化的网络学习速度比原来的网络越来越慢，并且在进行少量剪枝之后就会失去测试精度。
总结
本文中，作者提出了彩票假设并给出一种寻找中奖彩票的方法，通过迭代非结构化剪枝的方式可以找到一个子网络，用原始网络的初始化参数来初始化，可以在性能不下降的情况下更快的训练这个子网络，但是如果用随机初始化方法却达不到同样的性能。
作者也在文章中指出这项工作存在的一些问题。例如，迭代剪枝的计算量太大，需要对一个网络进行连续 15 次或 15 次以上的多次训练。未来可以探索更加高效的寻找中奖彩票的方法。
论文2：Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask
原文链接：https://arxiv.org/abs/1905.01067
彩票假设回顾
Frankle 和 Carbin 在彩票假设（LT）论文中提出一种模型剪枝方法：对网络训练后，对所有小于某个阈值的权重置 0（即剪枝），然后将剩下的权重重置成原始网络初始的权重，最后重新训练网络。基于这种方法，得到了两个有趣的结果。
一方面经过大量剪枝的网络（删掉 85%-95% 的权重）与原网络相比性能并没有明显的下降，而且，如果仅仅剪掉 50%-90% 的权重后的网络性能往往还会高于原网络。另一方面，对于训练好的普通网络，如果重新随机初始化权重然后再训练，得到的结果与之前的相当。而对于彩票假设的网络并没有这个特点，只有当网络使用和原网络一样的初始化权重，才能很好地训练，如果重新初始化会导致结果变差。剪枝掩模（如果删掉权重置 0，否则为 1）和权重的特定组合构成了中奖彩票。
存在的问题
虽然上篇论文里证明了彩票假设是有效的，然而许多潜在的机制尚未得到很好的理解。例如：LT 网络如何使他们表现出更好的性能？为什么掩模和初始权重集如此紧密地耦合在一起，以至于重新初始化网络会降低它的可训练性？为什么简单地选择大的权重构成了选择掩模的有效标准？其他选择掩模的标准也会起作用吗？本篇论文提出了对这些机制的解释，揭示了这些子网络的特殊模式，引入了与彩票算法相抗衡的变体，并获得了意外发现的衍生品：超级掩模（supermask）。
掩模准则
作者将每个权重的掩模值设为初始权值和训练后的权值的函数 M(w_i,w_f)，可以将这个函数可视化为二维空间中的一组决策边界，如图 1 所示。不同的掩码标准可以认为是将二维 (wi =初始权值，wf =最终权值) 空间分割成掩码值为 1 vs 0 的区域。
如图所示的掩码准则由两条水平线标识，这两条水平线将整个区域划分为掩码=1(蓝色) 区域和掩码=0(灰色) 区域，对应于上篇论文中使用的掩模准则:保留最终较大的权重，并剪掉接近于零的权重。作者将这种称为 large_final mask, M(w_i,w_f)=|w_f|。作者还提出了另外 8 种掩模准则，对应的公式都在下图表示出来了，保留椭圆中彩色部分的权重，将灰色部分的权重剪掉。
作者对这些掩模准则做了一系列对比试验，对于全连接和 Conv4 网络结果如下图所示。可以发现，magnitude increase 和 large_final 相比不相上下，在 Conv4 网络中还要表现的更好一些。
以随机掩模为基线，我们可以发现那些倾向于保留具有较大最终值的权重的准则能更好的发现子网络，而保留小权值的效果较差。
正负号的重要性
现在已经探索了对哪些权重进行减值效果较好。接下来的问题是该将保留下来的权重重置为何值。作者主要是想研究上篇论文中的一个有趣的结果，当重置为原网络初值的时候效果很好，但当随机初始化时，效果会变差。为什么重新初始化效果会变差以及初始化的哪些条件最重要？为了找到问题的答案，作者做了一系列初始化的实验。
  • Reinit：基于原始的初始化分布来初始化保留的权重
  • Reshuffle：基于保留权重的原始分布进行初始化
  • Constant：将保留的权重设为正或负的常数，即每层原初始值的标准差
可以发现保留权重的初始值并没有保留正负号这么重要。如果使用其他的初始化方法，但是忽略正负号，那么效果很差，和随机初始化差不多（图中虚线）。而如果和原来的权重保持一样的正负号，三种方法和 LT 网络的初始化效果相差无几（图中实线）。只要保持正负号一致，即使将剩下的权重都设为常量也不会影响网络的表现。
超级掩模
在开头提到了超级掩模的概念，它是一种二值掩模，当作用到随机初始化的网络上时，即使不重新训练，也可以得到更高的准确率。下面介绍如何找到最佳的超级掩模。
基于上述对初始符号重要性的洞察以及让权重更接近最终值的考虑，作者引入了一种新的掩模准则，选择较大的权重，而且这些权重在训练后也保持相同的正负号，作者将其称为 large_final, same sign。并且用 large_final, diff sign 作为对照，两者的区别如下图所示。
通过使用这一掩模准则，可以在 MNIST 上取得 80% 的测试准确率，而上一篇文章 large_final 方法在最好的剪枝率下只有 30% 的准确率（注意这是在没有进行重新训练的情况下）。
总结
这篇文章对上一篇文章进行了深度的解释。通过比较不同的掩模准则和初始化方案来回答为什么彩票假设可以表现的很好。并且有意思的是提出了一种新的「超级掩模」，通过它可以在不重新训练子网络的情况下得到很高的准确率。这为我们提供了一种新的神经网络压缩方法，只需要保存掩模和随机数种子就可以重构网络的权重。
参考文献
1. Cheng, Yu, et al. "A survey of model compression and acceleration for deep neural networks." arXiv preprint arXiv:1710.09282 (2017).
2. Frankle, Jonathan, and Michael Carbin. "The lottery ticket hypothesis: Finding sparse, trainable neural networks." ICLR (2019).
3. Zhou, Hattie, et al. "Deconstructing lottery tickets: Zeros, signs, and the supermask." arXiv preprint arXiv:1905.01067(2019).
4. https://eng.uber.com/deconstructing-lottery-tickets/
5. https://towardsdatascience.com/how-the-lottery-ticket-hypothesis-is-challenging-everything-we-knew-about-training-neural-networks-e56da4b0da27
作者介绍：朱梓豪，目前是中国科学院信息工程研究所的硕士研究生，主要研究方向为图神经网络、多模态机器学习、视觉对话等方向。爱好科研，喜欢分享，希望能通过机器之心和大家一起学习交流。
本文为机器之心原创，转载请联系本公众号获得授权。
✄------------------------------------------------
加入机器之心（全职记者 / 实习生）：[email protected]
投稿或寻求报道：content@jiqizhixin.com
广告 & 商务合作：[email protected]
继续阅读
阅读原文