关于javascript:深度强化学习在时序数据压缩中的应用ICDE-2020收录论文

彼节者有间，而刀刃者无厚；以无厚入有间，恢恢乎其于游刃必有余地矣 —– 庖丁解牛

前言：随着挪动互联网、IoT、5G 等的利用和遍及，一步一步地咱们走进了数字经济时代。随之而来的海量数据将是一种主观的存在，并施展出越来越重要的作用。时序数据是海量数据中的一个重要组成部分，除了开掘剖析预测等，如何高效的压缩存储是一个根底且重要的课题。同时，咱们也正处在人工智能时代，深度学习曾经有了很多很好的利用，如何在更多更广的层面发挥作用？深度学习的实质是做决策，用它解决具体的问题时很重要的是找到契合点，正当建模，而后整顿数据优化 loss 等最终较好地解决问题。在过来的一段时间，咱们在用深度强化学习进行数据压缩上做了一些钻研摸索并获得了一些问题，曾经在 ICDE 2020 research track 发表（Two-level Data Compression using Machine Learning in Time Series Database）并做了口头汇报。在这里做一个整体粗略介绍，心愿对其它的场景，至多是其它数据的压缩等，带来一点借鉴作用。

1. 背景形容

========

1.1 时序数据

时序数据顾名思义指的是和工夫序列相干的数据，是日常随处可见的一种数据模式。下图列举了三个示例 a）心电图，b）股票指数，c）具体股票交易数据。

对于时序数据库的工作内容，简略地，在用户的应用层面它须要响应海量的查问，剖析，预测等；而在底层它则须要解决海量的读写，压缩解压缩，采纳聚合等操作，而这些的基本操作单元就是时序数据，个别（也能够简化）用两个 8 byte 的值进行对立形容。
能够设想，任何电子设备每天都在产生各种各样海量的时序数据，须要海量的存储空间等，对它进行压缩存储及解决是一个自然而然的办法。而这里的着重点就是如何进行更高效的压缩。

1.2 强化学习

机器学习依照样本是否有 groundTruth 可分为有监督学习，无监督学习，以及强化学习等。强化学习顾名思义是不停得致力得去学习，不须要 groundTruth，真实世界很多时候也没有 groundTruth，譬如人的认知很多工夫就是一直迭代学习的过程。从这个意义上来说，强化学习是更合乎或更全面广泛的始终解决事实世界问题的过程和办法，所以有个说法是：如果深度学习缓缓地会像 C /Python/Java 那样成为解决具体问题的一个根底工具的话，那么强化学习是深度学习的一个根底工具。
强化学习的经典示意图如下，基本要素为 State，Action，和 Environment。根本过程为：Environment 给出 State，Agent 依据 state 做 Action 决策，Action 作用在 Environment 上产生新的 State 及 reward，其中 reward 用来领导 Agent 做出更好的 Action 决策，周而复始….
而常见的有监督学习则简略很多，能够认为是强化学习的一种非凡状况，指标很清晰就是 groudTruth，因而对应的 reward 也比拟清晰。

强化学习依照集体了解能够演绎为以下三大类：

• DQN：Deep Q network，比拟合乎人的直观感触逻辑的一种类型，它会训练一个评估 Q -value 的网络，对任一 state 能给出各个 Action 的 reward，而后最终抉择 reward 最大的那个 action 进行操作即可。训练过程通过评估 ” 预计的 Q -value“”和“真正失去的 Q -value”的后果进行反向传递，最终让网络预计 Q -value 越来越准。
• Policy Gradient：是更加端到端的一种类型，训练一个网络，对任一 state 间接给出最终的 action。DQN 的适用范围须要间断 state 的 Q -value 也比拟间断（下围棋等不实用这种状况），而 Policy Gradient 因为疏忽外部过程间接给出 action，具备更大的普适性。但它的毛病是更难以评估及收敛。个别的训练过程是：对某一 state，同时随机的采取多种 action，评估各种 action 的后果进行反向传递，最终让网络输入成果更好的 action。
• Actor-Critic：试着糅合后面两种网络，舍短取长，一方面用 policy Gradient 网络进行任一 state 的 action 输入，另外一方面用 DQN 网络对 policy gradient 的 action 输入进行较好的量化评估并以之来领导 policy gradient 的更新。如名字所示，就像表演者和评论家的关系。训练过程须要同时训练 actor（policy Graident）和 critic(DQN)网络，但 actor 的训练只须要 follow critic 的指引就好。它有很多的变种，也是以后 DRL 实践钻研上不停倒退的次要方向。

