deep compression:compressing deep neural networks with pruning,trained quantization and huffman codi

deep compression:compressing deep neural networks with pruning,trained quantization and huffman coding

摘要

神经网络是计算密集型和内存密集型的，这使得它们很难部署在硬件资源有限的嵌入式系统上。为了解决这个限制，我们引入了“深度压缩”，这是一个三阶段的管道:修剪、训练量化和霍夫曼编码，它们共同工作，在不影响精度的情况下，将神经网络的存储量减少35倍到49倍。我们的方法首先通过只学习重要的连接来精简网络。接下来，我们量化权值以加强权值共享，最后，我们应用霍夫曼编码。在前两个步骤之后，我们重新训练网络以微调剩余的连接和量化的中心。修剪，连接数减少9倍至13倍;然后量化将表示每个连接的比特数从32减少到5。在ImageNet数据集上，我们的方法将AlexNet所需的存储空间减少了35倍，从240MB减少到6.9MB，并且没有丢失准确性。我们的方法将VGG-16的大小减少了49倍，从552MB减少到11.3MB，同样没有丢失准确性。这允许将模型放入片上SRAM缓存中，而不是片外DRAM内存中。我们的压缩方法也便于在应用程序大小和下载带宽受限的移动应用程序中使用复杂的神经网络。以CPU、GPU和移动GPU为基准，压缩网络具有3到4倍的分层加速效果和3到7倍的能效。

引言

深度神经网络已经发展成为计算机视觉任务的最先进技术。虽然这些神经网络非常强大，但大量的权值会消耗相当大的存储空间和内存带宽。例如，AlexNet的Caffemodel超过200MB, VGG-16的Caffemodel超过500MB (BVLC)。这使得在移动系统上部署深度神经网络变得困难。
首先，对于百度和Facebook等许多以移动为优先的公司来说，各种应用程序都是通过不同的应用程序商店更新的，它们对二进制文件的大小非常敏感。例如，App Store有“小于100mb的应用必须连接Wi-Fi才能下载”的限制。因此，将二进制文件大小增加100MB的特性将比增加10MB的特性受到更多的审查。虽然在移动设备上运行的深度神经网络有很多很好的特性，比如更好的隐私性，更少的网络带宽和实时处理，但是巨大的存储开销阻止了深度神经网络被整合到移动应用程序中。

第二个问题是能源消耗。运行大型神经网络需要大量的内存带宽来获取权重，并需要大量的计算来做点积——这反过来会消耗大量的能量。移动设备的电池容量受到限制，使得深度神经网络等耗电应用难以部署。
能源消耗主要是内存访问。在45nm CMOS技术下，32位浮点加法消耗0.9pJ, 32位SRAM缓存访问消耗5pJ, 32位DRAM内存访问消耗640pJ，相当于一次加法操作的3个数量级。大型网络不适合芯片存储，因此需要更昂贵的DRAM访问。例如，以20fps运行一个10亿连接的神经网络，仅仅是DRAM访问就需要(20Hz)(1G)(640pJ) = 12.8W——远远超出了典型移动设备的功率范围。
接下来，权重被量化，以便多个连接共享相同的权重，因此只需要存储码本(有效权重)和索引。最后，我们应用霍夫曼编码来利用有效权值的偏置分布。
我们的主要观点是，剪枝和量化训练能够压缩网络而不相互干扰，从而导致惊人的高压缩率。它使所需的存储如此小(几兆字节)，所有的重量可以缓存在芯片上，而不是去到芯片外DRAM，这是能源消耗。基于“深度压缩”的EIE硬件加速器（Han等）(2016)后提出对压缩模型进行工作，实现了显著的加速和能效提高。

网络剪枝

