在神经网络模型压缩中的范氏哈夫曼编码应用研究

宦晖

摘要：随着神经网络技术深度学习模型的复杂度不断增加，导致神经网络技术难以在普通计算设备上实现实际应用，近年来神经网络模型压缩是一个重要的研究方向。通过网络压缩能够减少参数，更好地进行分布式训练，还能减少新模型导入客户端时所需的开销。本研究对于业内流行的深度学习模型压缩流程进行优化，以范氏哈夫曼编码为基础，在压缩流程中量化后的共享权重索引值的压缩效率提升方面具有一定价值。

关键词：神经网络模型压缩;哈夫曼编码;范氏哈夫曼编码;储存空间;压缩效率

1 引言

近年来，以深度学习为代表的人工智能技术得到了快速发展，在计算机视觉、自然语言处理、数据处理等领域得到日益广泛的应用。深度学习之所以在诸多领域有优异性能与突出表现，是因为其以卷积神经网络等技术为基础，通过对大量数据集的学习和训练，形成复杂的数据处理模型，从而解决不同类型的复杂问题。

尽管这些基于神经网络技术的深度学习模型取得了巨大的成功，但随之而来的是神经网络层数的扩展以及模型复杂程度的不断增加，使得神经网络参数数量得到急剧扩大，极大程度地消耗运算资源和存储空间。这些依赖于具有数千万乃至数十亿参数的深度神经网络模型，需要具有高计算能力的 GPU 才能让神经网络实现相对快速的训练，而普通的CPU难以完成这样的计算任务。在移动终端和一般的嵌入式设备上，面对具有如此庞大参数的神经网络需要很长的计算时间与能耗，难以实现实际应用。

因此，对于很多实时的深度学习应用，在嵌入式设备和移动终端上运行具有较多层和节点的神经网络时，如何减少神经网络存储和计算资源的消耗变得非常重要。在这些设备上实时运行深度神经网络模型，是神经网络模型压缩和加速的重要目标。要实现神经网络模型的压缩和加速，需要应用压缩算法、数据结构、硬件设计等多种不同领域的方法来共同制定解决方案。

2 深度学习神经网络模型压缩流程

在2016年，Han[1]等提出了相对完善且性能优异的深度学习神经网络模型的压缩方法，该论文获得了 ICLR 2016 的 Best Paper，在业界产生广泛的影响，并得到广泛应用。其具体的压缩流程是：1，参量修剪。针对训练权重值设置阈值，在将小于阈值的权重值删除后，减少了需要编码的权重值数量，然后再按正常方法重新训练稀疏连接的网络，得到一个稀疏的权重值矩阵。2，共享权重值和量化。将保留下来的训练权重值分配到多个集合中，进行 K-means 聚类计算后形成码书，将聚类中心点的权重值作为集合中共享的权重值，神经网络中对应的相关神经元在连接中将使用共享权重值。然后对权重值进行量化，进一步减少权重值所使用的比特数。3，哈夫曼编码（Huffman coding）[2]。对量化后的权重索引值进行哈夫曼编码，利用权重值的不均匀分布，进一步压缩神经网络参数数据的信息冗余。

在Han的神经网络压缩处理流程中，参量修剪、共享权重值与量化都大幅度减少了神经网络模型中所使用的参数数量，但其是以精度损失为代价的。而哈夫曼编码根据概率统计以减少权重值的信息冗余，是无损失地保留信息量的压缩编码方式，如果进行优化且取得更高的编码压缩率，则在保持相同的神经网络整体压缩率下，可更多地保留剪枝、共享权重值与量化时的精度。本研究探讨对Han压缩流程中所使用的哈夫曼编码进行进一步优化，使用范氏哈夫曼编码取代传统的哈夫曼编码，以取得更优的压缩性能。

3 哈夫曼编码

哈夫曼编码是基于数据源的统计特性建立哈夫曼树然后再进行编码的算法。建立哈夫曼树的过程是一个循环迭代的过程，每一步骤中的工作过程相同，具体为：编码器获取所有符号（Symbol）的统计频率，并将所有符号放置在同一个集合中;然后从集合中选取统计频率最低的两个符号作为节点，并创建一个新的内部节点;将新的内部节点放回到集合中，原来的两个节点被新创建的节点代替，新创建节点的统计频率为所选两个节点的统计频率之和;将所选的两个节点与新创建节点构成一个最小二叉树。这样不断的循环迭代，直到集合中只剩下一个节点（根节点），此时哈夫曼树构建完成。

