彼節(jié)者有間，而刀刃者無厚；以無厚入有間，恢恢乎其于游刃必有余地矣 ----- 庖丁解牛

前言：隨著移動互聯(lián)網(wǎng)、IoT、5G等的應(yīng)用和普及，一步一步地我們走進(jìn)了數(shù)字經(jīng)濟(jì)時代。隨之而來的海量數(shù)據(jù)將是一種客觀的存在，并發(fā)揮出越來越重要的作用。時序數(shù)據(jù)是海量數(shù)據(jù)中的一個重要組成部分，除了挖掘分析預(yù)測等，如何高效的壓縮存儲是一個基礎(chǔ)且重要的課題。同時，我們也正處在人工智能時代，深度學(xué)習(xí)已經(jīng)有了很多很好的應(yīng)用，如何在更多更廣的層面發(fā)揮作用？深度學(xué)習(xí)的本質(zhì)是做決策，用它解決具體的問題時很重要的是找到契合點(diǎn)，合理建模，然后整理數(shù)據(jù)優(yōu)化loss等最終較好地解決問題。在過去的一段時間，我們在用深度強(qiáng)化學(xué)習(xí)進(jìn)行數(shù)據(jù)壓縮上做了一些研究探索并取得了一些成績，已經(jīng)在ICDE 2020 research track發(fā)表（Two-level Data Compression using Machine Learning in Time Series Database）并做了口頭匯報(bào)。在這里做一個整體粗略介紹，希望對其它的場景，至少是其它數(shù)據(jù)的壓縮等，帶來一點(diǎn)借鑒作用。

背景描述
1.1 時序數(shù)據(jù)
時序數(shù)據(jù)顧名思義指的是和時間序列相關(guān)的數(shù)據(jù)，是日常隨處可見的一種數(shù)據(jù)形式。下圖羅列了三個示例 a）心電圖，b）股票指數(shù)，c）具體股票交易數(shù)據(jù)。

關(guān)于時序數(shù)據(jù)庫的工作內(nèi)容，簡略地，在用戶的使用層面它需要響應(yīng)海量的查詢，分析，預(yù)測等；而在底層它則需要處理海量的讀寫，壓縮解壓縮，采用聚合等操作，而這些的基本操作單元就是時序數(shù)據(jù)，一般（也可以簡化）用兩個8 byte的值進(jìn)行統(tǒng)一描述。
可以想象，任何電子設(shè)備每天都在產(chǎn)生各種各樣海量的時序數(shù)據(jù)，需要海量的存儲空間等，對它進(jìn)行壓縮存儲及處理是一個自然而然的方法。而這里的著重點(diǎn)就是如何進(jìn)行更高效的壓縮。

1.2 強(qiáng)化學(xué)習(xí)
機(jī)器學(xué)習(xí)按照樣本是否有g(shù)roundTruth可分為有監(jiān)督學(xué)習(xí)，無監(jiān)督學(xué)習(xí)，以及強(qiáng)化學(xué)習(xí)等。強(qiáng)化學(xué)習(xí)顧名思義是不停得努力得去學(xué)習(xí)，不需要groundTruth，真實(shí)世界很多時候也沒有g(shù)roundTruth，譬如人的認(rèn)知很多時間就是不斷迭代學(xué)習(xí)的過程。從這個意義上來說，強(qiáng)化學(xué)習(xí)是更符合或更全面普遍的一直處理現(xiàn)實(shí)世界問題的過程和方法，所以有個說法是：如果深度學(xué)習(xí)慢慢地會像C/Python/Java那樣成為解決具體問題的一個基礎(chǔ)工具的話，那么強(qiáng)化學(xué)習(xí)是深度學(xué)習(xí)的一個基礎(chǔ)工具。
強(qiáng)化學(xué)習(xí)的經(jīng)典示意圖如下，基本要素為State，Action，和Environment。基本過程為：Environment給出State，Agent根據(jù)state做Action決策，Action作用在Environment上產(chǎn)生新的State及reward，其中reward用來指導(dǎo)Agent做出更好的Action決策，循環(huán)往復(fù)….
而常見的有監(jiān)督學(xué)習(xí)則簡單很多，可以認(rèn)為是強(qiáng)化學(xué)習(xí)的一種特殊情況，目標(biāo)很清晰就是groudTruth，因此對應(yīng)的reward也比較清晰。