网络剪枝被广泛研究用于压缩CNN模型。在早期的工作中，网络剪枝被证明是降低网络复杂度和过拟合的有效方法。最近Han等人(2015)在没有丢失准确性的情况下对CNN的最新模型进行了修剪。我们以这种方法为基础。如图1左侧所示，我们首先通过常规的网络训练来学习连接性。接下来，我们删除小权重连接:所有权重低于阈值的连接都从网络中删除。最后，我们对网络进行重新训练，以学习剩余稀疏连接的最终权值。剪枝使AlexNet和VGG网路中的的参数数分别减少了9倍到13倍。

我们存储使用的是压缩稀疏行(CSR)或压缩稀疏列(CSC)格式，存储剪枝得到的稀疏结构，这需要$2a+n+1$个数字，其中$a$为非零元素的个数，n为行数或列数。
为了进一步压缩，我们存储索引差而不是绝对位置，并将这个差在卷积层编码为8位，在全连接层编码为5位。当我们需要一个大于边界的索引差时，我们使用图2所示的零填充解决方案:当差异超过时8，最大的3位(例如)无符号数，我们加一个填充零。

量化训练和权重共享

网络量化和权值共享通过减少表示每个权值所需的比特数，进一步压缩了经过修剪的网络。我们通过让多个连接共享相同的权重来限制需要存储的有效权重的数量，然后对这些共享权重进行微调。
权重共享如图3所示。假设层中有4个输入神经元和4个输出神经元，权值为4×4矩阵。左上角为4×4的权重矩阵，左下角为4×4的梯度矩阵。权重被量化为4个bin(用4种颜色表示)，同一个bin中的所有权重共享相同的值，因此对于每个权重，我们只需将一个小索引存储到共享权重表中。在更新期间，所有的梯度是分组的颜色和累加在一起，乘以学习率和减去共享中心上次迭代的值。对于修剪过的AlexNet，我们能够将每一个量化为8位(256个共享权重)CONV层，和5位(32共享权重)为每个FC层没有任何损失的准确性。

为了计算压缩率，给定k个簇，我们只需要log2 (k)位对索引进行编码。一般情况下，对于有n个连接的网络，每个连接用b比特表示，限制连接只有k个共享权值，压缩率为:
$$r=\frac{nb}{n{\text{log}}_2(k)+kb}$$
例如，图3显示了具有四个输入单元和四个输出单元的单层神经网络的权值。原本有$4\times 4=16$个权重，但只有4个共享权重:相似的权重被分组在一起，共享相同的值。最初我们需要存储16个权重，每个权重有32位，现在我们只需要存储4个有效权重(蓝色、绿色、红色和橙色)，每个权重有32位，加上16个2位索引，压缩率为$16?32/(4?32+2?16)=3.2$

权值共享

我们使用k-means聚类来识别训练过的网络的每一层的共享权值，这样落在同一个聚类中的所有权值将共享相同的权值。权重不跨层共享。我们将n个初始权重值W={ω1,ω2,?,ωn}W=\{\omega_1,\omega_2,\cdots,\omega_n\}W={ ω1?,ω2?,?,ωn?}分成$k$个类C={c1,c2,?,ck},n?kC=\{c_1,c_2,\cdots,c_k\},n\gg kC={ c1?,c2?,?,ck?},n?k,从而最小化群内平方和（WCSS）
$$\begin{array}{r}\text{arg min}\sum _{i=1}^k\sum _{\omega \in c_i}|\omega ?c_i{|}^2\end{array}$$
与HashNet (Chen 等2015)不同，HashNet的权值共享是在网络看到任何训练数据之前由哈希函数确定的，我们的方法是在网络完全训练之后确定权值共享，这样共享的权值就近似于原始网络。

共享权重的初始化

质心初始化影响聚类的质量，进而影响网络的预测精度。我们研究了三种初始化方法:Forgy(随机)，基于密度，和线性初始化。我们绘制了AlexNet中conv3层的原始权重分布(蓝色为CDF，红色为PDF)。网络修剪后权值呈双峰分布。在底部，它用3种不同的初始化方法绘制了有效权重(中心)(以蓝色、红色和黄色显示)。在本例中，有13个集群。

