グラフィカルモデルに基づく因果探索手法の調査

最近，因果推論や因果探索に興味を持ち，勉強している．というのも最近，ゆううきさんと一緒に分散システムの異常の原因を即時に診断するための研究を進めている．原因を診断するためのアプローチとして，サーバやコンテナ等から取得できる様々なメトリック（CPU使用率やメモリ使用率など）を（グラフ理論における）ノードとして，因果グラフを構築することを考えている．メトリック同士の単なる「相関」ではなく，結果と原因の関係である「因果」を捉えようとするアプローチである．例えば，システムの障害が発生した場合，相関だけでは，AとBが関連がありそうというところまでしか言えないが，因果を特定できると理想的には，Aの原因はBであるといった議論ができるため，有用だと考えている．
実際に，前述のような因果グラフを構築して障害の原因を特定しようというアプローチは，以下の例に挙げるようにここ数年で増えている印象がある．

今回の記事は，因果探索手法の中でもグラフィカルモデルに基づくアプローチに絞って，まとめていく．以下のサーベイ論文がよくまとまっていたので全面的に参考にした．

「Review of Causal Discovery Methods Based on Graphical Models（2019）」

グラフィカルモデル

グラフィカルモデルとは，確率モデルをグラフを用いて記述したものである．ここでいうグラフとは， $x$ 軸， $y$ 軸があるグラフではなく，グラフ理論のことであり，ノード（頂点）とエッジ（枝）の集合で構成されるものである．グラフィカルモデルを用いることで，どの確率変数同士が直接的に関係しているかを視覚的に表現できる．
上記でエッジと書いた部分は，単なる線と矢印の二つの表現があり，それぞれを用いたグラフを無向グラフおよび有向グラフと呼ぶ．変数間の因果を表現する際に利用されるのは主に後者の有向グラフである．有向グラフの代表的な例としてベイジアンネットワークが挙げられる．

因果探索

因果探索とは，データから因果関係（因果グラフ）を推定する手法である．前述のグラフィカルモデルで考えると，考慮すべき確率変数（ノード）のデータは手元にある状態で，因果の構造，すなわちどのようにエッジが繋がっているかを推定するということになる．多くの分野において，データの根底にある因果関係を見つけ出し，それを利用することは非常に重要であるため，因果探索は，ゲノミクス，臨床医学，疫学など幅広い分野に応用されている．次から，因果探索の具体的なアプローチについてまとめていく．

制約ベースの因果探索

制約ベースのアプローチでは，まず，観測変数にどのような条件付き独立性が成り立つかを推測する．次に推測された条件付き独立性を制約として，それを満たすような因果グラフを探索する．ここでは，代表的な制約ベースのアルゴリズムとして，PCアルゴリズム[1]を説明する．

PCアルゴリズム

PCアルゴリズムの処理の流れを以下の図を用いて説明する．前提として，PCアルゴリズムでは，未観測共通原因（潜在的な交絡因子）がないことを仮定している．

f:id:hirotsuru314:20201007095925p:plain — PCアルゴリズムによる因果グラフの推定

完全無向グラフを構築する．
条件付き独立性が成立するエッジをグラフから除外する．
ここで，条件付き独立性を検索する際は，条件として与える変数の数を0から1ずつ増やしながら，条件付き独立性が成立しうる全ノードの組合せを対象に行われる．
V-structureに基づきエッジの方向を決定する．
V-structureでは，三つの変数A，B，Cが「A-B-C」でA-C間にエッジがなく，A，Cを条件付き独立とする条件ノード群にBが含まれていないならば，「A→B←C」の関係が成立するとして，無向グラフ中の一部の因果の方向を推定する．
オリエンテーションルールに基づきエッジの方向を決定する．
オリエンテーションルールは有向非巡回グラフ（DAG）の定義から導かれるグラフの構造に関するルールである．具体的なルールについては「Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm」にまとめてある．

PCアルゴリズムは，一般にノード数が増加すると上記2の条件付き独立性を検索する際のノードの組合せの数が増大し，計算時間がかかるという問題がある．これに対して，条件付き独立性の検定をGPUで並列化して高速に処理するといった提案[2]もあるようだ．また，PCアルゴリズムは未観測共通原因がある場合のFast causal inferece（FCI）アルゴリズム[3]などへ拡張されている．

スコアベースの因果探索

スコアベースのアプローチでは，同じ条件付き独立性を与える因果グラフの集合であるマルコフ同値類ごとに，モデルのよさを測るスコアをつける．ここでは，代表的なスコアベースのアルゴリズムとして，Greedy Equivalence Search（GES）アルゴリズム[4]を説明する．

GESアルゴリズム

GESアルゴリズムでは，PCアルゴリズムのように完全無向グラフから始めるのではなく，空のグラフから始まり，必要なエッジを追加したり，不要なエッジを削除していきながら因果グラフを構築する．アルゴリズムの各ステップでは，グラフに有向エッジを追加することで，ベイズ情報量規準（BIC）のようなスコアや統計的仮説検定のZスコアで計測される適合性が向上するかどうかが決定され，適合性を最も向上させるエッジが追加される．スコアをそれ以上改善できなくなった場合，GESアルゴリズムは，どのエッジを削除するとスコアが最も改善されるかをエッジごとに検証していく．このような手順でスコア（例えばBIC）を用いて因果グラフを推定していく．

