如何更高效地壓縮時(shí)序數(shù)據(jù)？基于深度強(qiáng)化學(xué)習(xí)的探索

隨著移動(dòng)互聯(lián)網(wǎng)、IoT、5G 等的應(yīng)用和普及，一步一步地我們走進(jìn)了數(shù)字經(jīng)濟(jì)時(shí)代。隨之而來的海量數(shù)據(jù)將是一種客觀的存在，并發(fā)揮出越來越重要的作用。時(shí)序數(shù)據(jù)是海量數(shù)據(jù)中的一個(gè)重要組成部分，除了挖掘分析預(yù)測(cè)等，如何高效的壓縮存儲(chǔ)是一個(gè)基礎(chǔ)且重要的課題。同時(shí)，我們也正處在人工智能時(shí)代，深度學(xué)習(xí)已經(jīng)有了很多很好的應(yīng)用，如何在更多更廣的層面發(fā)揮作用？本文總結(jié)了當(dāng)前學(xué)術(shù)界和工業(yè)界數(shù)據(jù)壓縮的方法，分析了大型商用時(shí)序數(shù)據(jù)壓縮的特性，提出了一種新的算法，分享用深度強(qiáng)化學(xué)習(xí)進(jìn)行數(shù)據(jù)壓縮的研究探索及取得的成果。

深度學(xué)習(xí)的本質(zhì)是做決策，用它解決具體的問題時(shí)很重要的是找到契合點(diǎn)，合理建模，然后整理數(shù)據(jù)優(yōu)化 loss 等最終較好地解決問題。在過去的一段時(shí)間，我們?cè)谟蒙疃葟?qiáng)化學(xué)習(xí)進(jìn)行數(shù)據(jù)壓縮上做了一些研究探索并取得了一些成績(jī)，已經(jīng)在 ICDE 2020 research track 發(fā)表（Two-level Data Compression using Machine Learning in Time Series Database）并做了口頭匯報(bào)。在這里做一個(gè)整體粗略介紹，希望對(duì)其它的場(chǎng)景，至少是其它數(shù)據(jù)的壓縮等，帶來一點(diǎn)借鑒作用。

背景描述

1 時(shí)序數(shù)據(jù)

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

關(guān)于時(shí)序數(shù)據(jù)庫的工作內(nèi)容，簡(jiǎn)略地，在用戶的使用層面它需要響應(yīng)海量的查詢，分析，預(yù)測(cè)等；而在底層它則需要處理海量的讀寫，壓縮解壓縮，采用聚合等操作，而這些的基本操作單元就是時(shí)序數(shù)據(jù) <timestamp, value>，一般（也可以簡(jiǎn)化）用兩個(gè) 8 byte 的值進(jìn)行統(tǒng)一描述。

可以想象，任何電子設(shè)備每天都在產(chǎn)生各種各樣海量的時(shí)序數(shù)據(jù)，需要海量的存儲(chǔ)空間等，對(duì)它進(jìn)行壓縮存儲(chǔ)及處理是一個(gè)自然而然的方法。而這里的著重點(diǎn)就是如何進(jìn)行更高效的壓縮。

2  強(qiáng)化學(xué)習(xí)

機(jī)器學(xué)習(xí)按照樣本是否有 groundTruth 可分為有監(jiān)督學(xué)習(xí)，無監(jiān)督學(xué)習(xí)，以及強(qiáng)化學(xué)習(xí)等。強(qiáng)化學(xué)習(xí)顧名思義是不停地努力地去學(xué)習(xí)，不需要 groundTruth，真實(shí)世界很多時(shí)候也沒有 groundTruth，譬如人的認(rèn)知很多時(shí)候就是不斷迭代學(xué)習(xí)的過程。從這個(gè)意義上來說，強(qiáng)化學(xué)習(xí)是更符合或更全面普遍的一種處理現(xiàn)實(shí)世界問題的過程和方法，所以有個(gè)說法是：如果深度學(xué)習(xí)慢慢地會(huì)像 C/Python/Java 那樣成為解決具體問題的一個(gè)基礎(chǔ)工具的話，那么強(qiáng)化學(xué)習(xí)是深度學(xué)習(xí)的一個(gè)基礎(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í)則簡(jiǎn)單很多，可以認(rèn)為是強(qiáng)化學(xué)習(xí)的一種特殊情況，目標(biāo)很清晰就是 groudTruth，因此對(duì)應(yīng)的 reward 也比較清晰。

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

1）DQN