強(qiáng)化學(xué)習(xí)按照個人理解可以歸納為以下三大類：

DQN：Deep Q network，比較符合人的直觀感受邏輯的一種類型，它會訓(xùn)練一個評估Q-value的網(wǎng)絡(luò)，對任一state能給出各個Action的reward，然后最終選擇reward最大的那個action進(jìn)行操作即可。訓(xùn)練過程通過評估"估計(jì)的Q-value“”和“真正得到的Q-value”的結(jié)果進(jìn)行反向傳遞，最終讓網(wǎng)絡(luò)估計(jì)Q-value越來越準(zhǔn)。
Policy Gradient：是更加端到端的一種類型，訓(xùn)練一個網(wǎng)絡(luò)，對任一state直接給出最終的action。DQN的適用范圍需要連續(xù)state的Q-value也比較連續(xù)（下圍棋等不適用這種情況），而Policy Gradient由于忽略內(nèi)部過程直接給出action，具有更大的普適性。但它的缺點(diǎn)是更難以評價(jià)及收斂。一般的訓(xùn)練過程是：對某一state，同時隨機(jī)的采取多種action，評價(jià)各種action的結(jié)果進(jìn)行反向傳遞，最終讓網(wǎng)絡(luò)輸出效果更好的action。
Actor-Critic：試著糅合前面兩種網(wǎng)絡(luò)，取長補(bǔ)短，一方面用policy Gradient網(wǎng)絡(luò)進(jìn)行任一state的action輸出，另外一方面用DQN網(wǎng)絡(luò)對policy gradient的action輸出進(jìn)行較好的量化評價(jià)并以之來指導(dǎo)policy gradient的更新。如名字所示，就像表演者和評論家的關(guān)系。訓(xùn)練過程需要同時訓(xùn)練actor（policy Graident）和critic(DQN)網(wǎng)絡(luò)，但actor的訓(xùn)練只需要follow critic的指引就好。它有很多的變種，也是當(dāng)前DRL理論研究上不停發(fā)展的主要方向。
2. 時序數(shù)據(jù)的壓縮
對海量的時序數(shù)據(jù)進(jìn)行壓縮是顯而易見的一個事情，因此在學(xué)術(shù)界和工業(yè)界也有很多的研究和探索，一些方法有：

Snappy：對整數(shù)或字符串進(jìn)行壓縮，主要用了長距離預(yù)測和游程編碼（RLE），廣泛的應(yīng)用包括Infuxdb；
Simple8b：先對數(shù)據(jù)進(jìn)行前后delta處理，如果相同用RLE編碼；否則根據(jù)一張有16個entry的碼表把1到240個數(shù)（每個數(shù)的bits根據(jù)碼表）pack到8B為單位的數(shù)據(jù)中，有廣泛的應(yīng)用包括Infuxdb；
Compression planner：引入了一些general的壓縮tool如scale, delta, dictionary, huffman, run length和patched constant等，然后提出了用靜態(tài)的或動態(tài)辦法組合嘗試這些工具來進(jìn)行壓縮；想法挺新穎但實(shí)際性能會是個問題；
ModelarDB：側(cè)重在有損壓縮，基于用戶給定的可容忍損失進(jìn)行壓縮。基本思想是把維護(hù)一個小buff，探測單前數(shù)據(jù)是否符合某種模式（斜率的直線擬合），如果不成功，切換模式重新開始buff等；對支持有損的IoT領(lǐng)域比較合適；
Sprintz：也是在IoT領(lǐng)域效果會比較好，側(cè)重在8/16 bit的整數(shù)處理；主要用了scale進(jìn)行預(yù)測然后用RLC進(jìn)行差值編碼并做bit-level的packing；
Gorilla：應(yīng)用在Facebook高吞吐實(shí)時系統(tǒng)中的當(dāng)時sofa的壓縮算法，進(jìn)行無損壓縮，廣泛適用于IoT和云端服務(wù)等各個領(lǐng)域。它引入delta-of-delta對時間戳進(jìn)行處理，用xor對數(shù)據(jù)進(jìn)行變換然后用Huffman編碼及bit-packing。示例圖如下。
MO：類似Gorilla，但去掉了bit-packing，所有的數(shù)據(jù)操作基本都是字節(jié)對齊，降低了壓縮率但提供了處理性能；
…