哈夫曼编码压缩后的数据量等于哈夫曼树带权路径长度（Weighted Path Length，WPL）[3]。哈夫曼树的带权路径长度指的是所有节点的带权路径长度之和。n个编码长度为Li（i=1，2，…，n）的叶节点，其构建的哈夫曼树的带权路径长度为：

其中fi是每个叶节点符号的统计频率，即权值。

哈夫曼树是带权路径长度最小的二叉树，也是最优二叉树。在哈夫曼编码表的结构中，每一棵最小二叉树的左右子节点位置是随机的，如果将哈夫曼树中的任意一个最小二叉树的左右节点位置进行互换，只会导致某些字符的具体编码有改变，但整个哈夫曼树的带权路径总长度并不会变化，并不会影响哈夫曼编码的压缩率。如果能约定规则，限制哈夫曼树中的最小二叉树左右节点位置的不确定性，则表达哈夫曼树所需的數据量可以有效降低。

另外，传统的哈夫曼编码是通过将出现频率较高的符号进行较短编码，从而提高压缩率。这个方法有两个大的缺点：首先，每一个树节点都要储存其父节点与子节点等相关信息，符号集合包含很多不同概率的符号，其数量越大，对应存储空间将会增加越多;其次，哈夫曼树的跟踪和维护需要消耗非常大的计算资源。由于这两个原因，传统哈夫曼编码在储存空间以及计算效率上都有需要提升优化的空间。

4 范氏哈夫曼编码

范氏哈夫曼编码（Canonical Huffman Codes）是施瓦兹（Schwartz E S）提出的[4]，对传统哈夫曼编码进行优化的算法，通过对符号和编码的下列三个数字序列属性进行编码规则约定限制，从而更有效率地对哈夫曼树进行编码。

范氏哈夫曼编码约束规则：

1，具有相同哈夫曼编码长度的符号编码是连续二进制整数，对应原码的值越小则对应哈夫曼编码也越小。

2，編码长度为i的第一个符号的编码Hfirst（i）与长度为i-1的最后一个符号的编码Hlast（i-1）的关系满足下面公式：

这个约束公式的含义是，长度为i第一个符号的编码，是将长度为i-1的最后一个符号的编码进行左移一位并补零。

3，哈夫曼编码长度最小的第一个符号从0开始。第一个符号的编码方式是依照符号的编码长度分配相同长度的'0'值。

根据上面三个约束规则，可按照顺序为每个已经确定长度的符号分配唯一可译码（unique decodable code）。这样，就把存储整个哈夫曼树编码表的任务简化为存储每个符号编码长度的任务。

范氏霍夫曼编码要求相同长度编码必须是连续的;为尽可能减小储存空间，编码长度为i的第一个符号可以从编码长度为i-1的最后一个符号所获得;另外，最小编码长度的第一个编码必须从0开始。范氏哈夫曼编码利用约束规则，可以根据每个符号的长度，按照范氏哈夫曼编码的规则重新构出整个编码表。

神经网络一旦训练完成，权重值数据被确定后，需要实现两方面的最小化：存储编码表和哈夫曼树的存储空间最小化，以及编解码过程所消耗的计算资源的最小化。范式哈夫曼编码技术能同时满足这两方面的需求，比传统的哈夫曼编码技术更加优化。

5 提升神经网络模型压缩效率

在本研究中，将范氏哈夫曼编码取代传统哈夫曼编码，以LeNet-5卷积神经网络的压缩为例，研究范氏哈夫曼编码在提升存储空间压缩效率方面的效果。

哈夫曼编码的对象是神经网络压缩过程中的共享权重值在量化后的索引值，共享权重值是使用K-Means算法[5]对神经网络中每一层的权重值进行数据分类，通过计算均值迭代出最优的聚类结果。假设有n个权重值进行聚类计算，划分为k个类别，K-Means通过优化每一类中的所有权重值到聚类中心的距离来实现，如下式所现：

其中，w={w1，w2，…wn}表示n个初始权重值，c={c1，c2，…cn} 表示k个聚类。

