论文通过 DBTD 办法计算过滤阈值，再联合随机剪枝算法对特征值梯度进行裁剪，稠密化特征值梯度，可能升高回传阶段的计算量，在 CPU 和 ARM 上的训练别离有 3.99 倍和 5.92 倍的减速成果
 
起源：晓飞的算法工程笔记 公众号

** 论文: Accelerating CNN Training by Pruning
Activation Gradients**

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

Introduction

  在训练过程中，特征值梯度的回传和权值梯度的计算占了大部分的计算耗费。因为这两个操作都是以特征值梯度作为输出，而且零梯度不会占用计算资源，所以稠密化特征值梯度能够升高回传阶段的计算耗费以及内存耗费。论文的指标在于高效地升高训练负载，从而在资源无限的平台进行大规模数据集的训练。
  论文假如特征值梯度遵从正态分布，基于此计算阈值 $\tau$，随后应用随机剪枝算法 (stochastic pruning) 将小于阈值的特征值梯度随机置为零或 $\pm \tau$。经实践推理和试验证实，这种办法不仅可能无效地稠密化特征值梯度，还能在减速训练的同时，不影响训练的收敛性。

General Dataflow

  卷积层通常蕴含 4 个阶段：推理、特征值梯度回传、权值梯度计算和权值更新。为了示意这些阶段的计算，论文定义了一些符号：

  卷积层的四个训练阶段的总结为：

  论文通过可视化发现，回传阶段的特征值梯度简直全是十分小的、接近于零的值，自然而然地想到将这些值去掉不会对权值更新阶段造成很大的影响，所以论文认为剪枝特征值梯度可能减速卷积层在训练时的计算。

Sparsification Algorithms

Distribution Based Threshold Determination (DBTD)

  剪枝操作最要害的步骤是决定抉择哪些元素进行打消，先前有钻研应用最小堆进行元素抉择，但这会带来较大的额定计算开销。为此，论文采纳简略的阈值过滤进行元素抉择。

  论文首先剖析了两种经典的卷积网络结构的特征值梯度散布：Conv-ReLU 构造和 Conv-BN-ReLU 构造：

• 对于 Conv-ReLU 构造，输入的特征值梯度 $dO$ 是稠密的，但其散布是无规律的，而构造的输出特征值梯度 $dI$ 简直全是非零值。通过统计发现，$dI(\cdot)$ 的散布以零值对称散布，且密度随着梯度值的减少而降落。
• 对于 Conv-BN-ReLU 构造，BN 层设置在卷积层与 ReLU 层两头，扭转了梯度的散布，且 $dO$ 的散布与 $dI$ 相似，。

  所以，上述的两种构造的梯度都可认为遵从零均值、方差为 $\sigma^2$ 的正态分布。对于 Conv-ReLu 构造，因为 ReLU 不会升高稠密性，$dO$ 可能继承 $dI$ 的稠密性，将 $dI$ 是作为 Conv-ReLU 构造中的剪枝指标梯度 $g$。而对于 Conv-BN-ReLU 构造，则将 $dO$ 作为剪枝指标 $g$。这样，两种构造的剪枝指标都可对立为正态分布。假如 $g$ 的数量为 $n$，能够计算梯度的绝对值的均值，并失去该均值的冀望为：

  这里的冀望为从散布中采样 $n$ 个点的冀望，而非散布的整体冀望，再定义以下公式

  将公式 2 代入公式 1 中，能够失去：

  从公式 3 能够看出 $\tilde{\sigma}$ 为参数 $\sigma$ 的无偏预计，靠近于实在的均值，且 $\tilde{\sigma}$ 的整体计算耗费是能够承受的。基于下面的剖析，论文联合正态分布的累积函数 $\Phi$、剪枝率 $p$ 和 $\tilde{\sigma}$ 计算阈值 $\tau$：

Stochastic Pruning

  剪枝大量值较小的梯度简直对权值的更新没有影响，但如果将这些值较小的梯度全副设为零，则会对特征值梯度的散布影响很大，进而影响梯度更新，造成重大的精度损失。参考 Stochastic Rounding 算法，论文采纳随机剪枝来解决这个问题。

  随机剪枝逻辑如算法 1 所示，对于小于阈值 $\tau$ 的梯度值，随机采样一个缩放权重来计算新阈值，再依据新阈值将梯度值置为零或 $\pm \tau$。

  随机剪枝的成果如图 2 所示，可能在放弃梯度散布的数学冀望的状况下进行剪枝，与以后的办法相比，论文提出的办法的长处如下：

• Lower runtime cost：DBTD 的计算复杂度 $O(n)$ 小于 top- k 算法 $O(nlogk)$，且 DBTD 对硬件更敌对，可能在异构平台实现。
• Lower memory footprint：随机裁剪能放弃收敛性，且不须要存储而外的内存。

  至此，Sparsification Algorithms 在梯度回传时的特征值梯度计算为：

Experimental Results

  在 CIFAR-10、CIFAR-100 以及 ImageNet 上进行准确率验证。

  在 CIFAR-10 和 ImageNet 上进行收敛性验证。

  在不同的设施上进行减速成果验证。

Conclustion

  论文通过 DBTD 办法计算过滤阈值，再联合随机剪枝算法对特征值梯度进行裁剪，稠密化特征值梯度，可能升高回传阶段的计算量，在 CPU 和 ARM 上的训练别离有 3.99 倍和 5.92 倍的减速成果。论文提出的特征值稠密化算法看似很简略，其实进行了充沛的实践推导以及试验验证，才失去最终正当的过滤办法，惟一惋惜的是没在 GPU 设施上进行试验验证。论文对算法的收敛性以及冀望有具体的实践验证，不过这里没有列出来，有趣味的能够去看看原文。

如果本文对你有帮忙，麻烦点个赞或在看呗～
更多内容请关注 微信公众号【晓飞的算法工程笔记】