Generate problem data
rand('seed', 0)
randn('seed', 0)
n = 30
m = 10
A = randn(m,n)
x = sprandn(n, 1, 0.1*n)
b = A*x
xtrue = x
Solve problem
[x history] = basis_pursuit(A, b, 1.0, 1.0)
深度学习网络模型从卷积层到全连接层存在着大量冗余的参数，大量神经元激活值趋近于0，将这些神经元去除后可以表现出同样的模型表达能力，这种情况被称为过参数化，而对应的技术则被称为模型剪枝。
网络剪枝的过程主要分以下几步：
在实践过程中我们可以感受到大的网络比小的网络更容易训练，而且也有越来越多的实验证明大的网络比小的网络更容易收敛到全局最优点而不会遇到局部最优点和鞍点的问题。解释这一想象的一个假设是大乐透假设（Lottery Ticket Hypothesis）。
在下图中，首先我们使用一个大的网络然后随机初始化一组参数，这组参数用红色表示，然后训练后得到紫色的参数，接着进行网络剪枝。我们再尝试使用剪枝的网络结构随机初始化一组参数然后训练发现这种方式没能取得剪枝得到的效果，而如果用大的网络中对应的初始化参数来初始化这个剪枝的网络结构然后再进行训练，就发现可以取得较好的效果：
大乐透假设可以用来解释这个现象，在买大乐透时买得越多就越容易中奖，同样的这里我们假设一个大的网络中包含很多小的网络，这些小的网络结构有的可以训练成功而有的不可以训练成功，只要有一个训练成功，整个大的网络结构就可以训练成功，因此我们可以把多余的网络结构剪枝掉。
与大乐透假设不同的是《Rethinking the Value of Network Pruning》这篇得出了与其看似矛盾的假设。在下表中的实验中使用了不同的模型进行试验，表中Fined-tuned表示剪枝后的模型，Scratch-E和Scratch-B表示随机初始化剪枝网络的参数后训练的模型，只是Scratch-B训练了更多的epoch。可以看到随机初始化剪枝网络的参数后训练的模型也取得了不错的效果，这样就看起来和大乐透假设的实验结果相矛盾。事实上两篇paper的作者均对这种结果进行了回应，可以在网上找到回应的内容，这里不做赘述。
在进行网络剪枝时我们可以选择剪枝权重或者剪枝神经元。下图中进行了权重的剪枝：
剪枝权重的问题是会造成网络结构的不规则，在实际操作中很难去实现也很难用GPU去加速。下图展示了对AlexNet进行weight pruning后使用不同的GPU加速的效果，折线表示了对每一层的权重的剪枝的比例，被剪掉的权重大约占比95%左右，然后使用不同GPU加速发现加速效果并不好，这是因为剪枝做成了网络结构的不规则，因此难以用GPU进行加速。在进行实验需要使用weight pruning时可以使用将被剪枝的权重设置成0的方法。
而使用Neuron pruning就不会遇到上述问题，Neuron pruning后的网络结构仍然是规则的，因此仍然可以使用GPU进行加速。
其中重点在于两个，一个是如何评估一个连接的重要性，另一个是如何在剪枝后恢复模型的性能。
由于特征的输出是由输入与权重相乘后进行加权，权重的幅度越小，对输出的贡献越小，因此一种最直观的连接剪枝方法就是基于权重的幅度，如L1/L2范数的大小。这样的方法只需要三个步骤就能完成剪枝
当然这类框架还有可以改进之处，比如Dynamic network surgery框架[4]观察到一些在当前轮迭代中虽然作用很小，但是在其他轮迭代中又可能重要，便在剪枝的基础上增加了一个spliciing操作，即对一些被剪掉的权重进行恢复，如下：
基于权重幅度的方法原理简单，但这是比较主观的经验，即认为权重大就重要性高，事实上未必如此。而另一种经典的连接剪枝方法就是基于优化目标，根据剪枝对优化目标的影响来对其重要性进行判断，以最优脑损伤(Optimal Brain Damage, OBD)方法为代表，这已经是上世纪90年代的技术了。
Optimal Brain Damage首先建立了一个误差函数的局部模型来预测扰动参数向量对优化目标造成的影响。具体来说用泰勒级数来近似目标函数E，参数向量U的扰动对目标函数的改变使用泰勒展开后如下：
其中gi是优化目标对参数u的梯度，而h是优化目标对参数u的海森矩阵。对模型剪枝的过程是希望找到一个参数集合，使得删除掉这个参数集合之后损失函数E的增加最小，由于上面的式子需要求解损失函数的海森矩阵H，这是一个维度为参数量平方的矩阵，几乎无法进行求解，为此需要对问题进行简化，这建立在几个基本假设的前提上：
经过简化后只剩下了第二项，只需要计算H矩阵的对角项。它可以基于优化目标对连接权重的导数进行计算，复杂度就与梯度计算相同了，如下：
计算完之后就可以得到连接对优化目标改变的贡献，这就是它的重要性，因此可以进行剪枝，整个流程如下：
相对于连接权重剪枝，粗粒度剪枝其实更加有用，它可以得到不需要专门的算法支持的精简小模型。对滤波器进行剪枝和对特征通道进行剪枝最终的结果是相同的，篇幅有限我们这里仅介绍特征通道的剪枝算法代表。
通道剪枝算法有三个经典思路。第一个是基于 重要性因子 ，即评估一个通道的有效性，再配合约束一些通道使得模型结构本身具有稀疏性，从而基于此进行剪枝。第二个是利用 重建误差 来指导剪枝，间接衡量一个通道对输出的影响。第三个是基于 优化目标的变化 来衡量通道的敏感性。下面我们重点介绍前两种。
Network Trimming通过激活的稀疏性来判断一个通道的重要性，认为拥有更高稀疏性的通道更应该被去除。它使用batch normalization中的缩放因子γ来对不重要的通道进行裁剪，如下图：
具体实现起来，就是在目标方程中增加一个关于γ的正则项，从而约束某些通道的重要性。
类似的框架还有
与基于权重幅度的方法来进行连接剪枝一样，基于重要性因子的方法主观性太强，而另一种思路就是基于输出重建误差的通道剪枝算法，它们根据输入特征图的各个通道对输出特征图的贡献大小来完成剪枝过程，可以直接反映剪枝前后特征的损失情况。
如上图，基于重建误差的剪枝算法，就是在剪掉当前层B的若干通道后，重建其输出特征图C使得损失信息最小。假如我们要将B的通道从c剪枝到c'，要求解的就是下面的问题，第一项是重建误差，第二项是正则项。
第一步：选择候选的裁剪通道。
我们可以对输入特征图按照卷积核的感受野进行多次随机采样，获得输入矩阵X，权重矩阵W，输出Y。然后将W用训练好的模型初始化，逐渐增大正则因子，每一次改变都进行若干次迭代，直到beta稳定，这是一个经典的LASSO回归问题求解。
第二步：固定beta求解W，完成最小化重建误差，需要更新使得下式最小。
这类方法采用训练的方式，结合各种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]为代表。
有采用各种剪枝方法的就有和这些剪枝方法对着干的。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)，等等等等等......
一脉梳理下来感觉做纯的剪枝感觉很难了，对比人工设计的结构和准则，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