1. 时序数据的压缩

===========

对海量的时序数据进行压缩是不言而喻的一个事件，因而在学术界和工业界也有很多的钻研和摸索，一些办法有：

• Snappy：对整数或字符串进行压缩，次要用了长距离预测和游程编码（RLE），宽泛的利用包含 Infuxdb；
• Simple8b：先对数据进行前后 delta 解决，如果雷同用 RLE 编码；否则依据一张有 16 个 entry 的码表把 1 到 240 个数（每个数的 bits 依据码表）pack 到 8B 为单位的数据中，有宽泛的利用包含 Infuxdb；
• Compression planner：引入了一些 general 的压缩 tool 如 scale, delta, dictionary, huffman, run length 和 patched constant 等，而后提出了用动态的或动静方法组合尝试这些工具来进行压缩；想法挺新鲜但理论性能会是个问题；
• ModelarDB：偏重在有损压缩，基于用户给定的可容忍损失进行压缩。根本思维是把保护一个小 buff，探测单前数据是否合乎某种模式（斜率的直线拟合），如果不胜利，切换模式从新开始 buff 等；对反对有损的 IoT 畛域比拟适合；
• Sprintz：也是在 IoT 畛域成果会比拟好，偏重在 8 /16 bit 的整数解决；次要用了 scale 进行预测而后用 RLC 进行差值编码并做 bit-level 的 packing；
• Gorilla：利用在 Facebook 高吞吐实时零碎中的过后 sofa 的压缩算法，进行无损压缩，宽泛实用于 IoT 和云端服务等各个领域。它引入 delta-of-delta 对工夫戳进行解决，用 xor 对数据进行变换而后用 Huffman 编码及 bit-packing。示例图如下。
• MO：相似 Gorilla，但去掉了 bit-packing，所有的数据操作根本都是字节对齐，升高了压缩率但提供了解决性能；
• …

还有很多相干的压缩算法，总的来说：

