在神經網絡模型壓縮中的范氏哈夫曼編碼應用研究

宦暉

摘要：隨著神經網絡技術深度學習模型的復雜度不斷增加，導致神經網絡技術難以在普通計算設備上實現實際應用，近年來神經網絡模型壓縮是一個重要的研究方向。通過網絡壓縮能夠減少參數，更好地進行分布式訓練，還能減少新模型導入客戶端時所需的開銷。本研究對于業內流行的深度學習模型壓縮流程進行優化，以范氏哈夫曼編碼為基礎，在壓縮流程中量化后的共享權重索引值的壓縮效率提升方面具有一定價值。

關鍵詞：神經網絡模型壓縮;哈夫曼編碼;范氏哈夫曼編碼;儲存空間;壓縮效率

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.