How to Compress Time Series Data More Efficiently?

ディープラーニングの本質は意思決定を行うことにあります。具体的な問題を解決する際に、適切な接点を見つけ、合理的なモデルを構築し、データを整理して損失を最適化し、問題をよりよく解決することが非常に重要です。これまで一定期間にわたり、深層強化学習を用いたデータ圧縮の研究と探求を行い、一定の成果を上げてきました。その成果は ICDE 2020 の研究トラックで発表され (Two-level Data Compression using Machine Learning in Time Series Database)、口頭発表も行いました。以下は全体的な概要紹介であり、他のシナリオ、少なくとも他のデータの圧縮に対する参考となれば幸いです。

背景説明

1 時系列データ

時系列データとは、その名の通り時系列に関連するデータを指し、日常的にあらゆる場面で見られるデータ形式です。以下の図には 3 つの例を示しています。a) 心電図、b) 株価指数、c) 特定の株式取引データです。

時系列データベースの業務内容について簡潔に説明すると、ユーザーレベルでは大量のクエリ、分析、予測などに対応する必要があり、基盤レベルでは大量の読み書き、圧縮と展開、集約などの操作を処理する必要があります。これらの操作の基本単位が時系列データであり、一般的には 2 つの 8 バイト値によって統一的に (簡略化して) 記述できます。

あらゆる電子機器が毎日多種多様な大量の時系列データを生成し、大量のストレージスペースなどを必要とすることは想像に難くありません。圧縮して保存・処理するのは自然な方法です。ここでの焦点は、より効率的な圧縮をどのように実現するかです。

2 強化学習
機械学習は、サンプルに正解ラベルがあるかどうかに基づいて、教師あり学習、教師なし学習、強化学習に分類できます。強化学習は、その名の通り、止めることなく学習を続け、正解ラベルを必要としません。現実世界には正解ラベルが存在しないことがほとんどです。たとえば、人間の認知は継続的な反復学習のプロセスであることが多いです。この意味において、強化学習は現実世界の問題に対処するためにより適合した、あるいはより包括的で汎用的なプロセスと方法であり、次のような見方があります。ディープラーニングが C / Python / Java のように具体的な問題を解決するための基礎ツールになっていくとすれば、強化学習はディープラーニングにとっての基礎ツールである、というものです。

強化学習の典型的な模式図は以下の通りで、基本要素は状態 (State)、アクション (Action)、環境 (Environment) です。基本的なプロセスは、環境が状態を与え、エージェントが状態に基づいてアクションを決定し、アクションが環境に作用して新しい状態と報酬を生成します。ここで報酬はエージェントがより良いアクションを決定するための指針として使用され、このサイクルが繰り返されます。

一般的な教師あり学習ははるかに単純です。強化学習の特殊なケースと考えることができ、目標である正解ラベルが非常に明確で、対応する報酬も比較的明確です。

強化学習は個人的な理解に基づき、以下の 3 つのカテゴリに分類できます。

1) DQN

Deep Q Network は、人間の直感的な感覚ロジックにより適合するタイプで、Q 値を評価するネットワークをトレーニングし、任意の状態に対して各アクションの報酬を提示し、最終的に最も大きい報酬のアクションを選択して実行します。トレーニングプロセスは、「推定 Q 値」と「実際の Q 値」の結果の誤差を逆伝播し、ネットワークが Q 値をますます正確に推定できるようにします。

2) ポリシー勾配

よりエンドツーエンドのタイプで、ネットワークをトレーニングし、任意の状態に対して直接最終的なアクションを出力します。DQN の適用範囲は、連続する状態の Q 値も比較的連続している必要があります (囲碁などには適用できません) が、ポリシー勾配は内部プロセスを無視して直接アクションを出力するため、より高い汎用性を持ちます。ただし欠点として、評価と収束がより困難です。一般的なトレーニングプロセスは、ある状態に対して複数のアクションを同時にランダムに選択し、各アクションの結果を評価して逆伝播し、最終的にネットワークがより効果の高いアクションを出力します。

3) Actor-Critic

前述の 2 つのネットワークを組み合わせ、相互に補完しようとします。一方でポリシー勾配ネットワークを使用して任意の状態のアクションを出力し、もう一方で DQN ネットワークを使用してポリシー勾配が出力したアクションをより良く定量的に評価し、ポリシー勾配の更新を導きます。その名の通り、パフォーマーと批評家の関係のようなものです。トレーニングプロセスではアクター (ポリシー勾配) とクリティック (Q ネットワーク) の両方を同時にトレーニングする必要がありますが、アクターのトレーニングにはクリティックの指導のみが必要です。多くの変種があり、現在の深層強化学習の理論研究において継続的に発展している主要な方向です。

