用循環神經網路進行文件無損壓縮：斯坦福大學提出DeepZip

01-28

選自斯坦福大學

作者：Kedar Tatwawadi

機器之心編譯

參與：李澤南、黃小天

神經網路不僅可以分析、識別特徵，提出預測，還可以壓縮文件。斯坦福大學的研究者最近提交的論文中，循環神經網路捕捉長期依賴關係的優勢被用於無損壓縮任務中，這種被稱為 DeepZip 的技術已在文本和基因組數據文件中得到了實驗。研究人員稱，其結果頗具潛力。

正在進行的大數據變革讓我們收集了大量不同類型的數據，如圖像、文本和音頻等；新類型的數據如 3D VR 數據、用於自動駕駛的點雲數據、不同類型的基因組數據等，佔據著巨量的存儲空間。因此，人們對於統計模型和適用於各種數據格式的高效壓縮方法有著很大的需求。

近 50 年來，無損壓縮技術已經歷了很多重要的發展。在克勞德·香農的一個經典研究中，這位先驅者指出，熵率是給定數據源可能達到的最佳壓縮比，同時也給出了一種實現方法（儘管不甚實際）。J. Rissanen 提出了算術編碼，這是一個實現已知分布熵邊界的有效方法。對於未知分布的數據源（如文本和 DNA），他還設計了算術編碼的自適應變體，它可以通過嘗試學習條件 k-gram 模型的分布來進行壓縮。儘管這種過程的複雜度會隨 k 的變化而呈指數級增長，通常上下文會被限制在 k=20 符號。這會導致壓縮比例的顯著損失，因為模型無法捕捉長期依賴關係。我們都知道基於循環神經網路（LSTM/GRU）的模型善於捕捉長期依賴關係，同時可以較準確地預測下一個字母/單詞。如此一來，能否使用基於 RNN 的框架來用於壓縮任務？在斯坦福大學的一份研究中，研究人員探索了使用基於 RNN 的語言模型及算術編碼來提升無損壓縮的性能。

在這一研究的論文中，研究人員首先分析和理解了已知熵情況下，合成數據集上 RNN 和算術編碼方法的表現，其目的是對各種 RNN 結構的能力和極限進行直觀的理解。研究人員也對偽隨機數生成序列（PRNG）進行了測試，儘管其熵率為零（因為它們是確定性的），但使用標準技術極難壓縮。基於對此前在合成數據集上測試的經驗，研究人員使用了文本壓縮模型和基因組數據集。

壓縮器框架

2.1 概述

首先是用於實驗的壓縮器模型，其框架可以被分為兩個模塊：

RNN 概率評估器模塊：對於數據流 S_0，S_1……S_N，RNN 概率評估器模塊可以基於此前觀察到的負號 S_0，S_1……S_k-1 來估計 S_k 的條件概率分布。這一概率估計 P?（S_k|S_0, S_1, . . . , S_k?1）會被遞送到算術編碼模塊；
算術編碼器模塊：演算法編碼器模塊可被認為是 FSM，它接收下一個符號的概率分布估計並將其編碼成一個狀態（與解碼器的操作相反）。

2.2 RNN 概率評估器模塊

實際上，RNN 評估器模塊可以是任何循環神經網路（LSTM/GRU），其中包括最終估算概率的 Softmax 層。算術編碼器模塊可以是經典的算術編碼 FSM，或更快的非對稱數字系統（Asymmetric Numeral Systems，ANS）模塊。對於模型的運行，有一些重要的限制：

輸入的因果關係：RNN 評估器必須是具有因果關係的，它可以視輸入為特徵，僅僅基於此前的編碼符號進行估算（BiLSTM 等或許不行）。
權重更新：權重更新（如執行）應在編碼器和解碼器中執行。這是必要的，因為我們需要編碼器和解碼器生成每個符號的分布。

研究人員主要探索了兩個模型：符號級別的GRU模型（DeepZip-ChGRU）和基於特徵的模型（DeepZip-Feat）。在 DeepZip-GRU上，在第 k 步，GRU 模塊的輸入是 X_k-1，而 state_k-1 是輸出的狀態，直到 k 點為止。DeepZip-Feat 包含輸入作為特徵計算因果關係，如過去的 20 個符號，以及觀察到的流內上下文表現記錄。此外，研究人員也考慮過基於文字的模型（Attention-RWA 模型）。

2.3 算術編碼器模塊

算術編碼器保持在區間 [0，1] 之間。每個符號流唯一地確定一個範圍，這個範圍可按順序計算，並直接基於下一符號的概率評估。它可視為傳遞至下一迭代的算術編碼器的一個狀態。最後，該範圍被編碼，由此形成了壓縮數據。在給定概率評估的情況下，解碼操作則相反。算術編碼操作如圖 2 所示。

圖 2：獨立同分布 (0.6, 0.2, 0.1, 0.1) 作為分布源的序列 (0, 2, 3) 算術編碼

2.4 編碼器&解碼器操作

編碼器&解碼器操作如下圖所示：

算術編碼器模塊通常從首個符號 S_0 的自定義概率分布評估開始。完成之後，解碼器可以解碼首個符號。
算術編碼器和 RNN 評估器模塊都通過迭代傳遞狀態信息。算術編碼器的最終狀態充當壓縮數據。
如果模型訓練超過一個 epoch，RNN 評估器模塊的權重需要被存儲，並計算壓縮大小（MDL Principle [14]）。

圖 3：編碼器模型架構

接著研究人員討論了不同模型在上述數據集上的一些有趣實驗。模型有：

DeepZip-ChRNN：基於字元級 RNN 的神經網路模型。
DeepZip-ChGRU：基於字元級 GRU 的神經網路模型。
DeepZip-Feat：基於 GRU 的模型，其中包含所有以前觀察到的符號的功能，而不僅僅是之前的輸入。

3 合成數據集上的實驗

圖 5：包含 128 個單元的 DeepZip-ChRNN 模型在 Markov-k 源上的表現

圖 6：包含 128 個單元的 DeepZip-ChGRU 模型在 Markov-k 源上的表現

圖 7：包含 128 個單元的 DeepZip 模型與 GZIP[15]、適應性算術編碼-CABAC 的表現對比

圖 8：包含 128 個單元的 DeepZip 模型在實際數據集上的表現

論文：DeepZip: Lossless Compression using Recurrent Networks

論文地址：https://web.stanford.edu/class/cs224n/reports/2761006.pdf

摘要：現今，我們生成的數據量大幅增加。新類型的數據，比如基因組數據 [1]、3D-360 度 VR 數據、自動駕駛點雲數據已經出現。大量努力用在了分析以上數據的統計學信息，以設計好的壓縮器。我們由資訊理論得知，好的壓縮器來自好的預測器 [2]。我們知道基於循環神經網路（LSTM/GRU）的模型擅長捕捉長期依賴關係 [3]，並可以很好地預測下一字元/詞。這樣 RNN 可被有效用於壓縮嗎？我們分析了 RNN 在數據壓縮問題上的應用。

壓縮器 DeepZip 包含兩個主要模塊：基於 RNN 的概率評估器和算術編碼模塊。首先，我們討論了現有文獻和基本的模型架構。接著我們深入到合成及真實文本和基因組數據集的實驗結果。最後，我們對發現的結果和未來工作作了討論。