GraN-DAG：梯度搜索因果发现

可视化演示

展示四种测试覆盖率标准的分析过程：语句覆盖、分支覆盖、路径覆盖和MC/DC覆盖。切换标准查看代码行覆盖差异。

因果发现基础

林夏站在数据局的玻璃墙前，盯着满墙的数据曲线发愁。她发现“冰淇淋销量”和“溺水人数”高度相关——曲线几乎同步起伏。可稍有常识的人都明白，冰淇淋并不会把人推进水里，它们之所以同步，是因为背后有“夏天”这个隐形的推手。林夏意识到，如果只是把相关的曲线连起来，画出来的根本不是“影响地图”，而是一张“共舞舞伴名单”。因果发现要回答的，正是“谁真正影响了谁”这个更深的问题。

在数学世界里，林夏需要的工具叫结构化因果模型（SCM）。它假设每个变量都是由它的直接原因（父节点）加上一些随机扰动生成的。比如“教育投入”之所以高，可能是“GDP增长”这个父变量加上一些政策噪声共同作用的结果。因果发现的任务，就是根据观测数据反推出每个变量的父节点集合——也就是反画出这幅影响地图的骨架。

$$\displaystyle x_i = f_i(\mathrm{Pa}_i, \varepsilon_i)$$

1. 变量 $x_i$：表示第 $i$ 个变量的观测值，比如城市GDP、教育投入这些数据列。

$$\displaystyle x_i$$

2. 父节点集合 $\mathrm{Pa}_i$：表示直接影响 $x_i$ 的变量集合，是因果图上的“上游箭头来源”。

$$\displaystyle \mathrm{Pa}_i$$

3. 生成机制 $f_i$：描述父节点如何塑造 $x_i$，可以是线性函数，也可以是神经网络表达的非线性函数。

$$\displaystyle f_i(\cdot)$$

4. 独立噪声 $\varepsilon_i$：表示除父节点外其他随机因素的扰动，通常假设与其余变量独立。

$$\displaystyle \varepsilon_i$$

林夏看着这个公式，心里踏实了许多：原来画影响地图的第一步，是先明确“每个区域是被哪些上游区域塑造的”。只有把这层结构写清楚，后面用梯度搜索优化时，才知道该往哪个方向改线。

DAG与无环性

林夏的师父留下一条铁律：影响地图上绝对禁止画圈。如果A影响B、B又影响A，那“谁先存在”就变成了鸡生蛋、蛋生鸡的悖论，信息在圈里无限循环，任何一个变量的“原因”都说不清楚。这种带圈的图在因果世界里不仅荒谬，而且会让一切基于因果的预测和干预推算全部失效。因此，一幅合法的因果地图必须是有向无环图（DAG）——边有方向、图中无环。

但难题来了：梯度搜索喜欢的是光滑连续的数学对象，而“有没有环”是一个离散的、组合爆炸式的判定。总不能每优化一步都去遍历检查一万个可能的环吧？GraN-DAG借用了NOTEARS系列方法的智慧，把“图是否无环”写成一条光滑的数学约束：只要这个函数值等于零，图就一定是DAG；大于零，就说明存在环的“成分”。

$$\displaystyle h(A) = \mathrm{tr}(e^{A \circ A}) - d$$

1. 邻接矩阵 $A$：矩阵第 $i$ 行第 $j$ 列的元素 $A_{ij}$ 表示“变量 $i$ 到变量 $j$ 的因果边强度”，是整幅地图的数字化表达。

$$\displaystyle A$$

2. 逐元素平方 $A \circ A$：把每个元素平方，确保环的检测只依赖边强度的非负大小，不因正负抵消而漏判。

$$\displaystyle A \circ A$$

3. 矩阵指数 $e^{A \circ A}$：矩阵的泰勒级数展开，它能把图中所有长度的路径信息“叠加”起来——路径越长，贡献按阶乘衰减。

$$\displaystyle e^{A \circ A} = \sum_{k=0}^{\infty}\frac{(A \circ A)^k}{k!}$$

4. 迹 $\mathrm{tr}$：取矩阵主对角线之和。对角线上第 $j$ 个元素恰好衡量了“从 $j$ 出发走一圈又回到 $j$”的闭环总量。

$$\displaystyle \mathrm{tr}(e^{A \circ A})$$

5. 减去变量数 $d$：因为单位矩阵 $I$ 的迹就是 $d$，减去它之后，$h(A)$ 在无环时精确归零。

$$\displaystyle h(A) = \mathrm{tr}(e^{A \circ A}) - d$$

有了这条光滑的“铁律翻译”，林夏的魔法铅笔就懂得在画线时自动避开圆圈——哪条线想偷偷构成闭环，无环惩罚项就会把它往淡里拽。

连续化设计

