机器之心原创

2020/03/12 16:23

思源报道

剪枝与学习权重同等重要，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 相同，其剪裁掉的权重近似为零。

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

理论彩票假设剪枝ICLR 2019MIT权重

相关数据

激活函数技术

在计算网络中，一个节点的激活函数定义了该节点在给定的输入或输入的集合下的输出。标准的计算机芯片电路可以看作是根据输入得到"开"(1)或"关"(0)输出的数字网络激活函数。这与神经网络中的线性感知机的行为类似。一种函数（例如 ReLU 或 S 型函数），用于对上一层的所有输入求加权和，然后生成一个输出值（通常为非线性值），并将其传递给下一层。

来源：维基百科 Google ML glossary

权重技术

线性模型中特征的系数，或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0，则相应的特征对模型来说没有任何贡献。

来源：Google AI Glossary

参数技术

在数学和统计学裡，参数（英语：parameter）是使用通用变量来建立函数和变量之间关系（当这种关系很难用方程来阐述时）的一个数量。

来源：维基百科

剪枝技术

剪枝顾名思义，就是删去一些不重要的节点，来减小计算或搜索的复杂度。剪枝在很多算法中都有很好的应用，如：决策树，神经网络，搜索算法,数据库的设计等。在决策树和神经网络中，剪枝可以有效缓解过拟合问题并减小计算复杂度；在搜索算法中，可以减小搜索范围，提高搜索效率。

来源：Wikipedia

神经网络技术

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

准确率技术

分类模型的正确预测所占的比例。在多类别分类中，准确率的定义为：正确的预测数/样本总数。在二元分类中，准确率的定义为：(真正例数+真负例数)/样本总数

来源：Google ML Glossary

神经元技术

（人工）神经元是一个类比于生物神经元的数学计算模型，是神经网络的基本组成单元。对于生物神经网络，每个神经元与其他神经元相连，当它“兴奋”时会向相连的神经元发送化学物质，从而改变这些神经元的电位；神经元的“兴奋”由其电位决定，当它的电位超过一个“阈值”（threshold）便会被激活，亦即“兴奋”。目前最常见的神经元模型是基于1943年 Warren McCulloch 和 Walter Pitts提出的“M-P 神经元模型”。在这个模型中，神经元通过带权重的连接接处理来自n个其他神经元的输入信号，其总输入值将与神经元的阈值进行比较，最后通过“激活函数”（activation function）产生神经元的输出。

来源：Overview of Artificial Neural Networks and its Applications. (2018). medium.com.

强化学习技术

强化学习是一种试错方法，其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划（Dynamic Programming）。流行的强化学习方法包括自适应动态规划（ADP）、时间差分（TD）学习、状态-动作-回报-状态-动作（SARSA）算法、Q 学习、深度强化学习（DQN）；其应用包括下棋类游戏、机器人控制和工作调度等。

来源：机器之心

深度神经网络技术

深度神经网络（DNN）是深度学习的一种框架，它是一种具备至少一个隐层的神经网络。与浅层神经网络类似，深度神经网络也能够为复杂非线性系统提供建模，但多出的层次为模型提供了更高的抽象层次，因而提高了模型的能力。

来源：机器之心 Techopedia