還有很多相關(guān)的壓縮算法，總的來說：

它們基本都是支持單模式，或者有限的偏static的模式進(jìn)行數(shù)據(jù)的壓縮；
很多為了提高壓縮率，都用了bit-packing (甚至有損壓縮），但對越來越廣泛使用的并行計(jì)算不太友好；
3. 兩階段的基于深度學(xué)習(xí)的壓縮算法
3.1 時序數(shù)據(jù)壓縮的特性
時序數(shù)據(jù)來源于IoT、金融、互聯(lián)網(wǎng)、業(yè)務(wù)管理監(jiān)控等方方面面，形態(tài)特性相差很多，然后對數(shù)據(jù)精確度等的要求也不盡相同。如果只能有一種統(tǒng)一的壓縮算法進(jìn)行無差別對待地處理，那應(yīng)該是基于無損的、用8B數(shù)據(jù)進(jìn)行數(shù)據(jù)描述的算法。
下圖是阿里云業(yè)務(wù)中一些時序數(shù)據(jù)的示例，無損是從宏觀還是微觀層面，數(shù)據(jù)的pattern都是五花八門的，不僅僅是形狀曲線，也包括數(shù)據(jù)精度等。所以壓縮算法很有必要支持盡量多的一些壓縮模式，然后又可以既有效又經(jīng)濟(jì)地選擇其中一種進(jìn)行壓縮。

對于一個大型的商用的時序數(shù)據(jù)壓縮算法，需要重點(diǎn)關(guān)注三個重要的特性：

Time correlation：時序數(shù)據(jù)有很強(qiáng)的時間相關(guān)性，然后對應(yīng)的數(shù)據(jù)基本上是連續(xù)的。采樣間隔通常是1s，100ms等；
Pattern diversity：如上圖，pattern及特性差距會很大；
Data massiveness：每天、每小時、每秒需要處理的數(shù)據(jù)量都是海量的，總體處理數(shù)據(jù)至少是在每天10P的level，對應(yīng)的壓縮算法需要高效且有高吞吐率。
3.2 新算法核心理念
追本溯源，數(shù)據(jù)壓縮的本質(zhì)可分為兩階段：首先Transform階段把數(shù)據(jù)從一個空間轉(zhuǎn)化到另外一個更規(guī)則的空間，然后在差值編碼階段用各種各樣的辦法較好的標(biāo)識變換后的差值。
根據(jù)時序數(shù)據(jù)的特點(diǎn)，可以定義以下6個基本的transform primitives（可擴(kuò)展）。

然后定義以下3中基本的differential coding primitives（可擴(kuò)展）。

接下來把上面的兩種tools排列組合進(jìn)行壓縮？這樣可行但效果肯定是不太好，因?yàn)槟Ｊ竭x擇和相關(guān)參數(shù)的cost比重太高了，需要2B（primitive choice + primitive parameter）的控制信息，占了8B需要表達(dá)數(shù)據(jù)的25%。
更好的應(yīng)該是對數(shù)據(jù)的特性進(jìn)行抽象化分層表達(dá)，示意圖如下。創(chuàng)建一個控制參數(shù)集較好的表達(dá)所有的情況，然后在全局(一個timeline)層面選擇合適的參數(shù)來確定一個搜索空間（只包含少量的壓縮模式，譬如4種）；然后在具體進(jìn)行每個點(diǎn)的壓縮時，遍歷從中選擇出最好的那一種壓縮模式進(jìn)行壓縮。控制信息的比重在~3%。

3.3 兩階段壓縮框架AMMMO
AMMMO（adatpive multiple mode middle-out）整體過程分為兩個階段，第一階段確定當(dāng)前這條時間線的總體特性（確定9個控制參數(shù)的具體值）；然后在第二階段在少量的壓縮模式中遍歷并查找最后的一種進(jìn)行壓縮，具體框圖如下。

第二階段的模式選擇沒有難度，邏輯簡單適合高效率執(zhí)行；第一階段確定各參數(shù)值（9個這里）得到合適的壓縮空間有比較大的挑戰(zhàn)，需要從理論上的300K多個排列組合選擇里找出合適的那一個。