1. 它们根本都是反对单模式，或者无限的偏 static 的模式进行数据的压缩；
2. 很多为了进步压缩率，都用了 bit-packing (甚至有损压缩），但对越来越宽泛应用的并行计算不太敌对；
3. 两阶段的基于深度学习的压缩算法

===================

3.1 时序数据压缩的个性

时序数据来源于 IoT、金融、互联网、业务管理监控等方方面面，状态个性相差很多，而后对数据精确度等的要求也不尽相同。如果只能有一种对立的压缩算法进行无差别看待地解决，那应该是基于无损的、用 8B 数据进行数据形容的算法。
下图是阿里云业务中一些时序数据的示例，无损是从宏观还是宏观层面，数据的 pattern 都是形形色色的，不仅仅是形态曲线，也包含数据精度等。所以压缩算法很有必要反对尽量多的一些压缩模式，而后又能够既无效又经济地抉择其中一种进行压缩。

对于一个大型的商用的时序数据压缩算法，须要重点关注三个重要的个性：

• Time correlation：时序数据有很强的工夫相关性，而后对应的数据基本上是间断的。采样距离通常是 1s，100ms 等；
• Pattern diversity：如上图，pattern 及个性差距会很大；
• Data massiveness：每天、每小时、每秒须要解决的数据量都是海量的，总体解决数据至多是在每天 10P 的 level，对应的压缩算法须要高效且有高吞吐率。

3.2 新算法核心理念

寻根究底，数据压缩的实质可分为两阶段：首先 Transform 阶段把数据从一个空间转化到另外一个更规定的空间，而后在差值编码阶段用各种各样的方法较好的标识变换后的差值。
依据时序数据的特点，能够定义以下 6 个根本的 transform primitives（可扩大）。

而后定义以下 3 中根本的 differential coding primitives（可扩大）。

接下来把下面的两种 tools 排列组合进行压缩？这样可行但成果必定是不太好，因为模式抉择和相干参数的 cost 比重太高了，须要 2B（primitive choice + primitive parameter）的管制信息，占了 8B 须要表白数据的 25%。
更好的应该是对数据的个性进行抽象化分层表白，示意图如下。创立一个控制参数集较好的表白所有的状况，而后在全局 (一个 timeline) 层面抉择适合的参数来确定一个搜寻空间（只蕴含大量的压缩模式，譬如 4 种）；而后在具体进行每个点的压缩时，遍历从中抉择出最好的那一种压缩模式进行压缩。管制信息的比重在~3%。

3.3 两阶段压缩框架 AMMMO

AMMMO（adatpive multiple mode middle-out）整体过程分为两个阶段，第一阶段确定以后这条工夫线的总体个性（确定 9 个控制参数的具体值）；而后在第二阶段在大量的压缩模式中遍历并查找最初的一种进行压缩，具体框图如下。

第二阶段的模式抉择没有难度，逻辑简略适宜高效率执行；第一阶段确定各参数值（9 个这里）失去适合的压缩空间有比拟大的挑战，须要从实践上的 300K 多个排列组合抉择里找出适合的那一个。

3.4 基于规定的模式空间抉择算法

能够设计一种算法，譬如创立各个压缩模式的成果记录牌(scoreboard），而后遍历一个 timeline 里的所有点并进行剖析记录，而后再通过统计分析比拟等抉择最好的模式。一些不言而喻的问题有：

• 抉择的评估指标是否现实？
• 须要人工去思考并编写程序，有较多的实现，debug 和 maintain 的工作量；
• 如果算法中的 primitive，压缩模式等做了扭转，整个代码都须要重构，基于下面的抉择不是实践抉择，须要一种主动且较智能的办法撑持不停的演变等。

1. 深度强化学习

==========

4.1 问题建模

简化下面的整个模式空间抉择算法如下图，咱们能够把这个问题等同于多指标的分类问题，每个参数就是一个指标，每个参数空间的取值范畴就是可抉择的类目数。深度学习在图像分类，语义了解等方面证实了它的高可用性。相似地，咱们也能够把这里的模式空间的抉择问题用深度学习来实现，把它当做一个 multi-label 的 classification 问题。

用什么样的网络？思考到辨认的次要关系是 delta/xor, shift，bitmask 等为主，cnn 不失当，full-connect 的 mlp 比拟适合。相应地，把一条工夫线上的所有点，如果 1 小时就是 3600 个共 3600*8B，有些太多，思考到同一 timeline 外部一段一段的相似性，把 32 个点作为一个最根本的处理单元。
接下来，怎么去创立训练样本？怎么给样本寻找 label 呢？
在这里咱们引入了强化学习，而不是有监督的学习去训练，因为：

• 去创立有 label 的样本很难：32 个样本 256B，实践上 sample 有 256^256 中可能性，对每个这种样本，须要遍历 300K 的可能性能力找出最好的那一个。创立及抉择 sample，create label 的工作量都十分大；
• 这不是一般的 one-class-label 问题：给定一个样本，并不是有惟一的最好的一个后果，很有可能很多的抉择都能获得雷同的压缩成果；N class（N 根本不可知）的训练又减少了很多难度；
• 须要一种自动化的办法：压缩的 tool 等参数抉择很有可能是须要扩大的，如果产生整个训练样本的创立等都须要从新再来。须要一种自动化的方法。

用什么样的强化学习呢？DQN，policy gradient, 还是 actor-critic? 如后面剖析，DQN 是不太适宜 reward/action 不间断的的状况，这里的参数，譬如 majorMode 0 和 1 是齐全不同的两种后果，所以 DQN 不适合。此外，压缩问题一方面不容易评估另外网络也没有那么简单，不须要 actor-critic。最终咱们抉择了 policy gradient。
Policy gradient 常见的 loss 是用一个缓缓进步的 baseline 作为衡量标准来反馈以后的 action 是否适合，但这里并不太适合（成果尝试了也不太好），因为这里 sample 的实践 block(256^256) state 太多了一些。为此，咱们专门设计了一个 loss。

失去了每个 block 的参数后，思考到 block 的相关性等。能够用统计的方法，聚合失去整个 timeline 的最终参数设置。

4.2 深度强化学习网络框架

整体的网络框架示意图如下：

在训练端：随机抉择 M 个 block，每个 block 复制 N 份，而后输出到有 3 个隐含层的全连贯网络中，用 region softmax 失去各参数各种 choice 的概率，而后依照概率去 sample 每个参数的值，失去参数后输出到底层的压缩算法进行理论压缩并失去压缩值。复制的 N 个 block 互相比拟计算 loss 而后做反向流传。loss 的整体设计为：

_fn(copi)_形容了压缩成果，比 N 个 block 的均值高就正反馈，_Hcs(copi)_是穿插熵，心愿得分高的概率越大越确定越好；反之亦然。前面的_H（cop)_是穿插熵作为正则化因子来尽量避免网络固化且收敛到部分最优。
在推理端，能够把一个 timeline 的全副或部分 block 输出到网络中，失去参数，做统计聚合而后失去整个 timeline 的参数。

1. 后果数据

========

5.1 实验设计

测试数据局部一方面随机选取了阿里云业务 IoT 和 server 两个大场景下共 28 个大的 timeline；另外也选取了时序数据分析开掘畛域最通用的数据集 UCR。根本信息如下：

比照算法选取了比拟有对比性的 Gorilla，MO 和 Snappy。因为 AMMMO 是两阶段的压缩算法框架，第一阶段的参数抉择能够有各种各样的算法，这里选用了 Lazy（简略粗犷的设置一些普世参数），rnd1000Avg（随机 1000 次取成果平均值），Analyze（用人工代码的算法)和 ML（深度强化学习的方法）等。

