GESアルゴリズム

GESアルゴリズム#

Greedy Equivalence Search (GES) アルゴリズムはBIC（Bayesian Information Criterion）などのスコアを最大化する貪欲探索により DAG を求める手法。

エッジを追加したり削除したりしつつ最大のスコアとなるグラフを探索する。

  • 前向き段階（Forward Phase）

    • スコアが最も良くなるように エッジを追加していく

  • 後向き段階（Backward Phase）

    • スコアが最も良くなるように エッジを削除していく

../../_images/a7b42171a10ab1f3101b24465dbaf0ac68a30f74ce63d84421b45b03e5885f23.svg
../../_images/13b97299ccf72dc3541f651ba3bbe4b0857f2cba9601d42246dd528a6c6b373c.svg
../../_images/b9696c3af78d32be59fd683eeba5424e00b989587b9c340f559cc232d2007ceb.svg
../../_images/f4e8521664cf5a746d445462c98e87bbad8e749342afbf8220764fc2416bf23c.svg

スコア#

BIC#

\[ BIC = -2\ell(\hat{\theta}) + k\log n \]

ここで

  • \(n\)：サンプルサイズ

  • \(k\)：モデルのパラメータ数

  • \(\ell(\hat{\theta})\)：最尤推定したときの対数尤度

from castle.common import GraphDAG
from castle.metrics import MetricsDAG
from castle.datasets import load_dataset
from castle.algorithms import GES

X, true_dag, _ = load_dataset(name='IID_Test')
algo = GES()
algo.learn(X)

# plot DAG
GraphDAG(algo.causal_matrix, true_dag)

# calc Metrics
met = MetricsDAG(algo.causal_matrix, true_dag)
print(met.metrics)

INFO:root:Finished synthetic dataset
../../_images/91c416c9530a54dfad03f646345274ed285a9ffc350322be7b829b7e9aec4d80.png 
{'fdr': 0.3824, 'tpr': 1.05, 'fpr': 0.52, 'shd': 14, 'nnz': 34, 'precision': 0.4706, 'recall': 0.8, 'F1': 0.5926, 'gscore': 0.0}

実装#

Greedy Equivalence Search (GES) — 1.0.0 | pgmpy docs

# データセットの生成
import numpy as np
from pgmpy.utils import get_example_model
np.random.seed(42)
model = get_example_model("asia")
model.seed = 42
df = model.simulate(int(1e3))

# 因果構造を推定
from pgmpy.estimators import GES
est = GES(df)
dag = est.estimate(scoring_method="bic-d")

# daftパッケージで作図
dag.to_daft().render()

INFO:pgmpy: Datatype (N=numerical, C=Categorical Unordered, O=Categorical Ordered) inferred from data: 
 {'asia': 'C', 'xray': 'C', 'either': 'C', 'dysp': 'C', 'tub': 'C', 'smoke': 'C', 'bronc': 'C', 'lung': 'C'}
INFO:pgmpy: Datatype (N=numerical, C=Categorical Unordered, O=Categorical Ordered) inferred from data: 
 {'asia': 'C', 'xray': 'C', 'either': 'C', 'dysp': 'C', 'tub': 'C', 'smoke': 'C', 'bronc': 'C', 'lung': 'C'}
INFO:pgmpy: Datatype (N=numerical, C=Categorical Unordered, O=Categorical Ordered) inferred from data: 
 {'asia': 'C', 'xray': 'C', 'either': 'C', 'dysp': 'C', 'tub': 'C', 'smoke': 'C', 'bronc': 'C', 'lung': 'C'}

<Axes: >
../../_images/6d0f194fd29c356959a9ca45a3bb66ccdaf2253f7784940a387858d639bffa4b.png

参考#

Contents