DAG约束优化 (DAG Constraint Optimization)

定位: DAG约束优化研究如何将离散的有向无环图约束转化为连续可优化的形式,是NOTEARS系列方法的核心技术基础,并涵盖多种DAGness函数的设计与分析。

前置知识: NOTEARS算法、矩阵分析、梯度优化方法

核心直觉

核心直觉: DAG约束是因果结构学习的核心挑战。不同的DAGness函数在可微性、计算复杂度、优化Landscape等方面各有优劣。理解这些 trade-offs 对于设计高效的因果发现算法至关重要。

从离散搜索到连续优化的范式转变,本质上是用”软”约束替代”硬”约束。不同的DAGness函数提供了不同程度的松弛:有些精确但计算困难,有些近似但高效。

数学推导

1. DAGness函数的定义

DAGness: 度量一个加权矩阵是否对应DAG的函数,满足:

对 应

性质要求:

对所有
无环
连续可微(或至少连续)
优化友好

2. 指数族DAG约束 (NOTEARS)

NOTEARS DAGness:

特点:

精确: DAG
连续可微
计算复杂度
对权重幅度敏感: 大权重即使无环也可能使

展开形式:

只需计算矩阵幂级数的前项即可。

3. 谱约束 (Spectral)

基于特征值的约束:

其中为的特征值。

性质:

无环所有
计算复杂度(特征分解)
比指数约束更紧

4. 基于幂的约束

k-阶约束:

含义: 长度为的环之和应小于1。

特点:

只需计算矩阵幂
比更稳定
但不完备: 不保证无环

5. NOTEARS变体比较

变体	DAGness函数	可微性	稳定性
NOTEARS		是	中等
NOTEARS-MLP	同上	是	中等
NOTEARSs		是	更好
DAG-GNN		是	近似

6. GraN-DAG: 基于梯度的神经因果发现

GraN-DAG使用神经网络建模非线性因果:

损失函数:

DAG约束: 同NOTEARS,使用

关键创新: 将结构学习()和参数学习()联合优化

7. DAG-GNN

DAG-GNN使用图神经网络架构:

其中为学到的邻接矩阵(满足DAGness)。

目标:

使用重参数化技巧:确保无环。

训练与估计

优化策略

1. 增广拉格朗日 (NOTEARS原始方法):

见NOTEARS笔记。

2. 逐步松弛 (Successive Regression):

其中为无环矩阵凸包。

3. 梯度下降 + 投影:

在每步梯度下降后,投影到DAG空间:

超参数调优

参数	影响	典型值
(L2正则)	控制权重幅度	-
(ALM惩罚)	约束违反惩罚	1.0 - 10
学习率	收敛速度	-
最大迭代	时间限制	1000 - 10000

收敛性分析

NOTEARS收敛条件:

损失函数是-光滑的
增广拉格朗日函数在足够大时是凸的
迭代更新保证

推理/干预/反事实

从学到的进行因果推理

对于线性模型:

总因果效应通过路径分析计算。

do演算应用

给定DAG :

优点与局限

优点

可扩展性: 连续优化利用GPU,处理中等规模问题()
全局搜索: 避免贪婪搜索的局部最优
端到端学习: 结构学习和参数学习联合
理论框架: 有优化理论支撑

局限

局部最优: 非凸优化仍可能陷入局部最优
规模限制: 存储,计算限制了节点数
不精确松弛: 近似约束可能引入误差
稀疏性不保证: 需要额外正则化

与其他笔记的连接

前置: NOTEARS → 本笔记深入分析
对比: DAG约束 vs 组合搜索(GES)见”约束式与评分式方法”
评测: 因果发现评测指标验证约束优化方法性能
时间序列: 时序扩展见”时序因果图”和”动态因果发现方法”

可复现性说明

不同DAG约束实现对比

import torch
import numpy as np
 
# NOTEARS exponential DAGness
def h_notears(W):
    M = W * W
    E = torch.matrix_exp(M)
    return torch.trace(E) - W.shape[0]
 
# Spectral DAGness
def h_spectral(W):
    eigenvalues = torch.linalg.eigvals(W)
    return torch.sum(torch.abs(eigenvalues))
 
# k-order DAGness (truncated)
def h_k_order(W, k=3):
    M = W * W
    power = torch.eye(W.shape[0])
    trace_sum = W.shape[0]  # tr(M^0) = n
    for i in range(1, k+1):
        power = power @ M
        trace_sum += torch.trace(power)
    return trace_sum - W.shape[0]
 
# Gradient of NOTEARS DAGness
def grad_h_notears(W):
    M = W * W
    E = torch.matrix_exp(M)
    return 2 * (E * W)

优化器选择

优化器	优点	缺点
Adam	自适应学习率,快收敛	可能不收敛
SGD	稳定	慢收敛
L-BFGS	二阶信息,精最优	内存大

章节总结

DAG约束优化将离散的”无环”约束转化为连续可微函数,是NOTEARS系列方法的核心
主要DAGness函数: 指数族()、谱约束(特征值)、幂约束()
指数族约束精确但计算,对大权重敏感
NOTEARSs通过截断展开将复杂度降到,更稳定
GraN-DAG将DAG约束与神经网络结合,处理非线性因果关系
增广拉格朗日是标准求解方法,迭代更新乘子和惩罚参数
连续优化方法相比组合搜索(GES)有更好的规模化潜力
局部最优是非凸优化的主要挑战,可通过多次随机初始化缓解
计算复杂度限制了该方法应用于节点数<200的问题
稀疏性促进可通过L1正则化或procrustes投影实现

关键词: DAG约束, NOTEARS变体, 谱约束, 指数约束, GraN-DAG, DAG-GNN, 增广拉格朗日, 连续优化

Huajishe Notes

Explorer

2-DAG约束优化