# PCアルゴリズム Navigation: [[index]] | [[overview]] ## 定義 PC アルゴリズム(Peter と Clark にちなむ。Spirtes et al., 2000)は、制約ベースの因果構造学習法である。完全無向グラフから始めて、条件付き独立性の判定に基づき辺を再帰的に削除してスケルトンを得て、v 構造と向き付け規則によって同値類の代表(CPDAG)を出力する。ガウス分布ではペアごとの偏相関を Fisher の z 変換で検定し、調整パラメータは有意水準 α だけである。(Source: [[@2007__JMLR__Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm]]) ## 未解決の問い - 忠実性やガウス性が崩れる実データ(時系列・非線形・欠測)で、PC アルゴリズムの一致性の保証はどこまで残るか。 - ガウス性が崩れる設定や、条件付き独立性検定に別の手法を使う設定でも、PC-stable の順序独立性と、CPC/MPC が失う有向辺の量は同様に振る舞うか。 ## 未編纂の観察 - 疎な DAG(最大近傍サイズ q が n^{1-b} のオーダー)なら、p が n の任意の多項式で増えても一様一致で、計算量も O(p^q) で済む。統計的一致性と計算可能性が同じ疎性で決まる。(Source: [[@2007__JMLR__Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm]]) - 推論はスケルトン段階に集約され、向き付けは決定論的規則にすぎない。高次元ではスケルトンのほうが CPDAG より回復しやすい。(Source: [[@2007__JMLR__Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm]]) - [順序依存性] **PC アルゴリズムの標本版は変数の並び順で出力が変わり、高次元ではその差が結論を左右するほど大きい**。酵母遺伝子発現データ(5361 変数、63 サンプル)では、約 5000 辺のスケルトンのうち約 2000 辺が半数以下の並び順でしか現れず、IDA の ROC 曲線も並び順しだいで、ランダム推測と区別できないものから有効なものまでばらつく。低次元では差は小さい。(Source: [[@2014__JMLR__Order-Independent Constraint-Based Causal Structure Learning]]) - [順序依存性] **順序依存性はスケルトン(隣接集合の逐次更新)、v 構造の判定(並び順で変わる分離集合)、辺の向き付け(矛盾する v 構造の上書きと規則の適用順)の 3 段階で生じ、段階ごとに別の修正で除ける**。PC-stable(条件付けサイズごとに隣接集合を固定)、CPC/MPC-stable(全分離集合で判定)、リスト方式と双方向辺(向き付け)の順である。オラクル版の出力と高次元一致性は元と変わらない。(Source: [[@2014__JMLR__Order-Independent Constraint-Based Causal Structure Learning]]) - [順序依存性] **順序独立性と情報量にはトレードオフがある**。酵母データで CPC/MPC-stable は 25 通りの並び順でほぼ同じ CPDAG を返すが、有向辺は 2086 辺中約 90 本にとどまり、同値類が大きくなって IDA の性能が悪い。PC-stable に安定性選択を足す構成が最良だった。(Source: [[@2014__JMLR__Order-Independent Constraint-Based Causal Structure Learning]]) - 高次元一致性の保証(Kalisch and Bühlmann, 2007)は、PC-stable など全修正版に元と同じ条件で引き継がれる。修正版でも、検定はグラフの次数以下のサイズの部分集合に限るためである。(Source: [[@2014__JMLR__Order-Independent Constraint-Based Causal Structure Learning]], [[@2007__JMLR__Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm]]) - AIOps の障害診断では、PC アルゴリズムが時間窓ごとの相関(因果)グラフの構築に使われる。FacGraph は有意水準 α を 0.05〜0.5 で動かしても精度がほとんど変わらないと報告する一方、窓長は精度と所要時間に強く効く(α = 0.5・窓長 500 秒で 400 秒超)。窓長が短すぎるとグラフ構築が不正確になる。(Source: [[@2018__IPCCC__FacGraph - Frequent Anomaly Correlation Graph Mining for Root Cause Diagnose in Micro-Service Architecture]]) ## 関連 - ソース: [[@2007__JMLR__Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm]] / [[@2014__JMLR__Order-Independent Constraint-Based Causal Structure Learning]] / [[@2018__IPCCC__FacGraph - Frequent Anomaly Correlation Graph Mining for Root Cause Diagnose in Micro-Service Architecture]] - 概念: [[因果発見]] / [[有向グラフィカルモデル]] / [[因果推論ベースRCA]] - エンティティ: [[Peter Spirtes]] / [[Markus Kalisch]] / [[Peter Bühlmann]] / [[Diego Colombo]] / [[Marloes H. Maathuis]] ## 出典 - [[@2007__JMLR__Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm]] - [[@2014__JMLR__Order-Independent Constraint-Based Causal Structure Learning]](順序依存性の 3 発生源と PC-stable ほかの修正)