5.2 压缩成果比照

首先从整体压缩率来看，AMMMO 两阶段自适应多模式的压缩比起 Gorila/MO 等有显著的成果晋升，均匀压缩率晋升在 50% 左右。

而后 ML 的成果怎么样呢？下图在 ML 的视线比照了测试集 B 上的压缩成果，总的来说，ML 相比人工精心设计的算法略好，比随机均匀等显著好很多。

5.3 运行效率

AMMMO 借鉴了 MO 的设计思维，移除了 bit-packing，不仅仅在 CPU 上能高速运行，也特地适宜于并行计算平台如 GPU。此外 AMMMO 分两阶段，其中第一阶段的性能会差一些，但很多时候，譬如对一个特定的设施过来 2 天的数据，全局压缩参数是能够复用的。下图形容了整体的性能比照，试验环境为“Intel CPU 8163 + Nvidia GPU P100″，其中 AMMMO 的代码应用了 P100。

从上图中看出，AMMMO 在压缩端和解压缩端都能达到 GB/ s 的解决性能，性能指标还是很不错的。

5.4 算法学到的成果

深度强化学习训练的网络从最终成果上看着不错，那它是不是真的有学到有意义的内容呢？下标比照了 3 中算法在几个测试集上的体现，能够看出，ML 版本的参数抉择和剖析算法 / 最优成果抉择是差不多的，特地是在 byte offset 和 majorMode 的抉择上。

这种压缩的全连贯网络参数表象会是怎么样的？对第一层进行了参数 heatmap 可视化（正的参数为红色，负的为蓝色，值越大色彩越亮），如下：

能够显著看到 32 个点在雷同的 byte 上有很多规定的操作，竖线（如果逾越 byte 则混同状况），能够认为是在对应的地位上做 delta 或 xor 运算等。而后数字变动最大的 Byte0 的参数也比拟沉闷。
综上，深度学习学到的货色还是挺有解释性的。

1. 相干人员和致谢

===========

在整个过程中，Yanqing peng，飞刀，汪晟，乐予，麦君和 Yue Xie 等一起付出了很多的致力，特别感谢飞刀老师的方向指引和总体判断；
此外，特别感谢矽厉等在工作中给予的反对，感激德施等在业务上给予的帮忙和反对。

原文链接
本文为阿里云原创内容，未经容许不得转载。