**Forgy(随机)**初始化从数据集中随机选择k个观察值，并使用这些作为初始中心。初始化的中心用黄色显示。由于双峰分布中有两个峰，Forgy方法倾向于集中在这两个峰附近。
基于密度的初始化将权重的CDF在y轴上线性空间，然后找到与CDF的水平交点，最后找到x轴上的垂直交点，成为质心，如图蓝点所示。这种方法使两个峰周围的质心密度更大，但比福吉方法更分散。
线性初始化在原始权重的[最小值，最大值]之间线性地留出中心。与前两种方法相比，该初始化方法不受权重分布的影响，且最分散。
较大的权重比较小的权重起着更重要的作用(Han等.， 2015)，但是这些较大的权重较少。因此，无论是Forgy初始化还是基于密度初始化，只有极少数的质心具有较大的绝对值，这就导致了这几个大权重的代表性较差。线性初始化没有这个问题。实验部分比较了聚类和微调后的不同初始化方法的准确率，表明线性初始化效果最好。

前馈和反向传播

一维k均值聚类的中心是共享权值。在前向阶段和后向传播阶段，在查询权重表时，存在一个间接级别。为每个连接存储共享权重表的索引。在反向传播期间，计算每个共享权重的梯度，并用于更新共享权重。这个过程如图3所示。
用L表示损失函数，用$W_{ij}$表示第i列第j行的权值，用$I_{ij}$表示元素$W_{ij}$的质心指数用$C_k$表示层的第k个质心指数。利用指标函数1(.)计算出质心的梯度为:

霍夫曼编码

霍夫曼编码是一种最优的前缀代码，通常用于损失较少的数据压缩。它使用可变长度的码字对源符号进行编码。该表由每个符号的出现概率导出。更常见的符号用更少的位表示。
图5显示了AlexNet中最后一个全连接层量化权重的概率分布和稀疏矩阵指数。两个分布都是有偏的:大部分量化的权重分布在两个峰附近;稀疏矩阵指数差很少超过20。实验表明，这些非均匀分布值的霍夫曼编码节省了20% - 30%的网络存储空间。

实验

我们裁剪、量化和霍夫曼编码了四个网络:两个在MNIST和两个在ImageNet数据集。修剪前后的网络参数和精度如表1所示。压缩管道在不同网络之间节省了35到49倍的网络存储，而不会损失准确性。AlexNet的总大小从240MB减少到6.9MB，这是足够小的放入芯片SRAM，消除了需要在消耗能量的DRAM内存中存储模型。

使用Caffe框架进行训练。剪枝是通过向blob添加掩码来屏蔽剪枝连接的更新来实现的。通过维护存储共享权重的码本结构，计算各层梯度后按索引分组，实现量化和权重共享。每个共享权重都被更新为属于该bucket的所有梯度。霍夫曼编码不需要训练，并在所有微调完成后离线实现。

MNIST上的LENET-300-100和LENET-5

我们首先在MNIST数据集上使用LeNet-300-100和LeNet-5网络进行了实验。LeNet-300-100是一个具有两个隐藏层的全连接网络，分别是300和100个神经元，在Mnist上实现1.6%的错误率。LeNet-5是一个卷积网络，有两个卷积层和两个全连接层，在Mnist上的错误率为0.8%。压缩管道的统计数据见表2和表3。压缩率包括码本开销和稀疏索引。大部分的节省来自裁剪和量化(压缩32倍)，而霍夫曼编码给出了边际增益(压缩40倍)

ALEXNET ON IMAGE NET

我们进一步研究了在ImageNet ILSVRC-2012数据集上的深度压缩性能，该数据集有1.2万个训练示例和50k个验证示例。我们使用AlexNet Caffe模型作为参考模型，该模型有6100万个参数，准确率最高的为57.2%，最高的为5，准确率为80.3%。从表4可以看出，AlexNet可以被压缩到原来大小的2.88%而不影响精度。每个CONV层共有256个共享权重，编码为8位;每个FC层共有32个权重，编码为5位。相对稀疏索引编码为4位。霍夫曼编码压缩额外22%，总共35倍压缩。

