模型剪枝算法综述笔记

今天把最近看的一批模型剪枝相关论文整理了一下，方法大体可以分为三类：预定义结构剪枝、自动结构剪枝和非结构化剪枝。

先提一篇引发思考的文章：它做了大量对比实验，结论是——如果剪枝后的网络结构是预先定义好的，那么直接从头（scratch）训练这个瘦网络就能得到比较好的结果，没有必要再走那套繁琐的「预训练 → 剪枝 → fine-tune」流程。实验覆盖了 Predefined Structured Pruning、Automatic Structured Pruning、Unstructured Magnitude-based Pruning 三个方向。

预定义结构化剪枝

这类方法的共同点是：在执行剪枝之前，先由人工或通过敏感性分析确定每一层要删掉多少比例的 filter/channel，算法只负责在给定比例内找「最不重要」的那些。

L1 剪枝

论文：Pruning Filters for Efficient ConvNets

最直接的做法：把 L1 范数最小的卷积核直接去掉，相当于砍掉下一层的 channel 数。每层的剪枝比例是固定的，依赖事先做好的敏感性分析——逐层单独剪枝，在验证集上测精度；再对剪后的单层重新训练，再测精度，由此确定每层对剪枝的容忍度。如果没有预训练模型，这套流程意义不大，还不如重新训练。

ThiNet

论文：ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression

目标是：剪掉第 L 层的若干 filter 后，尽量保持第 L+2 层的输入（即第 L+1 层的输出）不变。删掉 L 层的 filter 后，L+1 层对应的输入 channel 数和 filter channel 数也随之减小。

做法是用贪心算法在第 L+1 层的输出里找对整体影响最小的 channel——按 feature map 维度和 batch 维度上绝对值之和排序，逐步去掉影响最小的那个。需要优化的式子如下（m 是分辨率 × channel 数 × batch 大小）：

\arg\min_{T} \sum_{i=1}^{m}\left(\sum_{j\in T}\hat{\mathbf{x}}_{i,j}\right)^2 \quad\text{s.t.}\quad |T| = C\times(1-r),\ T\subset\{1,2,\dots,C\}

使用的贪心算法如下：

Algorithm 1: A greedy algorithm for minimizing Eq. 6.
Input:  Training set {(x̂_i, ŷ_i)}, and compression rate r.
Output: The subset of removed channels T.
 1: T ← ∅;  I ← {1, 2, ..., C};
 2: while |T| < C × (1 − r) do
 3:     min_value ← +∞;
 4:     for each item i ∈ I do
 5:         tmpT ← T ∪ {i};
 6:         compute value from Eq. 6 using tmpT;
 7:         if value < min_value then
 8:             min_value ← value;  min_i ← i;
 9:         end if
10:     end for
11:     move min_i from I into T;
12: end while

LASSO 回归剪枝

论文：Channel Pruning for Accelerating Very Deep Neural Networks

出发点和 ThiNet 类似，同样是希望剪掉某些 channel 后让下游层响应尽量不变，但用 LASSO 回归的稀疏正则项替代了贪心搜索。对每个 channel 引入加权系数 β，目标是让 β 尽可能稀疏，同时保持重建误差最小。N 是采样的卷积输入块数量，Y 是 N×n 的特征矩阵：

\arg\min_{\boldsymbol{\beta},\mathbf{W}} \frac{1}{2N}\left\lVert\mathbf{Y}-\sum_{i=1}^{c}\beta_i \mathbf{X}_i \mathbf{W}_i^{\top}\right\rVert_F^2 + \lambda\lVert\boldsymbol{\beta}\rVert_1 \quad\text{s.t.}\quad \lVert\boldsymbol{\beta}\rVert_0 \le c',\ \forall i\ \lVert\mathbf{W}_i\rVert_F = 1

求解采用交替优化，分两步：

Step 1：固定 w，优化 β，直接当作 LASSO 回归问题求解：

\hat{\boldsymbol{\beta}}^{\mathrm{LASSO}}(\lambda) = \arg\min_{\boldsymbol{\beta}} \frac{1}{2N}\left\lVert\mathbf{Y}-\sum_{i=1}^{c}\beta_i \mathbf{Z}_i\right\rVert_F^2 + \lambda\lVert\boldsymbol{\beta}\rVert_1 \quad\text{s.t.}\quad \lVert\boldsymbol{\beta}\rVert_0 \le c'

Step 2：固定 β，优化 w：

