DAGs with NO TEARS: Continuous Optimization for Structure Learning
DAGs with NO TEARS: Continuous Optimization for Structure Learning
目录
有向图可以用邻接矩阵\(A \in \{0, 1\}^{d \times d}\)来表示, 其中\(A_{ij} = 1\) 表示 node \(i\) 指向 node \(j\). 进一步的, 我们想要表示有向无环图(DAG), 则\(A\)需要满足额外的性质, 保证无环.
现在的问题是, 有一堆观测数据\(X \in \mathbb{R}^{n \times d}\), 如何通过这些数据推测其(特征之间的)关系, 即对应的\(A\).
首先, 假设特征之间满足一个线性关系:
\[X_j = w_j^T X + z_j,
\]
其中
\[W = [w_1|w_2|\cdots|w_d] \in \mathbb{R}^{d},
\]
\(z\)为随机的噪声.
通过\(W\)可以推出相应的\(A=\mathcal{A}(W)\), 即
\[W_{ij} \not = 0 \Leftrightarrow A_{ij} = 1, W_{ij} =0 \Leftrightarrow A_{ij} = 0.
\]
故我们目标通常是:
\[\min_{W} \quad \ell(W;X) = \frac{1}{2n}\|X - XW\|_F^2, \\
\mathrm{s.t.} \quad \mathcal{A}(W) \in \mathbb{D},
\]
其中\(\mathbb{D}\)表示有向无环图.
进一步地, 因为我们希望\(W\)是一个系数的矩阵(否则断然不是DAG), 故
\[F(W;X) = \ell(W;X) + \lambda \|W\|_1,
\]
并
\[\min_W \quad F(W;X) \\
\mathrm{s.t.} \quad \mathcal{A}(W) \in \mathbb{D}.
\]
显然现在的关键是如何处理\(\mathcal{A}(W) \in \mathbb{D}\)这个条件, 以前的方法通常需要复杂的运算, 本文提出一种等价的条件
\[h(W) = 0,
\]
满足
- \(h(W)= 0\)当且仅当\(\mathcal{A}(W) \in \mathbb{D}\);
- \(h(W)\)越小, 说明\(\mathcal{A}(W)\)越接近无环图;
- \(h(W)\)是一个光滑函数;
- \(h(W)\)便于求导.
显然1是期望的, 2可以用于判断所得的\(W\)的优劣, 3, 4便于我们用数值方法求解.
等价条件的推导
\(\mathrm{tr}(I-W)^{-1} = d\)
Proposition 1: 假设\(W \in \mathbb{R}_+^{d \times d}\) 且 \(\|W\| < 1\), 则\(\mathcal{A}(W)\)能够表示有向无环图当且仅当
\[\mathrm{tr}(I - W)^{-1} = d.
\]
proof:
\(A = \mathcal{A}(W)\)能够表示有向无环图, 当且仅当
\[\mathrm{tr}(A^k) = 0 \Leftrightarrow \mathrm{tr} (W^k) = 0, \forall\: k=1,\cdots
\]
\(\Rightarrow\)
由于\(\|W\| < 1\)(最大奇异值小于1), 故
\[\mathrm{tr}(I-W)^{-1} = \mathrm{tr}(\sum_{k=0} W^k) = \mathrm{tr}(I) = d.
\]
\(\Leftarrow\)
\(\mathrm{tr}(W^k) \ge 0\), 故
\[\mathrm{tr}(I-W)^{-1} = d
\]
当且仅当
\[\mathrm{tr}(W^k) = 0.
\]
注: \(\|W\| < 1\)这个条件并不容易满足.
\(\mathrm{tr}(e^W)=d\)
注: \(e^A = I + \sum_{k=1} \frac{A^k}{k!}\).
Proposition 2: 假设\(W \in \mathbb{R}_+^{d \times d}\), 则\(\mathcal{A}(W)\)能够表示有向无环图当且仅当
\[\mathrm{tr}(e^W) = d.
\]
proof:
证明是类似的.
注: 此时对\(W\)的最大奇异值没有要求.
\(\mathrm{tr}(W^k) = 0\)
这部分的证明可能应该归属于DAG-GNN.
Proposition 3: 假设\(W \in \mathbb{R}_+^{d \times d}\) , 则\(\mathcal{A}(W)\)能够表示有向无环图当且仅当
\[\mathrm{tr}(W^k) = 0, \: k=1,2,\cdots, d.
\]
proof:
\(\Rightarrow\)是显然的, 证明\(\Rightarrow\)只需说明
\[\mathrm{tr}(W^k)=0, \: k=1,2,\cdots, d \Rightarrow \mathrm{tr}(W^k), \: k\ge 1.
\]
假设\(W\)的特征多项式为\(p(\lambda) = \sum_{k=0}^d \beta_k \lambda^k, \beta_d=1\), 则有
\[p(W) = \sum_{k=0}^d \beta_k W^k = 0.
\]
进一步有
\[W^{d} = -\sum_{k=0}^{d-1} \beta_k W^k \Rightarrow W^{d+1} = -\sum_{k=1}^d \beta_k W^{k+1} \Rightarrow \mathrm{tr}(W^{d+1}) = -\sum_{k=1}^d \beta_k \mathrm{tr}(W^{k+1}) = 0.
\]
由归纳假设可知结论成立.
Corollary 1: 假设\(W \in \mathbb{R}_+^{d \times d}\) , 则\(\mathcal{A}(W)\)能够表示有向无环图当且仅当
\[\mathrm{tr}(I+W)^d=d.
\]
\(\mathrm{tr}(e^{W \circ W}) =d\)
注: \(\circ\) 表示哈达玛积, 即对应元素相乘.
上面依然要求\(W\)各元素大于0, 一个好的办法是:
Theorem 1: 一个矩阵\(W \in \mathbb{R}^{d \times d}\), 则\(\mathcal{A}(W)\) 能表示有向无环图当且仅当
\[\mathrm{tr}(e^{W \circ W}) =d.
\]
proof:
\(\mathcal{A}(W)=\mathcal{A}(W \circ W)\).
\(\mathrm{tr}(I + W \circ W)^d =d\)
Theorem 2: 一个矩阵\(W \in \mathbb{R}^{d \times d}\), 则\(\mathcal{A}(W)\) 能表示有向无环图当且仅当
\[\mathrm{tr}(I + W \circ W)^d =d.
\]
注: \(W \circ W\)前面加个系数也是没关系的.
性质的推导
故, 此时我们只需设置
\[h(W) = \mathrm{tr}(e^{W\circ W}) - d
\]
显然满足1,2,3, 接下来我们推导其梯度
\[\begin{array}{ll}
\mathrm{d}h(W)
&= \mathrm{d}\: \mathrm{tr} (e^{W\circ W}) \\
&= \mathrm{tr} (\mathrm{d}e^{W\circ W}) \\
&= \mathrm{tr} (\mathrm{d}\sum_{k=1} \frac{M^k}{k!}) \\
&=\sum_{k=1} \mathrm{tr} ( \frac{\mathrm{d}M^k}{k!}) \\
&=\sum_{k=0} \mathrm{tr} ( \frac{M^k \mathrm{d}M}{k!}) \\
&= \mathrm{tr}(e^{W\circ W} \cdot \mathrm{d}(W\circ W)) \\
&= \mathrm{tr}(e^{W\circ W} \cdot (2W \circ \mathrm{d} W)) \\
&= \mathrm{tr}(e^{W\circ W} \circ 2W^T \cdot \mathrm{d} W) \\
\end{array}
\]
故
\[\nabla h(W) = (e^{W\circ W})^T \circ W.
\]
注: 其中\(M =W \circ W\).
求解
利用augmented Lagrangian转换为(这一块不是很懂, 但只是数值求解的东西, 不影响理解)
\[\min_W \max_{\alpha}\quad \ell (W;X) +\lambda \|W\|_1 + \frac{\rho}{2}|h(W)|^2 + \alpha h(W),
\]
具体求解算法如下:
手机扫一扫
移动阅读更方便
你可能感兴趣的文章