時系列データの圧縮
大量の時系列データを圧縮する必要性は明白であり、学界と産業界の両方で多くの研究と探求が行われています。いくつかの手法を紹介します。

Snappy：整数や文字列を圧縮し、主に長距離予測とランレングス圧縮 (RLE) を使用します。InfluxDB など幅広いアプリケーションで使用されています。
Simple8b：まず前後のデータに差分処理を行い、同じであれば RLE エンコーディングを使用します。そうでない場合は、16 エントリのコードテーブルに従い、1 〜 240 個の数値を 8 バイト単位でデータにパックします。InfluxDB など幅広いアプリケーションで使用されています。
Compression planner：スケール、差分、辞書、ハフマン、ランレングス、修正定数などの一般的な圧縮ツールを導入し、静的または動的な方法でこれらのツールを組み合わせて圧縮を試みることを提案しています。アイデアは非常に斬新ですが、実際のパフォーマンスが低下することが問題です。
ModelarDB：非可逆圧縮に焦点を当て、ユーザーが指定した許容損失に基づいて圧縮します。基本的な考え方は小さなバッファを維持し、先行データが特定のパターン (傾きの直線フィッティング) に適合するかどうかを検出し、適合しない場合はモードを切り替えてバッファを再開します。非可逆に対応する必要がある IoT フィールドのサポートに適しています。
Sprintz：IoT フィールドでも効果的で、8 / 16 ビット整数処理に焦点を当てています。主にスケールを使用して予測を行い、RLC による差分エンコーディングとビットレベルのパッキングを使用します。
Gorilla：Facebook の高スループットリアルタイムシステムで使用されている圧縮アルゴリズムで、可逆圧縮を実行し、IoT やクラウドサービスなどさまざまな分野で広く使用されています。delta-of-delta を導入してタイムスタンプを処理し、データを XOR で変換してからハフマンエンコーディングとビットパッキングを適用します。
MO：Gorilla と似ていますが、ビットパッキングを排除し、すべてのデータ操作は基本的にバイトアライメントされています。これにより圧縮率は低下しますが、処理パフォーマンスは向上します。
…
関連する圧縮アルゴリズムは多数あり、総じて次のように言えます。

基本的にシングルモード、または限定的な部分的静的モードのデータ圧縮をサポートしています。
多くの手法が圧縮率を向上させるためにビットパッキングを使用しています (非可逆圧縮でさえ) が、ますます広く使用されている並列計算に対してはあまりフレンドリではありません。
2 段階深層学習ベースの圧縮アルゴリズム
1 時系列データ圧縮の特徴
時系列データは IoT、金融、インターネット、ビジネス管理、モニタリングなどさまざまな分野から取得され、形態的特徴は大きく異なり、データ精度の要件も異なります。区別なく処理する単一の統一された圧縮アルゴリズムしかない場合、8 バイトデータでデータを記述する可逆アルゴリズムに基づく必要があります。

以下の図は Alibaba Cloud のビジネスにおける時系列データの例です。マクロレベルでもマイクロレベルでも可逆の場合、データパターンは多様で、形状の曲線だけでなくデータ精度も異なります。したがって、圧縮アルゴリズムは可能な限り多くの圧縮モードをサポートし、その中から効果的かつ経済的に 1 つを選択して圧縮する必要があります。

大規模な商用時系列データ圧縮アルゴリズムには、3 つの重要な特徴に重点を置く必要があります。

時間相関：時系列データは強い時間相関を持ち、対応するデータは基本的に連続しています。サンプリング間隔は通常 1 秒、100 ms などです。
パターン多様性：前述の図に示すように、パターンと特徴の間には大きな差があります。
データ大量性：毎日、毎時、毎秒処理する必要があるデータ量は膨大です。全体の処理データは 1 日あたり少なくとも 10 PB レベルです。対応する圧縮アルゴリズムは効率的で高スループットである必要があります。
2 新しいアルゴリズムのコアコンセプト
データ圧縮の本質を遡ると、2 つの段階に分けることができます。まず、変換段階でデータをある空間からより規則的な別の空間に変換し、次に差分符号化段階でさまざまな方法を使用して変換後の差分をより良く識別します。

時系列データの特徴に基づき、以下の 6 つの基本変換プリミティブ (拡張可能) を定義できます。



次に、以下の 3 つの基本差分符号化プリミティブ (拡張可能) を定義します。


次に、上記 2 つのツールを順列組み合わせで圧縮に使用します。これは実行可能ですが、モード選択と関連パラメータのコスト割合が高すぎるため、効果は決して良くありません。2 バイト (プリミティブ選択 + プリミティブパラメータ) の制御情報が必要で、8 バイトで表現するデータの 25% を占めます。

