宦暉

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

關(guān)鍵詞：神經(jīng)網(wǎng)絡(luò)模型壓縮;哈夫曼編碼;范氏哈夫曼編碼;儲存空間;壓縮效率

1 引言

近年來，以深度學習為代表的人工智能技術(shù)得到了快速發(fā)展，在計算機視覺、自然語言處理、數(shù)據(jù)處理等領(lǐng)域得到日益廣泛的應用。深度學習之所以在諸多領(lǐng)域有優(yōu)異性能與突出表現(xiàn)，是因為其以卷積神經(jīng)網(wǎng)絡(luò)等技術(shù)為基礎(chǔ)，通過對大量數(shù)據(jù)集的學習和訓練，形成復雜的數(shù)據(jù)處理模型，從而解決不同類型的復雜問題。

盡管這些基于神經(jīng)網(wǎng)絡(luò)技術(shù)的深度學習模型取得了巨大的成功，但隨之而來的是神經(jīng)網(wǎng)絡(luò)層數(shù)的擴展以及模型復雜程度的不斷增加，使得神經(jīng)網(wǎng)絡(luò)參數(shù)數(shù)量得到急劇擴大，極大程度地消耗運算資源和存儲空間。這些依賴于具有數(shù)千萬乃至數(shù)十億參數(shù)的深度神經(jīng)網(wǎng)絡(luò)模型，需要具有高計算能力的 GPU 才能讓神經(jīng)網(wǎng)絡(luò)實現(xiàn)相對快速的訓練，而普通的CPU難以完成這樣的計算任務(wù)。在移動終端和一般的嵌入式設(shè)備上，面對具有如此龐大參數(shù)的神經(jīng)網(wǎng)絡(luò)需要很長的計算時間與能耗，難以實現(xiàn)實際應用。

因此，對于很多實時的深度學習應用，在嵌入式設(shè)備和移動終端上運行具有較多層和節(jié)點的神經(jīng)網(wǎng)絡(luò)時，如何減少神經(jīng)網(wǎng)絡(luò)存儲和計算資源的消耗變得非常重要。在這些設(shè)備上實時運行深度神經(jīng)網(wǎng)絡(luò)模型，是神經(jīng)網(wǎng)絡(luò)模型壓縮和加速的重要目標。要實現(xiàn)神經(jīng)網(wǎng)絡(luò)模型的壓縮和加速，需要應用壓縮算法、數(shù)據(jù)結(jié)構(gòu)、硬件設(shè)計等多種不同領(lǐng)域的方法來共同制定解決方案。

2 深度學習神經(jīng)網(wǎng)絡(luò)模型壓縮流程

在2016年，Han[1]等提出了相對完善且性能優(yōu)異的深度學習神經(jīng)網(wǎng)絡(luò)模型的壓縮方法，該論文獲得了 ICLR 2016 的 Best Paper，在業(yè)界產(chǎn)生廣泛的影響，并得到廣泛應用。其具體的壓縮流程是：1，參量修剪。針對訓練權(quán)重值設(shè)置閾值，在將小于閾值的權(quán)重值刪除后，減少了需要編碼的權(quán)重值數(shù)量，然后再按正常方法重新訓練稀疏連接的網(wǎng)絡(luò)，得到一個稀疏的權(quán)重值矩陣。2，共享權(quán)重值和量化。將保留下來的訓練權(quán)重值分配到多個集合中，進行 K-means 聚類計算后形成碼書，將聚類中心點的權(quán)重值作為集合中共享的權(quán)重值，神經(jīng)網(wǎng)絡(luò)中對應的相關(guān)神經(jīng)元在連接中將使用共享權(quán)重值。然后對權(quán)重值進行量化，進一步減少權(quán)重值所使用的比特數(shù)。3，哈夫曼編碼（Huffman coding）[2]。對量化后的權(quán)重索引值進行哈夫曼編碼，利用權(quán)重值的不均勻分布，進一步壓縮神經(jīng)網(wǎng)絡(luò)參數(shù)數(shù)據(jù)的信息冗余。