VGG-16 ON IMAGE NET

有了在AlexNet上很好的结果，我们也看到了一个更大的，更近期的网络，vGG-16，在同一个ILSVRC-2012数据集上。VGG -16有更多的卷积层，但仍然只有三个完全连接的层。按照类似的方法，我们积极压缩卷积层和全连接层，以实现有效权值的显著减少，如表5所示。
VGG16网络整体压缩了49倍。CONV层中的权重用8位表示，FC层使用5位表示，这不会影响精度。最大的两个完全连接的层可以被修剪到原来尺寸的1.6%以下。这种简化对于实时图像处理是至关重要的，在实时图像处理中几乎没有这些层的重用(不像批处理)。这也是关键的快速目标检测算法，其中一个CONV通过是使用许多FC通过。减少的层将适合在一个片上SRAM和有适度的带宽要求。如果不减少，带宽的要求是禁止的。

讨论

剪枝和量化是一起工作的

图6显示了在不同压缩率下一起或单独进行修剪和量化的准确性。单独工作时，从紫色和黄色的线中可以看出，当剪枝网络压缩到原始大小的8%以下时，剪枝网络的准确率开始明显下降;当量化网络压缩到原始网络大小的8%以下时，其精度也开始显著下降。但是当两者结合时，如红线所示，网络可以被压缩到原始大小的3%而不损失准确性。最右边比较了奇异值分解的结果，虽然代价不高，但是压缩率很低。

图7中的三个图显示了CONV层的精度如何随着每个连接的比特数的减少而下降(左)，FC层(中间)和所有层(右)。每个线都报告了前1和前5的准确性。虚线只应用了量化，而没有进行修剪;实线同时进行了量化和剪枝。两者之间几乎没有差别。这表明剪枝在量化中工作得很好。

量化在修剪网络上工作得很好，因为未修剪的AlexNet有6000万个权重来量化，而修剪的AlexNet只有670万个权重来量化。考虑到相同数量的质心，后者的误差较小。
图7中的前两个图显示CONV层比FC层需要更多的精度。对于CONV层，精度显著下降到4位以下，而FC层更健壮:直到而2位则大大降低了精度。

重心的初始化

图8比较了三种不同初始化方法与top-1精度(左)和top-5精度(右)的精确度。网络被量化为2 ~ 8位，如x轴所示。线性初始化在所有情况下优于密度初始化和随机初始化，3位除外。
线性初始化的初始中心均匀地分布在x轴上，从最小值到最大值。这有助于维护大权重，因为大权重比小权重发挥更重要的作用，Han等(2015)也表明了这一点。随机或基于密度的初始化都不能保留大的中心。在这些初始化方法中，大的权重被聚集到小的中心上，因为大的权重很少。相比之下，线性初始化允许较大的权重更好地形成较大的形心。

