一、剪枝方法简介
剪枝就是通过去除网络中冗余的channels,filters, neurons, or layers以得到一个更轻量级的网络，同时不影响性能。 代表性的工作有：
奇异值分解SVD(NIPS 2014)： Exploiting linear structure within convolutional networks for efficient evaluation
韩松(ICLR 2016)： Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding
(NIPS 2015)： Learning both weights and connections for efficient neural network
频域压缩(NIPS 2016)： Packing convolutional neural networks in the frequency domain
剪Filter Reconstruction Error(ICCV 2017)： Thinet: A filter level pruning method for deep neural network compression
LASSO regression(ICCV 2017)： Channel pruning for accelerating very deep neural networks
Discriminative channels(NIPS 2018)： Discrimination-aware channel pruning for deep neural networks
剪枝(ICCV 2017)： Channel pruning for accelerating very deep neural networks
neuron level sparsity(ECCV 2017)： Less is more: Towards compact cnns
Structured Sparsity Learning(NIPS 2016)： Learning structured sparsity in deep neural networks
网络剪枝的步骤神经网络中的一些权重和神经元是可以被剪枝的，这是因为这些权重可能为零或者神经元的输出大多数时候为零，表明这些权重或神经元是冗余的。
模型剪枝是一个新概念吗？并不是，其实我们从学习深度学习的第一天起就接触过，Dropout和DropConnect代表着非常经典的模型剪枝技术，
模型剪枝不仅仅只有对神经元的剪枝和对权重连接的剪枝，根据粒度的不同，至少可以粗分为4个粒度。
1.细粒度剪枝(fine-grained)：即对连接或者神经元进行剪枝，它是粒度最小的剪枝。
2.向量剪枝(vector-level)：它相对于细粒度剪枝粒度更大，属于对卷积核内部(intra-kernel)的剪枝。
3.核剪枝(kernel-level)：即去除某个卷积核，它将丢弃对输入通道中对应计算通道的响应。
4.滤波器剪枝(Filter-level)：对整个卷积核组进行剪枝，会造成推理过程中输出特征通道数的改变。
image.png
细粒度剪枝(fine-grained)，向量剪枝(vector-level)，核剪枝(kernel-level)方法在参数量与模型性能之间取得了一定的平衡，但是网络的拓扑结构本身发生了变化，需要专门的算法设计来支持这种稀疏的运算，被称之为非结构化剪枝。
而滤波器剪枝(Filter-level)只改变了网络中的滤波器组和特征通道数目，所获得的模型不需要专门的算法设计就能够运行，被称为结构化剪枝。除此之外还有对整个网络层的剪枝，它可以被看作是滤波器剪枝(Filter-level)的变种，即所有的滤波器都丢弃。
深度学习网络模型从卷积层到全连接层存在着大量冗余的参数，大量神经元激活值趋近于0，将这些神经元去除后可以表现出同样的模型表达能力，这种情况被称为过参数化，而对应的技术则被称为模型剪枝。
1.剪枝步骤
网络剪枝的过程主要分以下几步：
①训练网络；
②评估权重和神经元的重要性：可以用L1、L2来评估权重的重要性，用不是0的次数来衡量神经元的重要性；
③对权重或者神经元的重要性进行排序然后移除不重要的权重或神经元；
④移除部分权重或者神经元后网络的准确率会受到一些损伤，因此我们要进行微调，也就是使用原来的训练数据更新一下参数，往往就可以复原回来；
⑤为了不会使剪枝造成模型效果的过大损伤，我们每次都不会一次性剪掉太多的权重或神经元，因此这个过程需要迭代，也就是说剪枝且微调一次后如果剪枝后的模型大小还不令人满意就回到步骤后迭代上述过程直到满意为止
2.为什么可以进行网络剪枝
在实践过程中我们可以感受到大的网络比小的网络更容易训练，而且也有越来越多的实验证明大的网络比小的网络更容易收敛到全局最优点而不会遇到局部最优点和鞍点的问题。解释这一想象的一个假设是大乐透假设（Lottery Ticket Hypothesis）。
（1）大乐透假设
在下图中，首先我们使用一个大的网络然后随机初始化一组参数，这组参数用红色表示，然后训练后得到紫色的参数，接着进行网络剪枝。我们再尝试使用剪枝的网络结构随机初始化一组参数然后训练发现这种方式没能取得剪枝得到的效果，而如果用大的网络中对应的初始化参数来初始化这个剪枝的网络结构然后再进行训练，就发现可以取得较好的效果：
大乐透假设可以用来解释这个现象，在买大乐透时买得越多就越容易中奖，同样的这里我们假设一个大的网络中包含很多小的网络，这些小的网络结构有的可以训练成功而有的不可以训练成功，只要有一个训练成功，整个大的网络结构就可以训练成功，因此我们可以把多余的网络结构剪枝掉。
（2）不需要剪枝，直接来训练小模型
与大乐透假设不同的是《Rethinking the Value of Network Pruning》这篇得出了与其看似矛盾的假设。在下表中的实验中使用了不同的模型进行试验，表中Fined-tuned表示剪枝后的模型，Scratch-E和Scratch-B表示随机初始化剪枝网络的参数后训练的模型，只是Scratch-B训练了更多的epoch。可以看到随机初始化剪枝网络的参数后训练的模型也取得了不错的效果，这样就看起来和大乐透假设的实验结果相矛盾。事实上两篇paper的作者均对这种结果进行了回应，可以在网上找到回应的内容，这里不做赘述。
3.剪枝权重还是剪枝神经元
在进行网络剪枝时我们可以选择剪枝权重或者剪枝神经元。下图中进行了权重的剪枝：
剪枝权重的问题是会造成网络结构的不规则，在实际操作中很难去实现也很难用GPU去加速。下图展示了对AlexNet进行weight pruning后使用不同的GPU加速的效果，折线表示了对每一层的权重的剪枝的比例，被剪掉的权重大约占比95%左右，然后使用不同GPU加速发现加速效果并不好，这是因为剪枝做成了网络结构的不规则，因此难以用GPU进行加速。在进行实验需要使用weight pruning时可以使用将被剪枝的权重设置成0的方法。
而使用Neuron pruning就不会遇到上述问题，Neuron pruning后的网络结构仍然是规则的，因此仍然可以使用GPU进行加速。
二、常见剪枝方法
(一)、细粒度连接剪枝(连接和神经元)
其中重点在于两个，一个是如何评估一个连接的重要性，另一个是如何在剪枝后恢复模型的性能。
1、如何评估一个连接的重要性
基于度量标准的剪枝通常是提出一个判断神经元是否重要的度量标准，依据这个标准计算出衡量神经元重要性的值，将不重要的神经元剪掉。在神经网络中可以用于度量的值主要分为3大块：Weight / Activation / Gradient。各种神奇的组合就产出了各种metric玩法。
（1）基于连接幅度
基于结构化剪枝中比较经典的方法是Pruning Filters for Efficient ConvNets(ICLR2017)，基于L1-norm判断filter的重要性。Filter Pruning via Geometric Median for Deep Convolutional Neural Networks Acceleration(CVPR2019) 把绝对重要性拉到相对层面，认为与其他filters太相似的filter不重要。
由于特征的输出是由输入与权重相乘后进行加权，权重的幅度越小，对输出的贡献越小，因此一种最直观的连接剪枝方法就是基于权重的幅度，如L1/L2范数的大小。这样的方法只需要三个步骤就能完成剪枝
- 第一步：训练一个基准模型。
- 第二步：对权重值的幅度进行排序，去掉低于一个预设阈值的连接，得到剪枝后的网络。
- 第三步：对剪枝后网络进行微调以恢复损失的性能，然后继续进行第二步，依次交替，直到满足终止条件，比如精度下降在一定范围内
当然这类框架还有可以改进之处，比如Dynamic network surgery框架[4]观察到一些在当前轮迭代中虽然作用很小，但是在其他轮迭代中又可能重要，便在剪枝的基础上增加了一个spliciing操作，即对一些被剪掉的权重进行恢复，如下：
（2）基于损失函数
这类方法通常从Loss出发寻找对损失影响最小的神经元。将目标函数用泰勒展开的方法可以追溯到上世纪90年代初，比如Lecun的Optimal Brain Damage 和 Second order derivatives for network pruning: Optimal Brain Surgeon 。近年来比较有代表性的就是Pruning Convolutional Neural Networks for Resource Efficient(ICLR2017)，对activation在0点进行泰勒展开。(是否prune一个卷积核只需要计算这个卷积核中每个权值的梯度与其之积，求和之后再求均值)原作者也很好的向我们展现了如何优雅地进行方法迁移 Importance Estimation for Neural Network Pruning(CVPR2019)，换成weight的展开再加个平方。类似的方法还有 Faster gaze prediction with dense networks and Fisher pruning，用Fisher信息来近似Hessian矩阵。SNIP: Single-shot Network Pruning based on Connection Sensitivity(ICLR2019)则直接利用导数对随机初始化的权重进行非结构化剪枝。相关工作同样可以追溯到上世纪80年代末Skeletonization: A Technique for Trimming the Fat from a Network via Relevance Assessment(NIPS1988)。历史总是惊人的相似：
image.png
基于权重幅度的方法原理简单，但这是比较主观的经验，即认为权重大就重要性高，事实上未必如此。而另一种经典的连接剪枝方法就是基于优化目标，根据剪枝对优化目标的影响来对其重要性进行判断，以最优脑损伤(Optimal Brain Damage, OBD)方法为代表，这已经是上世纪90年代的技术了。
Optimal Brain Damage首先建立了一个误差函数的局部模型来预测扰动参数向量对优化目标造成的影响。具体来说用泰勒级数来近似目标函数E，参数向量U的扰动对目标函数的改变使用泰勒展开后如下：
其中gi是优化目标对参数u的梯度，而h是优化目标对参数u的海森矩阵。对模型剪枝的过程是希望找到一个参数集合，使得删除掉这个参数集合之后损失函数E的增加最小，由于上面的式子需要求解损失函数的海森矩阵H，这是一个维度为参数量平方的矩阵，几乎无法进行求解，为此需要对问题进行简化，这建立在几个基本假设的前提上：
- 参数独立。即删除多个参数所引起的损失的改变，等于单独删除每个参数所引起的损失改变的和，因此上式第三项可以去除。
- 局部极值。即剪枝是发生在模型已经收敛的情况下，因此第一项可以去除，并且hii都是正数，即剪枝一定会带来优化目标函数的增加，或者说带来性能的损失。
- 二次近似假定。即上式关系为二次项，最后一项可以去除。
经过简化后只剩下了第二项，只需要计算H矩阵的对角项。它可以基于优化目标对连接权重的导数进行计算，复杂度就与梯度计算相同了，如下：
计算完之后就可以得到连接对优化目标改变的贡献，这就是它的重要性，因此可以进行剪枝，整个流程如下：
(3)基于激活值
Network trimming: A data-driven neuron pruning approach towards efficient deep architectures 用activations中0的比例 (Average Percentage of Zeros, APoZ)作为度量标准，[输入一张图，经过一层卷积，得到右边的feature map，我们计算，也就是输出的第一个通道的APOZ，也就是右边红色。假设红色的部分一半是0，那么这张图计算就等于50%。我们需要输入多张图，假如输入了1W张图，最后计算红色部分都是50%，那么就等于50%。下面那张table1，计算每一层的mean APOZ的时候，就是把所有通道的都计算出来取平均值]
An Entropy-based Pruning Method for CNN Compression 则利用信息熵进行剪枝。
（二）、粗粒度剪枝核心技术(通道剪枝)
相对于连接权重剪枝，粗粒度剪枝其实更加有用，它可以得到不需要专门的算法支持的精简小模型。对滤波器进行剪枝和对特征通道进行剪枝最终的结果是相同的，篇幅有限我们这里仅介绍特征通道的剪枝算法代表。
通道剪枝算法有三个经典思路。第一个是基于重要性因子，即评估一个通道的有效性，再配合约束一些通道使得模型结构本身具有稀疏性，从而基于此进行剪枝。第二个是利用重建误差来指导剪枝，间接衡量一个通道对输出的影响。第三个是基于优化目标的变化来衡量通道的敏感性。下面我们重点介绍前两种。
1. 基于重要性因子
（1）将激活的稀疏性当做重要性因子
Network Trimming通过激活的稀疏性来判断一个通道的重要性，认为拥有更高稀疏性的通道更应该被去除。它使用batch normalization中的缩放因子γ来对不重要的通道进行裁剪，如下图：
具体实现起来，就是在目标方程中增加一个关于γ的正则项，从而约束某些通道的重要性。
（2）将几何中位数对范数当做重要性因子Geometric Median
（3）其他方法
类似的框架还有
- 《Rethinking the smaller-norm-less-informative assumption in channel pruning of convolution layers》
- 《Data-Driven Sparse Structure Selection
2.基于输出重建误差
与基于权重幅度的方法来进行连接剪枝一样，基于重要性因子的方法主观性太强，而另一种思路就是基于输出重建误差的通道剪枝算法，它们根据输入特征图的各个通道对输出特征图的贡献大小来完成剪枝过程，可以直接反映剪枝前后特征的损失情况。
这类方法通过最小化特征输出的重建误差来确定哪些filters要进行剪裁，即找到当前层对后面的网络层输出没啥影响的信息。ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression 采用贪心法，Channel Pruning for Accelerating Very Deep Neural Networks(ICLR2017) 则采用Lasso regression。NISP: Pruning Networks using Neuron Importance Score Propagation(CVPR2018) 通过最小化网络倒数第二层的重建误差，并将反向传播的误差累积考虑在内，来决定前面哪些filters需要裁剪。
image.png
（1）经典方法
如上图，基于重建误差的剪枝算法，就是在剪掉当前层B的若干通道后，重建其输出特征图C使得损失信息最小。假如我们要将B的通道从c剪枝到c'，要求解的就是下面的问题，第一项是重建误差，第二项是正则项。
第一步：选择候选的裁剪通道。
我们可以对输入特征图按照卷积核的感受野进行多次随机采样，获得输入矩阵X，权重矩阵W，输出Y。然后将W用训练好的模型初始化，逐渐增大正则因子，每一次改变都进行若干次迭代，直到beta稳定，这是一个经典的LASSO回归问题求解。
第二步：固定beta求解W，完成最小化重建误差，需要更新使得下式最小。
（2）ThiNet
（三）基于稀疏训练的剪枝
这类方法采用训练的方式，结合各种regularizer来让网络的权重变得稀疏，于是可以将接近于0的值剪掉。Learning Structured Sparsity in Deep Neural Networks 用group Lasso进行结构化稀疏，包括filters, channels, filter shapes, depth。Data-Driven Sparse Structure Selection for Deep Neural Networks(ECCV2018)通过引入可学习的mask，用APG算法来稀疏mask达到结构化剪枝。A Systematic DNN Weight Pruning Framework using Alternating Direction Method of Multipliers(ECCV2018) 的思想类似，用约束优化中的经典算法ADMM来求解。由于每个通道的输出都会经过BN，可以巧妙地直接稀疏BN的scaling factor，比如 Learning Efficient Convolutional Networks through Network Slimming(ICCV2017) 采用L1 regularizer，Rethinking the Smaller-Norm-Less-Informative Assumption in Channel Pruning of Convolution Layers(ICLR2018) 则采用ISTA来进行稀疏。MorphNet: Fast & Simple Resource-Constrained Structure Learning of Deep Networks(CVPR2018) 也是直接利用L1 regularizer，但是结合了MobileNet中的width-multiplier，加上了shink-expand操作，能够更好的满足资源限制。
（四） 个性化剪枝
通常来说，模型在剪枝完后进行推理时不会发生变化，即对于所有的输入图片来说都是一样的计算量，但是有的样本简单，有的样本复杂，以前我们给大家介绍过动态推理框架，它们可以对不同的输入样本图配置不同的计算量，剪枝框架也可以采用这样的思路，以Runtime Neural Pruning [12]为代表。
（五）Random and Rethinking
有采用各种剪枝方法的就有和这些剪枝方法对着干的。Recovering from Random Pruning: On the Plasticity of Deep Convolutional Neural Networks 就表明了度量标准都没啥用，随机赛高。Rethinking the Value of Network Pruning(ICLR2019) 则表示剪枝策略实际上是为了获得网络结构，挑战了传统的 train-prune-finetune的剪枝流程。Pruning from Scratch 则直接用Network Slimming的方法对训练过程中的剪枝结构进行了一波分析，发现直接采用random初始化的网络权重能够获得更丰富的剪枝结构。
（六）自动化剪枝
剪枝中我们通常遵循一些基本策略：比如在提取低级特征的参数较少的第一层中剪掉更少的参数，对冗余性更高的FC层剪掉更多的参数。然而，由于深度神经网络中的层不是孤立的，这些基于规则的剪枝策略并不是最优的，也不能从一个模型迁移到另一个模型，因此AutoML方法的应用也是非常自然的，AutoML for Model Compression(AMC)是其中的代表
从AMC: AutoML for Model Compression and Acceleration on Mobile Devices[ECCV2018]开始将强化学习引入剪枝，剪枝的研究开始套上各种Auto的帽子，玩法更是层出不穷。AutoSlim: Towards One-Shot Architecture Search for Channel Numbers先训练出一个slimmable model（类似NAS中的SuperNet Once for All: Train One Network and Specialize it for Efficient Deployment），继而通过贪心的方式逐步对网络进行裁剪。
Network Pruning via Transformable Architecture Search(NIPS2019) 则把NAS可导的一套迁移过来做剪枝。Approximated Oracle Filter Pruning for Destructive CNN Width Optimization(ICML2019)平行操作网络的所有层，用二分搜索的方式确定每层的剪枝数。Fine-Grained Neural Architecture Search 把NAS的粒度降到了通道，包含了空的操作即剪枝。还有各种拿进化来做的也就不提了。
此外，还有基于信息瓶颈的方法Compressing Neural Networks using the Variational Information Bottleneck(ICML2018)，聚类的方法Centripetal SGD for Pruning Very Deep Convolutional Networks with Complicated Structure(CPVR2019)，等等等等等......
三、剪枝之外
- 提升精度： 利用剪枝的方式来提升模型精度，比如DSD: Dense-Sparse-Dense Training for Deep Neural Networks(ICLR2017)利用非结构化剪枝，阶段性的砍掉某些权重再恢复。稀疏训练Sparse Networks from Scratch: Faster Training without Losing Performance在训练过程中保持网络的稀疏率不变，动态调整层间的稀疏率。
- 动态结构：不同的输入图片可以走网络中的不同结构。
BlockDrop: Dynamic Inference Paths in Residual Networks(CVPR2018)引入一个Policy Network，以Block为单位进行选择。Dynamic Channel Pruning: Feature Boosting and Suppression(ICLR2019)引入SEBlock，以Channel为单位进行选择。Improved Techniques for Training Adaptive Deep Networks采用截断式的选择，简单的图片采用靠前的网路层解决，复杂的加入后面得网络层。
四、总结
一脉梳理下来感觉做纯的剪枝感觉很难了，对比人工设计的结构和准则，NAS出来的模型可以又小巧精度又高，剪枝也逐渐受其影响快、准、狠地寻找结构。这些效果好的结构和权重背后到底还藏着些什么
常见论文
https://www.cnblogs.com/wujianming-110117/p/12702802.html
https://zhuanlan.zhihu.com/p/157562088
https://zhuanlan.zhihu.com/p/48269250
https://zhuanlan.zhihu.com/p/330575000