在Han的神經(jīng)網(wǎng)絡(luò)壓縮處理流程中，參量修剪、共享權(quán)重值與量化都大幅度減少了神經(jīng)網(wǎng)絡(luò)模型中所使用的參數(shù)數(shù)量，但其是以精度損失為代價的。而哈夫曼編碼根據(jù)概率統(tǒng)計以減少權(quán)重值的信息冗余，是無損失地保留信息量的壓縮編碼方式，如果進行優(yōu)化且取得更高的編碼壓縮率，則在保持相同的神經(jīng)網(wǎng)絡(luò)整體壓縮率下，可更多地保留剪枝、共享權(quán)重值與量化時的精度。本研究探討對Han壓縮流程中所使用的哈夫曼編碼進行進一步優(yōu)化，使用范氏哈夫曼編碼取代傳統(tǒng)的哈夫曼編碼，以取得更優(yōu)的壓縮性能。

3 哈夫曼編碼

哈夫曼編碼是基于數(shù)據(jù)源的統(tǒng)計特性建立哈夫曼樹然后再進行編碼的算法。建立哈夫曼樹的過程是一個循環(huán)迭代的過程，每一步驟中的工作過程相同，具體為：編碼器獲取所有符號（Symbol）的統(tǒng)計頻率，并將所有符號放置在同一個集合中;然后從集合中選取統(tǒng)計頻率最低的兩個符號作為節(jié)點，并創(chuàng)建一個新的內(nèi)部節(jié)點;將新的內(nèi)部節(jié)點放回到集合中，原來的兩個節(jié)點被新創(chuàng)建的節(jié)點代替，新創(chuàng)建節(jié)點的統(tǒng)計頻率為所選兩個節(jié)點的統(tǒng)計頻率之和;將所選的兩個節(jié)點與新創(chuàng)建節(jié)點構(gòu)成一個最小二叉樹。這樣不斷的循環(huán)迭代，直到集合中只剩下一個節(jié)點（根節(jié)點），此時哈夫曼樹構(gòu)建完成。

哈夫曼編碼壓縮后的數(shù)據(jù)量等于哈夫曼樹帶權(quán)路徑長度（Weighted Path Length，WPL）[3]。哈夫曼樹的帶權(quán)路徑長度指的是所有節(jié)點的帶權(quán)路徑長度之和。n個編碼長度為Li（i=1，2，…，n）的葉節(jié)點，其構(gòu)建的哈夫曼樹的帶權(quán)路徑長度為：

其中fi是每個葉節(jié)點符號的統(tǒng)計頻率，即權(quán)值。

哈夫曼樹是帶權(quán)路徑長度最小的二叉樹，也是最優(yōu)二叉樹。在哈夫曼編碼表的結(jié)構(gòu)中，每一棵最小二叉樹的左右子節(jié)點位置是隨機的，如果將哈夫曼樹中的任意一個最小二叉樹的左右節(jié)點位置進行互換，只會導致某些字符的具體編碼有改變，但整個哈夫曼樹的帶權(quán)路徑總長度并不會變化，并不會影響哈夫曼編碼的壓縮率。如果能約定規(guī)則，限制哈夫曼樹中的最小二叉樹左右節(jié)點位置的不確定性，則表達哈夫曼樹所需的數(shù)據(jù)量可以有效降低。

另外，傳統(tǒng)的哈夫曼編碼是通過將出現(xiàn)頻率較高的符號進行較短編碼，從而提高壓縮率。這個方法有兩個大的缺點：首先，每一個樹節(jié)點都要儲存其父節(jié)點與子節(jié)點等相關(guān)信息，符號集合包含很多不同概率的符號，其數(shù)量越大，對應存儲空間將會增加越多;其次，哈夫曼樹的跟蹤和維護需要消耗非常大的計算資源。由于這兩個原因，傳統(tǒng)哈夫曼編碼在儲存空間以及計算效率上都有需要提升優(yōu)化的空間。

4 范氏哈夫曼編碼

