彼節者有間，而刀刃者無厚；以無厚入有間，恢恢乎其于遊刃必有餘地矣。
——庖丁解牛
深度學習的本質是做決策，用它解決具體的問題時很重要的是找到契合點，合理模組化，然後整理資料優化 loss 等最終較好地解決問題。在過去的一段時間，我們在用深度強化學習進行資料壓縮上做了一些研究探索并取得了一些成績，已經在 ICDE 2020 research track 發表（Two-level Data Compression using Machine Learning in Time Series Database）并做了口頭彙報。在這裡做一個整體粗略介紹，希望對其它的場景，至少是其它資料的壓縮等，帶來一點借鑒作用。
背景描述
1 時序資料
時序資料顧名思義指的是和時間序列相關的資料，是日常随處可見的一種資料形式。下圖羅列了三個示例：a）心電圖，b）股票指數，c）具體股票交易資料。
關于時序資料庫的工作内容，簡略地，在使用者的使用層面它需要響應海量的查詢，分析，預測等；而在底層它則需要處理海量的讀寫，壓縮解壓縮，采用聚合等操作，而這些的基本操作單元就是時序資料 ，一般（也可以簡化）用兩個 8 byte 的值進行統一描述。
可以想象，任何電子裝置每天都在産生各種各樣海量的時序資料，需要海量的存儲空間等，對它進行壓縮存儲及處理是一個自然而然的方法。而這裡的着重點就是如何進行更高效的壓縮。
2 強化學習
機器學習按照樣本是否有 groundTruth 可分為有監督學習，無監督學習，以及強化學習等。強化學習顧名思義是不停地努力地去學習，不需要 groundTruth，真實世界很多時候也沒有 groundTruth，譬如人的認知很多時候就是不斷疊代學習的過程。從這個意義上來說，強化學習是更符合或更全面普遍的一種處理現實世界問題的過程和方法，是以有個說法是：如果深度學習慢慢地會像 C/Python/Java 那樣成為解決具體問題的一個基礎工具的話，那麼強化學習是深度學習的一個基礎工具。
強化學習的經典示意圖如下，基本要素為 State，Action，和 Environment。基本過程為：Environment 給出 State，Agent 根據 state 做 Action 決策，Action 作用在 Environment 上産生新的 State 及 reward，其中 reward 用來指導 Agent 做出更好的 Action 決策，循環往複….
而常見的有監督學習則簡單很多，可以認為是強化學習的一種特殊情況，目标很清晰就是 groudTruth，是以對應的 reward 也比較清晰。
強化學習按照個人了解可以歸納為以下三大類：
1）DQN
Deep Q network，比較符合人的直覺感受邏輯的一種類型，它會訓練一個評估 Q-value 的網絡，對任一 state 能給出各個 Action 的 reward，然後最終選擇 reward 最大的那個 action 進行操作即可。訓練過程通過評估 “估計的 Q-value” 和 “真正得到的 Q-value” 的結果進行反向傳遞，最終讓網絡估計 Q-value 越來越準。
2）Policy Gradient
是更加端到端的一種類型，訓練一個網絡，對任一 state 直接給出最終的 action。DQN 的适用範圍需要連續 state 的 Q-value 也比較連續（下圍棋等不适用這種情況），而 Policy Gradient 由于忽略内部過程直接給出 action，具有更大的普适性。但它的缺點是更難以評價及收斂。一般的訓練過程是：對某一 state，同時随機的采取多種 action，評價各種 action 的結果進行反向傳遞，最終讓網絡輸出效果更好的 action。
3）Actor-Critic
試着糅合前面兩種網絡，取長補短，一方面用 policy Gradient 網絡進行任一 state 的 action 輸出，另外一方面用 DQN 網絡對 policy gradient 的 action 輸出進行較好的量化評價并以之來指導 policy gradient 的更新。如名字所示，就像表演者和評論家的關系。訓練過程需要同時訓練 actor（policy Graident）和 critic（QN）網絡，但 actor 的訓練隻需要 follow critic 的指引就好。它有很多的變種，也是目前 DRL 理論研究上不停發展的主要方向。
時序資料的壓縮
對海量的時序資料進行壓縮是顯而易見的一個事情，是以在學術界和工業界也有很多的研究和探索，一些方法有：
- 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，所有的資料操作基本都是位元組對齊，降低了壓縮率但提供了處理性能。
- …
還有很多相關的壓縮算法，總的來說：
- 它們基本都是支援單模式，或者有限的偏static的模式進行資料的壓縮。
- 很多為了提高壓縮率，都用了 bit-packing (甚至有損壓縮），但對越來越廣泛使用的并行計算不太友好。
兩階段的基于深度學習的壓縮算法
1 時序資料壓縮的特性
時序資料來源于 IoT、金融、網際網路、業務管理監控等方方面面，形态特性相差很多，然後對資料精确度等的要求也不盡相同。如果隻能有一種統一的壓縮算法進行無差别對待地處理，那應該是基于無損的、用 8B 資料進行資料描述的算法。
下圖是阿裡雲業務中一些時序資料的示例，無損是從宏觀還是微觀層面，資料的 pattern 都是五花八門的，不僅僅是形狀曲線，也包括資料精度等。是以壓縮算法很有必要支援盡量多的一些壓縮模式，然後又可以既有效又經濟地選擇其中一種進行壓縮。
對于一個大型的商用的時序資料壓縮算法，需要重點關注三個重要的特性：
- Time correlation：時序資料有很強的時間相關性，然後對應的資料基本上是連續的。采樣間隔通常是 1s，100ms 等。
- Pattern diversity：如上圖，pattern 及特性差距會很大。
- Data massiveness：每天、每小時、每秒需要處理的資料量都是海量的，總體處理資料至少是在每天 10P 的 level，對應的壓縮算法需要高效且有高吞吐率。
2 新算法核心理念
追本溯源，資料壓縮的本質可分為兩階段：首先 Transform 階段把資料從一個空間轉化到另外一個更規則的空間，然後在內插補點編碼階段用各種各樣的辦法較好的辨別變換後的內插補點。
根據時序資料的特點，可以定義以下 6 個基本的 transform primitives（可擴充）:
然後定義以下 3 種基本的 differential coding primitives（可擴充）:
接下來把上面的兩種 tools 排列組合進行壓縮，這樣可行但效果肯定不太好，因為模式選擇和相關參數的 cost 比重太高了，需要 2B（primitive choice + primitive parameter）的控制資訊，占了 8B 需要表達資料的 25%。
更好的方法應該是對資料的特性進行抽象化分層表達，示意圖如下。建立一個控制參數集較好的表達所有的情況，然後在全局（一個 timeline）層面選擇合适的參數來确定一個搜尋空間（隻包含少量的壓縮模式，譬如 4 種）；然後在具體進行每個點的壓縮時，周遊從中選擇出最好的那一種壓縮模式進行壓縮。控制資訊的比重在 ~3%。
3 兩階段壓縮架構AMMMO
AMMMO（adatpive multiple mode middle-out）整體過程分為兩個階段，第一階段确定目前這條時間線的總體特性（确定 9 個控制參數的具體值）；然後在第二階段在少量的壓縮模式中周遊并查找最後的一種進行壓縮，具體框圖如下：
第二階段的模式選擇沒有難度，邏輯簡單适合高效率執行；第一階段确定各參數值（9個這裡）得到合适的壓縮空間有比較大的挑戰，需要從理論上的 300K 多個排列組合選擇裡找出合适的那一個。
4 基于規則的模式空間選擇算法
可以設計一種算法，譬如建立各個壓縮模式的效果記錄牌（scoreboard），然後周遊一個 timeline 裡的所有點并進行分析記錄，然後再經過統計分析比較等選擇最好的模式。一些顯而易見的問題有：
- 選擇的評估名額是否理想？
- 需要人工去思考并編寫程式，有較多的實作，debug 和 maintain 的工作量。
- 如果算法中的 primitive，壓縮模式等做了改變，整個代碼都需要重構，基于上面的選擇不是理論選擇，需要一種自動且較智能的方法支撐不停的演化等。
深度強化學習
1 問題模組化
簡化上面的整個模式空間選擇算法如下圖，我們可以把這個問題等同于多目标的分類問題，每個參數就是一個目标，每個參數空間的取值範圍就是可選擇的類目數。深度學習在圖像分類，語義了解等方面證明了它的高可用性。類似地，咱們也可以把這裡的模式空間的選擇問題用深度學習來實作，把它當做一個 multi-label 的 classification 問題。
用什麼樣的網絡？考慮到識别的主要關系是 delta/xor, shift，bitmask 等為主，cnn 不恰當，full-connect 的 mlp 比較合适。相應地，把一條時間線上的所有點，如果 1 小時就是 3600 個共 3600*8B，有些太多，考慮到同一 timeline 内部一段一段的相似性，把 32 個點作為一個最基本的處理單元。
接下來，怎麼去建立訓練樣本？怎麼給樣本尋找 label 呢？
在這裡我們引入了強化學習，而不是有監督的學習去訓練，因為：
1）去建立有 label 的樣本很難
32 個樣本 256B，理論上 sample 有 256^256 種可能性，對每個這種樣本，需要周遊 300K 的可能性才能找出最好的那一個。建立及選擇 sample，create label 的工作量都非常大。
2）這不是普通的 one-class-label 問題
給定一個樣本，并不是有唯一的最好的一個結果，很有可能很多的選擇都能取得相同的壓縮效果，N class（N 基本不可知）的訓練又增加了很多難度。
3）需要一種自動化的方法
壓縮的 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 的最終參數設定。
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 實驗設計
測試資料部分一方面随機選取了阿裡雲業務 IoT 和 server 兩個大場景下共 28 個大的 timeline；另外也選取了時序資料分析挖掘領域最通用的資料集 UCR。基本資訊如下：
對比算法選取了比較有對比性的 Gorilla，MO 和 Snappy。因為 AMMMO 是兩階段的壓縮算法架構，第一階段的參數選擇可以有各種各樣的算法，這裡選用了 Lazy（簡單粗暴的設定一些普世參數），rnd1000Avg（随機 1000 次取效果平均值），Analyze（用人工代碼的算法)和 ML（深度強化學習的辦法）等。
2 壓縮效果對比
首先從整體壓縮率來看，AMMMO 兩階段自适應多模式的壓縮比起 Gorila/MO 等有明顯的效果提升，平均壓縮率提升在 50% 左右。
然後 ML 的效果怎麼樣呢？下圖在 ML 的視野對比了測試集 B 上的壓縮效果，總的來說，ML 相比人工精心設計的算法略好，比随機平均等明顯好很多。
3 運作效率
AMMMO 借鑒了 MO 的設計思想，移除了 bit-packing，不僅僅在 CPU 上能高速運作，也特别适合于并行計算平台如 GPU。此外 AMMMO 分兩階段，其中第一階段的性能會差一些，但很多時候，譬如對一個特定的裝置過去 2 天的資料，全局壓縮參數是可以複用的。下圖描述了整體的性能對比，實驗環境為 “Intel CPU 8163 + Nvidia GPU P100"，其中 AMMMO 的代碼使用了 P100。
從上圖中看出，AMMMO 在壓縮端和解壓縮端都能達到 GB/s 的處理性能，性能名額還是很不錯的。
4 算法學到的效果
深度強化學習訓練的網絡從最終效果上看着不錯，那它是不是真的學到了有意義的内容呢？下标對比了 3 種算法在幾個測試集上的表現，可以看出，ML 版本的參數選擇和分析算法/最優效果選擇是差不多的，特别是在 byte offset 和 majorMode 的選擇上。
這種壓縮的全連接配接網絡參數表象會是怎麼樣的？對第一層進行了參數 heatmap 可視化（正的參數為紅色，負的為藍色，值越大顔色越亮），如下：
可以明顯看到 32 個點在相同的 byte 上有很多規則的操作，豎線（如果跨越 byte 則混淆情況），可以認為是在對應的位置上做 delta 或 xor 運算等。然後數字變動最大的 Byte0 的參數也比較活躍。
綜上，深度學習學到的東西還是挺有解釋性的。
機器學習公開課 | 跟阿裡雲技術專家學習智能推薦系統
阿裡雲機器學習 PAI 團隊推出系列課程，結合各個推薦場景的經驗，給大家帶來推薦業務相關的知識普及。課程包括推薦系統基本概念及架構說明、召回算法、排序算法和線上服務編排，帶你 10 分鐘實作一個簡單的推薦系統。
識别下方二維碼或點選文末“
閱讀原文”立刻學習吧：