より良い方法は、データの特性を抽象化して層化することです。以下の模式図に示します。制御パラメータセットを作成してすべての状況をより良く表現し、グローバル (1 つのタイムライン) レベルで適切なパラメータを選択して検索空間を決定します (少数の圧縮モードのみを含む、たとえば 4 つ)。そして、各ポイントの詳細な圧縮時に走査して最適な圧縮モードを選択して圧縮します。制御情報の割合は約 3% です。

3 2 段階圧縮フレームワーク AMMMO
AMMMO (adaptive multiple mode middle-out) の全体プロセスは 2 つの段階に分かれています。第 1 段階では現在のタイムラインの全体的な特性を決定します (9 つの制御パラメータの具体的な値を決定)。その後、第 2 段階で少数の圧縮モードを走査して最適なものを発見して圧縮します。具体的なブロック図は以下の通りです。

第 2 段階のモード選択は難しくなく、ロジックはシンプルで効率的な実行に適しています。第 1 段階では、パラメータ値 (ここでは 9 つ) を決定して適切な圧縮空間を得ることが比較的大きな課題であり、30 万以上の理論的な順列組み合わせから適切なものを見つける必要があります。

4 ルールベースのパターン空間選択アルゴリズム
アルゴリズムを設計することは可能です。たとえば、各圧縮モードの効果のスコアボードを作成し、タイムライン内のすべてのポイントを走査して分析と記録を行い、統計分析と比較を通じて最適なモードを選択します。いくつかの明らかな問題があります。

選択した評価メトリックは理想的か？
手動での思考とプログラミングが必要で、実装、デバッグ、保守の作業量が増加します。
アルゴリズムのプリミティブと圧縮モードが変更された場合、コード全体をリファクタリングする必要があります。上記の選択は理論的な選択ではなく、継続的な進化をサポートする自動化されたインテリジェントな方法が必要です。

深層強化学習

1 問題のモデリング

上記のパターン空間選択アルゴリズム全体を簡略化したものを以下の図に示します。この問題は多目的分類問題と等価と考えることができます。各パラメータが 1 つの目標であり、各パラメータ空間の値の範囲が選択可能なカテゴリ数です。ディープラーニングは画像分類やセマンティック理解などで高い有用性を示しています。同様に、ここでのパターン空間の選択問題にもディープラーニングを使用でき、マルチラベル分類問題として扱います。

どのようなネットワークを使用するか？認識の主な関係は delta / xor、シフト、ビットマスクなどであることを考慮すると、CNN は適切ではなく、全結合 MLP がより適切です。対応して、タイムライン上のすべてのポイントについて、1 時間に 3,600 ポイントある場合、合計 3,600 x 8 バイトとなり、多すぎます。同じタイムライン内のセクションの類似性を考慮し、32 ポイントを最も基本的な処理単位とします。

次に、トレーニングサンプルをどのように作成するか？サンプルのラベルをどのように見つけるか？

ここで教師あり学習ではなく強化学習を導入してトレーニングを行う理由は以下の通りです。

1) ラベル付きサンプルの作成が困難

32 サンプル 256 バイトで、理論的にはサンプルあたり 256 の 256 乗の可能性があります。各サンプルについて、30 万の可能性を走査して最適なものを見つける必要があります。サンプルの作成と選択、ラベルの作成の作業量は非常に大きいです。

2) 通常の単一クラストラベル問題ではない

あるサンプルが与えられた場合、唯一の最良の結果があるわけではありません。多くの選択が同じ圧縮効果を達成できる可能性が高く、N クラス (N は基本的に不明) のトレーニングは難しさを大幅に増加させます。

3) 自動化されたアプローチが必要

圧縮ツールなどのパラメータの選択は拡張が必要になる可能性があり、トレーニングサンプル全体の作成をやり直す必要があります。自動化されたアプローチが必要です。

どのような強化学習を使用するか？DQN、ポリシー勾配、それとも Actor-Critic か？前述の分析の通り、DQN は不連続な報酬 / アクションには適していません。ここでのパラメータ、たとえば majorMode の 0 と 1 は完全に異なる結果であり、DQN は不適切です。また、圧縮問題は一方では評価が容易ではなく、ネットワークもそれほど複雑ではないため、Actor-Critic は不要です。最終的にポリシー勾配を採用しました。

ポリシー勾配の一般的な損失は、ゆっくり増加するベースラインを尺度として使用し、現在のアクションが適切かどうかをフィードバックすることですが、ここでは適していません (試行後、効果があまり良くありませんでした)。ここでのサンプルの理論的なブロック (256 の 256 乗) の状態が多すぎるためです。このため、特別に損失を設計しました。

各ブロックのパラメータを取得した後、ブロック間の相関などを考慮し、統計的手法を使用してタイムライン全体の最終パラメータ設定を集約できます。

2 深層強化学習ネットワークフレームワーク
全体的なネットワークフレームワーク図は以下の通りです。