Deep Q network，比較符合人的直觀感受邏輯的一種類型，它會(huì)訓(xùn)練一個(gè)評(píng)估 Q-value 的網(wǎng)絡(luò)，對(duì)任一 state 能給出各個(gè) Action 的 reward，然后最終選擇 reward 最大的那個(gè) action 進(jìn)行操作即可。訓(xùn)練過程通過評(píng)估 “估計(jì)的 Q-value” 和 “真正得到的 Q-value” 的結(jié)果進(jìn)行反向傳遞，最終讓網(wǎng)絡(luò)估計(jì) Q-value 越來越準(zhǔn)。

2）Policy Gradient

是更加端到端的一種類型，訓(xùn)練一個(gè)網(wǎng)絡(luò)，對(duì)任一 state 直接給出最終的 action。DQN 的適用范圍需要連續(xù) state 的 Q-value 也比較連續(xù)（下圍棋等不適用這種情況），而 Policy Gradient 由于忽略內(nèi)部過程直接給出 action，具有更大的普適性。但它的缺點(diǎn)是更難以評(píng)價(jià)及收斂。一般的訓(xùn)練過程是：對(duì)某一 state，同時(shí)隨機(jī)的采取多種 action，評(píng)價(jià)各種 action 的結(jié)果進(jìn)行反向傳遞，最終讓網(wǎng)絡(luò)輸出效果更好的 action。

3）Actor-Critic

試著糅合前面兩種網(wǎng)絡(luò)，取長(zhǎng)補(bǔ)短，一方面用 policy Gradient 網(wǎng)絡(luò)進(jìn)行任一 state 的 action 輸出，另外一方面用 DQN 網(wǎng)絡(luò)對(duì) policy gradient 的 action 輸出進(jìn)行較好的量化評(píng)價(jià)并以之來指導(dǎo) policy gradient 的更新。如名字所示，就像表演者和評(píng)論家的關(guān)系。訓(xùn)練過程需要同時(shí)訓(xùn)練 actor（policy Graident）和 critic（QN）網(wǎng)絡(luò)，但 actor 的訓(xùn)練只需要 follow critic 的指引就好。它有很多的變種，也是當(dāng)前 DRL 理論研究上不停發(fā)展的主要方向。

時(shí)序數(shù)據(jù)的壓縮

對(duì)海量的時(shí)序數(shù)據(jù)進(jìn)行壓縮是顯而易見的一個(gè)事情，因此在學(xué)術(shù)界和工業(yè)界也有很多的研究和探索，一些方法有：

Snappy：對(duì)整數(shù)或字符串進(jìn)行壓縮，主要用了長(zhǎng)距離預(yù)測(cè)和游程編碼（RLE），廣泛的應(yīng)用包括 Infuxdb。

Simple8b：先對(duì)數(shù)據(jù)進(jìn)行前后 delta 處理，如果相同用RLE編碼；否則根據(jù)一張有 16 個(gè) entry 的碼表把 1 到 240 個(gè)數(shù)（每個(gè)數(shù)的 bits 根據(jù)碼表）pack 到 8B 為單位的數(shù)據(jù)中，有廣泛的應(yīng)用包括 Infuxdb。

Compression planner：引入了一些 general 的壓縮 tool 如 scale, delta, dictionary, huffman, run length 和 patched constant 等，然后提出了用靜態(tài)的或動(dòng)態(tài)辦法組合嘗試這些工具來進(jìn)行壓縮；想法挺新穎但實(shí)際性能會(huì)是個(gè)問題。

ModelarDB：側(cè)重在有損壓縮，基于用戶給定的可容忍損失進(jìn)行壓縮�；�本思想是把維護(hù)一個(gè)小 buff，探測(cè)單前數(shù)據(jù)是否符合某種模式（斜率的直線擬合），如果不成功，切換模式重新開始buff等；對(duì)支持有損的 IoT 領(lǐng)域比較合適。

Sprintz：也是在 IoT 領(lǐng)域效果會(huì)比較好，側(cè)重在 8/16 bit 的整數(shù)處理；主要用了 scale 進(jìn)行預(yù)測(cè)然后用 RLC 進(jìn)行差值編碼并做 bit-level 的 packing。

Gorilla：應(yīng)用在 Facebook 高吞吐實(shí)時(shí)系統(tǒng)中的當(dāng)時(shí) sofa 的壓縮算法，進(jìn)行無損壓縮，廣泛適用于 IoT 和云端服務(wù)等各個(gè)領(lǐng)域。它引入 delta-of-delta 對(duì)時(shí)間戳進(jìn)行處理，用 xor 對(duì)數(shù)據(jù)進(jìn)行變換然后用 Huffman 編碼及 bit-packing。示例圖如下所示。

MO：類似 Gorilla，但去掉了 bit-packing，所有的數(shù)據(jù)操作基本都是字節(jié)對(duì)齊，降低了壓縮率但提供了處理性能。