2019__Review of Causal Discovery Methods Based on Graphical Models

### Abstract 生物学を含む科学の様々な分野では、基礎となる因果関係を見つけ出し、それを利用することが基本的な課題となっています。因果関係は、介入を適切に行えば見えてくるが、多くの場合、介入を行うことは困難であり、不可能である。そこで、純粋に観測されたデータの統計的性質を分析することで因果関係を発見する必要があります。本論文では、過去30年間に開発された因果関係発見のための計算手法の紹介と簡単なレビューを行うことを目的としており、制約に基づく手法やスコアに基づく手法、機能的因果モデルに基づく手法などがあり、いくつかの図解や応用例がある。 ### 1. INTORODUCTION 科学のほとんどすべては、因果関係とそれを支配する法則や規則性を明らかにすることにあります。17世紀に近代科学が始まって以来、原因を発見するための手順とその結果としてのデータには2種類ありました。どちらの方法も17世紀には輝いていましたが、当時も現在と同様に両者が絡み合っていました。エヴァンゲリスタ・トリチェリは、水銀の入った管を水銀の入った水盤に立てて角度や形を操作し、管の中の水銀の高さが変化しないことを示した。パスカルは、トリチェリが設計したマノメーターをピュイ・ド・ドームという山に運ばせて、水銀の高さが高度によって変化することを示した。ガリレオは、トリチェリの部下であり、観測された時系列データからジョビウスの衛星の軌道を（定性的に）特定し、黒点も同様に特定した。ガリレオの北の同時代人であるケプラーは、惑星の観測から3つの法則を導き出し、その1世代後のニュートンは、太陽系の観測と振り子を使った1つの実験から重力の法則を導き出し、現代物理学の基礎を築いた。現代の分子生物学は実験的な学問ですが、生物学の基礎であるダーウィンの『種の起源』には、種子の漂流というたった一つの実験しかありません。この論文は、因果関係の表現の一種である有向グラフィカル因果モデル（DGCM）の科学的応用と、観測的、実験的、あるいはその両方のデータからその種の真の因果表現を見つけるためのコンピュータ化された方法について述べたものである。ここでDGCMに注目したのは、2000年に遺伝子発現の研究のために最初に提案されたモデル（Murphy and Mian, 1999; Friedman et al., 2000; Spirtes et al., 2000）が、システムバイオロジー、特にオミックスや神経結合の研究に広く利用されるようになり、最近では、生物学的応用においてこのような表現を発見するためのアルゴリズムが爆発的に増えているからです。因果関係を発見するための伝統的な方法は、介入や無作為化実験を用いることですが、多くの場合、費用や時間がかかりすぎ、あるいは不可能です。そのため、純粋に観測データを分析することで因果関係を明らかにする「因果関係の発見」が注目されている（Spirtes et al.2000）。この数十年の間に、観察データ、あるいは実験と観察の混合データから因果関係や効果の大きさを特定するアルゴリズムが、分野を超えて次々と開発された。これらの開発は、適切な「ビッグデータ」の利用を可能にすると期待されています。これらのアルゴリズムは、すでにゲノミクス、生態学、疫学、宇宙物理学、臨床医学、神経科学など多くの分野で応用されており、多くの場合、その予測が実験的または準実験的に検証されています。このレビューでは、因果関係の発見に焦点を当てます。従来の因果関係研究では、因果関係が完全または部分的にわかっている場合に、因果効果の同定や介入の効果に関する推論を行うアルゴリズムは、別のクラスの問題を扱っていた。ここでは、因果関係を発見するためのスコアベースの方法だけでなく、いわゆる制約ベースの方法から始めます。1990年代以降、データの[[条件付き独立性]]関係を利用して、根本的な因果構造を復元することが行われてきた。典型的な（条件付き独立）制約ベースのアルゴリズムとしては、[[PC]]やFast Causal Inference ([[FCI]]) (Spirtes et al., 2000)がある。PCは、交絡因子（2つの測定変数の観測されていない直接の共通原因）がないことを前提としており、発見された因果情報は漸近的に正しい。FCIは交絡因子があっても漸近的に正しい結果が得られる。このようなアプローチは，信頼性の高い条件付き独立性の検定方法があれば，様々な種類のデータ分布や因果関係を扱うことができるため，広く応用できる．しかし、これらのアプローチは、（独立）同値クラス、すなわち、同じ条件付き独立性を満たす因果構造の集合を出力するため、必ずしも完全な因果情報を提供するわけではない。PCアルゴリズムとFCIアルゴリズムでは、これらの同値クラスをグラフィカルに表現します。交絡因子がない場合には、適切に定義されたスコア関数を最適化することにより、因果構造を見つけることを目的としたスコアベースのアルゴリズムも存在する。その中でも、Greedy Equivalence Search (GES) (Chickering, 2003)は、同値クラスの空間を直接探索する2段階の手順としてよく知られています。近年，適切に定義された Functional Causal Models (FCM) に基づくアルゴリズムが，同一等価クラスの異なる Directed Acyclic Graph (DAG) を区別できることが示されている．この利点は，条件付き独立関係よりもデータ分布に対する追加的な仮定に負うところが大きい．FCMでは，効果変数Yを直接原因Xとノイズ項Eの関数として表現します．すなわち，Y = f (X, E)，ここでEはXから独立しています．制約された関数クラスのおかげで，ノイズと原因の間の独立条件が真の因果方向に対してのみ成立し，誤った方向に対しては違反するため，XとYの間の因果方向を特定することができます．線形非ガウスモデル(Shimizu et al., 2006)や非線形モデル(Hoyer et al., 2009; Zhang and Hyvärinen, 2009b)に基づく因果関係発見法をレビューし、その適用性について議論する。実際には、信頼性の高い因果関係の発見のためには、因果関係のプロセスや観測データを生成するためのサンプリング・プロセスにしばしば生じる特定の課題に対処する必要があります。そこで、時系列における因果関係、測定誤差、欠損データ、データの非定常性や不均一性、選択バイアスなど、多くの実用的な課題に対処する方法を議論する。最後に、生物学における因果関係検索アルゴリズムおよび関連するいくつかの手法の応用について簡単に説明し、その選択と使用についていくつかの指針を示す。 ### 2. DIRECTED GRAPHICAL CAUSAL MODELS DGCM は次のような構成要素をもっています．(1) 「[[確率変数]]」とみなされる変数の集合，(2) 変数のペアの間の有向エッジの集合，各エッジは，他のすべての変数がある値に固定されていて，尾部の変数が外生的に変化した場合に，2つの変数が関連するという仮説とみなされる，(3) すべての変数の可能な値に対する共同確率分布，である．変数は時間を指標とすることができ、因果関係のある一連の確率過程を形成します。また、変数のいくつかは測定されないこともあり、変数はカテゴリー、順序、または連続であることもあり、測定誤差や選択バイアスがあることもありますが、これもグラフで表されます。一般に「構造方程式モデル」（SEM）や「関数的因果モデル」（FCM）と呼ばれるDGCMのクラスは、各変数の値が、グラフ上の直接原因と測定されていない外乱の決定論的な関数であると仮定しています。変数とその直接の原因とを結びつける関数は何でもよいが、線形モデルが最も一般的である。DGCM のクラスには，回帰モデル，因子モデル，ARM 時系列モデル，潜在クラスモデルなどが含まれますが，それよりも一般的です．DGCM は初期条件 (時系列を除く) や境界条件を必要としないので，微分方程式系や偏微分方程式系とは対照的に，因果関係のシステムを表現することができます．すべての有向グラフモデルが因果関係の解釈を持つわけではないことに注意してください。従来のグラフモデルは、データの結合分布をより単純な要因の積として分解するコンパクトで柔軟な方法を提供していますが(Koller and Friedman, 2009)、上に示したDGCMの第2成分は、有向グラフが因果関係の意味を持つために不可欠です。これは、末尾の変数が外生的に変化している間、他のすべての変数がある値に固定されていた場合、間にエッジを持つ2つの変数が関連することを述べ、したがって、有向グラフにおいてXi→Xjの場合、XiがXjの直接の原因であることを示している。言い換えれば、有向グラフにおいてXi→Xjであれば、Xjの分布（あるいは値）を直接変化させるようなXiへの介入が存在することを示している。因果ベイジアンネットワークは、Pearl (2000, p.23)によって同様の方法で定義された。有向グラフと、その変数の値に関する共同確率分布のペアは、制約を受けることになる。サイクルのない（閉じた有向パスのない）有向グラフの場合、グラフィカルな条件-d分離-が確率分布の条件付き独立性を意味するという制約がある。頂点X1から頂点Xnへのパスとは、各頂点のペアXiとXi+1に対して、エッジXi→Xi+1またはXi+1→Xiが存在するような、異なる頂点＜X1, ..., Xn＞の並びである。XiからXnへの有向パスは、各ペアXi、Xi+1について、Xi→Xi+1となるパスである。変数Xiは、パスにXi-1→Xi←Xi+1が含まれていればパスP上のコリダーであり（すなわち、Xiはパス上の隣人の共通の効果である）、そうでなければ非コリダーである。変数の3つの離接集合X, Y, Sについて、Xの任意のメンバーとYの任意のメンバーの間のすべてのパスがSによってブロックされている場合、XはSを条件としてYからd分離されます。 d-分離のグラフ特性と条件付き独立性との関係は、より直感的ではあるが、実際にはあまり役に立たない局所的なマルコフ条件に相当する。すなわち、有向非環状グラフ内のすべての変数Xは、その親（Xに向かう辺を持つ変数）を条件として、その非子孫から独立している。マルコフ条件は、実験的推論におけるおなじみの原理を一般化したものと考えることができます。つまり、ある目的の変数Xに直接影響を与える変数の値を固定することで、より直接的な原因を介してのみXに影響を与えることができる、より遠い原因を「スクリーンオフ」することができるのです。同じd分離特性を持つグラフは、通常「Markov equivalent」と呼ばれ、同じ条件付き独立関係を意味する。Markov equivalentであるすべての有向非循環グラフを集めたものがMarkov Equivalence Class (MEC)である。線形システムでは、d-分離のグラフ特性は、サイクルクローズした有向パスを持つ有向グラフに一般化されている(Spirtes, 1995)。より大きなシステムの限界グラフを表すグラフを持つシステムには、それに対応する関係であるm-separationが存在する（Ayesha et al. 因果関係のあるグラフとそれに関連する人口分布に対してマルコフ条件が成立すると仮定した場合、それを因果関係のあるマルコフ仮定と呼ぶ。ここで重要なことは、[[d分離]]とその関連特性は、変数の値に関する共同確率分布における条件付き独立関係の必要条件を提供するが、十分条件ではないということである。確率分布には、グラフに適用されるd-separationでは規定されない追加の条件付き独立関係が存在する可能性があります。そのような余分な条件付き独立関係がない場合、分布はグラフに忠実であると言われる（因果関係のあるグラフとそれに対応する母集団の分布が真であると仮定した場合、因果関係忠実性の仮定と呼ばれる）。 DGCM のグラフ関係を，単なる関連性や依存性の表現ではなく，因果関係の主張とみなす理由は，DGCM が多くの仮想実験の結果についての主張を伴うからである．非周期的な DGCM が有向辺 X → Y を含む場合，実験的な主張は，グラフで表される他のすべての変数を固定した場合，X を強制的に変化させれば X と Y は共食いするが，Y を強制的に変化させれば共食いしないというものである．これらの実験的予測は，グラフと確率分布から計算することができる(Spirtes et al., 2001)． ### 3. TRADITIONAL CONSTRAINT-BASED AND SCORE-BASED CAUSAL DISCOVERY METHODS 大雑把に言えば、因果探索法とは、グラフィカルな因果構造を記述するパラメータを統計的に推定することに他ならない。計算量の多い推定ではあるが、それでも統計的なパラメータの推定であり、身近なものとして理解できる。ほとんどの統計的推定法では、データの関数として直接、推定された相関関係を数値や区間で示します。しかし、他の推定量はもっと手間がかかります。単純なモデルを除くすべてのモデルにおいて、例えば事後確率分布の推定や、循環構造方程式モデルの推定には、通常、反復またはモンテカルロ手順が必要であり、ときには「探索」と明示されることもある（Hoff, 2009）。非相互作用的な原因を持ち，観察されない交絡因子（交絡因子は，2つの観察される変数の観察されない直接の共通原因である）を持たない非循環モデルの単純なケースで推定されるパラメータは，N×N行列のエントリーだけである。ここで，Nは変数の数であり，（i, j）番目のエントリーは，変数jが変数iの親であるかどうかを示す。一組の変数の間の直接的な関係が、ないことがわかっているのではなく、未知である場合には、さらに値を加えることができる。問題は、これらのパラメータをどのように推定するかである。統計的な推定には様々な望ましい条件があります。統計的な「一貫性」、すなわち、サンプリングの仮定の下で、推定値が確率的にあるいはほぼ確実に真値に収束すること、一様収束、すなわち、有限標本サイズでの誤差の大きさに確率的な境界があることなどである。忠実性の仮定に基づき、条件付独立関係が成立するグラフ因果モデル探索は、一般に「点的」な整合性しかなく、有限標本の誤差確率も推定構造の信頼区間も得られない。ただし、変数の数やグラフのスパース性を標本サイズの関数として制御するモデル群では、忠実性よりも強い仮定を置くと一様な整合性が得られる（Kalisch and Bühlmann, 2007）。ほとんどの場合、探索アルゴリズムには2つのクラスがあり、そのサブクラスと "近傍法 "がある。1つのクラスの探索アルゴリズムは、母集団において成立すると判断された条件付き独立関係のセットを（因果的マルコフおよび忠実性の仮定の下で）最も密接に内包するグラフのMECを効率的に探索しようとするものである。また、別のクラスのアルゴリズムでは、独立したノイズに対する各変数の依存性または条件付き独立性を推定し、これらの関係を用いて有向グラフモデルを構築する。これらのそれぞれがどのように可能かを説明し、いくつかの変種についても言及する。 #### 3.1. The [[PC]] Algorithm 潜在的交絡因子がないと仮定したi.i.d.サンプリングの下で一貫性のある最も古いアルゴリズムの1つがPCアルゴリズム(Spirtes et al., 2001)であり、条件付き独立性を決定するための多くの統計的手続きを差し込むことができる検索アーキテクチャを提供しています。条件付独立性の仮説検定や、特定の有向エッジを持つモデルと持たないモデルの間の[[ベイズ情報量規準]]（BIC）のような適合スコアの差に基づく方法など、そのような統計的決定手順があるとします。 ![[Pasted image 20210702150102.png]] 真の構造を図1Aのようにする。d分離により、この構造はXがYから独立していることを意味し、X⊥Yと書き、XとYはそれぞれZを条件としてWから独立していることを意味し、{X,Y}⊥W|Zと書く。呼び出されたときに、統計的意思決定手続きがこれらの関係を見つけたとする。PCは、因果マルコフ条件と忠実性の仮定の下で、潜在的な交絡因子がない場合、2つの変数が独立である残りの変数の条件付けの部分集合が存在しない場合に限り、2つの変数が直接因果関係を持つ（間にエッジがある）という事実に基づいている(Spirtes et al., 2001)。これは次のような仕組みです。 1. 図1Bのように、完全な無向グラフを作成する。 2. 無条件に独立している変数間の辺を削除する。この場合、X-Yの辺となり、図1Cのグラフとなる。 3. 各ペアの変数(A, B)の間にエッジがある場合は図1Dのように、A⊥B|Cの場合、AとBの間のエッジを削除する。 4. 間にエッジを持つ変数A、Bの各ペアと、両方ともAに接続されたエッジまたは両方ともBに接続されたエッジを持つ変数{C,D}の各ペアについて、A⊥B|{C,D}であれば、AとBの間のエッジを消去する。この例では、ZとWは、Xに対してもYに対しても、あるいはXとYの両方に対しても条件付きで独立ではないので、これ以上の統計的決定はしない。XとZ、YとZについても同様です。 5. AとBが隣接し、BとCが隣接し、AとCが隣接していないような変数の三重項(A,B,C)に対して、AとCが独立し、それに伴って両者の間のエッジが除去された集合条件にBが含まれていなかった場合、オリエント・ヘッジA-B-C as A→B←Cを行う。このような変数の三重構造をv構造と呼ぶ。この例では、X-Yのエッジを消す際にZが条件になっていないので、X→Z←YのようにX-Z-Yを配し、図1Eのような結果になります。 6. A → B - Cで、AとCが隣接していないような変数の三重項について、B - Cの辺をB → Cのように配向させることを配向伝搬といいます。この例では、X-Yのエッジを消す際にZが条件になっていないので、X→Z←YのようにX-Z-Yを配し、図1Eのような結果になります。ここでは図示していませんが、他にもいくつかの単純な方向性伝播規則があります。図示された推論ステップは、この例のために調整されたものではなく、有向非環状グラフからの任意のi.i.d.データに対して成立する一般的なルールセットのインスタンスです。条件付き独立性の決定が大規模サンプルの限界で正しい場合、PCアルゴリズムは、Causal MarkovとFaithfulnessの仮定、i.i.d.サンプル、測定されていない交絡因子がないと仮定して、大規模サンプルの限界で真のMarkov Equivalence Classに収束することが保証されます。なお、いくつかの例では、指向性ルールのいずれも、与えられた無指向性エッジには適用されず、そのエッジは出力では無指向性のままとなります。これは、2つの変数が隣接していることはわかっていても、エッジがどの方向を向いているかはわかっていないことを意味し、同等に、エッジの方向が異なる2つの異なるMECのメンバーが存在することを意味する。有向エッジと無向エッジが混在するグラフオブジェクトは、DAGのMECを表すパターンまたはCPDAG（Completed Partially Directed Acyclic Graph）と呼ばれます。疎なグラフの場合、PCアルゴリズムは、少なくとも数万個の変数で実行可能である（線形または多項式の場合、条件付独立性テストが計算上効率的である）。 PCのような因果関係発見アルゴリズムの出力は、いわゆる「条件付き独立グラフ」(Lauritzen, 1996)とは異なり、2つの変数が残りのすべての変数から条件付きで独立している場合に限り、隣接していないというものであり、それよりもはるかに情報量が多いことは注目に値する。(条件付き独立グラフは、共同ガウス変数の特殊なケースでは「偏相関グラフ」に還元される)。条件付き独立グラフでは、辺は無方向なので、因果関係の解釈はできません。さらに、隣接関係は推定された因果関係グラフとは異なる可能性があります。例えば、上記の例では、XとYはわずかに独立しているものの、残りの変数、すなわち{Z, W}があれば条件付き独立ではありません。その結果、条件付き独立グラフでは、これらは隣接しており、因果関係のグラフとは異なります。 ### 3.2. The FCI Algorithm PCアルゴリズムは、その登場以来、数多くのバリエーションが発表されており、様々なヒューリスティック、つまり「ラッパー」で補完されてきました。最も重要な一般化は、Fast Causal Inference (FCI) Algorithm (Spirtes et al., 2001) であり、未知の交絡変数を許容し、時には発見することができる。このアルゴリズムの結果は、交絡変数が存在する場合でも、漸近的に正しいことが示されています。図2Aは、Uが測定されていない変数である場合、FCIアルゴリズムの複雑さを完全に示すことなく、これがどのように可能であるかを示しています。 ![[Pasted image 20210702151204.png]] PC手順の最初の状態と同様に、FCIは統計的独立性の判断を呼び出して無向グラフを刈り込むと、図2Bのようになります。 "o "マークは、矢の頭にも矢の尻尾にもなることを意味します。o "マークの理由は明らかになります。FCIでは、PCと同様の手順でエッジを配置しますが、すべてのエッジがどちらかに向くことを前提としていません。XとZは無条件に独立しているので、XZのエッジはYを条件とせずに排除され、XYZのトリプルは、X＞Y＜⊸Zという「コライダー」になります。同様にYZWは、Y＞Z＜⊸Wという「コライダー」になり、図2Cが得られます。 XとWにある残りの "o "記号は、X,Yの接続が、XからYへの有向性エッジなのか、測定されていない交絡因子なのか、あるいはその両方なのかをアルゴリズムが判断できないことを示しています。 YとZの測定されていない交絡因子が少なくとも1つあると判断できるこの例とは対照的に、交絡因子がある可能性を除外できる状況は他にもあります。例えば、図1Aの因果関係グラフを考え、それによって生成された十分なデータがあるとします。そうすると、FCIの出力では、ZとWの交絡子は存在しないことがわかります。そうでなければ、XとWはZに対する独立した条件付けができないからです（ZとWに交絡子がある場合、XとWはZによってd分離されません）。 PCと同様に、FCIにもバリエーションがあり、ほとんどの場合、情報量の減少を犠牲にしてアルゴリズムを高速化するように設計されています（例えば、RFCIアルゴリズム Colombo et al, 2012を参照）。 ### 3.3. The Greedy Equivalence Search ### 6. PRACTICAL ISSUES IN CAUSAL DISCOVERY 因果関係の発見は、観測データを分析して因果関係を発見することである。実際には、信頼性の高い因果関係の発見を行うためには、因果関係のプロセスやサンプリングのプロセスに特有の課題に取り組む必要がある。以下では、最近検討されている課題について報告する。これらの課題の多くは、因果関係の発見の信頼性と計算効率を向上させるために、より良いアプローチが必要である。 ### 6.1. Causality in Time Series #timeseries 多変量時系列は，ゲノミクスにおけるmRNAの発現系列や，神経心理学におけるBOLD（Blood Oxygenation Level Dependent）時系列など，多くの生物学的およびその他の科学的研究のためのデータを提供する。このようなデータを生成する因果関係を明らかにすることは、生成過程が非線形である可能性、データ取得速度が基本的な変化の速度よりもはるかに遅い可能性、測定誤差がある可能性、システムが非定常である可能性（すなわち、原因に応じて変数の確率分布が変化し、さらに因果関係も変化する可能性がある）、測定できない交絡要因がある可能性など、多くの理由から困難です。時系列の因果生成過程を推定するという一般的な問題は解決に近いものではありませんが、様々なクラスのケースでこれらの問題に対処する方法の理解は進んでおり、一般的な方法がうまくいかない理由についても理解が深まっています。原理的には、これまで説明してきた手法やその他の手法は、時系列に対して使用することができます。しかし、その精度は先に述べたすべての要素に影響されます。時系列データを扱うにはいくつかの戦略がある。1つは、データを別々の「ウィンドウ」に分割し、各ユニットの測定値をデータ分析ユニットとして扱う方法です。もう1つは、いくつかのラグ効果を仮定または推定し、そのラグ数を超えない範囲ですべての測定値をデータ分析単位として扱う方法です。これは、ベクトル自己回帰の標準的な手順であり、"Granger Causality "と呼ばれています。もう一つの方法は、任意の時間の測定値を他の時間の測定値から独立したものとして扱うことです。それぞれに欠点があります。窓法では、窓を越えた関係が必然的に除外され、窓の大きさの選択によって結果が変わる可能性があります。他の2つの方法では、ユニットはすべて独立ではないが、ほとんどのユニットは独立である。最も一般的な手順であるGranger因果関係は、時間的なアグリゲーションやサブサンプリングに非常に敏感であることが確立されている［アグリゲーションやサブサンプリングの影響と、それに対処するためのいくつかの可能な方法については、（Danks and Plis, 2013; Gong* et al., 2015; Gong et al., 2017）を参照］。サンプリング率が、信号が伝播するのに必要な実際の時間間隔に等しい場合（そして交絡因子がない場合）、Grangerの方法は非常に正確です。しかし、多くの時系列では、測定装置やサンプリング手順に起因して、あるいは効率的な収集・保存を目的として、データがサブサンプリングされたり、時間的に集計されたりする。しかし、適切な仮定の下では、サブサンプリングされたデータと時間的に集約されたデータの両方から真の因果関係を特定できることが示されています。特に、高度に時間的に集約されたデータのために、元の因果プロセスにおける時間的に遅れた因果影響が集約された時系列では瞬間的に見えることが示されており、これは低解像度の集約されたデータから推定された瞬間的な因果関係が根本的な因果影響と一致することを意味している(Gong et al., 2017)。応用面では、機能的磁気共鳴画像（fMRI）の時系列データに関する研究が盛んに行われており、最近では複数の手法の比較も行われています。大雑把に言えば，fMRIデータは，基礎となる神経活動を時間的に高度に集約したものと考えることができます。第5節で説明したTwo-StepとFASKの手順は、最高の精度（見つかったエッジのうち正しいものの割合）とリコール（見つかった真のエッジの割合）を持つことが証明されています（Sanchez-Romero et al. 驚くべきことに、これらは、分散が変数の測定なしの分散よりも大きくない変数の（シミュレートされた）エラーに対してロバストです。Two-stepは高い精度を維持していますが、リコールの損失が大きく、FASKは良好な精度とリコールの両方を維持しています。