在聚类之后，每类的所有权重共享一个共同权重值，并且这些聚类后的权重值参数使用单精度的浮点数表示，需要占用很大的存储空间。而对共享权重值进行量化和索引，将浮点数映射为索引值，可大幅减少所需的存储空间。

传统哈夫曼编码必须保存哈夫曼树，本研究中采用静态数组实现哈夫曼树的构建，哈夫曼树节点包括权值、父节点、左右子节点，数据结构如下所示：

typedef struct  HuffmanTreeNode{

float weight;   //权值

int parent;     //父节点

int leftChild; //左子节点

int rightChild; //右子节点

}HuffmanTreeNode;

与传统哈夫曼编码相比，范式哈夫曼编码节省了保存哈夫曼树本身所需的数据量。

本文基于LeNet-5进行神经网络压缩研究，LeNet-5是LeCun[6]及其合作者在1989年提出的一个卷积神经网络模型，在手写数据集上取得了巨大的成功，得到广泛关注，在OCR领域有很多的成功应用。LeNet-5是卷积神经网络中比较基础的网络模型，是由卷积层、池化层、全连接层等组成的一个七层网络模型。

对LeNet-5网络进行训练时所使用的数据集是MNIST数据集。MNIST数据集是深度学习的基础数据集，来自于美国国家标准与技术研究所（ National Institute of Standards and Technology ，NIST），其中训练集 （training set）有60000张图片，每张图片的内容是0至9的数字，由250 个不同的人手写而成;测试集（test set） 有10000张图片，内容也是同样比例的手写数字。

LeNet-5网络的各层之间的连接参数很多，初始数据量的统计结果为431K。卷积层参数数量相对较少，大多数为全连接层的参数。经过剪枝、K-Means聚类计算及量化，在保持TOP1识别精度为99%的情况下，本研究对LeNet-5网络模型的压缩率实验数据统计结果如下表所示：

基于LeNet-5压缩的实验结果显示，使用范式哈夫曼编码取代传统哈夫曼编码后，整体的网络压缩率从2.45%优化到了1.82%。

5 结束语

使用范式哈夫曼编码取代传统哈夫曼编码，在LeNet-5这种较为简单的网络模型压缩实验中有较好的结果。对于较复杂的网络模型，网络参数大幅增加，此时每层聚类计算时的分类数量增加不多，而索引数据量却大比例地增加，意味着用于存储哈夫曼树的数据量相对于索引数据量的数据冗余会减少，将导致采用范氏哈夫曼编码时的压缩率会相对降低，但相对于传统哈夫曼编码，范氏哈夫曼编码仍然具有较多优势。

范氏哈夫曼编码相对于传统哈夫曼编码的改进效果，与剪枝后的神经网络参数规模、神经网络层数、聚类计算时的分类数量、以及量化比特数有关。除了能节省神经网络的存储空间，范氏哈夫曼编码对计算速度的提升也是明显的。

在研究神经网络模型压缩的计算速度提升时，要考虑如何基于硬件平台进行软件算法上的优化，即针对不同硬件平台的数据吞吐量和缓存资源，进一步改进和优化算法。

参考文献：

[1]Han S，Mao H，Dally J W.Deep compression：compressing deep neural networks with pruning，trained quantization and Huffman coding [J].Fiber，2015，56（4）：3-7.

[2]KAO M Y，WANG J.Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees[J].Theoretical computer science，2001，262（1/2）：101-115.

[3]Puteaux P，Puech W.An efficient MSB prediction -based method for high-capacity reversible data hiding in encrypted images[J].IEEE Transactions on Information Forensics and Security，2018，13（7）：1670-1681.

[4]Anwar S，Hwang K，Sung W.Structured Pruning of Deep Convolutional Neural Networks[J].ACM Journal on Emerging Technologies in Computing Systems，2015，13（3）：32.

[5]Hartigan J A，Wong M A.Algorithm AS 136：A K-Means Clustering Algorithm[J].Journal of the Royal Statistical Society，1979，28（1）：100-108.

[6]Lecun Yann，Boser Bernhard，Decker John，et al.Back Propagation applied to handwritten zip code recognition[J].Neural Computation，1989，1（4）：541-551.