ECML-PKDD 2024 にて統計的因果探索の代表的モデル LiNGAM の高速な学習法 LayeredLiNGAM について発表しました

はじめに

こんにちは。人工知能研究所の鈴木です。富士通研究所では「因果探索を活用した意思決定」に関する研究開発を行っており、エンゲージメント調査データに基づく従業員の生産性向上など、現実の意思決定タスクに取り組んでいます。このたび、我々の研究成果である「線形非ガウス因果モデル LiNGAM における高速な因果探索技術」に関する研究論文が、機械学習・データマイニング分野の主要な国際会議である ECML-PKDD 2024 に採択されたので、その内容を紹介します。

対象論文

タイトル：LayeredLiNGAM: A Practical and Fast Method for Learning a Linear Non-Gaussian Structural Equation Model
著者：Hirofumi Suzuki (Fujitsu Limited)
発表会議：European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD) 2024
以下、その他リンクを随時追加予定

はじめに
採択された論文の内容
おわりに
- 参考文献

採択された論文の内容

概要

本論文では、線形非ガウス非巡回モデル（Linear Non-Gaussian Acyclic Model, LiNGAM）と呼ばれる因果モデルにおいて、その代表的な因果探索アルゴリズムである DirectLiNGAM に着目し、DirectLiNGAM の理論的枠組みを一般化することで、より高速なアルゴリズムである LayeredLiNGAM を提案しました。

背景

因果探索では、複数の観測と変数からなる所与のデータセットから、すべての変数対における因果関係を分析します。例えば、「降水量・来客数・売上」の3変数を持つデータセットが与えられたとき、「降水量が増えると来客数が減る」（降水量から来客数への因果）や「来客数が増えると売上が増える」（来客数から売上への因果）といった因果関係が推論されます。このような複数の因果関係をまとめた構造は因果グラフと呼ばれます。因果グラフがあれば、ある変数に介入（恣意的に値を決定）したとき、他の変数にどのような影響を及ぼすかがわかります。そのため、従業員の生産性とそれに関連しそうな複数の変数について因果探索を行い、介入の効果を分析して従業員の生産性向上のための計画を立てるなど、意思決定に応用できるのです。

因果グラフはしばしば構造方程式モデル（Structural Equation Model, SEM）でモデル化され、有向非巡回グラフ (Directed Acyclic Graph, DAG)として出力されます。前述の例では「降水量→来客数→売上」のような一本道の DAG が得られると予想されますが、一般には変数が増えることでより複雑な DAG が得られることもあります。SEM の中でも基礎的な位置づけにあるのが LiNGAM であり、単純ながらも重要な性質を備えています [1]。そして、DirectLiNGAM は LiNGAM を仮定した代表的な因果探索アルゴリズムであり [2]、Python パッケージ lingam を軸に広く普及しています [3]。

LiNGAM

$d$ 個の変数で構成されるデータを $d$ 次元のベクトル $\mathbf{x} = (x_1, \ldots, x_d)^\top \in \mathbb{R}^d$ で表します。これに対して、 $d$ 個のノードを持つ DAG の重み付き隣接行列 $\mathbf{B} = (b_{ij})_{d \times d} \in \mathbb{R}^{d \times d}$ を考えます。このとき LiNGAM とは以下の式で表されるデータ生成プロセスのことを指します。

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

ここで、 $\mathbf{e} = (e_1, \ldots, e_d)^\top \in \mathbb{R}^d$ はノイズ項であり、各 $e_i$ は非ガウスかつ平均が $0$ である確率分布に従うと仮定されます。すなわち、LiNGAM は各変数を他変数と非ガウスなノイズ項の線形和で表すモデルです。

$\mathbf{B}$ が DAG を表すことを考えると、変数は先行関係に基づいて番号付けすることができます。その番号付けを因果的順序と呼び $\mathcal{CO}$ で表し、 $\mathcal{CO(i)}$ を変数 $x_i$ に付けられた番号とします。すなわち、 $\mathcal{CO}(j) \lt \mathcal{CO}(i)$ ならば $x_j$ は $x_i$ に先行するということです。因果的順序を用いると、LiNGAM の式は以下のように読み替えることができます。

$x_i = \sum_{j~\text{s.t.}~\mathcal{CO}(j) < \mathcal{CO}(i)} b_{ij} x_j + e_i$