深度压缩针对的是运行在移动设备上的非常滞后的应用程序，这些应用程序需要实时推断，比如在自动驾驶汽车内的嵌入式处理器上进行行人检测。等待批处理进行组装会显著增加延迟。因此，在计算性能和能效时，我们考虑了批量大小为1时的情况。
模型尺寸以全连通层为主(90%以上)，被压缩最多深度压缩(vga -16中96%的权重被删除)。在最先进的目标检测算法，如快速R-CNN (Girshick, 2015)，高达38%的计算时间消耗在未压缩模型的FC层。所以对FC层进行基准测试是很有趣的，看看Deep的效果压缩性能和能量。因此我们在FC6、FC7、FC8层上设置了基准测试AlexNet VGG-16。在非批处理的情况下，激活矩阵是一个只有一列的向量，因此计算可以归结为原始模型/剪枝模型的稠密/稀疏矩阵-向量相乘。由于目前CPU和GPU上的BLAS库不支持间接查找和相对索引，所以我们没有对量化模型进行基准测试。我们比较了三种现成的硬件:NVIDIA GeForce GTX Titan X和IntelCore i7 5930K作为桌面处理器(与英伟达数字开发盒包相同)和英伟达TegraK1作为移动处理器。为了在GPU上运行基准测试，我们使用cuBLAS GEMV对原始的稠密层进行测试。对于修剪后的稀疏层，我们将稀疏矩阵存储为CSR格式，并使用cuSPARSE CSRMV内核，该内核对GPU上的稀疏矩阵向量乘法进行了优化。为了在CPU上运行基准测试，我们对原始的稠密模型和MKL使用MKL CBLAS GEMV用于修剪稀疏模型的SPBLAS CSRMV。
为了比较不同系统之间的功耗，以一致的方式测量功耗是很重要的。为了进行分析，我们比较了整个应用程序处理器(AP) / SOC和DRAM的预调控能力。在CPU上，基准测试运行在具有单个Haswell-E类Core i7-5930K处理器的单个套接字上。CPU插槽和DRAM电源是由Intel提供的pcm电源utility报告的。对于GPU，我们使用nvidia-smi工具来报告Titan x的功耗。对于移动GPU，我们使用Jetson TK1开发板并使用功率表来测量总功耗。我们假设有15%的AC到DC转换损耗，85%的调压器效率和15%的功耗由外设组件(NVIDIA, a)来报告用于Tegra K1的AP+DRAM功率。
在有批处理和没有批处理的情况下，内存访问比计算特性是不同的。当输入激活被批量分配到一个矩阵时，计算变成了矩阵-矩阵相乘，其中局部性可以通过阻塞来改进。矩阵可以被阻塞以适合缓存并有效地重用。在本例中，内存访问量为O(n2)，计算量为O(n3)，内存访问与计算的比率为1/n。在不允许批处理的实时处理中，输入激活为单个向量，计算为矩阵向量乘法。在本例中，内存访问量为O(n2)，计算量为O(n2)，内存访问和计算量大小相同(而不是1/n)。这表明MV比MM有更多的内存限制，因此减少内存占用对于非批处理情况是至关重要的。

图9演示了不同硬件上修剪的加速。下面是每个基准测试的6列，显示了密集/修剪网络上CPU / GPU / TK1的计算时间。时间被归一化到CPU。当批大小等于1时，修剪后的网络层在密集网络上平均得到3 ~ 4倍的加速，因为它的内存占用更小，减轻了数据传输开销，特别是对于无法被缓存容纳的大型矩阵。例如VGG16实验中最大的层FC6包含25088×4096×4字节≈400MB的数据，与L3缓存的容量相去甚远。在那些允许延迟的应用程序中，批处理改进了内存局部性，其中权重可以被阻塞并在矩阵-矩阵乘法中重用。在这种情况下，剪枝网络不再显示其优势。我们在附录A中给出了详细的计时结果。
图10演示了不同硬件上修剪的能源效率。

我们将功耗与计算时间相乘得到能耗，然后归一化到CPU得到能效。当批大小为1时，修剪后的网络层比密集网络平均少消耗3 ~ 7倍的能量。据nvidia-smi报道，在密集和稀疏情况下，GPU利用率都是99%。

权重、索引、码本之比

修剪使得权值矩阵稀疏，因此需要额外的空间来存储非零元素的索引。量化为码本增加了存储空间。实验部分已经包含了这两个因素。图11显示了量化四个网络时三个不同组件的分解情况。因为平均来说权重和稀疏索引都是用5位编码的，它们的存储大约是一半一半。codebook的开销非常小，通常可以忽略不计。

相关工作