3.4 基于規(guī)則的模式空間選擇算法
可以設(shè)計(jì)一種算法，譬如創(chuàng)建各個壓縮模式的效果記錄牌(scoreboard），然后遍歷一個timeline里的所有點(diǎn)并進(jìn)行分析記錄，然后再經(jīng)過統(tǒng)計(jì)分析比較等選擇最好的模式。一些顯而易見的問題有：

選擇的評估指標(biāo)是否理想？
需要人工去思考并編寫程序，有較多的實(shí)現(xiàn)，debug和maintain的工作量；
如果算法中的primitive，壓縮模式等做了改變，整個代碼都需要重構(gòu)，基于上面的選擇不是理論選擇，需要一種自動且較智能的方法支撐不停的演化等。
4. 深度強(qiáng)化學(xué)習(xí)
4.1 問題建模
簡化上面的整個模式空間選擇算法如下圖，我們可以把這個問題等同于多目標(biāo)的分類問題，每個參數(shù)就是一個目標(biāo)，每個參數(shù)空間的取值范圍就是可選擇的類目數(shù)。深度學(xué)習(xí)在圖像分類，語義理解等方面證明了它的高可用性。類似地，咱們也可以把這里的模式空間的選擇問題用深度學(xué)習(xí)來實(shí)現(xiàn)，把它當(dāng)做一個multi-label的classification問題。

用什么樣的網(wǎng)絡(luò)？考慮到識別的主要關(guān)系是delta/xor, shift，bitmask等為主，cnn不恰當(dāng)，full-connect的mlp比較合適。相應(yīng)地，把一條時間線上的所有點(diǎn)，如果1小時就是3600個共3600*8B，有些太多，考慮到同一timeline內(nèi)部一段一段的相似性，把32個點(diǎn)作為一個最基本的處理單元。
接下來，怎么去創(chuàng)建訓(xùn)練樣本？怎么給樣本尋找label呢？
在這里我們引入了強(qiáng)化學(xué)習(xí)，而不是有監(jiān)督的學(xué)習(xí)去訓(xùn)練，因?yàn)?#xff1a;

去創(chuàng)建有l(wèi)abel的樣本很難：32個樣本256B，理論上sample有256^256中可能性，對每個這種樣本，需要遍歷300K的可能性才能找出最好的那一個。創(chuàng)建及選擇sample，create label的工作量都非常大；
這不是普通的one-class-label問題：給定一個樣本，并不是有唯一的最好的一個結(jié)果，很有可能很多的選擇都能取得相同的壓縮效果；N class（N基本不可知）的訓(xùn)練又增加了很多難度；
需要一種自動化的方法：壓縮的tool等參數(shù)選擇很有可能是需要擴(kuò)展的，如果發(fā)生整個訓(xùn)練樣本的創(chuàng)建等都需要重新再來。需要一種自動化的辦法。
用什么樣的強(qiáng)化學(xué)習(xí)呢？DQN，policy gradient, 還是actor-critic? 如前面分析，DQN是不太適合reward/action不連續(xù)的的情況，這里的參數(shù)，譬如majorMode 0和1是完全不同的兩種結(jié)果，所以DQN不合適。此外，壓縮問題一方面不容易評價(jià)另外網(wǎng)絡(luò)也沒有那么復(fù)雜，不需要actor-critic。最終我們選擇了policy gradient。
Policy gradient常見的loss是用一個慢慢提高的baseline作為衡量標(biāo)準(zhǔn)來反饋當(dāng)前的action是否合適，但這里并不太合適（效果嘗試了也不太好），因?yàn)檫@里sample的理論block(256^256) state太多了一些。為此，我們專門設(shè)計(jì)了一個loss。

得到了每個block的參數(shù)后，考慮到block的相關(guān)性等。可以用統(tǒng)計(jì)的辦法，聚合得到整個timeline的最終參數(shù)設(shè)置。

4.2 深度強(qiáng)化學(xué)習(xí)網(wǎng)絡(luò)框架
整體的網(wǎng)絡(luò)框架示意圖如下：