因果的順序の先頭になることができる変数は特に外生変数と呼ばれ、以降で説明する因果探索アルゴリズムにおいて重要な役割を果たします。

LiNGAM は識別可能性と呼ばれる実用上とても重要な性質を持っています。これは、「モデルのパラメータが異なるとき、生成されるデータは必ず異なる」という性質であり、言い換えれば「所与のデータに対してモデルのパラメータは一意に定まる」ということです。この性質により、LiNGAM の仮定を満たすデータセットにおいて、隣接行列 $\mathbf{B}$ の一意な推定が保証されています。

DirectLiNGAM

DirectLiNGAM による因果探索は (1) 因果的順序 $\mathcal{CO}$ の推定と (2) 隣接行列 $\mathbf{B}$ の推定の二つのステップからなります。 $\mathcal{CO}$ が定まれば $\mathbf{B}$ は LiNGAM の式に従ったスパース回帰で推定できるため、特に重要なのは因果的順序の推定です。そこには二つの補題と一つの系からなる理論的枠組みがあります。以下に、これら補題と系の一覧を示します。

補題 1. ([2])
$x_i$ を $x_j$ で単回帰した残差を $r_i^{(j)}$ と書く。このとき、 $x_j$ が外生変数であることと、 $x_j$ がすべての $r_i^{(j)}~(i \neq j)$ と独立なことは等価である。

補題 2. ([2])
外生変数 $x_j$ による残差を集めたベクトルを $\mathbf{r}^{(j)} := (r_i^{(j)})_{i \neq j}^\top$ とすると、 $\mathbf{r}^{(j)}$ もまた LiNGAM に従う。

系 1. ([2])
外生変数 $x_j$ に対して $\mathcal{CO}_j$ を $\mathbf{r}^{(j)}$ 上の因果的順序とすると、これは元の因果的順序 $\mathcal{CO}$ を保存している。

まず、補題 1 により外生変数を識別できることがわかるため、任意に一つの外生変数を選択します。そして、データから選択した外生変数の影響を取り除くと、補題２より、それは LiNGAM の仮定を満たすため、再帰的に補題１を適用できます。これらの操作を繰り返すと、いつかすべての変数が取り除かれることになります。ここで、系 1 により、変数を取り除いた順序は元のデータの因果的順序と等しくなっています。これが、DirectLiNGAM による因果的順序の推定の理論的枠組みです。

本論文の貢献

本論文では、DirectLiNGAM の計算速度における改善の余地を示し、理論的枠組みを一般化することで、実際により高速なアルゴリズム LayeredLiNGAM を提案しました。具体的な貢献は以下のようにまとめられます。

DirectLiNGAM における因果的順序の推定アルゴリズムについて、計算時間的な課題を理論計算量の議論と計算機実験による実測で明確化しました。
DAG の層という概念を利用して、DirectLiNGAM の理論的枠組みを一般化し LayeredLiNGAM を導出しました。また、その計算量について DirectLiNGAM と比べた優位性を明らかにしました。
計算機実験により、LayeredLiNGAM が精度劣化なく DirectLiNGAM より高速に動作することを示しました。具体的には、疎な人工グラフで最大 25 倍ほど、実データでも 5 倍ほどの高速化を達成する例がありました。

DirectLiNGAM の計算量と実際

入力されるデータ数を $n$ として、DirectLiNGAM の計算量を議論してみましょう。因果的順序の推定は、すべての変数が取り除かれるまで外生変数を一つずつ取り除いていくアルゴリズムですから、外生変数の選択という処理を $d$ 回だけ繰り返すことになります。外生変数の選択には、補題 1 より、全変数対での単回帰と独立性検定が必要です。一つの変数対に対する単回帰にかかる計算時間は $O(n)$ です。独立性検定の方法は様々ですが、一つの変数対に対する独立性検定にかかる計算時間を仮に $O(C)$ とすると $C \geq n$ です。よって、外生変数の選択にかかる計算時間は $O( (n + C) d^2 ) = O( C d^2 )$ となるため、因果的順序の推定は $O(Cd^3)$ 時間かかることになります。隣接行列の推定は LARS アルゴリズム [4] などの高速なスパース回帰アルゴリズムを活用すれば $O(nd^3)$ を達成することができます。したがって、DirectLiNGAM は全体でも $O(Cd^3)$ です。