神经网络通常都是过度参数化的，深度学习模型存在大量冗余（Predicting parameters in deep
learning.）这会导致计算和内存使用的浪费。关于取消冗余的建议有很多: Vanhoucke等人(2011)探索了8位整数(vs 32位浮点)激活的定点实现。黄&唱(2014)提出了一种三元权值、3位激活的定点网络优化方法。Anwar等人(2015)使用L2误差最小化量化神经网络，在MNIST和CIFAR-10数据集上取得了更好的精度。denton等人(2014)利用神经网络的线性结构，找到参数的合适低秩近似，并将精度保持在原始模型的1%以内。
本文的经验成功与权值为+1/0/-1的类随机稀疏网络的理论研究相一致(Arora et al.， 2014)，它已被证明具有良好的性质
(例如可逆性)，并允许一个可证明的多项式时间算法的训练。
很多工作都集中在将网络参数封装到bucket中，只需要存储bucket中的值。HashedNets(Chen et al.， 2015)通过使用哈希函数随机分组连接权值来减小模型大小，这样同一个哈希桶中的所有连接都共享一个参数值。在他们的方法中，权值是由哈希函数预先确定的，而不是通过训练来学习的，这并不能捕捉图像的本质。Gong等人(2014)使用矢量量化压缩深度卷积网，导致1%的精度损失。两种方法都只研究了全连接层，而忽略了卷积层。
还有其他一些尝试，通过用全局平均池代替全连接层来减少神经网络的参数数量。网络体系结构中的网络(Lin等，和GoogLenet(Szegedy et al.， 2014)采用这一理念，在几个基准测试中取得了最先进的结果。然而，这种方法更难实现迁移学习，即重用在ImageNet数据集上学习到的特征，并仅通过微调完全连接的层将它们应用到新的任务中。Szegedy等人(2014)注意到了这个问题，并促使他们在其网络顶部添加一个线性层，以实现迁移学习。
网络剪枝被用于降低网络复杂度和减少过拟合。修剪的早期方法是偏重衰减(Hanson & Pratt, 1989)。最佳的脑损伤
(LeCun et al.， 1989)和最佳脑外科医生(Hassibi et al.， 1993)基于丢失函数的Hessian对网络进行修剪，以减少连接的数量，并认为这种修剪比基于数量的修剪(如重量衰减)更准确。最近的工作(Han等，2015)成功地修剪了几种先进的大规模网络，并表明参数的数量可以减少一个数量级。Van Nguyen等人(2015)还尝试减少压缩和加速激活的次数。

未来的工作

虽然修剪后的网络已经在各种硬件上进行了基准测试，但具有权重共享的量化网络却没有，因为现成的cuSPARSE或MKL SPBLAS库不支持间接矩阵条目查找，也不支持CSC或CSR格式的相对索引。因此，深度压缩在缓存中适合模型的全部优势还没有完全显露出来。一个软件解决方案是编写定制的GPU内核来支持这一点。一个硬件解决方案是建立定制的专用ASIC体系结构，以遍历稀疏和量化的网络结构，也支持定制量化位宽。我们希望这种架构能以芯片上的能源为主
SRAM访问而不是芯片外DRAM访问。

结论

我们提出了“深度压缩”，可以在不影响精度的情况下压缩神经网络。我们的方法是通过裁剪不重要的连接，使用权共享量化网络，然后应用霍夫曼编码。我们强调了我们在AlexNet上的实验，在不损失准确性的情况下，减少了35倍的重量存储。我们对49倍和39倍压缩的VGG-16和LeNet网络显示了相似的结果，但没有丢失准确性。这使得将convnets放入移动应用程序的存储需求更小。经过深度压缩，这些网络的大小可以放入片上SRAM缓存(5pJ/access)，而不需要芯片外DRAM内存(640 pj /访问)。这可能会使深度神经网络在移动设备上运行时更加节能。我们的压缩方法也便于在应用程序大小和下载带宽受限的移动应用程序中使用复杂的神经网络。