## Memo ### 0. Metadata - Amazon Researchの著者らによるML系トップ会議のICMLで発表された論文である。 - CausalRCAという用語が文中に出現するが、AIOpsの[[2022__arXiv__CausalRCA - Causal Inference based Precise Fine-grained Root Cause Localization for Microservice Applications|CausalRCA]]とは関係がなく、文中で定義される著者ら独自の用語である。 - [[PyWhy]]のDoWhyが実装で用いられていることから、たしかにAmazonの因果推論に関連する研究であることがうかがえる。 ### 1. Contributions - **変数の因果グラフが既知であり、関数型因果モデル（FCM）が妥当であることを前提条件**とした「外れ値の根本原因」を定式化する。 - 提案法は、（１）既存の外れ値スコアを確率的に校正する情報理論的（IT）外れ値スコアを導入し、 （２）[[反実仮想]]を基に、目標とする外れ値スコアに対する各変数（上流ノード）の寄与を、協力ゲーム理論の[[シャープレイ値]]を用いて定量化する。 - 合成データセットと河川流の急激な増加を示すリアルデータセットを用いて評価した。 ### 2. Standpoints - 外れ値の「根本原因」 を定義する正式な方法はない。 - 本論文では、変数$X_1,...,X_n$の中の外れ値が$x_n$としたとき、$x_n$の外れ値スコアに対する各ノイズ$N_j$の寄与を定量化することにより、$x_n$の根本原因を特定する形式的な手法を提示する。 - 寄与という概念は、$x_n$の外れ値スコアに対する（ノード $X_j$ における）事象 $x_j$ の「原因機構」の貢献度を捉えるもの。 - クラウドサービスの根本原因特定の例では、図１のように、サービス遅延の依存関係と遅延の観測値が与えられ、(d)のように寄与率を出力する問題設定となる。 - ![[Pasted image 20230418112917.png|400]] ### 3. Major Ideas - IT外れ値スコア - 情報理論的な観点からは、ある事象が稀であればあるほど、その事象はより多くの情報を運ぶ。 - 外れ値スコアの定義は式（2） - ![[Pasted image 20230418113426.png|300]] - 任意の特徴マップ$\tau$を用いることで、既存の外れ値スコアを、例えば[[Isolation Forest]]とすることができる。何が極端なイベントであるかは、$X$の分布だけでな く、特徴マップτにも依存するため、多変量$X$や他の領域に対しても、簡単に外れ値を定義できる。 - IT外れ値スコアは、入力空間Xの代わりに、特徴空間 τ(X )上の分布を考慮 - [[Z-score]]の例 ![[Pasted image 20230418113836.png|300]] - IT外れ値スコアは、SτX (X)が大きい確率が指数関数的に減少するため、極端な外れ値はめったに起こらないはず。 - 寄与率 - 反実仮想の質問：外れ値$x_n$に関連する既存の機構ではなく、ノードにむしろ「正常な」因果機構を割り当てていれば、事象$x_n$は外れ値ではなかっただろうか？ - ノード自体の 寄与を、その親から継承される寄与と分離する。 - 実際の値xnそのものではなく、事象xnの外れ 値に焦点を当てる。 - Halpern & Hitchcock (2013)の「graded causation」 の精神に基づくと、何かが原因である度合いは、他の変数のインスタンス化が「正常」であるかどうかの問題である。 - $x_n$のITスコアに対するFCMの各ノイズ項$N_j$の寄与を、$X_j$の因果機構が「正常」であった可能性の対数減少の観点から測定する。 - 反実仮想のより具体的な質問：事象$x_n$は、$N_j$をランダム化して$X_j$に正常な因果機構を割り当てていれば外れ値ではなかったか? → 質問時のテールイベントの対数尤度の変化を定量化する。 - 寄与は、式(10)で計算できるが、ノイズをランダム化する部分集合$I$に依存する。この順序への依存性による恣意性を排除するために、シャプレー値（全ての順序を対称にする）を導入する。すべての可能な順序を考慮し、各順序の寄与を計算し、平均を取る。 - ![[Pasted image 20230418115113.png|300]] - ![[Pasted image 20230418115152.png|300]] - 確率$p_j$が低いほど、ノイズ項 $N_j$ の寄与度 $- log\ p_j$が高くなるため、稀な必要条件は寄与度が高く、 根本原因である可能性が高い。 ### 4. Experimental design & Results - 実装にはDoWhyのgcmモジュールを用いる。 - 河川流のデータソースは https://environment.data.gov.uk/hydrology/explore - シミュレーション実験 - 合成データを用いて、モデルの仮定が成立・不成立の各場合で、top-kの根本原因を特定できるかを評価する。不成立を再現するために、グランドトゥルースの因果グラフからランダムにエッジを削除する。 - 因果関係グラフと関連するFCMをランダムに生成する。FCMから学習サンプルを生成する。異なる強さのターゲットの上流の機構を摂動させ、外れ値を得る。 - ベースラインは、z-score（NaiveRCA）と、特徴マップとしてz-scoreを用いたシャプレー値（CausalRCA）を用いる。 - ランキングの評価指標は、結果の関連性が段階的に高いランキングを測定するために広く使われている指標であるNDCG@kを用いる。 - 1K個のランダムな因果グラフを描く。 - 実験結果は図６に示され、モデルの仮定が成立しない場合でも提案法は優れている。ただし、エッジを多く削除するとほど性能が低下する。 - ![[Pasted image 20230418120747.png|600]] - リアルデータ実験 - データからFCMを推定する(OLSによる因果回帰係数とノイズの推定など)ことは、交絡バイアスに悩まされるが、各観測点での水流のほとんどが下流の観測点にも達すると仮定すると、各観測点での流れと上流の流量の和の差だけで、ノイズを推定する。 ### 5. Discussions & Limitations - データから関数やノイズを推測することはしばしば問題であるが、領域知識により解決できることがある。 - シャプレー値の寄与を数値的に計算するためには、式（10）を全ての順序$I$について平均化する必要があるが、変数の数が多いと厳密な計算は難しい。そこで、サンプリング近似を適用して、精度と速度のトレードオフ化できる。 - 外れ値とは、必ずしもノイズの外れ値に基づくものではなく、提案法ではノイズ以外の要因による外れ値を想定していない。 ### 6. Thoughts - 異常スコアに基づき、シャプレー値による寄与度を根本原因とみなす手法は、以前に検討し、日本語で論文化したもの（鶴田, 坪内, IOTS2021）だが、ICMLだけあって圧倒的に理論的に洗練されている。 - 理論的枠組みは理解できないところがほとんどだったが、じっくり読み込めばなんとかなりそうな範疇にはみえる。 - ICについては、単に異常スコアに対して負の対数をとっているようにみえる。異常検知での異常スコアの定義に対数尤度を使うことがあるが、同じなのか差異があるのか。 - 論文にも書かれているように、因果グラフが判明していて、FCMも妥当であるという少ないとも、AIOps領域適用の観点からみると強い仮定が置かれている。評価では河川の水量という単純な線形性をもつ領域知識からFCMのノイズ項を計算しているが、クラウドシステムで同等の領域知識を導出できるかは疑問である。 ## Abstract 外れ値を説明する現在の技術では、外れ値の原因を見分けることができない。我々は、変数の中から外れ値の「根本原因」を特定する正式な方法を提示する。この方法は、関数型因果モデルとともに、変数の因果グラフを必要とする。これは、各変数がどの程度、目標とする外れ値の「根本原因」であるかを説明する、目標とする外れ値スコアに対する各変数の寄与を定量化するものである。我々は、シミュレーションを通じて本手法の経験的性能を研究し、極端な河川流の「根本原因」を特定する実世界のケーススタディを提示する。 [[2022__ICML__Causal structure-based root cause analysis of outliers__translation]]