范氏哈夫曼編碼（Canonical Huffman Codes）是施瓦茲（Schwartz E S）提出的[4]，對傳統(tǒng)哈夫曼編碼進行優(yōu)化的算法，通過對符號和編碼的下列三個數(shù)字序列屬性進行編碼規(guī)則約定限制，從而更有效率地對哈夫曼樹進行編碼。

范氏哈夫曼編碼約束規(guī)則：

1，具有相同哈夫曼編碼長度的符號編碼是連續(xù)二進制整數(shù)，對應原碼的值越小則對應哈夫曼編碼也越小。

2，編碼長度為i的第一個符號的編碼Hfirst（i）與長度為i-1的最后一個符號的編碼Hlast（i-1）的關(guān)系滿足下面公式：

這個約束公式的含義是，長度為i第一個符號的編碼，是將長度為i-1的最后一個符號的編碼進行左移一位并補零。

3，哈夫曼編碼長度最小的第一個符號從0開始。第一個符號的編碼方式是依照符號的編碼長度分配相同長度的'0'值。

根據(jù)上面三個約束規(guī)則，可按照順序為每個已經(jīng)確定長度的符號分配唯一可譯碼（unique decodable code）。這樣，就把存儲整個哈夫曼樹編碼表的任務(wù)簡化為存儲每個符號編碼長度的任務(wù)。

范氏霍夫曼編碼要求相同長度編碼必須是連續(xù)的;為盡可能減小儲存空間，編碼長度為i的第一個符號可以從編碼長度為i-1的最后一個符號所獲得;另外，最小編碼長度的第一個編碼必須從0開始。范氏哈夫曼編碼利用約束規(guī)則，可以根據(jù)每個符號的長度，按照范氏哈夫曼編碼的規(guī)則重新構(gòu)出整個編碼表。

神經(jīng)網(wǎng)絡(luò)一旦訓練完成，權(quán)重值數(shù)據(jù)被確定后，需要實現(xiàn)兩方面的最小化：存儲編碼表和哈夫曼樹的存儲空間最小化，以及編解碼過程所消耗的計算資源的最小化。范式哈夫曼編碼技術(shù)能同時滿足這兩方面的需求，比傳統(tǒng)的哈夫曼編碼技術(shù)更加優(yōu)化。

5 提升神經(jīng)網(wǎng)絡(luò)模型壓縮效率

在本研究中，將范氏哈夫曼編碼取代傳統(tǒng)哈夫曼編碼，以LeNet-5卷積神經(jīng)網(wǎng)絡(luò)的壓縮為例，研究范氏哈夫曼編碼在提升存儲空間壓縮效率方面的效果。

哈夫曼編碼的對象是神經(jīng)網(wǎng)絡(luò)壓縮過程中的共享權(quán)重值在量化后的索引值，共享權(quán)重值是使用K-Means算法[5]對神經(jīng)網(wǎng)絡(luò)中每一層的權(quán)重值進行數(shù)據(jù)分類，通過計算均值迭代出最優(yōu)的聚類結(jié)果。假設(shè)有n個權(quán)重值進行聚類計算，劃分為k個類別，K-Means通過優(yōu)化每一類中的所有權(quán)重值到聚類中心的距離來實現(xiàn)，如下式所現(xiàn)：

其中，w={w1，w2，…wn}表示n個初始權(quán)重值，c={c1，c2，…cn} 表示k個聚類。

在聚類之后，每類的所有權(quán)重共享一個共同權(quán)重值，并且這些聚類后的權(quán)重值參數(shù)使用單精度的浮點數(shù)表示，需要占用很大的存儲空間。而對共享權(quán)重值進行量化和索引，將浮點數(shù)映射為索引值，可大幅減少所需的存儲空間。

傳統(tǒng)哈夫曼編碼必須保存哈夫曼樹，本研究中采用靜態(tài)數(shù)組實現(xiàn)哈夫曼樹的構(gòu)建，哈夫曼樹節(jié)點包括權(quán)值、父節(jié)點、左右子節(jié)點，數(shù)據(jù)結(jié)構(gòu)如下所示：