上記の議論から、DirectLiNGAM のボトルネックは因果的順序の推定であるということが容易にわかります。ところが、独立性検定について、最大エントロピー近似という技法を用いることで $C=n$ を達成できることが明らかにされており [5]、その技法の下では DirectLiNGAM は $O(nd^3)$ で動作します。それでは、最大エントロピー近似によって DirectLiNGAM のボトルネックは解消されたと言えるのでしょうか？実は、そうではありません。以下の予備実験結果が、DirectLiNGAM のボトルネックは相変わらず因果的順序の推定であることを示しており、最大エントロピー近似におけるオーバーヘッドの存在を示唆しています。これが、因果的順序の推定における $d^3$ の項を改善するモチベーションとなります。

LayeredLiNGAM

DirectLiNGAM の計算量を削減するために、 $d$ 回行われるループ処理の回数を減らすことを考えてみます。そのためには、一回のループで複数の変数をまとめて順序付けしなければなりません。そこで、DAG は複数のノードをまとめた層に分解できるという事実を利用します。今、 $\mathcal{CO}$ に変わる新たな順序付け $\mathcal{LO}$ を考えます。 $\mathcal{LO}$ は複数の変数に対して同じ値を持つことができ、同じ値を持つ変数集合を一つの層と見做します。そして、次のような LiNGAM の式が成り立つとき、 $\mathcal{LO}$ を層化因果的順序と呼ぶことにします。

$x_i = \sum_{j~\text{s.t.}~\mathcal{LO}(j) < \mathcal{LO}(i)} b_{ij} x_j + e_i$

この式からわかる通り、層化因果的順序 $\mathcal{LO}$ は因果的順序 $\mathcal{CO}$ の一般化になっています。

本論文では、DirectLiNGAM における因果的順序の推定を層化因果的順序の推定に置き換えたアルゴリズムを提案し LayeredLiNGAM と名付けました。LayeredLiNGAM は補題 2 と系 1 を一般化した新たな理論的枠組みに基づいています。

補題 3.
$x_i$ を変数集合 $X_J = \{ x_j \mid j \in J \}$ で重回帰した残差を $r_i^J$ とする。 $X_J$ が外生変数の集合であるとき、 $\mathbf{r}^J := (r_i^J)_{i \notin J}^\top$ とすると、 $\mathbf{r}^J$ もまた LiNGAM に従う。

系 2.
外生変数の集合 $X_J$ に対して $\mathcal{LO}_J$ を $\mathbf{r}^J$ 上の層化因果的順序とすると、これは元の層化因果的順序 $\mathcal{LO}$ を保存している。

まず、DirectLiNGAM で用いた補題 1 は、外生変数を一つ選択するだけでなく、外生変数の集合 $X_J$ 、すなわち層の選択にも利用できます。そして、データから $X_J$ の影響を取り除くと、補題 3 より、それは LiNGAM の仮定を満たすため、再帰的に補題１を適用できます。これらの操作を繰り返すと、いつかすべての変数が取り除かれることになります。ここで、系 2 により、層を取り除いた順序は元のデータの層化因果的順序と等しくなっています。これが、LayeredLiNGAM による層化因果的順序の推定の理論的枠組みです。

LayeredLiNGAM の計算量はどうなっているでしょうか？DirectLiNGAM と比べたアルゴリズムの差分は、外生変数を選択するループの回数が検出した層の数になることと、外生変数によるデータの残差を重回帰で取るようになることです。各ループにおける外生変数の識別処理は DirectLiNGAM と LayeredLiNGAM で同等です。重回帰は最小二乗法により $O(nd^2 + d^3)$ 時間で計算可能です。よって、検出した層の数を $T$ として、LayeredLiNGAM による層化因果的順序の推定は $O( C T d^2 + T ( n d^2 + d^3 ) ) = O( ( C + d ) T d^2 )$ 時間かかることになります。LiNGAM の推定には回帰問題が含まれるため一般的には $n \geq d$ が望ましいことと、層数は必ず変数の数以下（ $T \leq d$ ）であることに注意してください。すると、一般的な設定の下で LayeredLiNGAM における層化因果的順序の推定の計算量は $O( C T d^2 )$ であり、DirectLiNGAM における因果的順序の推定よりも高速であることがわかります。

実験的な結果

