PCアルゴリズム。未観測共通原因がないことを仮定している。 ![[Pasted image 20210702141856.png]] 1. 完全無向グラフを構築する 2. [[条件付き独立性]]が成立するエッジをグラフから除外する [[条件付き独立性検定]] 3. [[V-structure]]に基づきエッジの方向を決定する 4. [[オリエンテーションルール]]に基づきエッジの方向を決定する 詳細は、[[2007__Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm]] - ノード数が増加すると、2.の条件付き独立性の検索時の組み合わせの数が増大するため、計算時間が増加するという問題がある。 - 条件集合の大きさの昇順に検定を行うことで疎結合ネットワークでは高速な計算が可能 - 密なネットワークに対しては計算量が大幅に増加する - 条件付き独立性の条件変数集合の誤検出が矢線の向きの誤りを次々に導くという二重の負の連鎮性 - [[FCI]]への拡張がある。 - Pythonでは、 [[Pcalg]] パッケージがある。 ## 計算量 [[ベイジアンネットワークにおける因果発見]] 4.3節より。 kをあるノードに隣接するノード数、nをノード数として計算量の上限は、 $n^2(k+ 1) (n -2)^k/k!$ ## 文献 - P. Spirtes, C. N. Glymour, R. Scheines, and D. Heckerman, Causation, prediction, and search. MIT press, 2000. - [PCアルゴリズムの2次の独立性検定を実施しない理由について · Issue #8 · YutaroOgawa/causal_book · GitHub](https://github.com/YutaroOgawa/causal_book/issues/8)