DYNOTEARS

DYNOTEARS#

DYNOTEARSはNOTEARSを動的（時系列要素を加味）にしたもの。

Pamfil et al. (2020) Dynotears: Structure learning from time-series data (PMLR)

モデル#

Notation#

データセットを次のように表す

\[ \{ x_{m,t} \in \mathbb{R}^d \mid m = 1,\dots,M,\; t = 0,\dots,T \} \]

  • 変数の数：\(d\)

  • 独立な時系列の本数：\(M\)

  • 各時系列の長さ：\(T+1\)

モデル（SVAR）#

同時因果（intra-slice）と時間遅れ因果（inter-slice）を同時に扱うため、 構造ベクトル自己回帰（SVAR）型SEM モデルを使う

\[ x_{m,t}^\top = x_{m,t}^\top W + x_{m,t-1}^\top A_1 + \cdots + x_{m,t-p}^\top A_p + u_{m,t}^\top \]

  • \(W \in \mathbb{R}^{d \times d}\)：同時（intra-slice）因果行列

  • \(A_k \in \mathbb{R}^{d \times d}\)：\(k\) 期遅れ（inter-slice）因果行列

  • \(p\)：自己回帰次数

  • \(u_{m,t}\)：平均0の独立誤差項

同時因果行列 \(W\) は DAG（非巡回） であると仮定する。一方、\(A_k\) は時間方向を持つため巡回制約を必要としない。

行列表現#

すべての時系列をまとめると、モデルは次のように表される：

\[ X = XW + Y_1 A_1 + \cdots + Y_p A_p + U \]

ここで、

  • \(X \in \mathbb{R}^{n \times d}\)：観測データ行列

  • \(Y_k\)：\(k\) 期ラグを取ったデータ行列

  • \(n = M (T + 1 - p)\)：有効サンプルサイズ

さらに

\[ Y = [Y_1 \mid \cdots \mid Y_p], \quad A = [A_1^\top \mid \cdots \mid A_p^\top]^\top \]

と定義すると、モデルは簡潔に

\[ X = XW + YA + U \]

と書ける。

識別性（Identifiability）#

以下のいずれかが成り立つとき、同時因果行列 \(W\) は識別可能である

  1. 誤差 \(u_{m,t}\) が 非ガウス（LiNGAMと同様）

  2. 誤差が 等分散ガウス かつ \(W\) が DAG

DYNOTEARSはいずれかの条件が成立すると仮定する。

パラメータの推定#

基本目的関数#

観測データ \(X, Y\) が与えられたとき、\(W, A\) を推定するために以下の二乗誤差損失を最小化する：

\[ \ell(W, A) = \frac{1}{2n} \lVert X - XW - YA \rVert_F^2 \]

スパース性の導入#

高次元設定を考慮し、\(W, A\) に \(\ell_1\) 正則化を加える：

\[ f(W, A) = \ell(W, A) + \lambda_W \lVert W \rVert_1 + \lambda_A \lVert A \rVert_1 \]

  • \(\lambda_W, \lambda_A\)：正則化係数

  • \(\lVert \cdot \rVert_1\)：要素ごとの \(\ell_1\) ノルム

非巡回性制約#

全体のネットワークが非巡回であるためには、同時因果行列 \(W\) のみが DAG であれば十分である。

NOTEARSを提案したZheng et al. (2018) により、次の関数を用いて DAG 制約を滑らかに表現できることが明らかにされている：

\[ h(W) = \operatorname{tr}\left( e^{W \circ W} \right) - d \]

ここで \(\circ\) はアダマール積を表す。このとき、

\[ h(W) = 0 \quad \iff \quad W \text{ は DAG} \]

が成り立つ。そのため、制約付き最適化問題としてパラメータ推定を行う。

制約付き最適化問題#

最終的な最適化問題は次のように定式化される：

\[ \min_{W, A} f(W, A) \quad \text{subject to} \quad h(W) = 0 \]

解法（拡張ラグランジュ法）#

制約付き問題を、以下の拡張ラグランジュ関数を用いて解く：

\[ F(W, A) = f(W, A) + \frac{\rho}{2} h(W)^2 + \alpha h(W) \]

  • \(\rho\)：ペナルティ係数

  • \(\alpha\)：ラグランジュ乗数

これにより問題は 滑らかな非線形最適化問題 となり、 L-BFGS-B などの標準的な数値最適化手法で解くことができる。

Contents