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 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

DFS中的奇偶剪枝学习笔记

奇偶剪枝学习笔记 描述 现假设起点为(sx,sy),终点为(ex,ey),给定t步恰好走到终点, s | ...

2594
来自专栏数据科学与人工智能

【数据分析】异常值检测

什么是异常(outlier)?Hawkins(1980)给出了异常的本质性的定义:异常是在数据集中与众不同的数据,使人怀疑这些数据并非随机偏差,而是产生于完全不...

3936
来自专栏从流域到海域

How To Implement The Decision Tree Algorithm From Scratch In Python (从零开始在Python中实现决策树算法)

How To Implement The Decision Tree Algorithm From Scratch In Python 原文作者:Jason B...

3009
来自专栏机器之心

教程 | 如何使用TensorFlow和自编码器模型生成手写数字

40011
来自专栏计算机视觉战队

简单易懂的讲解深度学习(入门系列之五)

我们知道,《三字经》里开篇第一句就是:“人之初,性本善”。那么对于神经网络来说,这句话就要改为:“网之初,感知机”。感知机( Perceptrons ),基本上...

701
来自专栏小鹏的专栏

tf25: 使用深度学习做阅读理解+完形填空

记的在学生时代,英语考试有这么一种类型的题,叫:阅读理解。首先让你读一段洋文材料,然后回答一些基于这个洋文材料提的问题。 我先给你出一道阅读理解 Big ...

5295
来自专栏AI研习社

手把手教你用 Keras 实现 LSTM 预测英语单词发音

我近期在研究一个 NLP 项目,根据项目的要求,需要能够通过设计算法和模型处理单词的音节 (Syllables),并对那些没有在词典中出现的单词找到其在词典中对...

762
来自专栏量化投资与机器学习

从Seq2seq到Attention模型到Self Attention(二)

系列一介绍了Seq2seq和 Attention model。这篇文章将重点摆在Google於2017年发表论文“Attention is all you ne...

2705
来自专栏CreateAMind

浅析互信息与特征选择

那么什么是互信息呢?变量x与变量y之间的互信息,可以用来衡量已知变量x时变量y的不确定性减少的程度,同样的,也可以衡量已知变量y时变量x的不确定性减少的程度。

2072
来自专栏杨熹的专栏

RNN与机器翻译

---- CS224d-Day 9: GRUs and LSTMs -- for machine translation 视频链接 课件链接 ---- 本...

3305

扫码关注云+社区