Stanford提出DeepZip:用循环神经网络进行文件无损压缩!

一、论文摘要

如今,我们生成的数据量大幅增加。新类型的数据,比如基因组数据 [1]、3D-360 度 VR 数据、自动驾驶点云数据已经出现。大量的工作用在了分析以上数据的统计学信息,以设计好的压缩器。由信息论得知,好的压缩器来自好的预测器 [2]。基于循环神经网络(LSTM/GRU)的模型擅长捕捉长期依赖关系 [3],并可以很好地预测下一字符/词。这样 RNN 可被有效用于压缩吗?我们分析了 RNN 在数据压缩问题上的应用。

压缩器 DeepZip 包含两个主要模块:基于 RNN 的概率评估器和算术编码模块。首先,我们讨论了现有文献和基本的模型架构。然后,我们深入到合成及真实文本和基因组数据集的实验结果。最后,我们对发现的结果和未来工作作了讨论。

二、项目介绍

大数据变革产生了大量不同类型的数据,如图像、文本和音频等;新类型的数据如 3D VR 数据、用于自动驾驶的点云数据、不同类型的基因组数据等,占据着巨量的存储空间。因此,人们对于统计模型和适用于各种数据格式的高效压缩方法有着很大的需求。

近 50 年来,无损压缩技术已经历了很多重要的发展。在克劳德·香农的一个经典研究中指出,熵率是给定数据源可能达到的最佳压缩比,同时也给出了一种实现方法(尽管不甚实际)。J. Rissanen 提出了算术编码,这是一个实现已知分布熵边界的有效方法。对于未知分布的数据源(如文本和 DNA),他还设计了算术编码的自适应变体,可以通过尝试学习条件 k-gram 模型的分布来进行压缩。尽管这种过程的复杂度会随 k 的变化而呈指数级增长,通常上下文会被限制在 k=20 符号。这会导致压缩比例的显著损失,因为模型无法捕捉长期依赖关系。我们都知道,基于循环神经网络(LSTM/GRU)的模型善于捕捉长期依赖关系,同时可以较准确地预测下一个字母/单词。如此一来,能否使用基于 RNN 的框架来用于压缩任务?在斯坦福大学的一份研究中,研究人员探索了使用基于 RNN 的语言模型及算术编码来提升无损压缩的性能。

三、过去的处理方式

基于CMIX Compressor使用LSTM进行上下文混合的流程图

四、压缩器的框架

(一)概述:用于实验的压缩器模型,框架可被分为两个模块:

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,它接收下一个符号的概率分布估计并将其编码成一个状态(与解码器的操作相反)。

(二)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 模型)。

(三)算术编码器模块

算术编码器保持在区间 [0,1] 之间。每个符号流唯一地确定一个范围,这个范围可按顺序计算,并直接基于下一符号的概率评估。它可视为传递至下一迭代的算术编码器的一个状态。最后,该范围被编码,由此形成了压缩数据。在给定概率评估的情况下,解码操作则相反。算术编码操作如图 2 所示。

图 2:独立同分布 (0.6, 0.2, 0.1, 0.1) 作为分布源的序列 (0, 2, 3) 算术编码

(四)编码器&解码器操作

编码器&解码器操作如下图所示:

算术编码器模块通常从首个符号 S_0 的自定义概率分布评估开始。完成之后,解码器可以解码首个符号。

算术编码器和 RNN 评估器模块都通过迭代传递状态信息。算术编码器的最终状态充当压缩数据。

如果模型训练超过一个 epoch,RNN 评估器模块的权重需要被存储,并计算压缩大小(MDL Principle [14])。

图 3:编码器模型架构

接着研究人员讨论了不同模型在上述数据集上的一些有趣实验。模型有:

DeepZip-ChRNN:基于字符级 RNN 的神经网络模型。

DeepZip-ChGRU:基于字符级 GRU 的神经网络模型。

DeepZip-Feat:基于 GRU 的模型,其中包含所有以前观察到的符号的功能,而不仅仅是之前的输入。

五、合成数据集上的实验

图 5:包含 128 个单元的 DeepZip-ChRNN 模型在 Markov-k 源上的表现

图 6:包含 128 个单元的 DeepZip-ChGRU 模型在 Markov-k 源上的表现

图 7:包含 128 个单元的 DeepZip 模型与 GZIP[15]、适应性算术编码-CABAC 的表现对比

图 8:包含 128 个单元的 DeepZip 模型在实际数据集上的表现

六、研究结论

研究人员首先分析和理解了已知熵情况下,合成数据集上 RNN 和算术编码方法的表现,其目的是对各种 RNN 结构的能力和极限进行直观的理解。研究人员也对伪随机数生成序列(PRNG)进行了测试,尽管其熵率为零(因为它们是确定性的),但使用标准技术极难压缩。基于对此前在合成数据集上测试的经验,研究人员使用了文本压缩模型和基因组数据集。

代码:Code: https://github.com/kedartatwawadi/NN_compression

论文:https://web.stanford.edu/class/cs224n/reports/2761006.pdf

本文来自企鹅号 - AI讲堂媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏李炼的专栏

加权有限状态机在语音识别中的应用

WFST 在语音识别中的应用,要从 Mohri 的《Weighted Finite-State Transducers in Speech Recognitio...

7721
来自专栏AI科技评论

开发 | 机器学习之确定最佳聚类数目的10种方法

AI科技评论按,本文作者贝尔塔,原文载于知乎专栏数据分析与可视化,AI科技评论获其授权发布。 在聚类分析的时候确定最佳聚类数目是一个很重要的问题,比如kmean...

34312
来自专栏AI科技评论

ACL论文 | 深度学习大神新作,神经网络的自然语言翻译应用

在 8月7日在德国柏林召开的2016 计算语言学(ACL)大会上,学者Thang Luong、Kyunghyun Cho 和 Christopher D. Ma...

3435
来自专栏MyBlog

数值分析读书笔记(1)导论

一般来说,解决实际问题的第一步是将实际问题转换为数学问题,接着建立数学模型来解决这个数学问题,而理论解或者解析解通常难以求得,于是数值计算的方法应运而生

1272
来自专栏钱塘大数据

大数据最核心的关键技术:32个算法

奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutsch...

3709
来自专栏PPV课数据科学社区

连载 | 概率论与数理统计(1) – 基本概念

作者:Belter。专注于生物方向的数据分析,一位编程爱好者。关注Python, R和大数据。

941
来自专栏新智元

【榜单】计算机科学中最重要的32个算法

【新智元导读】 奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph...

3557
来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib 之 大规模数据集的相似度计算原理探索

在spark中RowMatrix提供了一种并行计算相似度的思路,下面就来看看其中的奥妙吧!

1540
来自专栏贾老师の博客

【笔记】ejoy2d —— matrix

1054
来自专栏语言、知识与人工智能

基于语言模型的拼写纠错

本文则针对中文拼写纠错进行一个简要的概述,主要分享基于n-gram语言模型和困惑集来做中文拼写纠错的方法。

1K7

扫码关注云+社区