我们有将模型部署在资源受限的设备上的需求，比如很多移动设备，在这些设备上有受限的存储空间和受限的计算能力。由此带来深度学习面临的挑战：模型大小越来越大，难以在移动设备更新；所需要的训练时间越来越长（即使在大型设备上）；能耗越来越大（模型越大，需要的访存操作也越多，能耗大头）。因此要压缩空间大小、加快计算速度等。

解决办法：算法和硬件的协同设计Improve the Efficiency of Deep Learning by Algorithm-Hardware Co-Design

高效推断的算法

Pruning模型剪枝

神经网络的参数有很多，但其中有些参数对最终的输出结果贡献并不大，相反就显得冗余，将这些冗余的参数剪掉的技术称为剪枝。

剪枝可以从权重入手，也可以从神经元入手。剪枝可以减小模型大小、提升运行速度，还可以防止过拟合，同时保持准确度基本不变。还可以减少访存，节能。

步骤

训练一个大的模型
评估权重或神经元的重要性
1. 每个参数的重要性
  - 看绝对值大小
  - 套用Life-long learning的思想，计算bi 的值
2. 每个神经元的重要性
  - 计算神经元输出不为0的次数
（对权重或者神经元的重要性进行排序），移除不重要的参数或神经元，减小模型大小。经过剪枝，模型性能会下降
使用原来的训练数据微调剩余的参数
循环进行

为了不会使剪枝造成模型效果的过大损伤，每次不会一次性剪掉太多的权重或神经元，因此这个过程需要迭代，也就是说剪枝且微调一次后，如果剪枝后的模型大小还不令人满意，就迭代上述过程直到满意为止。

下图一直剪掉了90%的权重

下面把模型剪了95%就不行了

剪去参数——形状不规则

剪枝权重的问题是会造成网络结构的不规则（每个节点的输出和输出节点数都会变得不规则），在实际操作中很难去实现，也很难用GPU去加速矩阵运算。实际上是使用0来代替被剪掉的权重，模型实际上没有变小

实验结果表明，即使剪掉95%的参数，但是运算时大多数时候加速比小于1，并没有变得更快。

剪去神经元——形状仍然规则

删减neuron之后网络结构能够保持一定的规则，实现起来方便，而且也能起到一定的加速作用。

通过上述可知，实际上做weight pruning是很麻烦的，通常我们都进行neuron pruning，可以更好地进行implement，也很容易进行speedup。

Why Pruning

先要训练一个大的Network，然后再去把它变小，得到的小 Network 跟大 Network正確率沒有差太多，为什么不直接训练一个小的Network呢？因为一个大的Network比较容易训练。

解释：大乐透假说

大的 Network可以視為是很多小的 Sub-network 的組合。當我們去訓練這個大的 Network 的時候，等於是在訓練很多小的 Network。

一個小的 Network不一定可以成功的被訓練出來，不一定可以通过 Gradient Descent找到一個好的 Solution讓它的 Loss 變低。但是对于大量的 Sub-network，只要其中一個成功，大的 Network 就成功了。那么大的 Network 裡面，如果包含的小的 Network 越多，就好像是去買樂透的時候，買比較多的彩券一樣，彩券越多，中獎的機率就越高。所以一個 Network 越大，它就越有可能成功的被訓練起來。

Pruning Changes Weight Distribution

Weight clustering 聚类权重

若干个比较接近的权重分为一类，用一个数（平均）来代替这一群数据，这样对于一个模型就只需要记录：

模型的每一个参数属于哪一个类：如果只有4群，用2bit的数字即可表示。
每一群参数使用哪一个数字来代替：用一个表进行记录

于是每个参数用更少的位数存储。结果是会导致误差变大，不过也有可能避免数字太精准可能导致的过拟合。

左边表示网络中正常权重矩阵，将相近权值聚为一类，得到一个聚类中心（centroids）向量，权重矩阵存储的是类别号，只需要2个bit，而不是整个32位浮点数，存储空间下降。得到梯度后，将梯度按照权重类别（cluster index）分类，求和得到梯度向量，乘以学习率，再从原始的权重中心减去权值，得到新的权重中心向量，完成一个随机梯度下降迭代

经过处理，权值由左边的连续变成了右边的离散。对权重离散值取对数可以知道只需要多少位的数来标识权重。训练中权重会被调节（adjust），这种微小的调整可以补偿准确率的损失

需要保留多少位：CNN：到4位以下，准确度才开始下降；FC：2位

Pruning + Trained Quantization Work Together：将这两种方法结合到一起，我们会发现，在不影响准确率的要求下，单个方法可以将模型压缩到10％，而两个方法同时用可以压缩到3％。

霍夫曼编码

对于每个类别的“类别号”，用较长的编码表示不常出现的权重，用较短的编码表示常出现的权重

在不影响准确率的要求下，这三种方法联合使用可以降低10到49倍的模型复杂度。

即使对于小模型也很有效

Quantization量化理论

广泛应用于TPU设计（TPU只使用8位来推断）。这一部分没有看懂。。。

步骤：

• Train with float 用标准浮点数训练网络
• Quantizing the weight and activation:
• Gather the statistics for weight and activation 如最大值、最小值、需要多少位数来表示该范围
• Choose proper radix point position 用这些位数表示整数，剩下的位数表示其他部分
• Fine-tune in float format
• Convert to fixed-point format 用定点数前向传播，用浮点数反向传播并更新权值

使用8位数，模型准确率下降不大

Qiu et al. Going Deeper with Embedded FPGA Platform for Convolutional Neural Network, FPGA’16

Low Rank Approximation低秩近似

全连接层

左边是一个普通的全连接层，输入有 N 个 Neuron，输出有 M 个 Neuron，两层之间的参数量W就是 N x M ，只要 N 跟 M 其中一者很大，这个 W 的参数量就会很大。

为了减少参数量，可以在 N 跟 M 中间再插一层，这一层 Neuron 的数目是 K。

原来一层的 Network，参数量是 M x N；现在拆成两层 Network，第一层U的参数量是 N x K，第二层V是 K x M。如果你 K 远小于 M 跟 N，那U 跟 V 的参数量加起来，比 W 还要少的多，所以插入一层后参数减少了。

限制：低秩近似之所以叫低秩，是因为原来的矩阵的秩最大可能是min(M,N)，而新增一层后可以看到矩阵U和V的秩都是小于等于K 的，矩阵秩运算公式rank(AB)≤min(rank(A),rank(B))，所以相乘之后的矩阵的秩一定是小于等于K 。
那么这样会带来什么影响呢？那就是原先全连接层能表示更大的空间，而现在只能表示小一些的空间，会限制原来的NN能做的事情。