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 \}

(1)

変数の数： $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

(2)

$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

(3)

ここで、

$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

(4)

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

X = XW + YA + U

(5)

と書ける。

識別性（Identifiability）¶

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

誤差 $u_{m,t}$ が 非ガウス（LiNGAMと同様）
誤差が 等分散ガウス かつ $W$ が DAG

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

パラメータの推定¶

基本目的関数¶

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

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

(6)

スパース性の導入¶

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

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

(7)

$\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

(8)

ここで ∘ はアダマール積を表す。このとき、

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

(9)

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

制約付き最適化問題¶

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

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

(10)

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

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

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

(11)

$\rho$ ：ペナルティ係数
$\alpha$ ：ラグランジュ乗数

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