トレーニング側：ランダムに M 個のブロックを選択し、各ブロックを N 部にコピーし、3 つの隠れレイヤーを持つ全結合ネットワークに入力します。region ソフトマックスを使用して各パラメータの各種選択の確率を取得し、各パラメータの値をサンプリングします。パラメータを取得した後、基盤となる圧縮アルゴリズムに入力して実際の圧縮を実行し、圧縮値を取得します。コピーされた N 個のブロックを相互に比較して損失を計算し、誤差逆伝播を行います。損失の全体的な設計は以下の通りです。

fn(copi) は圧縮効果を記述し、N ブロックの平均値より高い正のフィードバックを与えます。Hcs(copi) は交差エントロピーで、スコアが高いほど確率が高いほど良いことを示し、その逆も同様です。以下の H(cop) は交差エントロピーを正則化因子として使用し、ネットワークの固定化と局所最適への収束を回避します。

推論側では、タイムラインの全部または一部のブロックをネットワークに入力してパラメータを取得し、統計的に集約してタイムライン全体のパラメータを決定します。

結果データ
1 実験設計
テストデータについては、一方で Alibaba Cloud ビジネスの IoT とサーバーという 2 つの主要シナリオの下で 28 の大規模タイムラインをランダムに選択しました。他方で、時系列データ分析とマイニングの分野で最も一般的なデータセットである UCR も選択しました。基本情報は以下の通りです。

比較アルゴリズムについては、Gorilla、MO、Snappy を選択しました。AMMMO は 2 段階の圧縮アルゴリズムフレームワークであるため、第 1 段階のパラメータ選択にはさまざまなアルゴリズムを使用できます。ここでは Lazy (シンプルにいくつかの共通パラメータを設定)、rnd1000Avg (1,000 回のランダム選択で効果の平均値を取得)、Analyze (人工コードによるアルゴリズム)、ML (深層強化学習の手法) などを選択しています。

2 圧縮効果の比較
まず、全体的な圧縮率の観点から見ると、AMMMO の 2 段階適応マルチモード圧縮は Gorilla / MO などと比較して効果が大幅に向上し、平均圧縮率は約 50% 向上しています。

では、ML の効果はどうでしょうか？以下の図は ML の視野でのテストセット B の圧縮効果を比較しています。総じて、ML は人工的に設計されたアルゴリズムよりわずかに優れ、ランダム平均より大幅に優れています。

3 動作効率
AMMMO は MO の設計思想を取り入れ、ビットパッキングを排除しています。CPU で高速に動作できるだけでなく、GPU などの並列計算プラットフォームに特に適しています。また、AMMMO は 2 段階に分かれており、第 1 段階のパフォーマンスは劣りますが、多くの場合、たとえば過去 2 日間の特定デバイスのデータに対して、グローバル圧縮パラメータを再利用できます。以下の図は全体的なパフォーマンス比較を示しています。実験環境は Intel CPU 8163 + Nvidia GPU P100 で、AMMMO コードは P100 を使用しています。

上記の図から分かるように、AMMMO は圧縮側と展開側の両方で GB/s の処理パフォーマンスを達成でき、パフォーマンス指標は依然として非常に優れています。

4 アルゴリズムが学習した効果
深層強化学習でトレーニングされたネットワークは最終的な効果から見ると良好に見えますが、本当に意味のある内容を学習したのでしょうか？下標は 3 つのアルゴリズムのいくつかのテストセットでのパフォーマンスを比較しています。ML 版のパラメータ選択は分析アルゴリズム / 最適効果選択と類似しており、特にバイトオフセットと majorMode の選択で顕著であることが分かります。

この圧縮された全結合ネットワークのパラメータ表現はどのようになるでしょうか？第 1 層のパラメータヒートマップ可視化を行いました (正のパラメータは赤、負のパラメータは青、値が大きいほど色が明るい)。以下の通りです。

32 個のデータポイントが同じバイトに対して多くの規則的な操作を行っていることが明確に見えます。縦線 (バイトをまたぐと状況が混乱する場合があります) は、対応する位置での delta 演算または xor 演算と解釈できます。そして、変化量が最も大きい Byte0 のパラメータもより活発です。

以上より、ディープラーニングが学習した内容は十分に説明力があると言えます。

機械学習公開講座 | Alibaba Cloud の技術エキスパートからインテリジェントレコメンデーションシステムを学ぶ

Alibaba Cloud の機械学習 PAI チームは、シリーズ講座を開設し、さまざまなレコメンデーションシナリオでの経験を組み合わせて、レコメンデーション業務に関連する知識の普及をお届けします。講座にはレコメンデーションシステムの基本概念とアーキテクチャの説明、リコールアルゴリズム、ランキングアルゴリズム、オンラインサービスのオーケストレーションが含まれます。10 分間でシンプルなレコメンデーションシステムを実装できます。