構造方程式モデルに基づく因果探索（非ガウス性・非線形性の活用）

先に挙げた制約ベース・スコアベースの因果探索は，データの構造に対してできるだけ仮定をおかずに，データのみから因果グラフを推測するアプローチである．これは，後述する構造方程式モデルにおける関数形と誤差変数の分布に仮定をおかないノンパラメトリックアプローチに分類される．仮定をおかないため様々なデータに適用できるという利点があるが，因果の構造を正確に推定できないケースも多い．そこで，分析者の事前知識を仮定としてモデルに取り入れるアプローチがある．ここでは，仮定を取り入れる上で重要な概念である構造方程式モデルについて述べ，非ガウス性の仮定を利用したLiNGAMという手法について述べる．

構造方程式モデル

構造方程式モデルは，データの生成過程を記述するツールである．ここで， $x$ ， $y$ という二つの変数について，以下のような単純な因果グラフを考える．

f:id:hirotsuru314:20201007131606p:plain — 因果グラフのサンプル

このような因果グラフにおける構造方程式を以下のように表す．

$\displaystyle x=e_x \\ y=f_y(x, e_y) \\$

ここで， $x$ ， $y$ は観測変数で， $e_x$ と $e_y$ は未観測の変数であり，誤差変数という． $e_y$ は $y$ の値を決定するために寄与しうる $x$ 以外の全ての変数をまとめて表した変数という意味をもつ．因果グラフをこのような方程式で表現した場合，分析者は以下の2点に仮定を導入することができる．

関数 $f_y$ の仮定（例えば線形か非線形か）
誤差変数 $e_x$ と $e_y$ の分布の仮定（例えば，ガウス分布か非ガウス分布か）

上記の二つに仮定を導入するものをパラメトリックアプローチ，関数には仮定をおく一方，誤差変数の分布には仮定をおかないものをセミパラメトリックアプローチと呼ぶ．ここでは，代表的なセミパラメトリックアプローチであるLiNGAMという手法を紹介する．

LiNGAM

LiNGAMはLinear Non-Gaussian Acyclic Modelの略であり，関数形に線形性を，誤差変数の分布に非ガウス分布を仮定するアプローチである．一見，二つの仮定をおいているようにも見えるが，非ガウス分布という仮定はガウス分布でさえなければどんな（連続）分布でも良いということからほぼ仮定をおいていないという解釈ができ，セミパラメトリックアプローチに分類されるようだ．LiNGAMについては，機械学習プロフェッショナルシリーズの「統計的因果探索」に詳しく解説されている．ここではさらっとアルゴリズムの概要をまとめる．
まずLiNGAMにおける仮定を整理する．

関数形が線形
誤差変数が非ガウス連続分布
有向非巡回グラフ（DAG）
誤差変数が独立性（未観測共通原因がないことを意味する）

p個の観測変数 $x_1,x_2,...x_p$ に対するLiNGAMモデルは構造方程式モデルを用いて以下のように表される．

$\displaystyle x_i=\sum_{i \neq j}^p b_{ij}x_i+e_i$

これを行列・ベクトルで表現すると以下のようになる．

$\displaystyle \mathbf{x}=\mathbf{B}\mathbf{x}+\mathbf{e}$

ここで， $p$ 次元ベクトル $\mathbf{x}$ は観測変数ベクトル， $p$ × $p$ 行列 $\mathbf{B}$ は係数行列， $p$ 次元ベクトル $\mathbf{e}$ は誤差変数ベクトルである．そして， $\mathbf{e}$ の成分 $e_i$ は独立で，それぞれ非ガウス連続分布に従う．係数行列 $\mathbf{B}$ は，観測変数の分布 $p(x)$ に基づいて一意に推定可能であり， $\mathbf{B}$ の成分のゼロ・非ゼロパターンから因果グラフを描くことができる．係数行列の推定には，独立成分分析（ICA）によるアプローチと回帰分析と独立性評価によるアプローチがある[5]．どちらのアプローチもcdt15/lingamで実装されている．OSSのコードも含めてLiNGAMはもう少し詳細に追いかけたい．

さいごに

今回は，サーベイ論文を参考にグラフィカルモデルを用いた因果探索の手法を整理した．ここでいくつかアルゴリズムを紹介したが，最近機械学習技術を活用した多くの手法が提案されている．例えば，深層強化学習[6]，敵対的生成ネットワーク（GAN）[7]を活用したものなどがあり，まだまだ奥が深い．また，重要なイシューとして，確率変数が時系列データの場合にどのように時系列の情報を消失せずにモデリングするかというのも大変興味深い．今後も因果探索について着実に勉強していって，ブログにまとめていきたい．