如果让林夏直接用“画/不画”来决定每一条线，她有 $2^{d^2}$ 种选择——变量稍微多一点，这个数字就比宇宙中的原子还大，根本没法系统地搜索。更麻烦的是，“画或不画”是一个离散的跳变：要么有边，要么没边，中间没有过渡，也就没有“坡度”可言。而梯度搜索这种“顺坡走”的技法，最怕的就是没有坡。

魔法铅笔的聪明之处，在于它把“画/不画”的二元抉择，软化成了“线画多浓”的连续调节。每一条候选边不再是存在或不存在两种状态，而是有一个从0到1之间的连续浓度值。这个浓度值可以理解为“这条边目前的可信度权重”——0表示肯定不画，1表示肯定要画，0.6表示“有点想画但还拿不准”。这种设计在深度学习中有一个形象的名字：软掩码（soft mask）。它相当于把整个图结构变成了一块处处可微的调色板，梯度信号可以在每一条线上自由流淌。

$$\displaystyle A_{ij} = \sigma(s_{ij})$$

1. 原始分数 $s_{ij}$：神经网络为候选边 $i \to j$ 输出的一个实数打分，可以是正数也可以是负数，代表“这条边应该存在的倾向”。

$$\displaystyle s_{ij}$$

2. 平滑映射 $\sigma$：Sigmoid 函数，将任意实数平滑地压缩到 $(0,1)$ 区间，且处处可导——这是梯度能够穿过的关键。

$$\displaystyle \sigma(s_{ij}) = \frac{1}{1 + e^{-s_{ij}}}$$

3. 连续邻接权重 $A_{ij}$：松弛后的边强度，取值接近1表示“这条边基本确定”，接近0表示“这条边基本可以擦掉”。

$$\displaystyle A_{ij} \in (0,1)$$

林夏恍然大悟：原来魔法铅笔的笔触不是非黑即白的，而是能画出无数种浓淡不同的虚线。正是这种“灰度空间”，让整个因果地图变成了一张可以被优化算法反复打磨的画布。

梯度搜索机制

有了连续这块画布，林夏的魔法铅笔开始了它的“顺坡走”旅程。想象一位蒙眼登山者站在山坡上，他看不见全貌，但能通过脚下的坡度感知哪个方向是下坡。他只需沿着最陡的下坡方向迈一步，再感知、再迈步，就能一步步走到谷底。梯度搜索就是这个原理：每一步都计算“当前参数往哪个方向调整，能让损失下降得最快”，然后朝那个方向迈出小小的一步。

在GraN-DAG中，损失函数由两部分组成。第一部分是数据拟合损失——预测值和真实观测值差多少；第二部分是无环惩罚——图里还残留多少“环的成分”。两者相加，就像给登山者加了一个双重目标：既要走到“拟合得好”的谷底，又要避开“有环”的禁区。每一步迭代，算法都沿着总损失的负梯度方向更新所有边的浓度值，环的边被惩罚项持续推淡，真正影响数据的边则被拟合项持续加深。

$$\displaystyle L(A, \theta) = \frac{1}{n}\sum_{i=1}^{n}\lVert x_i - g_{\theta}(x_i, A)\rVert_2^2 + \lambda h(A)$$

1. 总损失 $L$：衡量“这幅画好不好”的分数，越小越好，是梯度搜索的优化目标。

$$\displaystyle L(A, \theta)$$

2. 平均拟合项：对所有 $n$ 个样本求平均，衡量预测与真实值的二范数平方距离，代表地图对数据的解释力。

$$\displaystyle \frac{1}{n}\sum_{i=1}^{n}\lVert x_i - \hat{x}_i\rVert_2^2$$

3. 神经网络预测 $g_\theta(x_i, A)$：以样本 $x_i$ 和当前邻接矩阵 $A$ 为输入，输出对每个变量的预测值。$g_\theta$ 由神经网络参数 $\theta$ 刻画的非线性函数。

$$\displaystyle g_{\theta}(x_i, A)$$

4. 无环惩罚 $\lambda h(A)$：$\lambda$ 控制“避免闭环”这一铁律的严格程度，$\lambda$ 越大，算法越不敢画出环来。

$$\displaystyle \lambda h(A)$$

5. 梯度迭代规则：每一步沿负梯度方向更新 $A$，其中 $\eta$ 是学习率（步长）。

$$\displaystyle A \leftarrow A - \eta\frac{\partial L}{\partial A}$$

林夏在画布前看着魔法铅笔不断微调，每一笔都不是乱改，而是严格顺着“最不协调”的坡道精准修正。这正是梯度搜索的灵魂：用连续的信息，走确定的坡。

联合优化策略