typedef struct ?HuffmanTreeNode{

float weight; ? //權(quán)值

int parent; ? ? //父節(jié)點

int leftChild; //左子節(jié)點

int rightChild; //右子節(jié)點

}HuffmanTreeNode;

與傳統(tǒng)哈夫曼編碼相比，范式哈夫曼編碼節(jié)省了保存哈夫曼樹本身所需的數(shù)據(jù)量。

本文基于LeNet-5進行神經(jīng)網(wǎng)絡(luò)壓縮研究，LeNet-5是LeCun[6]及其合作者在1989年提出的一個卷積神經(jīng)網(wǎng)絡(luò)模型，在手寫數(shù)據(jù)集上取得了巨大的成功，得到廣泛關(guān)注，在OCR領(lǐng)域有很多的成功應用。LeNet-5是卷積神經(jīng)網(wǎng)絡(luò)中比較基礎(chǔ)的網(wǎng)絡(luò)模型，是由卷積層、池化層、全連接層等組成的一個七層網(wǎng)絡(luò)模型。

對LeNet-5網(wǎng)絡(luò)進行訓練時所使用的數(shù)據(jù)集是MNIST數(shù)據(jù)集。MNIST數(shù)據(jù)集是深度學習的基礎(chǔ)數(shù)據(jù)集，來自于美國國家標準與技術(shù)研究所（ National Institute of Standards and Technology ，NIST），其中訓練集 （training set）有60000張圖片，每張圖片的內(nèi)容是0至9的數(shù)字，由250 個不同的人手寫而成;測試集（test set） 有10000張圖片，內(nèi)容也是同樣比例的手寫數(shù)字。

LeNet-5網(wǎng)絡(luò)的各層之間的連接參數(shù)很多，初始數(shù)據(jù)量的統(tǒng)計結(jié)果為431K。卷積層參數(shù)數(shù)量相對較少，大多數(shù)為全連接層的參數(shù)。經(jīng)過剪枝、K-Means聚類計算及量化，在保持TOP1識別精度為99%的情況下，本研究對LeNet-5網(wǎng)絡(luò)模型的壓縮率實驗數(shù)據(jù)統(tǒng)計結(jié)果如下表所示：

基于LeNet-5壓縮的實驗結(jié)果顯示，使用范式哈夫曼編碼取代傳統(tǒng)哈夫曼編碼后，整體的網(wǎng)絡(luò)壓縮率從2.45%優(yōu)化到了1.82%。

5 結(jié)束語

使用范式哈夫曼編碼取代傳統(tǒng)哈夫曼編碼，在LeNet-5這種較為簡單的網(wǎng)絡(luò)模型壓縮實驗中有較好的結(jié)果。對于較復雜的網(wǎng)絡(luò)模型，網(wǎng)絡(luò)參數(shù)大幅增加，此時每層聚類計算時的分類數(shù)量增加不多，而索引數(shù)據(jù)量卻大比例地增加，意味著用于存儲哈夫曼樹的數(shù)據(jù)量相對于索引數(shù)據(jù)量的數(shù)據(jù)冗余會減少，將導致采用范氏哈夫曼編碼時的壓縮率會相對降低，但相對于傳統(tǒng)哈夫曼編碼，范氏哈夫曼編碼仍然具有較多優(yōu)勢。

范氏哈夫曼編碼相對于傳統(tǒng)哈夫曼編碼的改進效果，與剪枝后的神經(jīng)網(wǎng)絡(luò)參數(shù)規(guī)模、神經(jīng)網(wǎng)絡(luò)層數(shù)、聚類計算時的分類數(shù)量、以及量化比特數(shù)有關(guān)。除了能節(jié)省神經(jīng)網(wǎng)絡(luò)的存儲空間，范氏哈夫曼編碼對計算速度的提升也是明顯的。

在研究神經(jīng)網(wǎng)絡(luò)模型壓縮的計算速度提升時，要考慮如何基于硬件平臺進行軟件算法上的優(yōu)化，即針對不同硬件平臺的數(shù)據(jù)吞吐量和緩存資源，進一步改進和優(yōu)化算法。

參考文獻：

[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.