剪枝与学习权重同等重要，Lottery Ticket Hypothesis第一次被理论证明

Pruning is All You Need，只要对随机初始化的神经网络做个好剪枝，不怎么训练也能有个好效果。

在百万、千万参数中，它们生而不平等。有的参数对神经网络极其重要，决定了深度模型的最终性能；有的参数作用不大，多它少它最终性能都差不多。

对于深度神经网络这种大模型，参数量远远大于数据量（过参数化）。它带来的好处是，模型的表达能力非常强，能拟合图像、音频和语言等复杂数据；与此同时，过多参数需要更多的储存空间，一般也需要更多的计算量。

那么为什么深度模型参数生而不平等呢？在 ICLR 2019 最佳论文中，MIT 的研究者从底层机制提出 Lottery Ticket Hypothesis，它表示如果某些参数在模型中很重要，那么开始训练之前就是重要的。

选自：arXiv:1803.03635。

上面表达的是，如果神经网络完成了随机初始化，那么它就包含了一个子网络。该子网络从头开始训练相同的迭代次数，就能获得与整体网络相媲美的效果。这样的假设似乎是反直觉的，因为我们一直有一个概念「剪枝后的子网络从头学习肯定效果要差于整体网络」。

在 MIT 的那篇论文中，研究者通过巧妙的实验验证了这样的假设。其核心思想是：

既然常规的模型剪枝能在删除大量权重的情况下保持准确率基本不变，那么在那种初始化条件下，它就是有效子结构。如果我们保留该子结构，并将权重返回到之前初始化结果，要是重新训练能达到最优效果，那么就证明了 Lottery Ticket Hypothesis。

在希伯来大学的新论文中，它们从理论推导的方向证明了这样的假设，并提出更加严格与具体的规则。具体而言，一个充分过参数化的神经网络，其随机初始化权重包含一个子网络，该子网络不需要额外更多的训练就能和完整网络相媲美。

论文地址：https://arxiv.org/abs/2002.00585

剪枝，远比你想象中的重要

在这项工作中，希伯来大学的研究者证明了更强的猜想：只要分布有界、目标网络的权重有界，那么这样的过参数化网络是服从 Lottery Ticket Hypothesis 的。

研究者将子神经网络分为两种：weight-subnetwork，通过移除特定权重的子网络；neuron-subnetwork，通过移除整个神经元而获得的子网络。对于这两种子网络，研究者证明得出两种结果：

• 对于任意深度 l 的神经网络（ReLU激活函数），它都可以通过搜索深度为 2l 、宽度足够的随机网络，并找到一个 weight-subnetwork 来逼近它。

• 对于两层神经网络（一个隐藏层），研究者证明它有一个能媲美的 neuron-subnetwork。

研究者表示，这是第一篇从理论上证明随机初始化的神经网络存在优秀子网络的论文，即证明强 Lottery Ticket Hypothesis 的研究。研究者表明：「从根本上来说，剪枝随机初始化的神经网络与优化权重值一样重要。」

虽然目前找到一个好的神经网络，常用方法还是训练其权重参数。但该论文的研究结果表明，我们需要的仅仅是一个好的剪枝机制。

这和 谷歌大脑去年的一项研究 有异曲同工之妙，谷歌研究者表示，神经网络架构本身就有非常强的能力，有的架构即使完全采用随机生成的权重也能完成强化学习或图像识别等任务。

如上所示，一般神经网络在架构内随机初始化权重，再学习权重以找到最优解，这样的模型就能完成特定任务。对于谷歌大脑提出不用学习权重的神经网络，它相当于不停地特化架构，或者说降低模型方差。这样，当架构越来越小而只包含最优解时，随机化的权重也就能解决实际问题了。

而我们知道，对权重或神经元进行剪枝，本身就相当于构造不同的神经网络架构。

Pruning is All You Need，也许与传统学习模型权重相比，剪枝与修正架构也是非常值得注意的方向。

Lottery Ticket Hypothesis 证明

对于上面两个结论的证明，论文最后有 11 页附录，这里只介绍主要定理结果。第一条证明是关于带 ReLU激活函数的神经网络，证明它可以通过对随机初始化的神经网络进行剪枝而逼近。

现在假设 σ(x) = max{x, 0}，我们先定义一个神经网络G : R^d → R，它有 l 层，每层宽度为 n。具体而言：

对于 G 的剪枝结果 G tilde，它的宽度同样为 n、深度为 l。研究者得出的第一条结果表明，对于深度为 l，且权重有界的目标神经网络，一个随机初始化的神经网络有很高概率包含一个子网络以逼近目标网络，该随机网络深度为 2l、宽度为多项式宽度。

更严格的表述为：

这条定理看上去就比较复杂，论文中的证明概览及附录中的完整过程都非常硬核。不过，我们先了解证明结论也是很好的。

现在对于第二条证明，我们的问题是，假设二层神经网络能很好地逼近函数 f，其宽度为多项式宽度。那么如果我们能通过剪枝随机初始化的二层神经网络，能否逼近这样的函数 f？

研究者表示该问题的答案是否定的，实际上剪裁整个神经元等价于著名的随机特征模型。直观而言，我们只需要训练神经网络的最后一层就够了，同时通过裁剪整个神经元，我们也可以构建一个优秀的子网络。

首先定义随机特征模型，如下所示它比较像二层神经网络：

其不同之处在于，二层随机特征网络只训练第二层，即只训练权重u_i。这种随机特征模型类似于在随机特征σ(<w_i , x>) 上训练一个线性模型。

定理 3.2 表示，对于任意数据分布，如果随机特征模型能实现非常小的损失值，那么它就能找到一个剪枝神经元的子网络（neuron-subnetwork），并实现相同的损失。这表明剪枝神经元能和随机特征模型相媲美。

同样，如果在数据分布上找到的 neuron-subnetwork 能实现小的损失值，那么我们也能找到相媲美的随机特征模型。研究者表示，如果将随机特征模型的权重设置为与 neuron-subnetwork 相同，其剪裁掉的权重近似为零。

最后，基于这两条理论证明，作者表示，剪枝与优化权重是同等重要的，只不过现在缺少一种高效的模型剪枝算法。