# NO TEARS DAGs with NO TEARS(Non-combinatoric Optimization via Trace Exponential Augmented lagRangian Structure learning、Zheng, Aragam, Ravikumar, Xing, 2018 [267])は、[[@2022__CSUR__D'ya Like DAGs - A Survey on Structure Learning and Causal Discovery - Chapter 5 Continuous Optimization Based Approaches]] §5.2 において「組合せ的なグラフ探索問題を連続最適化問題として再定式化した最初の手法と一般に見なされる(generally considered as the first)」と評される。同章が扱う継続最適化ベース手法群(30件)のほぼ全てが、この手法の非巡回性制約を直接拡張・改良・置換する形で系譜づけられる。(Source: [[@2022__CSUR__D'ya Like DAGs - A Survey on Structure Learning and Causal Discovery - Chapter 5 Continuous Optimization Based Approaches]] §5.2) ## 定式化 隣接行列 $A$ が定める非巡回性を、次の連続な等式制約 $h(A)=0$ に置き換える: $h(A) = tr(e^{A\odot A}) - d = 0$ ここで $tr$ はトレース演算子、$\odot$ はアダマール積、$d$ はグラフの頂点数である。この制約と、スコア関数 $S(A)$ の最小化を組み合わせた等式制約付きプログラム(Equality Constrained Program)として構造発見問題を定式化する。想定する構造方程式モデルは線形($X_j = a_j^T X + U_j$、ノイズはガウス性を仮定しない)であり、最小二乗損失に $l_1$ ペナルティ(疎性)を加えた目的関数を拡張ラグランジアン法(L-BFGS)で最適化する。合成データに加え、Sachs et al. (2005) のタンパク質・リン脂質データセットでも評価されている。(Source: [[@2022__CSUR__D'ya Like DAGs - A Survey on Structure Learning and Causal Discovery - Chapter 5 Continuous Optimization Based Approaches]] §5.2) ## 既知の限界 - 行列指数関数 $tr(e^{A\odot A})$ の計算に $O(d^3)$ を要する。 - $h(A)$ は実際には小さいが非ゼロになりやすく、事後的な辺の閾値処理が必要になる。 - 定式化された最適化問題自体は最適解を保証しない(ただし実験では準最適な結果を示す)。 ## 後続手法による拡張・批判の系譜 - **計算量削減**: NO BEARS(2019)がスペクトル半径近似で $O(d^2)$ へ、LEAST(2020)がスペクトル半径の上界をさらに反復近似し概ね $O(d)$ 相当まで削減(5〜15倍高速化、160,000頂点まで実証)。 - **制約の妥当性への批判**: NO FEARS(2020)が、NO TEARS の制約に対する拡張ラグランジアン最適化が実行可能解 $h(A)=0$ へ収束する保証がないことを理論的に示し、$A\odot A$ ではなく絶対値 $\lvert A\rvert$ に基づく制約へ変更。 - **制約の必要性自体への批判**: GOLEM(2020)が、線形ガウス・忠実性の仮定下では漸近的にハードな非巡回性制約自体が不要であり、尤度ベースのスコア関数とソフトなペナルティで十分であることを示した。 - **非線形化**: DAG-GNN(2019、式13)・GAE(2019、式8と同一の制約を非線形グラフオートエンコーダへ適用)・GranDAG(2020、式19)・CausalVAE(2020、式21)がいずれも NO TEARS の制約を直接継承・変形して非線形/生成モデルへ拡張。 - **識別可能性の欠如という指摘**: MaskedNN(2020)は NO TEARS → DAG-GNN → GAE → GranDAG という系譜を振り返り、いずれも識別可能性の詳細な議論を欠くと明示的に指摘した。 (Source: [[@2022__CSUR__D'ya Like DAGs - A Survey on Structure Learning and Causal Discovery - Chapter 5 Continuous Optimization Based Approaches]] §5.2, §5.9, §5.6, §5.7, §5.12, §5.13, §5.23, §5.25, §5.24) ## 関連 - [[@2022__CSUR__D'ya Like DAGs - A Survey on Structure Learning and Causal Discovery - Chapter 5 Continuous Optimization Based Approaches]] — 本手法を起点とする継続最適化ベース手法群の系譜を整理した章 - [[因果発見]] — 因果発見全体の横断 concept。非巡回性制約の連続緩和という転換の中心事例 - [[D'ya like DAGs]] — サーベイ全体のハブ entity