DAG の構造学習を連続最適化問題に落とし込んで解く NO TEARS アルゴリズム - Qiita

NO TEARS アルゴリズムとは NO TEARS はデータから有向非巡回グラフ（Directed Acyclic Graph; DAG）を推定するためのアルゴリズムです。因果推論ライブラリ CausalNex の中で使われています。 $d$ 個の変数間の関係を知るために DAG を推定しようとすると、$d$ に対して計算量が急増化することは容易に想像できます。実際、DAG 学習問題は素直に取り組むと NP 困難となります。これを解消するために、NO TEARS アルゴリズムでは「非巡回」という条件を滑らかな関数で表現し、DAG の学習を連続最適化問題に落とし込みます。つまり、重み $W \in M_d\left(\mathbb{R}\right)$ のグラフ $G\left(W\right)$ があり得る DAG の集合 $\mathbb{D}$ に含まれているかという条件のもとでの最

[sh19910711]

"NO TEARS: データから有向非巡回グラフ（DAG）を推定するためのアルゴリズム / d 個の変数間の関係を知るために DAG を推定しようとすると、d に対して計算量が急増化する / 「非巡回」という条件を滑らかな関数で表現"