在訓(xùn)練端：隨機(jī)選擇M個block，每個block復(fù)制N份，然后輸入到有3個隱含層的全連接網(wǎng)絡(luò)中，用region softmax得到各參數(shù)各種choice的概率，然后按照概率去sample每個參數(shù)的值，得到參數(shù)后輸入到底層的壓縮算法進(jìn)行實(shí)際壓縮并得到壓縮值。復(fù)制的N個block相互比較計(jì)算loss然后做反向傳播。loss的整體設(shè)計(jì)為：
?
fn(copi)描述了壓縮效果，比N個block的均值高就正反饋，Hcs(copi)是交叉熵，希望得分高的概率越大越確定越好；反之亦然。后面的H（cop)是交叉熵作為正則化因子來盡量避免網(wǎng)絡(luò)固化且收斂到局部最優(yōu)。?
在推理端，可以把一個timeline的全部或局部block輸入到網(wǎng)絡(luò)中，得到參數(shù)，做統(tǒng)計(jì)聚合然后得到整個timeline的參數(shù)。

結(jié)果數(shù)據(jù)
5.1 實(shí)驗(yàn)設(shè)計(jì)
測試數(shù)據(jù)部分一方面隨機(jī)選取了阿里云業(yè)務(wù)IoT和server兩個大場景下共28個大的timeline；另外也選取了時序數(shù)據(jù)分析挖掘領(lǐng)域最通用的數(shù)據(jù)集UCR。基本信息如下：

對比算法選取了比較有對比性的Gorilla，MO和Snappy。因?yàn)锳MMMO是兩階段的壓縮算法框架，第一階段的參數(shù)選擇可以有各種各樣的算法，這里選用了Lazy（簡單粗暴的設(shè)置一些普世參數(shù)），rnd1000Avg（隨機(jī)1000次取效果平均值），Analyze（用人工代碼的算法)和 ML（深度強(qiáng)化學(xué)習(xí)的辦法）等。

5.2 壓縮效果對比
首先從整體壓縮率來看，AMMMO兩階段自適應(yīng)多模式的壓縮比起Gorila/MO等有明顯的效果提升，平均壓縮率提升在50%左右。

然后ML的效果怎么樣呢？下圖在ML的視野對比了測試集B上的壓縮效果，總的來說，ML相比人工精心設(shè)計(jì)的算法略好，比隨機(jī)平均等明顯好很多。

5.3 運(yùn)行效率
AMMMO借鑒了MO的設(shè)計(jì)思想，移除了bit-packing，不僅僅在CPU上能高速運(yùn)行，也特別適合于并行計(jì)算平臺如GPU。此外AMMMO分兩階段，其中第一階段的性能會差一些，但很多時候，譬如對一個特定的設(shè)備過去2天的數(shù)據(jù)，全局壓縮參數(shù)是可以復(fù)用的。下圖描述了整體的性能對比，實(shí)驗(yàn)環(huán)境為“Intel CPU 8163 + Nvidia GPU P100"，其中AMMMO的代碼使用了P100。

從上圖中看出，AMMMO在壓縮端和解壓縮端都能達(dá)到GB/s的處理性能，性能指標(biāo)還是很不錯的。

5.4 算法學(xué)到的效果
深度強(qiáng)化學(xué)習(xí)訓(xùn)練的網(wǎng)絡(luò)從最終效果上看著不錯，那它是不是真的有學(xué)到有意義的內(nèi)容呢？下標(biāo)對比了3中算法在幾個測試集上的表現(xiàn)，可以看出，ML版本的參數(shù)選擇和分析算法/最優(yōu)效果選擇是差不多的，特別是在byte offset和majorMode的選擇上。

這種壓縮的全連接網(wǎng)絡(luò)參數(shù)表象會是怎么樣的？對第一層進(jìn)行了參數(shù)heatmap可視化（正的參數(shù)為紅色，負(fù)的為藍(lán)色，值越大顏色越亮），如下：

可以明顯看到32個點(diǎn)在相同的byte上有很多規(guī)則的操作，豎線（如果跨越byte則混淆情況），可以認(rèn)為是在對應(yīng)的位置上做delta或xor運(yùn)算等。然后數(shù)字變動最大的Byte0的參數(shù)也比較活躍。
綜上，深度學(xué)習(xí)學(xué)到的東西還是挺有解釋性的。

相關(guān)人員和致謝
在整個過程中，Yanqing peng，飛刀，汪晟，樂予，麥君和Yue Xie等一起付出了很多的努力，特別感謝飛刀老師的方向指引和總體判斷；
此外，特別感謝矽厲等在工作中給予的支持，感謝德施等在業(yè)務(wù)上給予的幫助和支持。

原文鏈接
本文為阿里云原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的深度强化学习在时序数据压缩中的应用--ICDE 2020收录论文的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。