2021__ATC__Jump-Starting Multivariate Time Series Anomaly Detection for Online Service Systems

## Memo - [[NetManAIOps]]の論文。 - [GitHub - NetManAIOps/JumpStarter](https://github.com/NetManAIOps/JumpStarter) - 異常検知の時間のかかる初期学習フェーズを大幅に短縮する論文。 ## Abstract オンラインサービスの普及に伴い，システムの信頼性向上のためには，CPU使用率，平均応答時間，1秒あたりのリクエスト数などの多変量時系列に対する異常検知が重要である．この目的のために，多くの学習ベースのアプローチが設計されてきたが，我々の実証研究によると，これらのアプローチは十分な学習データを得るための初期化時間が長いという問題がある．本論文では、圧縮センシング技術を多変量時系列異常検知に導入し、迅速な初期化を行う。ジャンプスタート型の異常検出器を構築するために、JumpStarterと名付けたアプローチを提案する。JumpStarterのために、ドメイン固有の洞察に基づいて、形状ベースのクラスタリングアルゴリズムと異常値耐性のあるサンプリングアルゴリズムを設計する。2つのインターネット企業から収集した実世界の多変量時系列データを用いた我々の結果は、JumpStarterが平均F1スコア94.12%を達成し、20分という短い初期化時間で、最先端の異常検知アルゴリズムを大幅に凌駕することを示している。我々はJumpStarterをオンラインサービスシステムに適用し、実世界のシナリオにおいて有益な教訓を得ました。 ## 1 Introduction 近年，オンライン・オフィスや電子商取引など，クラウドを利用したオンライン・サービス・システムが急速に普及している．例えば，ビデオ会議アプリ「Zoom」の毎日の会議参加者数は，2020年5月までに3億人を超えると予想されています[31]．オンライン・サービス・システムは複雑かつ大規模であるため，その信頼性を保証するためには，自動的な異常検知が極めて重要である[36]．サービスの品質を厳密に監視するために，オンラインサービスプロバイダやMicrosoftやAWSなどのクラウドコンピューティングプラットフォームは，各パフォーマンス指標（CPU使用率，平均応答時間，1秒あたりのリクエスト数など）の監視データを等間隔で継続的に収集しています[3, 33]．メトリクスの監視データは一変量時系列を構成するため，複数のメトリクスを持つサービスシステムの監視データは多変量時系列を構成します．従来の多変量時系列異常検知アプローチは、一般的に一変量時系列の検知に基づいている[15, 32, 36]。しかし、オペレータは、特定の指標の状態ではなく、サービス全体の状態を気にしています[28]。一変量時系列の異常検知では，異なる一変量時系列間の複雑な時間的関係を捉えることができないため[28]，アラートストームを引き起こす傾向があります[5]．この問題に対処するため，最近の研究[12,22-24,28,34]では，深層学習技術を用いて，多変量時系列異常検知のための学習モデルを構築している．例えば、最先端のアプローチであるOmniAnomaly[28]は、多変量時系列の時間的関係を学習するために、確率的リカレント・ニューラルネットワーク・モデルを利用している。 ![[Pasted image 20211025154602.png]] 学習ベースのアプローチは、通常、長期間の学習データを必要とするため、実際にはほとんど適用できません。オンラインサービスのシステムは，新機能の導入やバグの修正など，非常に頻繁に導入・変更されます[35]．Google [3]やBaidu [35]などの大規模なサービスプロバイダでは，毎日何千ものソフトウェアの変更が行われていることが報告されています．このようなソフトウェアの変更により，多変量時系列のデータ分布が大きく変化する可能性があり，これを予想概念ドリフト（[[Expected concept drift]]）と呼ぶ[17]．例えば，オペレータがソフトウェアの変更を行ってサービスをより多くのインスタンスにデプロイすると，図1に示すように，各インスタンスの「Requests Per Second」という指標が大幅に低下します．これは運用者にとって想定内のことであり、ソフトウェア変更をロールバックする必要はありません。変更後は、変更前のデータに基づいて学習された学習ベースの異常検知モデルが無効になるため、多くの誤警報または誤検知が発生します[17]。これは、データの分布がトレーニングセットとテストセットの間で同じでなければならないという、深層学習における一般的な前提[10]が破られるためです。そのため，これらの学習ベースのアプローチは，再学習する必要がある．しかし，この再学習プロセスは，定常状態に達するまでに数十日から数百日を要することがある[28, 32]．本研究では，多変量時系列の異常検知モデルの「初期化」に要する時間を定量的に測定するために，まず初期化時間を，モデルが起動してから十分に学習されるまでのタイムラグと定義する．次に，実世界のオンラインサービスシステムから収集したデータセットを用いて，実証研究を行った．その結果、以下の2点が明らかになった。(1）既存の学習ベースのアプローチの平均的な初期化時間は、10日から100日程度である。(2) 最先端のアプローチ（OmniAnomaly [28]とMSCRED [34]）は，漸進的再学習（Incremental retraining）[15]によって改善された場合，満足のいく性能を得られない．また，学習データの期間が短い場合には，これらの手法の精度は低くなる．そこで我々は，初期化時間の短い多変量時系列のためのロバストな異常検知アプローチを設計することを目的とする．本論文では，JumpStarterと呼ばれる，[[圧縮センシング]](CS)に基づいた新しい多変量時系列異常検出手法を提案する．CSは，行列（多変量時系列）中の高エネルギー成分をスパース（高エネルギー成分が少ない）にする信号処理技術である[4]．そのため，元の時系列に異常がない場合，低エネルギー成分のみで構成された元の時系列と再構成された多変量時系列の差はホワイトノイズに似ているはずである．異常検知にCSを使う背景には、ジッター、突然のドロップやサージなどの多変量時系列の異常は、通常、高エネルギー成分を含む強い信号として現れ、ホワイトノイズとは大きく異なるという直感がある[16]。そのため、スライディング・ウィンドウ（32）内のオリジナルと再構成された多変量時系列の差がホワイト・ノイズと大きく異なるかどうかをチェックすることで、時系列に異常があるかどうかを判断することができます。CSは固定長の窓を使用して異常検出モデルを「訓練」するだけなので、JumpStarterの初期化時間は窓のサイズに依存し、通常は20分です。これは、学習ベースのアプローチの初期化時間よりもはるかに短い時間です。次に、CSベースのJumpStarterが学習ベースのアプローチよりもはるかに少ない学習データしか必要としない理由を説明します。学習ベースのアプローチでは、異常を検出するために、正規の多変量時系列の「振る舞い」(確率分布)を明示的に学習する必要があります。それに比べて、JumpStarterでは、再構成された多変量時系列は、明示的な学習を伴わずに、この正常な挙動を暗黙のうちに継承します。しかし、実世界のシナリオは複雑であるため、以下のような状況では、CSを適用してジャンプスターター型の多変量時系列異常検知を実現することは困難である。時系列の数が多い。大規模なオンラインサービスシステムでは，各システムテムごとに数十の時系列が監視され，多変量時系列が形成される[17]．一般的に，CSは多数の時系列を再構成するのに時間がかかる．なぜなら，時間の複雑さが時系列の数に依存する凸型最適化問題を解く必要があるからである．この課題に取り組むために、我々はこれらの時系列を形状に基づいてクラスタリングする。同じグループの時系列は似たような形をしているので、時間的な関係を失うことなく、効率的に再構成することができる[14]。時系列のランダムな異常セグメントからのサンプリング。CSは通常、制限付き異常値特性（RIP）を保証するために、元の時系列からのサンプリングに[[ガウス分布]]を使用する。しかし、それにもかかわらず、いくつかの長期的な異常セグメントからサンプリングされた再構成時系列を生成することは避けられない。これらの再構成時系列に基づいた異常検知モデルは、いくつかの誤ったポジティブまたは誤ったネガティブを引き起こす可能性がある。そこで、異常な時系列セグメントではなく、正常な時系列セグメントからサンプリングすることで、異常値に強いサンプリングアルゴリズムを設計する。我々は、2つのインターネット企業の28および30の大規模な産業用オンラインサービスシステムから得られた3つのデータセットに基づいて、JumpStarterの性能を評価するための包括的な研究を行いました。1つ目のデータセットはA社のもので、5週間分の時系列オープンデータセットです。他の2つのデータセットは、世界中の8億人以上のユーザーにサービスを提供している、世界トップクラスのコンテンツプラットフォーム企業B社のものです。これらのデータセットは7週間の時系列データです。実験の結果、JumpStarterは、最先端の学習ベースの多変量時系列異常検知アプローチ（Omni- Anomaly [28]とMSCRED [34]）とクラスタリングベースのLESINN [20]の両方を上回る性能を示した。また，AWS CloudWatchで使用されているRRCF [11]よりもJumpStarterの方が適しています．Jump-Starterの平均F1スコアは94.12%であるのに対し、他の4つのアプローチの平均F1スコアはそれぞれ86.51%、59.64%、82.5%、36.01%となっています。また、Jump-Starterの主なコンポーネント(形状ベースのクラスタリングと外れ値に強いサンプリング)は、Jump-Starterの全体的な性能に大きく貢献していることが分かりました。JumpStarterは、20分という短い初期化時間で良好な精度を達成しており、 https://github.com/NetManAIOps/JumpStarter でオープンソース化されています。JumpStarterをBに適用したところ、実際に良好な異常検知性能を得ることができました。また、2つの事例を紹介し、学界と産業界の双方にとっての教訓を得る。 ## 2 Background and Empirical Study 本研究では，多変量時系列の異常検知モデルの「初期化」に要する時間を定量的に測定するために，まず初期化時間を，モデルが起動してから十分に学習されるまでのタイムラグと定義する．次に，実世界のオンラインサービスシステムから収集したデータセットを用いて，実証研究を行うことにした。その結果、以下の2点が明らかになった。(1）既存の学習ベースのアプローチの平均的な初期化時間は、10日から100日程度である。(2) 最先端のアプローチ（OmniAnomaly [28]とMSCRED [34]）は，漸進的再学習（Incremental retraining）[15]によって改善された場合，満足のいく性能を得られない．また，学習データの期間が短い場合には，これらの手法の精度は低くなる．そこで我々は，初期化時間の短い多変量時系列のためのロバストな異常検知アプローチを設計することを目的とする．本論文では，JumpStarterと呼ばれる，圧縮センシング(CS)に基づいた新しい多変量時系列異常検知手法を提案する．CSは，行列（多変量時系列）中の高エネルギー成分をスパース（高エネルギー成分が少ない）にする信号処理技術である[4]．そのため，元の時系列に異常がない場合，低エネルギー成分のみで構成された元の時系列と再構成された多変量時系列の差は[[ホワイトノイズ]]に似ているはずである．異常検知にCSを使う背景には、ジッター、突然のドロップやサージなどの多変量時系列の異常は、通常、高エネルギー成分を含む強い信号として現れ、ホワイトノイズとは大きく異なるという直感がある[16]。そのため、スライディング・ウィンドウ（32）内のオリジナルと再構成された多変量時系列の差がホワイト・ノイズと大きく異なるかどうかをチェックすることで、時系列に異常があるかどうかを判断することができます。CSは固定長の窓を使用して異常検出モデルを「訓練」するだけなので、JumpStarterの初期化時間は窓のサイズに依存し、通常は20分です。これは、学習ベースのアプローチの初期化時間よりもはるかに短い時間です。次に、CSベースのJumpStarterが学習ベースのアプローチよりもはるかに少ない学習データしか必要としない理由を説明します。学習ベースのアプローチでは、異常を検出するために、正規の多変量時系列の「振る舞い」(確率分布)を明示的に学習する必要があります。それに比べて、JumpStarterでは、再構成された多変量時系列は、明示的な学習を伴わずに、この正常な挙動を暗黙のうちに継承します。しかし、実世界のシナリオは複雑であるため、以下のような状況では、CSを適用してジャンプスターターによる多変量時系列の異常検出を実現することは困難である。大量の時系列。大規模なオンライン・サービス・システムでは，各システムについて数十の時系列が監視され，多変量時系列が形成される[17]．一般的に，CSは多数の時系列を再構築するのに時間がかかる．なぜなら，時間の複雑さが時系列の数に依存する凸型最適化問題を解く必要があるからである．この課題に取り組むために、我々はこれらの時系列を形状に基づいてクラスタリングする。同じグループの時系列は似たような形をしているので、時間的な関係を失うことなく、効率的に再構成することができる[14] ([[2018__IWQoS__Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection|ROCKA]])。時系列のランダムな異常セグメントからのサンプリング。CSは通常、制限付き異常値特性（RIP）を保証するために、元の時系列からのサンプリングにガウス分布を使用する。しかし、それにもかかわらず、いくつかの長期的な異常セグメントからサンプリングされた再構成時系列を生成することは避けられない。これらの再構成時系列に基づいた異常検知モデルは、いくつかの誤ったポジティブまたは誤ったネガティブを引き起こす可能性がある。そこで、異常な時系列セグメントではなく、正常な時系列セグメントからサンプリングすることで、異常値に強いサンプリングアルゴリズムを設計する。 JumpStarterの性能を評価するために、2つのインターネット企業の大規模オンラインサービスシステムから得られた3つのデータセットを用いて、包括的な研究を行った。1つ目のデータセットはA社のもので、5週間の時系列オープンデータです。他の2つのデータセットは、世界中の8億人以上のユーザーにサービスを提供している、世界トップクラスのコンテンツプラットフォーム企業B社のものです。これらのデータセットは7週間の時系列データです。実験の結果、JumpStarterは、最先端の学習ベースの多変量時系列異常検知アプローチ（Omni-Anomaly [28]およびMSCRED [34]）と、クラスタリングベースのLESINN [20]の両方を上回る性能を示すことがわかった。また，AWS CloudWatchで使用されているRRCF [11]よりもJumpStarterの方が適しています．Jump-Starterの平均F1スコアは94.12%であるのに対し、他の4つのアプローチの平均F1スコアはそれぞれ86.51%、59.64%、82.5%、36.01%となっています。また、Jump-Starterの主なコンポーネント(形状ベースのクラスタリングと外れ値に強いサンプリング)は、Jump-Starterの全体的な性能に大きく貢献していることが分かりました。JumpStarterは、20分という短い初期化時間で良好な精度を達成しており、<https://github.com/NetManAIOps/JumpStarter> でオープンソース化されています。JumpStarterをBに適用したところ、実際に良好な異常検知性能を得ることができました。また、2つの事例を紹介し、学界と産業界の双方にとっての教訓を得る。 ## 3 JumpStarter Approach ![[Pasted image 20220915210105.png|600]] ### 3.2 Overview of JumpStarter ![[Pasted image 20220915213102.png|600]] オフライン処理とオンライン処理の両手順からなるJumpStarterのアプローチを図5に示す。時系列数が多いという課題に取り組むため、オフライン処理では、多変量時系列の一変量時系列をいくつかのグループに分けるために、形状ベースのクラスタリング手法（[[Shape-based distance|SBD]]）を採用する。オンライン異常検出では、多変量時系列に対してスライディングウィンドウ法を適用する。各グループの一変量時系列に対して、異常セグメントからのサンプリングによってもたらされる課題を解決するために、新しい外れ値耐性サンプリングアルゴリズムを提案し、それらを再構成するために圧縮センシングを適用する。その後、これらの再構成された時系列を連結し、元の時系列と再構成された多変量時系列との差を異常スコアとして測定し、異常スコアに対してEVT閾値を用いて異常検出を行う。 ### 3.3 Shape-Based Clustering それぞれのストローマンソリューションには利点と欠点があるが、我々はそれらを組み合わせて、両方の利点を得る方法を見つける。具体的には、Xtをいくつかの時系列のクラスタに分割し、それぞれのクラスタを再構築する。問題は、この分割をどのように行うかである。最初のストローマン解法では、異なる形状の時系列を扱うことができないことを思い出してください。したがって、我々はXtを形状に基づいて分割することを選択する。この解決法は高精度と高効率の両方を達成することができる。 ![[Pasted image 20220915210324.png|600]] 我々は、2つの単一化された時系列間の距離を測定するために、[[相互相関]]に基づいた方法である形状ベース距離 ([[Shape-based distance|SBD]][21]を採用する。これは、高次元時系列を扱う際に高い計算効率を達成することができる。[[2018__IWQoS__Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection|ROCKA]][14]とは異なり、クラスタ数を手動で設定する必要がなく効率的な[[階層型クラスタリング]]を基本クラスタリングアルゴリズムとして使用します。表2にクラスタリング結果の一例を示す。多変量時系列の9つの一変量時系列が3つのクラスタにグループ化されている。各クラスタにおいて、時系列は対応する監視指標の物理的な意味と相関しており、本手法が直感的であることを示している。一変量時系列のほとんどは、顧客の昼間の使用パターンと一致する24時間周期でほぼ周期的に変化するため、1日分のデータに基づいて、すべての多変量時系列に対して一変量時系列をクラスタ化する[17] ([[2018__ISSRE__Robust and Rapid Adaption for Concept Drift in Software System Anomaly Detection|StepWise]]) 。さらに、一変量時系列の形状は、通常、ソフトウェアの変更後も変化しないことが確認されています[38] ([[2019__TNSM__Automatic and Generic Periodicity Adaptation for KPI Anomaly Detection|Period]])。その結果、ソフトウェア変更後に再クラスター化する必要はない。 ### 3.4 Outlier-Resistant Sampling Insight. ランダムガウシアンサンプリングの問題を解決するために、多数のオンラインサービスシステムの調査や運営者との議論から洞察を得る．実世界のシナリオでは、異常はほとんど発生しない[15, 32]。つまり、異常は通常、観測（スライディング）ウィンドウにおける外れ値である[16]。異常がウィンドウサイズより長く続く場合、正常なパターンとは大きく異なるため、最初から捕捉することができる。したがって、各データ点のサンプリング信頼度を得るために、簡単な外れ値検出アルゴリズムを採用することができる。あるデータ点が外れ値である可能性が高いほど、そのサンプリング信頼度は低くなり、選択される可能性は低くなる。この洞察に基づき、我々はRIPを保証するだけでなく外れ値に強いサンプリングアルゴリズム、すなわち1次元ランダムガウスを設計する。アルゴリズム Algorithm 1で外れ値に強いサンプリングの設計を説明し、図6で主なステップを示す。形状に基づくクラスタリングの後、各クラスタに対して、k個の一変量時系列からなるw＊k行列を得ることができる。また、アルゴリズムの入力として、サンプリング比θを設定する。φは0からwまでのm個のランダムなガウス型サンプリングタイムスタンプを含むベクトルとして初期化される[20]。しかし、4.2 節で示すように、LESINN 自身は多変量時系列の異常検知を効果的に扱うことができない。これは、時系列間の複雑な時間的関係を捉えることができないからである。図 6(a)は、ウィンドウサイズ 20 の元の時系列（青線）と、各タイムスタンプのサンプリング信頼度（オレンジ点線）の一例である。次に、値のサンプリングを行う（5〜14行目）。まず、scの値の合計が1になるように正規化し、R個の等幅のステップを作成する。各ステップは正規化されたscをもとにタイムスタンプtにマッピングされる（8行目）。各ステップについて、(0, 1)からランダムに値をサンプリングし、ガウス分布の類似バージョンの確率と比較する。