NOTEARS算法 (Non-combinatorial Optimization via Trace Exponential and Augmented lagRangian for Structure learning)

定位: NOTEARS是一种将DAG约束转化为连续优化问题的里程碑式算法,通过矩阵指数的迹作为DAGness度量,实现无需组合搜索的因果发现。

前置知识: 矩阵分析(矩阵指数、迹)、优化理论(增广拉格朗日方法)、神经网络基础、因果发现基础(PC/GES)

核心直觉

核心直觉: 有向无环图(DAG)的核心约束是”无环性”,这一约束在邻接矩阵上是离散的(排列组合)。NOTEARS的核心发现是:矩阵指数的迹可以作为一个连续可微的DAGness度量,使得梯度下降法可直接应用于DAG结构学习。

传统方法将DAG学习视为离散搜索问题(如贪婪搜索),复杂度为。NOTEARS通过连续松弛,将组合约束转化为平滑约束,使得经典优化算法可直接使用。

数学推导

1. DAGness约束的构造

设为加权邻接矩阵(无自环),定义矩阵指数:

其中表示Hadamard积(元素-wise乘法)。

DAGness函数:

其中为节点数。当且仅当对应一个DAG。

性质1: 连续可微性 是的连续可微函数,可计算梯度。

性质2: DAGness等价性 若对应DAG,则。若不对应DAG,则。

性质3: 直观解释

对角元素的第个对角元素为:

这是从节点出发,经步回到节点的所有路径强度之和。

度量了所有长度为的环的强度。包含了所有长度环的贡献。若存在环(无论长度),迹必大于。

2. 连续优化框架

NOTEARS将结构学习形式化为:

其中:

: 拟合损失(如MSE)
: L2正则化
: DAG约束

3. 增广拉格朗日方法

使用增广拉格朗日处理等式约束:

其中为惩罚参数,为拉格朗日乘子。

优化步骤(ALM):

初始化 W^0, α^0, ρ^0
while not converged:
    # 步骤1: 固定(α, ρ), 优化 W
    W^{k+1} = argmin_W ℒ_ρ(W, α^k)

    # 步骤2: 更新乘子
    α^{k+1} = α^k + ρ * h(W^{k+1})

    # 步骤3: 可选增大惩罚
    ρ = min(ρ * 1.1, ρ_max)

4. NOTEARS-MLP: 非线性扩展

对于非线性结构,使用多层感知器(MLP):

其中为神经网络函数。

优化目标:

指示哪些父节点被使用(通过mask实现)。

5. 梯度计算

的梯度:

推导:

其中为第元素为1的矩阵。

训练与估计

优化细节

初始化: 使用弱随机初始化,避免初始环

学习率: 起始学习率,使用Adam优化器

收敛判断:

(如)
或连续几步下降不足

计算复杂度

前向传播: 其中为隐层维度
梯度计算: (矩阵指数计算),实际可通过截断展开近似
空间复杂度:

参数估计

在线性情况下,可解释为偏回归系数矩阵:

推理/干预/反事实

结构解释

学习到的矩阵可直接解释因果效应:

对于线性模型,是给定其他父节点时,对的直接影响。

干预计算

给定,do演算:

优点与局限

优点

连续优化: 无组合搜索,利用GPU加速
可微约束: DAG约束连续可微,支持梯度下降
理论保证: 在无限样本下收敛到正确DAG
非线性扩展: NOTEARS-MLP处理非线性因果关系

局限

局部最优: 连续优化可能陷入局部最优
超参数敏感: , 等需要调优
矩阵规模: 存储,计算,对大图有挑战
稀疏性不保证: 需要额外正则化促进稀疏

与其他笔记的连接

前置: GES算法 → NOTEARS(从离散到连续)
延伸: DAG约束优化 → GraN-DAG, NOTEARSs
对比: 约束式/评分式vs连续优化见”约束式与评分式方法”
应用: 时序因果图使用类似思想扩展

可复现性说明

关键参数

参数	建议值	说明
	-	L2正则化强度
	1.0	增广拉格朗日惩罚参数
	0	初始拉格朗日乘子
		最大惩罚值
		收敛阈值
max_iter	10000	最大迭代次数

PyTorch实现示例

import torch
import numpy as np
 
def h(W):
    """DAGness constraint: tr(e^{W◦W}) - n"""
    M = W * W  # Hadamard product
    E = torch.matrix_exp(M)  # Matrix exponential
    h_val = torch.trace(E) - W.shape[0]
    return h_val
 
def compute_grad_h(W):
    """Gradient of h(W) = 2 * (e^{W◦W} ◦ W)"""
    M = W * W
    E = torch.matrix_exp(M)
    return 2 * (E * W)
 
def notears_algo(X, lambda1=0.1, rho=1.0, alpha=0.0, max_iter=100):
    n, d = X.shape
    W = torch.randn(d, d, requires_grad=True)
    optimizer = torch.optim.Adam([W], lr=0.01)
 
    for iteration in range(max_iter):
        optimizer.zero_grad()
 
        # Fitting loss (least squares)
        loss_fit = torch.norm(X @ W - X, p='fro') ** 2 / (2 * n)
 
        # L2 regularization
        loss_reg = lambda1 * torch.norm(W, p='fro') ** 2 / 2
 
        # Augmented Lagrangian
        h_val = h(W)
        loss_al = rho * h_val ** 2 / 2 + alpha * h_val
 
        loss = loss_fit + loss_reg + loss_al
        loss.backward()
 
        optimizer.step()
 
        # Update multiplier
        alpha += rho * h_val.item()
 
        if abs(h_val.item()) < 1e-6:
            break
 
    return W.detach().numpy()

章节总结

NOTEARS通过将DAG约束连续化,是因果发现的里程碑式工作
矩阵指数的迹度量环的存在:有环则,无环则
连续可微,允许使用梯度下降优化DAG结构
增广拉格朗日方法处理等式约束,迭代更新乘子和惩罚
NOTEARS-MLP通过mask机制将DAG约束应用于神经网络,处理非线性因果关系
优化复杂度为(矩阵指数),空间为
线性情况下可解释为直接因果效应矩阵
存在局部最优问题,超参数()需要仔细调优
是后续GraN-DAG、DAG-GNN等方法的基础
与传统组合方法(PC/GES)相比,NOTEARS在中等规模问题()上效率更高

关键词: NOTEARS, DAG约束, 矩阵指数, 连续优化, 增广拉格朗日, NOTEARS-MLP, 结构学习

Huajishe Notes

Explorer

1-NOTEARS算法