传统画家画影响地图，往往分两步走：先画草图决定哪些线存在，再描墨线决定每条线的粗细。这种“先结构后参数”的做法有一个致命伤：如果第一步草图就画错了，第二步的墨线再漂亮也是白费，还得推倒重来。GraN-DAG的魔法铅笔则完全不同——线的“虚实浓淡”（结构）和“粗细力度”（参数）由同一支笔尖同时决定，互相反馈、彼此修正。

这种“边画边改边定粗细”的机制，在深度学习里叫端到端联合优化。在GraN-DAG中，邻接矩阵 $A$ 并不是一个独立的自由变量，而是由神经网络参数 $\theta$ 通过注意力机制产生的——也就是说，“哪些边存在”本身就是网络的输出。因此，对网络参数的一次反向传播，就会同时更新结构的表达（边的权重）和机制的表达（每个变量如何被其父节点影响）。结构学习和参数学习不再是两个割裂的阶段，而是同一枚硬币的两面。

$$\displaystyle \frac{\partial L}{\partial \theta} = \sum_{i=1}^{d}\sum_{j=1}^{d}\frac{\partial L}{\partial A_{ij}}\cdot\frac{\partial A_{ij}}{\partial \theta}$$

1. 网络参数 $\theta$：神经网络中所有可学习的权重和偏置，是“画笔”的内在肌肉记忆。

$$\displaystyle \theta$$

2. 边权重的梯度 $\frac{\partial L}{\partial A_{ij}}$：表示损失对第 $i \to j$ 条边的敏感度——这条边变浓或变淡，损失会变化多少。

$$\displaystyle \frac{\partial L}{\partial A_{ij}}$$

3. 边对参数的梯度 $\frac{\partial A_{ij}}{\partial \theta}$：表示边权重如何随网络参数变化，由注意力机制的平滑映射保证可导。

$$\displaystyle \frac{\partial A_{ij}}{\partial \theta}$$

4. 双重求和与连乘：遍历所有 $d \times d$ 条候选边，把“边的误差”通过链式法则一步步传回网络深处。

$$\displaystyle \sum_{i=1}^{d}\sum_{j=1}^{d}\frac{\partial L}{\partial A_{ij}}\cdot\frac{\partial A_{ij}}{\partial \theta}$$

林夏发现魔力就在于此：结构不再是一张需要单独修改的草图，而是融入画布肌理的活笔触。每一轮梯度回传，都在同时回答两个问题——“要画哪些线”和“每根线该用多大力道”。

阈值化输出

经过漫长的梯度迭代，画布上的线条终于分出了层次：真正的因果边浓墨重彩、清晰有力；噪声痕迹则淡如烟尘、若有若无。但林夏知道，最终交付给数据局的不能是这么一幅“灰度印象派”作品——对方要的是明确的地图：哪些边有，哪些边没有，一目了然。这就需要最后一步操作：阈值化。

阈值化的逻辑非常朴素：定一个门槛 $\tau$，边权重高于门槛就保留（置为1），低于门槛就擦掉（置为0）。这就像林夏拿起橡皮，把那些淡到看不见的辅助线统统擦去，只留下浓墨重彩的主干道。阈值 $\tau$ 是一个超参数，需要根据数据规模、噪声水平以及业务对“假阳性”的容忍度来调节：$\tau$ 设得高，得到的图更稀疏、更保守；$\tau$ 设得低，则可能保留更多弱连接、更容易混入噪声边。

$$\displaystyle \hat{A}_{ij} = \mathbb{1}[A_{ij} > \tau]$$

1. 连续权重 $A_{ij}$：训练结束后第 $i \to j$ 条边的最终浓度值，是阈值化的输入。

$$\displaystyle A_{ij}$$

2. 阈值 $\tau$：事先设定的临界值，是“保留还是擦除”的分界线，通常取 $0.3$ 到 $0.5$ 之间。

$$\displaystyle \tau$$

3. 指示函数 $\mathbb{1}[\cdot]$：括号内条件成立时输出 1，不成立时输出 0，将“灰度”二值化为“有无”。

$$\displaystyle \mathbb{1}[A_{ij} > \tau]$$

4. 离散化结果 $\hat{A}_{ij}$：阈值化后的 0/1 矩阵，代表最终交付的离散 DAG——不再有任何中间灰度。

$$\displaystyle \hat{A}_{ij} \in \{0, 1\}$$

擦去辅助线的那一刻，魔法铅笔的画作终于定稿。林夏检查了一遍：没有环，方向清晰，每一根保留下来的线都经得起数据验证——一幅货真价实的因果地图诞生了。

方法定位比较

林夏在画坛摸底一圈，发现自己的魔法铅笔并非唯一技法。传统NOTEARS方法像一支“直尺配铅笔”，只能画直线关系——它假设变量的生成机制是线性的，优点是简洁高效，但遇到非线性机制（比如“GDP对教育的影响随发展阶段逐渐饱和”这种先增后平的关系）就力不从心。另一类方法是基于强化学习（RL）的离散搜索，像一位“反复纠结的画家”，每画一笔都要回到起点重新权衡整幅图，计算开销极大。

