# Survey on Models and Techniques for Root-Cause Analysis > [!abstract] 概要 > クラウドと IoT の時代には、複雑な人間の意思決定を支える自動化と計算機知能が、大規模な分散システムの管理に不可欠になる。複雑なシステムで観測された症状の根本原因を理解することは、数十年来の大問題である。産業が IoT の世界へ踏み込み、年間のデータ生成量が驚くべき速度で増えるなか、膨大なデータを扱える、あるいは実時間で有用なフィードバックを返せる根本原因の判定機構をどう見つけるかが重要な問いになる。システム挙動のモデル化技法と、得られたモデルに基づく根本原因の推論の全体像をまとめたサーベイ論文は多いが、さまざまな技法が性能とスケーラビリティに関して増大する要求にどう適合するかを分析したものはない。本サーベイは、これらの側面に焦点を当てて根本原因分析を概観する。あわせて、特定のシステムとアプリケーションの要件に応じて最良の根本原因分析戦略を選ぶための指針を示す。 ## 論文情報 - タイトル: Survey on Models and Techniques for Root-Cause Analysis - 著者・所属: Marc Solé・Victor Muntés-Mulero(CA Technologies)、Annie Ibrahim Rana・Giovani Estrada(Intel) - 媒体: arXiv(cs.AI)、v2 は 2017-07-03。18 ページ。LeanBigData(FP7-619606)プロジェクトの支援 - arXiv ID: 1701.08546 - キーワード: Big data、failure diagnosis、root-cause analysis ## 概要 IT システムに適用できる根本原因分析(RCA)のモデルと、その生成・推論アルゴリズムを、性能面に注目して整理したサーベイである。モデルは決定的・確率的の 2 族に分類し、モデルの入手法(手動・支援付き・自動)と学習アルゴリズムを Table II、推論アルゴリズムを複数故障・厳密性・未知の症状などの次元と計算量で Table III・IV に分類する。結論は、表現力と扱いやすさの通常のトレードオフが広い範囲にわたって現れるというものである。 ## 問題設定 - 背景: SaaS・クラウド・IoT の拡大により、ダッシュボードでの人手の監視は限界を迎え、原因仮説を生成する自動化が要る。手法は数十年の蓄積があるが、IoT のようにスケーラビリティと実時間性が本質になる環境への適用は理解が不足している。 - 範囲: IT システムに適用できる技法に限る。ネットワーク・ソフトウェア・産業システム・自動車・航空宇宙などの分野別サーベイは既存文献に委ね、一般的サーベイ Kavulya らの文献 [2] の上に立つ。 - 用語は [2] に従う。イベント、障害(fault)/問題/根本原因(他のイベントを起こすが自身は起こされない)、エラー、故障(failure。外部から観測できるエラー)、症状(故障と、アラームのような外部指標)。RCA は障害箇所特定・障害分離・アラーム/イベント相関とも呼ばれ、症状の集合を生んだ障害の集合を推論する過程である。 - RCA 課題を分ける次元: 分析意図(根本原因だけか、説明まで要るか)、分析時間(実時間か事後か。実時間では推論の一部を事前計算し空間を時間と交換する)、複雑さ(システム規模・データ規模・推論長・影響伝播時間・進化速度)、必要なドメイン知識、必要なシステム知識(ブラックボックスからホワイトボックス)。推論長が 0 のときは異常検知そのものなので、推論長 1 以上に限る。 **Figure 1: RCA のワークフロー(Root-Cause Analysis workflow)** ![[_attachments/arxiv-1701.08546/fig01-rca-workflow.png]] (Figure 1. ドメイン知識・システム知識・観測からモデルを構築し、推論によって根本原因と説明を出力する。システムが変化したとき、モデルが更新可能なら更新し、そうでなければ再構築する。) ワークフローは Figure 1 のとおりで、ドメイン知識の変更はシステム知識の変更よりはるかに稀なのでワークフローには明示されず、モデルの再構築を伴うものとして扱われる。 ## 提案手法 本論文は新規手法ではなく分類体系を提案する。 ### RCA モデル(Section III-A) - 2 族: 決定的モデル(既知の事実と推論に不確かさが無い)と確率的モデル(不確かさを扱える)。それぞれに論理・コンパイル済み・分類器・プロセスモデルがあり、確率側にはベイジアン(ベイジアンネットワーク、確率的関係モデル、マルコフ論理ネットワーク、和積ネットワーク、動的ベイジアンネットワーク、隠れマルコフモデル等)が加わる。実装ごとに性能が異なり、例えば決定木はニューラルネットより診断が速いことが多い。 **Table I: RCA のモデル(Models for RCA)** ![[_attachments/arxiv-1701.08546/table1-rca-models.png]] (Table I. 各モデルと、診断への適用例の参考文献。多項式木(polytree)と和積ネットワークには診断応用が見つからず「?」である。) - 分類器は自動生成が機械学習の中心課題であるにもかかわらず RCA では主流でない。理由は、(i) 予測された根本原因しか返さず説明を得にくい、(ii) 論理規則を出さずドメイン知識との併用が難しい、(iii) 単一ラベル分類向けで、複数故障診断には閾値選択かマルチラベル分類器が要る、の 3 点である。 - 表の分類はきれいすぎる。コードブックは命題論理の一実装とみなせ、規則集合は決定木・ベイジアンネットワーク・SVM・ニューラルネットから抽出できるなど、モデル間の変換が存在する。 **Figure 2: RCA モデルの分類(Classification of RCA models)** ![[_attachments/arxiv-1701.08546/fig02-model-classification.png]] (Figure 2. 有向辺はモデル間で可能な変換を表す。例えばファジィ故障木・一階述語論理・故障木はベイジアンネットワークへ、ベイジアンネットワークは算術回路へ、和積ネットワークと算術回路は相互に変換できる。) - 変換には診断性能への強い効果があるものがある。ベイジアンネットワークは特定の診断課題向けに算術回路へコンパイルでき、コンパイルは高価だがその後の診断ははるかに速い。 - ベイジアンネットワークの階層は、ナイーブベイズ、二部グラフ、多項式木、一般の順に一般化される。 **Figure 3: ベイジアンネットワークモデルの階層(Hierarchy of Bayesian Network models)** ![[_attachments/arxiv-1701.08546/fig03-bn-hierarchy.png]] (Figure 3. 各クラスの例。黒が原因、白が症状、灰色がどちらでもないノード。二部グラフの一例である QMR-DT は医療診断のエキスパートシステムに使われた。BN2O は原因と症状の関係にノイジー OR を使う二部 BN である。) - モデルの性質として、サイズ(変数・規則・ノードの数)と推論構造(要素の相互関係)を挙げ、後者の導出指標が推論長である。 ### モデルの入手(Section III-A・III-B) - 手動生成: 専門家がモデルを与える。精度は高いが知識抽出が遅く、進化の速いシステムでは非実用的である。 - 支援付き生成: 部分システムのモデル(サブモデルライブラリ)をトポロジ等のシステム知識に基づいて組み上げる。産業環境の文献の大半がここに入り、手動と自動の折衷である。 - 自動生成: データのみから標準的アルゴリズムでモデルを作る。ドメイン知識が得られない場合の唯一の選択肢である。 - 構造とパラメータを区別できるモデル(ベイジアンネットワーク、ファジィ論理)では、表には構造まで学習するアルゴリズムを載せた。 **Table II: RCA モデルの自動構築アルゴリズム(Automated construction algorithms of RCA models)** ![[_attachments/arxiv-1701.08546/table2-learning-algorithms.png]] (Table II. モデルごとの学習アルゴリズム。ドンプスター・シェーファー理論・ファジィ故障木・非公理論理には見つからず「–」、多項式木 BN には「?」。) - 学習速度: 規則学習(決定木・規則集合)が最速の部類で、eBay の診断に使われた貪欲な MinEntropy がある。プロセスモデル(オートマトン・ペトリネット)にも高速アルゴリズムがあるが精度は低いことが多い。ストリームからの適応的な決定木(VFDT、CVFDT、Adaptive Hoeffding Tree)は IoT のようにデータを 2 度読めない環境に向き、Apache Samoa が並列化を実装する。 - ナイーブベイズは 1 パス学習で、文献 [131] によれば Google で最も広く使われた学習器の一つである。SVM の学習は O(n²) から O(n³)(反復近似で O(nr))、ニューラルネットの一般の学習問題は NP 完全である。 - ベイジアンネットワークの学習も NP 完全であり、分類器に対する優位は無い。ただし因果推定できる規模は進歩した。PC アルゴリズムの計算量は O(n log(n) max(p^q, p²))(n は標本数、p は変数数、q は隣接集合の最大サイズ)で最悪指数的なため、変数百個超は困難だった。局所因果から大域因果を生成する LGL は変数百万まで引き上げたが、実行時間は二次から指数まで幅がある。並列 PC も提案されている。 - 進化速度が高いと、モデルか学習アルゴリズムが増分更新可能(ID5R、BN の更新時 χ² 検定)か全再学習が速い必要がある。分類器は、標本が少ない・ラベル付けに人間診断が要り遅い(クラウドソーシングは専門性と機微データの問題で不向き)ため不向きである。人間が検証するだけの推測ラベルは、推論過程や根拠事実の提示が無ければ節約が小さい。 ### 推論(Section IV) - 推論(アブダクション)の意味づけ: 規則集合では結論と発火した規則の列が説明になる。ベイジアンネットワークでは、周辺確率が最大の原因、最確説明(MPE。全変数の最も確からしい割当て)、最大事後確率(MAP。一部変数を周辺化してから最大化)がある。さらに最も合理的な説明(MRE)、最も情報量のある説明(MIE)など、ユーザーが対象集合を事前に指定しなくても最も情報のある変数部分集合を選ぶ拡張がある。 - 分類の次元(Table III・IV): 複数故障(同時故障数の上限 k を含む)、厳密性、未知の症状、未知の原因、ノイズのある症状、ノイズのある伝播(故障が完全には伝播しない)、適応性(解の内部状態を類似クエリや新証拠に再利用できるか)。 - 選び方の指針: 変数に ok/failure が付いた明確な故障変数があり原因が多くなければ、周辺確率(単一故障向き)、MPE・MAP(複数故障向き)で足りる。変数が設定オプションを表し何も本質的に誤りでない場合は、影響が最大の変数部分集合を選ぶ代替的説明法が要る。 ## 新規性 - 既存のサーベイはシステム挙動のモデル化技法と根本原因の推論を要約するが、性能とスケーラビリティ要求に技法がどう合うかを分析していない、という空白を埋める。 - 各アルゴリズムを、複数故障・厳密性・未知症状・未知原因・ノイズ・適応性の次元と計算量で並べ、システム要件(進化速度、実時間性、ドメイン知識の量)から戦略を選ぶ視点を与える。 ## 実験設定 実験は無く、文献調査である。対象はモデル 30 種近く(Table I)、学習アルゴリズム(Table II)、推論アルゴリズム(Table III の 30 件超、Table IV の 40 件超)である。計算量は原論文の記載、または(決定木のように記載が無い場合)著者が単純な実装を仮定して置いた値で、論文中に明記される。 ## 実験結果 推論アルゴリズムの整理が本論文の主結果である。 **Table III: 非ベイジアン RCA モデルの推論アルゴリズム(Inference algorithms in non-Bayesian RCA models)** ![[_attachments/arxiv-1701.08546/table3-inference-non-bayesian.png]] (Table III. r は規則数、e は証拠数、c は規則あたりの平均条件数、f は潜在故障数、a は算術回路/SPN のサイズ、d は決定木のノード数、l はニューラルネットの層数、h は隠れ層のニューロン数。) - コードブックは最小ハミング距離復号で O(f·s)、複数故障へ拡張すると O(f^k·s)。単一故障しか扱えないのが欠点。 - 命題論理のアブダクションは決定可能だが計算量が大きく、一階述語論理では説明の集合が無限になりうるため決定不能である。前向き連鎖(Rete 系)は規則ベースで実用的に使われる。 - ドンプスター・シェーファー理論の結合則の適用は #P 完全で、素朴な信念更新は指数的なので、近似(モンテカルロ)が提案される。 - 和積ネットワークは周辺確率・MPE が回路サイズに線形で、算術回路と密接に関係する。マルコフ論理ネットワークは追加の論理式でアブダクションでき、持ち上げ推論(FOVE、WFOMC、C++ へのコンパイル)で周辺確率を出せる。 - 二部グラフの集合被覆は最小集合被覆が NP 困難、貪欲法が O(e·f)。 - 決定木は推論が O(d)(d は最悪 O(n)、平均 O(log₂ n))。ニューラルネットの前向き伝播は O(max(s,f,h)²·l)、SVM はカーネル依存(線形なら s に線形)。 **Table IV: ベイジアンネットワークの推論アルゴリズム(Inference algorithms in Bayesian Networks)** ![[_attachments/arxiv-1701.08546/table4-inference-bayesian.png]] (Table IV. n は変数数、m は変化する変数数、w は木幅、w_c は制約付き木幅、d は変数の平均定義域サイズ、s は症状変数数、f は潜在故障変数数。) - 一般の BN では、周辺確率・MPE は NP 困難、MAP は NP^PP 完全で O(n exp(w_c))(w_c は w より大きい)。MPE は O(n exp(w))。多項式木では木幅が親の最大数 p に等しく MPE は O(n exp(p))だが MAP は依然 NP 完全である。二部グラフ向けの反復 MPE は O(n⁵)、多項式木への近似適用では O(n⁶)。 - 二部モデルは簡単で近似が効くが、複雑なモデルからの変換が肥大化しうる(文献 [160] の IHU・IHU+ は例で n⁴)。 - 厳密が高価なとき、近似アルゴリズムは本質的にいつでも停止可能(anytime)なので実時間向きである。分類は確率的標本抽出、局所探索(MAP に遺伝的アルゴリズム・山登り・タブー探索・焼きなまし)、モデル簡略化の 3 系統。ループ付き信念伝播は収束時に近似周辺確率を出すが、収束と精度の条件は一般には理解されていない。 - MPE・MAP の時間を減らす 2 つの道: 事前計算(算術回路は評価が回路サイズに線形だが、コンパイルが高価で構造変更時に再コンパイルが要る)と、探索空間を狭める仮定(障害は稀で同時に最大 k 個、O(f^k))。 - MAP の拡張(explanatory MAP、MRE、MIE、explanation tree、causal explanation tree)は過剰特定を避ける。計算量は NP^PP 困難や、下位推論の呼出し回数(explanation tree が O(n²d²)、causal explanation tree が O(nd))で示される。複雑さゆえに普及していないと著者は推測する。 - 系列としての症状(プロセス)は、部分的に確率的なペトリネットで最も確からしい遷移(障害)列を求める手法がある。並列化は主にジャンクションツリー(OpenMP、pthreads、GPU、FPGA)で、OpenMP 版の計算量は O(n²w/p + w d^w n/p + n log p) である。 ## 考察 - 全体の傾向として、扱いやすさと表現力にトレードオフがあり、厳密解が高価なので近似・事前計算・仮定による探索空間の削減が共通の対処になる(結論)。 - RCA では最も基本的な二部・非確率的の集合被覆でさえ NP 困難であり、厳密推論はすぐに高価になる。 - 実時間診断には、事前計算(コードブック、算術回路)か、いつでも停止可能な近似が現実的な解である。 - 進化の速いシステム(IoT、クラウド)では、増分更新可能なモデルか全再学習が速いモデルが要り、ラベルを要する分類器は不利である。 ## 強み / 弱点・課題 - 強み: モデル・学習・推論を統一した次元で分類し、モデル間の変換関係(Figure 2)と各アルゴリズムの計算量を一望できる。文献の広さ(200 件超の文献)と、選択指針の明示。 - 弱点(論文が述べる): 表は網羅的でなく、任意の分類器が RCA に使える。著者は今後の課題として、ビッグデータ向け RCA の利用者ガイドの作成を挙げる(結論)。 - 読み取れる懸念: 計算量は理論値で、実データでの精度・遅延の比較は無い。決定木の一部の計算量は著者の仮定に基づく推定である。ニューラルネット・深層学習を扱う範囲は限られ、可観測性データ(ログ・メトリクス・トレース)の実システムへの適用は範囲外である。