\arg\min_{\mathbf{W}'}\left\lVert\mathbf{Y}-\mathbf{X}'(\mathbf{W}')^{\top}\right\rVert_F^2

与 ThiNet 的主要区别就在求解算法上，这里是交替优化而不是贪心枚举。

自动结构化剪枝

这类方法不需要人工指定每层的剪枝比例，训练过程本身会决定哪些 channel 该去掉，某种程度上可以看作轻量级的 NAS。

Network Slimming

论文：Learning Efficient Convolutional Networks through Network Slimming

在 BN 层的缩放参数（γ）上加 L1 正则化。由于 BN 层的 weight 是在 channel 维度上独立作用的，某个 channel 对应的 γ 趋近于零就意味着这个 channel 的输出几乎被压制，可以直接剪掉。

与 L1 filter pruning 的关键区别：Network Slimming 的阈值是对所有 BN 层的 γ 做全局排序后得出的，而 L1 剪枝是在每层内部做相对排序。前者不需要人工指定每层的压缩比，结构自动涌现。L1 不可导，实现时直接对梯度做操作（次梯度），用普通 SGD 即可收敛。

Sparse Structure Selection

论文：Data-Driven Sparse Structure Selection for Deep Neural Networks

思路与 Network Slimming 类似，通过数据驱动的稀疏正则化让网络自动选择结构。

其他值得关注的方法

AOFP（ICML 2019）

论文：Approximated Oracle Filter Pruning for Destructive CNN Width Optimization

用二分搜索来定位最不重要的 channel，通过多次随机采样估计每个 channel 对下一层输出的影响，然后剪掉影响较小的 channel。用采样来近似估计影响量，避免枚举所有组合，这个思路挺值得借鉴的。

NISP

论文：NISP: Pruning Networks Using Neuron Importance Score Propagation

同样是预定义每层剪枝比例，再按某种重要性分数进行剪枝，属于预定义类方法的变体。

SNIP

论文：SNIP: Single-Shot Network Pruning Based on Connection Sensitivity

非结构化剪枝，直接剪掉 loss 对 mask 梯度最小的连接——即对 loss 最不敏感的 weight。其中 s 是敏感度，用近似微分来得到：

Algorithm 1: SNIP — Single-shot Network Pruning based on Connection Sensitivity.
Require: Loss function L, training dataset D, sparsity level κ.  (Refer Equation 3)
Ensure:  ||w*||_0 ≤ κ
1: w ← VarianceScalingInitialization                        (Refer Section 4.2)
2: D^b = {(x_i, y_i)}_{i=1}^{b} ∼ D                          (Sample a mini-batch of training data)
3: s_j ← |g_j(w; D^b)| / Σ_{k=1}^{m} |g_k(w; D^b)|,  ∀j ∈ {1...m}   (Connection sensitivity)
4: s̃ ← SortDescending(s)
5: c_j ← 1[ s_j − s̃_κ ≥ 0 ],  ∀j ∈ {1...m}                  (Pruning: choose top-κ connections)
6: w* ← arg min_{w∈ℝ^m} L(c ⊙ w; D)                         (Regular training)
7: w* ← c ⊙ w*

这样只需一次 backward 就能算出所有 weight 的敏感度，不需要多次 forward：

\Delta L_j(\mathbf{w};\mathcal{D}) \approx g_j(\mathbf{w};\mathcal{D}) = \left.\frac{\partial L(\mathbf{c}\odot\mathbf{w};\mathcal{D})}{\partial c_j}\right|_{\mathbf{c}=\mathbf{1}} = \left.\lim_{\delta\to 0}\frac{L(\mathbf{c}\odot\mathbf{w};\mathcal{D}) - L((\mathbf{c}-\delta\,\mathbf{e}_j)\odot\mathbf{w};\mathcal{D})}{\delta}\right|_{\mathbf{c}=\mathbf{1}}

Autopruner

论文：Autopruner: An End-to-End Trainable Filter Pruning Method for Efficient Deep Model Inference

不用简单的惩罚项来驱动稀疏，而是用额外的网络结构来预测每个 filter 的 mask。对 sigmoid 做了改造，逐渐增大 α 使激活值越来越接近 0/1 编码，相当于用神经网络激活值直接充当 mask，这样可以端到端用反向传播找到最佳编码。缺点是压缩率不易控制，还需要额外措施。

整体框架如下：

AutoPruner 层的整体框架示意图 — 图：AutoPruner 层的框架。对一个 mini-batch 的激活张量 $X \in \mathbb{R}^{N \times C \times H \times W}$ 先做 batch-wise average pooling 与 max pooling 得到单个张量，再经全连接层投影成 $C$ 维向量，最后用 scaled sigmoid $y = \mathrm{sigmoid}(\alpha x)$ 得到近似二值的编码（逐渐增大 $\alpha$ 使其趋于 0/1）。该编码与原激活逐元素相乘，对应 0 的 filter/channel 在训练后被裁掉，AutoPruner 层本身也随之移除。

压缩率的控制通过在 loss 中加正则项实现，v 是编码向量，C 是向量长度，r 是目标保留比例：

\min\ \mathcal{L}_{\text{classification}} + \lambda\left\lVert\frac{\lVert\mathbf{v}\rVert_1}{C} - r\right\rVert_2^2

其他备忘

ISTA-based（Rethinking the Smaller-Norm-Less-Informative Assumption in Channel Pruning of Convolution Layers）：暂跳过，看着很费劲，之后再补。
C-SGD（Centripetal SGD for Pruning Very Deep Convolutional Networks with Complicated Structure）：针对 ResNet 这类有复杂跳接结构的网络设计。
AMC（AMC: AutoML for Model Compression and Acceleration on Mobile Devices）：用 DDPG 搜索每层的压缩比超参，把确定「剪多少」这件事也交给强化学习来解决。
SFP（Soft Filter Pruning for Accelerating Deep Convolutional Neural Networks）、CFP、GDP、SSR-L2、DCP 等：记下来，后续有时间细读。
Influence Functions（Understanding Black-Box Predictions via Influence Functions）：好像也是利用求导找敏感度，和 SNIP 的思路有相通之处。

小结

结构化剪枝（无论预定义还是自动）在硬件加速上更友好，能直接缩小网络规模；非结构化剪枝虽然理论压缩比更高，但稀疏矩阵在常规 GPU 上难以真正加速，实用价值有限。自动结构剪枝和 NAS 越来越接近，Network Slimming 用稀疏正则、AMC 用强化学习，分别代表两种搜索结构的路线，是目前看来比较有意思的方向。

另外，今天还看了 MixMatch 的论文，把 CSAPP 第三章看完了，收获不少。

论文笔记
剪枝
模型压缩

2019 · 05 · 23