計算機実験では、三種類の疎なランダムグラフに基づく人工データセットと、遺伝子発現と薬剤設計の二つの実データセットを用いて、LayeredLiNGAM の性能を DirectLiNGAM と Ruixuan らによる LiNGAM 推定アルゴリズム [6] と比較しました。ここでは、人工データセットに関する実験結果を示し、LayeredLiNGAM の挙動を簡単に述べます。実データセットでの実験については、論文をご参照ください。

人工データセットの生成方法は次の通りです。ランダムに DAG を生成した後、非ゼロである各 $b_{ij}$ の値を [−2.0, −0.5] ∪ [0.5, 2.0] の範囲でランダムに設定しました。その後、各ランダムノイズ $e_i$ を平均 0 および分散 1 のラプラス分布から生成し、LiNGAM の式に基づいて $n= 5000$ 個のデータをサンプリングしました。ランダムな DAG の生成方法として下記の3種類を用いました。

RG4：一定の割合で辺を張るランダムグラフであり、平均次数が4の無向グラフを生成し、ノードにランダムな順序を付けることで DAG 化しました。
BA4：Barabási–Albert モデルと呼ばれる有名なランダムグラフであり、モデルパラメータを $m=4$ として無向グラフを生成し、ノードにランダムな順序を付けることで DAG 化しました。
LA128：ノード数 $d=128$ と層数 $T \in \{ 2, 4, 8, 16, 32, 64, 128 \}$ が固定され、各層が厳密に $\frac{d}{T}$ 個のノードを持つ DAG で、各ノードは自身の直上・直下の層それぞれでランダムな 1 つのノードと接続されます。

図4が人工データセットに対する実験の結果です。RG4 および BA4 についてはノード数 $d \in \{10, 25, 50, 100, 250, 500\}$ の変化に対する振舞いを、LA128 では層数 $T \in \{ 2, 4, 8, 16, 32, 64, 128 \}$ に対する振舞いを観測しました。このとき各実験パラメータに対して 10 個のデータセットを生成し、それらに対する各手法の実行時間および精度に関する平均値と標準誤差をプロットしました。

因果的順序の推定について、LayeredLiNGAM は DirectLiNGAM と比較して RG4 と BA4 で最大 50 倍高速で、その速度は隣接行列の推定に追いつくほどになり、因果探索全体の計算時間としては最大 25 倍の高速化を達成しました。LA128 では、LayeredLiNGAM が計算量の議論通りに DAG の層数が少ないほど高速であり、 $T=d$ のときに DirectLiNGAM と同等になることを確認しました。また、LayeredLiNGAM は DirectLiNGAM と比べて全体的に精度が劣化していないことも観察できました。以上のことから、LayeredLiNGAM は LiNGAM における因果探索を DirectLiNGAM と比べて精度劣化なく高速に行えることが確認できました。

おわりに

本記事では、ECML-PKDD 2024 に採択された「線形非ガウス因果モデル LiNGAM における高速な因果探索技術」に関する研究について紹介しました。本記事で説明しきれなかった点として、補題と系の証明、LayeredLiNGAM のハイパーパラメータ、実データを用いた実験がありますが、これらについては論文をご参照ください。今後の課題として、LayeredLiNGAM の高速性を保ったまま、出力の DAG を DirectLiNGAM による DAG により近づける工夫、あるいは精度を向上させる工夫を考察することは興味深いのではないかと考えています。

参考文献

[1] Shimizu et al., "A Linear Non-Gaussian Acyclic Model for Causal Discovery", Journal of Machine Learning Research 7, Pages: 2003–2030, 2006
[2] Shimizu et al., "DirectLiNGAM: A Direct Method for Learning a Linear Non-Gaussian Structural Equation Model", Journal of Machine Learning Research 12, Pages: 1225–1248, 2011
[3] Ikeuchi et al., "Python package for causal discovery based on LiNGAM", Journal of Machine Learning Research 24, Pages: 14:1–14:8, 2023
[4] Efron et al., "Least Angle Regression", The Annals of Statistics 32(2), Pages: 407 – 499, 2004
[5] Hyvärinen et al, "Pairwise Likelihood Ratios for Estimation of Non-Gaussian Structural Equation Models", Journal of Machine Learning Research 14, Pages: 111–152, 2013
[6] Zhao et al., "Learning linear non-Gaussian directed acyclic graph with diverging number of nodes", Journal of Machine Learning Research 23, Pages: 269:1–269:34, 2021

fltech - 富士通研究所の技術ブログ

富士通研究所の研究員がさまざまなテーマで語る技術ブログ