@2014__JMLR__Order-Independent Constraint-Based Causal Structure Learning

# Order-Independent Constraint-Based Causal Structure Learning > [!abstract] 概要 > 我々は、PC、FCI、RFCI、CCD アルゴリズム(Spirtes et al., 1993, 2000; Richardson, 1996; Colombo et al., 2012; Claassen et al., 2013)のような、因果構造学習のための制約ベース手法を考える。これらのアルゴリズムはすべて、最初の段階として PC アルゴリズムの隣接探索を行う。PC アルゴリズムは順序依存であることが知られており、出力が変数を与える順序に依存しうる。この順序依存性は低次元の設定では小さな問題である。しかし我々は、高次元の設定ではそれが非常に顕著になり、結果が大きくばらつきうることを示す。我々は、この順序依存性の一部または全部を除く PC アルゴリズム(したがって他のアルゴリズム)のいくつかの修正を提案する。提案する修正はすべて、元のアルゴリズムと同じ条件のもとで、高次元の設定で一致性を持つ。我々は、PC、FCI、RFCI アルゴリズムとそれらの修正を、シミュレーション研究と酵母の遺伝子発現データセットで比較する。修正は、低次元の設定では同程度の性能を、高次元の設定では改善された性能を与えることを示す。すべてのソフトウェアは R パッケージ pcalg に実装されている。 ## 論文情報 - 著者: [[Diego Colombo]]、[[Marloes H. Maathuis]](ともに [[ETH Zürich]] Seminar for Statistics) - 掲載: Journal of Machine Learning Research 15 (2014) 3921-3962。投稿 2013 年 9 月、改訂 2014 年 7 月、掲載 2014 年 11 月。編集は [[Peter Spirtes]]。42 ページ。 - 実装: R パッケージ pcalg。高次元一致性を示した [[@2007__JMLR__Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm]] の結果を、修正版でも保つ。 - 構成は通常の論文で、本文 7 節と付録 3 節(追加の低次元・中次元の実験、計算時間、α の選択)からなる。章立てに分ける長編文書ではないため、本 source 1 枚で扱う。 ## 概要 [[PCアルゴリズム]]の出力が変数の並び順(ordering)に依存することを、酵母の遺伝子発現データで示したうえで、依存の発生源を「スケルトン」「v 構造の判定」「辺の向き付け」の 3 つに分解し、それぞれを除く修正を与える論文である。核になるのは PC-stable で、条件付けサイズ ℓ ごとに隣接集合を固定し、辺の削除を次の ℓ まで遅らせる。これだけで標本版のスケルトンが順序独立になる。v 構造には保守的 PC(CPC)と多数決則 PC(MPC)、向き付けにはリスト方式と双方向辺を使う。FCI と RFCI にも同じ修正を持ち込める。 ## 問題設定 - 制約ベースの因果構造学習(PC、FCI、RFCI、CCD)はいずれも、PC アルゴリズムの隣接探索を最初の段階に持つ。そのため PC の性質は他のアルゴリズムにそのまま波及する。 - PC アルゴリズムは、標本版では入力する変数の並び順で出力が変わる。先行研究(Dash and Druzdzel, 1999; Cano et al., 2008; Spirtes et al., 2000)はあるが、多くの文献では小さな問題として扱われてきた。 - 著者らは酵母遺伝子発現データ(Hughes et al., 2000。観察データ 63 サンプル × 5361 遺伝子、単一遺伝子欠失 234 株の介入データ)で、高次元では順序依存性が結論を左右するほど大きいことを示す。 **Figure 1: 酵母データにおける順序依存性** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig01-yeast-order-dependence.png]] (Figure 1. 酵母遺伝子発現データを 25 通りのランダムな並び順で解析した結果(α = 0.01)。(a) 各並び順で推定されたスケルトンの辺。辺の頻度順に並べてあり、全並び順で現れる辺と 1 回だけ現れる辺が混在する。(b) 各並び順に対応する IDA の ROC 曲線。原順序で公表された曲線(青破線)は中間にあり、ランダム推測と区別がつかない曲線から、はるかに良い曲線までばらつく。) - 各スケルトンは約 5000 辺で、約 1500 辺は全並び順で安定、約 1500 辺は 50% 以上の並び順で出現、約 2000 辺は 50% 以下の並び順でしか出現しない(Figure 1(a))。 - 因果効果の下限を推定する IDA(Maathuis et al., 2010)の ROC 曲線も並び順で大きく変わる(Figure 1(b))。 ## 提案手法 ### 順序依存性の 3 つの発生源各段階で、標本版は条件付き独立性の判定を誤るため、並び順が結果に響く。オラクル版(完全な独立性情報)では並び順は影響しない。 **Figure 2: 例 1・例 4 のグラフ** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig02-example1-skeleton.png]] (Figure 2. 例 1 と例 4 に対応するグラフ。(a) 真の DAG、(b) オラクル版と order1 の標本版(および PC-stable)が返すスケルトン、(c) order2 の標本版が返すスケルトン。order2 では辺 X3 − X4 の誤削除に続いて、辺 X2 − X4 が誤って残る。) 1. **スケルトン(例 1、Figure 2)**: 隣接集合は辺の削除のたびに更新される。そのため同じ ℓ のなかでも、どの辺を先に調べたかで、後続の検定の条件付け候補が変わる。例 1 では、誤判定の辺 X3 − X4 を先に消す並び順だと X4 の隣接集合から X3 が消え、X2 ⊥⊥ X4 | {X1, X3} を検査し損ねて辺 X2 − X4 が残る。 **Figure 3: 例 2・例 5 のグラフ** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig03-example2-vstructure.png]] (Figure 3. 例 2 と例 5 に対応するグラフ。(a) 真の DAG、(b) オラクル版の出力(任意の並び順)および order6 の標本版の出力、(c) order5 の標本版の出力。order5 では誤った分離集合 {X4} により、誤った v 構造 X1 → X2 ← X3 が生じる。) 2. **v 構造の判定(例 2、Figure 3)**: 分離集合は並び順で変わる。オラクル版では、ある頂点は全分離集合に入るか全く入らないかのどちらかなので影響しない。標本版では、誤って見つかった分離集合が誤った v 構造を生む。 **Figure 4: 例 3・例 6 のグラフ** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig04-example3-orientation.png]] (Figure 4. 例 3 と例 6 に対応するグラフ。(a) 標本版の PC で Step 1 の後に得られうるスケルトン。(b) Step 2 の後に得られうる部分有向グラフ。矛盾する v 構造を上書きする実装では、最後に処理した v 構造が向きを決める。規則 R1 でも、先に処理した三つ組で向きが変わる。) 3. **辺の向き付け(例 3、Figure 4)**: 矛盾する v 構造は pcalg では後勝ちの上書きになる。規則 R1〜R3 の適用順でも結果が変わる。スケルトンと分離集合が順序独立でも残る。 ### PC-stable(スケルトン) Algorithm 3.2 との違いは、条件付けサイズ ℓ を上げるたびに全頂点の隣接集合 a(Xi) を計算して保存し、その ℓ の間はこれを使う点だけである。辺の削除は記録するが、隣接集合には次の ℓ で初めて反映する。 - 標本版でも順序独立なスケルトンを返す(定理 3)。辺 Xi − Xj は、a(Xi) か a(Xj) の部分集合で独立と判定されるものがあれば、どの並び順でも消え、なければどの並び順でも残るためである。分離集合は並び順で変わりうる。 - オラクル版は元のアルゴリズムと同じ CPDAG を返す(定理 2)。 - 各 ℓ で辺ごとの検定が独立になるため並列化しやすい。代償として検定回数はやや増える(付録 A.2)。 ### CPC/MPC-stable(v 構造の判定) Ramsey et al. (2006) の保守的 PC(CPC)を使う。非隣接の三つ組 (Xi, Xj, Xk) について、Xi と Xk の隣接集合の部分集合をすべて調べ、独立になる分離集合を全部求める。Xj がすべてに入る、またはひとつにも入らないなら「曖昧でない」とし、そうでなければ曖昧とみなして向き付けをしない。CPC は標本版で曖昧な三つ組が多く、非常に保守的になる。そこで著者らは、Xj が分離集合のちょうど 50% に入るときだけを曖昧とみなす多数決則 PC(MPC)を提案する。v 構造か否かは、Xj が半数未満の分離集合にだけ入るかで決める。どちらも Step 1 の(順序依存の)分離集合を使わず、順序独立なスケルトンから決めるため、v 構造の判定が順序独立になる(定理 5)。 ### リスト方式(辺の向き付け) Step 2 の v 構造と、Step 3 の規則 R1〜R3 について、適用候補のリストを先に作り、すべてをいっせいに向き付ける。矛盾する辺は双方向辺(↔)で表す。双方向辺は因果的には解釈できず、矛盾があったことの印である。並び順を変えても向きが一致し、標本版で完全な順序独立になる(定理 7)。名称は L を付け、LCPC-stable、LMPC-stable のようにする。 **Table 1: 順序依存性の問題と PC アルゴリズムの修正** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/tab01-orderdep-pc.png]] (Table 1. 順序依存性の問題と、それを除く PC アルゴリズムの修正。チェックは標本版でその部分が順序独立に推定されることを示す。例えば PC-stable ではスケルトンは順序独立だが、v 構造と辺の向きは順序依存である。行名の BCPC/BMPC-stable は、本文のリスト方式 LCPC/LMPC-stable に対応する。) ### FCI・RFCI・CCD への展開 - FCI: PC-stable でスケルトンを得て、CPC で v 構造を決め、Possible-D-SEP 集合を全ペアぶん先に計算して固定する(FCI-stable)。v 構造の再判定に CPC/MPC を使うと CFCI/MFCI-stable、向き付けにリスト方式を足すと LCFCI/LMFCI-stable になる。ただし FCI の 10 個の向き付け規則をリスト方式にすると、識別パスの規則などで遅くなる。 - RFCI: 追加の条件付き独立性検定が Step 1 の(順序依存の)分離集合に依存するため、RFCI-stable は完全な順序独立にはならない。順序依存性は大幅に減る。CRFCI/MRFCI-stable で v 構造の順序依存も減らせる。 - CCD も同様の方法で順序独立にできると述べるにとどまり、実験はしていない。 **Table 2: 順序依存性の問題と FCI アルゴリズムの修正** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/tab02-orderdep-fci.png]] (Table 2. 順序依存性の問題と、それを除く FCI アルゴリズムの修正。読み方は Table 1 と同じで、FCI-stable ではスケルトンのみが順序独立になる。) ### 高次元一致性 PC は、誤りがなければ、グラフの次数以下のサイズの部分集合でだけ検定する性質を持つ。修正はすべてこの性質を保つため、Kalisch and Bühlmann (2007) の結果(ガウス分布)と Harris and Drton (2013) の結果(ガウス・コピュラ、順位相関)が、元のアルゴリズムと同じ条件のまま成り立つ。FCI 系は Colombo et al. (2012) の結果が同様に成り立つ。 ## 新規性 - 順序依存性を「スケルトン」「v 構造」「向き付け」に分けて個別に除いた、体系的な分析。従来は Cano et al. (2008) の辺強度を使う複雑な方法などに限られていた。 - PC-stable という、隣接集合の更新を遅らせるだけの単純な修正。オラクル版の健全性・完全性と高次元一致性を保つ。 - CPC を多数決則へ緩めた MPC と、双方向辺つきリスト方式による完全な順序独立化。 - 同じ考え方を FCI、RFCI へ拡張し、R パッケージ pcalg に実装した。 ## 実験設定 - **シミュレーション**: 重み付きランダム DAG(重みは Uniform[0.1, 1]、ノイズは標準正規)から多変量ガウスデータを生成する。高次元は p = 1000、E(N) = 2、n = 50 で 250 個の DAG を用い、DAG ごとに 20 通りの並び順、α ∈ {0.000625, ..., 0.04} の 7 通りで推定する。潜在変数ありの設定では、親を持たず子を 2 個以上持つ変数の半分を隠す。酵母データの規模に似せた設定である。低次元(n = 1000)の結果は付録 A.1 にある。 - **比較対象**: (L)PC(-stable)、(L)CPC(-stable)、(L)MPC(-stable)、RFCI(-stable)、CRFCI(-stable)、MRFCI(-stable)。FCI と RFCI のリスト方式は計算量の都合で除外。 - **指標**: 辺の数、誤り数(余分または欠落した辺)、真の発見率(TDR)、構造ハミング距離(SHD)、PAG では辺マークの SHD、ROC(有向辺の TPR と FPR)。 - **酵母データ**: 観察データに PC と PC-stable を適用し、介入データの上位 10% の大きな因果効果を正解として、IDA の順位付けを評価する。α = 0.01。 ## 実験結果 ### 高次元シミュレーション **Figure 5: スケルトンの推定性能** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig05-skeleton-metrics.png]] (Figure 5. PC(丸・黒線)と PC-stable(三角・赤線)による CPDAG のスケルトン(左列)、RFCI と RFCI-stable による PAG のスケルトン(右列)の推定性能。上から辺の数、余分または欠落した辺の数、TDR。x 軸は α(対数目盛)。平均±1 標準偏差で、250 個のグラフと 20 通りの並び順にわたる。真のグラフの平均辺数は約 1000。) - PC-stable と RFCI-stable は、すべての α で辺の数が少なく、誤りも少なく、TDR も高い(Figure 5)。ほぼ全ての α で推定グラフは真のグラフより疎で、PC-stable はさらに疎だが、偽陽性の減少が偽陰性の増加を上回る。 **Figure 6: 並び順ごとの推定辺** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig06-edge-occurrence-sim.png]] (Figure 6. 高次元設定のランダム DAG 1 個について、PC(黒)で 20 通りの並び順から推定された辺と、PC-stable(赤、21 番目の並び順として表示)の辺。x 軸は元の PC における出現頻度順で、どの並び順にも現れなかった辺は省く。) - PC は、全並び順で現れる安定な辺のほかに、並び順しだいで現れたり消えたりする多数の辺を出す。PC-stable は、この安定な辺をほぼ捉えた少数の辺を返す(Figure 6)。 **Figure 7: SHD による推定性能** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig07-shd.png]] (Figure 7. CPDAG の SHD(左、(L)PC(-stable)、(L)CPC(-stable)、(L)MPC(-stable))と PAG の辺マーク SHD(右、RFCI 系)。250 個のグラフと 20 通りの並び順にわたる平均。x 軸は α(対数目盛)。) - -stable 版は、すべての α で SHD が有意に小さい。CPC(-stable)、MPC(-stable) は PC(-stable) より良い。LCPC/LMPC のリスト方式の効果は小さい(Figure 7)。 **Figure 8: SHD の分散** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig08-shd-variance.png]] (Figure 8. 20 通りの並び順にわたる SHD の分散(CPDAG、左)と SHD 辺マークの分散(PAG、右)。250 個のグラフの平均で、x 軸は α(対数目盛)。) - -stable 版は SHD の分散が有意に小さく、(L)CPC-stable と (L)MPC-stable ではさらに小さい(Figure 8)。 **Figure 9: 有向辺の ROC** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig09-roc-directed.png]] (Figure 9. CPDAG(左)と PAG(右)の有向辺の TPR と FPR。250 個のグラフと 20 通りの並び順にわたる平均で、曲線は α を変えて描く。) - 潜在変数を許す設定では有向辺の発見は格段に難しく、TPR が低く FPR が高い。MPC-stable と MRFCI-stable が最良の ROC を示す(Figure 9)。 ### 低次元・中次元(付録) 付録の低次元設定(Figure 13、Figure 14、Figure 15、Figure 16)では、PC 系・(R)FCI 系の性能はほぼ同等で、順序依存性の大半は辺の向き付けに残る。M(R)FCI(-stable) が SHD の分散を最も減らす。中次元の潜在変数設定(付録 A.3、Figure 17、Figure 18)でも、修正版が元より良い。計算量では、PC-stable の検定回数は PC より多く、実行時間はわずかに長い(Table 4、Table 5)。 ### 酵母データ **Figure 10: 酵母スケルトンの解析** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig10-yeast-skeleton.png]] (Figure 10. PC と PC-stable による酵母データの CPDAG スケルトンの解析(α = 0.01)。(a) Figure 1(a) に、26 通りの並び順に対して PC-stable が返す唯一のスケルトンの辺(赤、27 番目の並び順として表示)を加えたもの。(b) 元の PC で各辺が現れた並び順の割合(階段関数)と、PC-stable のスケルトンの辺(赤)。PC-stable は、元の PC の並び順間で安定していた辺をほぼ捉える。) - PC-stable は 26 通りすべてで同じ 2086 辺のスケルトンを返す。PC は並び順により 5015〜5159 辺を返す。 **Table 3: 安定な辺の捕捉** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/tab03-stable-edges.png]] (Table 3. 推定グラフの辺のうち、集合 1・集合 2 に含まれる数(IN)と含まれない数(OUT)。26 通りの並び順にわたる平均(標準偏差)。集合 1 は元の PC が全 26 並び順で出した辺(1478 辺)、集合 2 は 90% 以上の並び順で出した辺。) - 安定な辺(IN)の数は PC と PC-stable でほぼ同じで、それ以外の辺(OUT)は PC-stable が大幅に少ない。例えば集合 1 では OUT が 3606 に対し 607 である(Table 3)。 **Figure 11: 酵母データの IDA と ROC** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig11-yeast-ida-roc.png]] (Figure 11. 25 通りの並び順に対する酵母データの ROC 曲線(α = 0.01)。PC-stable は実線、MPC-stable と CPC-stable は黒破線、Maathuis et al. (2010) の曲線は青破線、ランダム推測は赤の一点鎖線。) - PC-stable は元の PC より良く、安定した結果を出すが、v 構造と向き付けは順序依存のまま残り、ばらつきがある。3 本は当てはまりが非常に悪い。 - CPC-stable と MPC-stable は 25 並び順でほぼ同じ CPDAG を返すが、有向辺は 2086 辺中約 90 本にとどまり、同値類が大きくなって IDA の性能が悪い(Figure 11 の破線)。 **Figure 12: 安定性選択との比較** ![[wiki/sources/_attachments/2014__Order-Independent-Constraint-Based-Causal-StructureLearning/fig12-stability-selection.png]] (Figure 12. PC、PC-stable、MPC-stable を、原順序(実線)、並び順を固定した 100 回の安定性選択(+ SS、破線)、並び順を並べ替えた 100 回の安定性選択(+ SSP、点線)で比較した酵母データの解析。灰色の線 RG はランダム推測。上位 20000 の効果で評価。) - 安定性選択(Stekhoven et al., 2012)を組み合わせると、PC と PC-stable の両方で後半の性能が上がる。PC-stable + 安定性選択(並べ替えの有無を問わない)が最良である。PC-stable は完全な順序独立ではないが、並べ替えの有無の差は小さい。 ## 考察 - 高次元の疎な設定で制約ベース手法を使う場合、順序依存性は無視できない問題であり、系統的に取り除ける。 - 修正は、できるだけ単純にし、健全性・完全性・高次元一致性を保つことを優先して設計した。 - 残る順序依存性: 最終段階の向き付け規則を適用する順序(1 つの辺が複数の規則で向き付け可能になる場合)は扱っていない。実験は元の規則順を使った。 - 修正は、PC の変種(ハイブリッド版、PC* など)ともあわせて使える。 ## 強み / 弱点・課題 - 強み: 発生源の分解が明快で、修正が単純である。オラクル版と一致性が変わらないため導入時の理論的コストがない。シミュレーションと実データの両方で検証している。並列化しやすい。 - 弱点・課題: PC-stable 単独では v 構造と向き付けの順序依存が残る。完全な順序独立の CPC/MPC 系は有向辺が激減し、IDA の因果効果の順位付けが使えなくなる(酵母では有向辺が約 90 本)。つまり順序独立性と情報量にトレードオフがある。検定回数の増加、FCI と RFCI のリスト方式の計算量の問題。 - 実験はガウス分布と偏相関検定が中心で、非ガウス・非線形の検定への一般化は示していない。α の選択は付録 B に BIC と安定性選択の 2 案を挙げるにとどまる。 - 図の一部に表記ゆれがある。Table 1 の行名は BCPC/BMPC-stable だが、本文は LCPC/LMPC-stable と呼ぶ。 ## 関連 - 概念: [[PCアルゴリズム]] / [[因果発見]] - エンティティ: [[Diego Colombo]] / [[Marloes H. Maathuis]] / [[ETH Zürich]] / [[Peter Spirtes]] / [[Markus Kalisch]] - ソース: [[@2007__JMLR__Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm]]