在神經(jīng)網(wǎng)絡(luò)模型壓縮中的范氏哈夫曼編碼應(yīng)用研究

宦暉

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

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

1 引言

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

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

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

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

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

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

3 哈夫曼編碼

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

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

其中fi是每個(gè)葉節(jié)點(diǎn)符號(hào)的統(tǒng)計(jì)頻率，即權(quán)值。

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

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

4 范氏哈夫曼編碼

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

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

1，具有相同哈夫曼編碼長(zhǎng)度的符號(hào)編碼是連續(xù)二進(jìn)制整數(shù)，對(duì)應(yīng)原碼的值越小則對(duì)應(yīng)哈夫曼編碼也越小。

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

這個(gè)約束公式的含義是，長(zhǎng)度為i第一個(gè)符號(hào)的編碼，是將長(zhǎng)度為i-1的最后一個(gè)符號(hào)的編碼進(jìn)行左移一位并補(bǔ)零。

3，哈夫曼編碼長(zhǎng)度最小的第一個(gè)符號(hào)從0開始。第一個(gè)符號(hào)的編碼方式是依照符號(hào)的編碼長(zhǎng)度分配相同長(zhǎng)度的'0'值。

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

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

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

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

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

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

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

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

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

typedef struct ?HuffmanTreeNode{

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

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

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

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

}HuffmanTreeNode;

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

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

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

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

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

5 結(jié)束語

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

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

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

參考文獻(xiàn)：

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