GraN-DAG的定位恰好在这两者之间找到最佳平衡：它的生成机制用神经网络表达，能拟合各种非线性关系；同时优化过程是连续的梯度搜索，不需要在离散空间里暴力回溯。把两种方法的损失函数摆在一起，差异一目了然：

$$\displaystyle L_{N} = \frac{1}{2n}\lVert X - XA\rVert_F^2 + \lambda h(A) \quad \text{vs} \quad L_{G} = \frac{1}{n}\sum_{i=1}^{n}\lVert x_i - g_{\theta}(x_i, A)\rVert_2^2 + \lambda h(A)$$

1. 线性拟合 $XA$：NOTEARS假设每个变量是其他变量的线性组合，$XA$ 表示线性预测值，优点是解空间简单。

$$\displaystyle XA$$

2. 非线性网络 $g_{\theta}(x_i, A)$：GraN-DAG用神经网络对每个变量建模，能捕捉数据中的复杂非线性交互。

$$\displaystyle g_{\theta}(x_i, A)$$

3. 共享的无环约束 $\lambda h(A)$：两种方法都依赖同一个连续无环约束来保证图合法，这是“无环铁律”在两种技法中的共同体现。

$$\displaystyle \lambda h(A)$$

4. 模型的局限：GraN-DAG的损失是非凸的，梯度搜索只能保证收敛到局部最优，且对未观测混杂变量敏感。

$$\displaystyle \min_{A,\theta} L_G \quad \text{（非凸问题，无全局最优保证）}$$

林夏把魔法铅笔放回笔袋，若有所思。这套“边画边学”的技法虽然强大，但也有自己的边界：它不能凭空创造数据里不存在的因果信息，也不能保证每次都能走到全局最优。理解工具的边界，才能真正用好工具。

AI 应用场景

Python 演示

import numpy as np  def generate_data(n=800, seed=42):    rng = np.random.default_rng(seed)    e1 = rng.normal(size=(n, 1))    e2 = rng.normal(size=(n, 1))    e3 = rng.normal(size=(n, 1))    x1 = e1    x2 = 0.9 * x1 + 0.3 * e2    x3 = 0.7 * x2 + 0.2 * x1 + 0.3 * e3    return np.concatenate([x1, x2, x3], axis=1)  def dagness(A):    d = A.shape[0]    B = A * A    term = np.eye(d)    M = np.eye(d)    for k in range(1, 12):        term = term @ B / k        M = M + term    return np.trace(M) - d  def dagness_grad(A):    d = A.shape[0]    B = A * A    term = np.eye(d)    M = np.eye(d)    for k in range(1, 12):        term = term @ B / k        M = M + term    return M.T * (2 * A)  def train(X, iters=400, lr=0.03, lam=2.0):    n, d = X.shape    A = np.zeros((d, d))    for t in range(iters):        pred = X @ A        mse = np.mean((X - pred) ** 2)        mse_grad = X.T @ (pred - X) / n        h_val = dagness(A)        h_grad = dagness_grad(A)        grad = mse_grad + lam * h_grad        A = A - lr * grad        A = np.maximum(A, 0)        if t % 100 == 0:            print("step", t, "mse", round(mse, 4), "h(A)", round(h_val, 4))    return A  def threshold(A, tau=0.3):    return (A > tau).astype(int)  if __name__ == "__main__":    X = generate_data()    A = train(X)    print("learned adjacency:")    print(np.round(A, 3))    print("thresholded DAG:")    print(threshold(A))

1. x2 = 0.9 * x1 + 0.3 * e2按真实因果结构生成数据：x1 影响 x2，x2 影响 x3，x1 也直接影响 x3。
2. B = A * A逐元素平方，保证路径检测基于正向边强度，这是无环约束的标准预处理。
3. term = term @ B / k泰勒展开逐项累加矩阵指数 $e^B$，展开到 12 项时精度已足够工程使用。
4. return np.trace(M) - d返回无环度 $h(A)$，越接近 0 表示图越接近 DAG。
5. mse_grad = X.T @ (pred - X) / n数据拟合损失的解析梯度：预测与真实的残差反向投影到邻接矩阵空间。
6. grad = mse_grad + lam * h_grad总梯度 = 拟合梯度 + 无环惩罚梯度，两者共同引导搜索方向。
7. A = np.maximum(A, 0)投影操作，保持边权重非负，确保因果强度的物理意义。
8. return (A > tau).astype(int)阈值化：权重超过 0.3 的边保留为 1，其余置 0，得到最终离散 DAG。

常见误区

面试题