用循环神经网络进行文件无损压缩：斯坦福大学提出DeepZip

2018 年 1 月 2 日 机器之心

选自斯坦福大学

作者：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 的概率评估器和算术编码模块。首先，我们讨论了现有文献和基本的模型架构。接着我们深入到合成及真实文本和基因组数据集的实验结果。最后，我们对发现的结果和未来工作作了讨论。