有向无环图DAG：Markov等价类

可视化演示

展示DAG的Markov等价类：具有相同骨架和v-结构的DAG编码相同条件独立性，构成等价类，用CPDAG表示其中不可区分的边方向。

DAG基础概念

规划师拿到旧图纸的第一件事，是检查路网有没有“绕圈”的毛病：如果 A 大街通向 B 大道，B 大道通向 C 花园，那么 C 花园就绝不能偷偷修一条回头路回到 A——否则车辆会陷入无限循环，整座城市的交通都会崩溃。因果图同样立下这条“无环”军规：没有任何一条有向路径能绕回起点，这正是“有向无环图”（DAG）名字里“无环”二字的含义。

在因果推断里，每个变量就是一个路口（结点），每条“原因→结果”的单行线就是一条有向边。变量与有向边合在一起，就构成一张因果图。DAG 最值钱的资产，是它编码的条件独立性：当我们已经掌握某些中间变量的取值后，其他变量之间的信息传递就会被切断。在车流隐喻里，这就像你一旦确认了枢纽 B 的拥堵状态，A 与 C 两个路口的车流就变得互不相干。

形式化地说，若给定 Z 时 X 与 Y 的联合分布可以分解为各自条件分布的乘积，就称 X 与 Y 在给定 Z 下条件独立：

判断图中任意两点是否条件独立，靠的是 d-分离准则：信息像车流一样沿有向边按方向流动，遇到“对撞结构”（两条边同时指向一点）时，若没有给定该点则路径被阻断，一旦给定反而被激活。理解了“信息在哪里被切断、在哪里被激活”，我们才能回答一个关键问题：为什么有些车流观察会完全无法区分两套单行方案？这就进入了等价类的核心。

等价类定义

一天下来，规划师震惊地发现：两份完全不同的单行方案，却产生了分毫不差的车流记录。他恍然大悟——观测数据只能告诉我们“哪些方案长得一模一样”，不能告诉我们“哪个才是真相”。这些互相无法区分的方案被他叠成一摞，命名为“等价类”。

在因果推断里，两个结点集合相同的 DAG，如果编码的条件独立性完全一致，就称它们马尔可夫等价，同属一个 Markov 等价类。比如三条链式 DAG（A→B→C、A←B→C、A←B←C）都满足 A 与 C 在给定 B 时独立，因此在观测层面无法区分。判断等价不需要逐个核对所有独立性，Verma 与 Pearl 发现，只需盯住两样东西。

第一样是骨架：把有向边全部抹去方向后得到的无向图，回答“哪些路口相邻”。第二样是 V 型结构：形如 X→Y←Z 且 X、Z 之间没有边相连的结构，也叫未屏蔽对撞子。在车流隐喻里，V 型结构就像“漏斗式汇合”——两股来路都只能冲进同一个枢纽，而两个源头之间没有直连，这种结构是唯一能“铁证”单一方向的局部模式。形式化的等价定义如下：

就像规划师先掂量“底层连接”和“漏斗汇合”两样清单，就能判断两份方案是否车流等价——这份清单的正式名字，就叫 Verma-Pearl 定理。

Verma-Pearl判定定理

有了等价类的直觉，规划师还需要一把快刀：如何不用把两份方案的所有细节逐一比对，就能断定它们是否同属一摞？答案是把目光聚焦在两类“关键证据”上：底层连接是否一致，漏斗式汇合的位置是否一致。

定理的表述非常干净：两个 DAG 马尔可夫等价，当且仅当它们的骨架相同且 V 型结构集合相同。这是充要条件——既不多，也不少。特别要注意，V 型结构必须“未屏蔽”：如果父结点 X 与 Z 之间也有一条边直接相连，那么这个对撞子就被屏蔽了，箭头方向的信息也随之丢失，不能再作为判定证据。

$$\displaystyle G_1 \sim G_2 \iff \mathrm{Skel}(G_1) = \mathrm{Skel}(G_2) \ \wedge\ \mathrm{VStr}(G_1) = \mathrm{VStr}(G_2)$$

1. 骨架相等：去掉所有箭头方向后，两图的“哪些路口相邻”完全一致。

$$\mathrm{Skel}(G_1) = \mathrm{Skel}(G_2)$$

2. 逻辑与：两个条件必须同时成立，缺一不可。

$$\wedge$$

3. V 型结构集合相等：未屏蔽对撞子的位置在两图中一一对应。

$$\mathrm{VStr}(G_1) = \mathrm{VStr}(G_2)$$

为什么这两样就够？因为 d-分离的格局完全由骨架和 V 型结构决定：其余方向无论怎么翻转，条件独立性清单都不会变。规划师从此只需检查两份地图的连接关系与漏斗位置，就能断言车流等价——哪怕箭头画得完全不同。

CPDAG图表示

一个等价类可能包含很多张 DAG，总不能把所有候选方案都摊在桌上吧？规划师想出一个聪明的办法：把确定的方向画成实线箭头，把拿不准的方向画成双头线——一张“半定向地图”就浓缩了整个等价类。

这张图就是完全部分有向图，简称 CPDAG。构造规则很直观：对于等价类中的每一条边，如果所有成员 DAG 都一致地取 X→Y，那么它是强制边，方向已被数据钉死；如果某些成员取 X→Y、另一些取 X←Y，那么它是不确定边，用一条无方向的边 X—Y 表示。这样，等价类的信息被无损压缩进一张图。

$$\displaystyle [G_0] = \left\{ G \mid G \sim G_0 \right\}, \qquad X \to Y\ \text{为强制边} \iff X \to Y \in G,\ \forall\, G \in [G_0]$$

1. 等价类集合：[G₀] 把“所有走起来一样的单行方案”收进同一个集合。

$$[G_0] = \left\{ G \mid G \sim G_0 \right\}$$

2. 全称量词：对集合中每一个成员 G 都成立，才配叫“强制”。

$$\forall\, G \in [G_0]$$

3. 强制边判定：方向在所有成员中一致，说明观测数据已经把方向钉死。

$$X \to Y \in G$$

CPDAG 是等价类的“身份证”：一张图，一族方案，清清楚楚标出哪些方向已被数据确认、哪些仍悬而未决。对工程实践来说，这张诚实的“半定向地图”远比一张武断的全定向图更有价值。

PC算法学习

光有理论还不够，规划师决定亲自上街勘测：第一步，摸清哪些路口真的相连；第二步，寻找漏斗式汇合点；第三步，利用几条交通铁律把方向尽量传播到全城。这套三步勘测法，就是 PC 算法。

在忠实性假设下——即数据中的条件独立性完全由图结构编码，不多也不少——PC 算法从观测数据中恢复出整个等价类。它的思路不是从零画图，而是从“全连接”开始做减法：对每对变量做条件独立性检验，若发现某个条件集能让二者独立，就删除这条边，并记录下这个“分离集”。

$$\displaystyle \exists\, S \subseteq \mathrm{adj}(X) \setminus \{ Y \} \ \text{使} \ X \perp\!\!\!\perp Y \mid S \;\Rightarrow\; \text{删除边 } X \text{—} Y$$

1. 邻接集合：adj(X) 是当前图中 X 的全部邻居结点。

$$\mathrm{adj}(X)$$

2. 条件集存在性：在 X 的邻居中（不含 Y）能找到某个 S 使二者独立。

$$\exists\, S \subseteq \mathrm{adj}(X) \setminus \{ Y \}$$

3. 删边决策：条件独立成立，意味着 X—Y 之间没有直接因果连接。

$$X \perp\!\!\!\perp Y \mid S \Rightarrow \text{移除边}$$

拿到骨架后，算法在骨架上寻找 V 型结构并定向：若出现 X—Y—Z 而 X、Z 不相邻，则定向为 X→Y←Z。最后用 Meek 规则传播方向——例如已知 X→Y 且 Y—Z 而 X、Z 不相邻，则强制 Y→Z。最终输出的正是上一节那张 CPDAG。勘测手册的最终产物并不是一张全定向的“真相图”，而是一张标明“已知/未知”的诚实地图；剩下的方向，要靠干预实验来补测。

因果识别应用

车流能告诉我们“哪些方案无法区分”，可当市政厅问：“如果封掉 X 路口的某个方向，Z 区域的流量会变成什么样？”等价类内的不同方案会给出大相径庭的预测。这时，观测数据的权力到此为止，真正的主角是干预实验——亲手封路。

这是因果识别的核心困境：等价类成员在观测分布上不可区分，但 do 算子（干预算子）下的分布未必相同。最经典的例子是链 X→Y→Z 与叉 X←Y→Z：两者骨架相同、都没有 V 型结构，因此同属一个等价类；但因果含义天差地别——链中 X 通过 Y 中介影响 Z，叉中 X 与 Z 根本没有因果通路。

$$\displaystyle \text{链: } P(z \mid do(x)) = \sum_{y} P(z \mid y)\, P(y \mid x); \qquad \text{叉: } P(z \mid do(x)) = P(z)$$

1. do 算子：do(x) 对应规划师“封路施工”后的世界，与“看到车流 X=x”完全不同。

$$P(z \mid do(x))$$

2. 链式路径求和：X 经 Y 中介影响 Z，要按中间变量 Y 的所有可能取值加权求和。

$$\sum_{y} P(z \mid y)\, P(y \mid x)$$

3. 叉式无通路：X 与 Z 之间没有因果路径，干预 X 不改变 Z 的分布。

$$P(z \mid do(x)) = P(z)$$

工程实践的标准姿势因此清晰起来：用 PC 等算法输出 CPDAG，识别出等价类边界；对方向存疑的关键边，再用随机干预（A/B 测试、CRISPR 扰动、自然实验）补测方向。规划师终于明白——观测车流图只能框定“迷宫”的边界，真正的钥匙，是亲手封路测一次。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-# Markov等价类判定: 骨架 + V型结构 (Verma-Pearl定理)  def skeleton(edges):    """返回无向骨架, 用双向邻接集合表示: {(u,v),(v,u)}"""    s = set()    for u, v in edges:        s.add((u, v))        s.add((v, u))    return s  def parents(node, edges):    """返回指定结点的全部父结点集合"""    return {u for u, v in edges if v == node}  def v_structures(edges):    """返回V型结构(未屏蔽对撞子)集合, 每个元素为三元组 (u, v, w)"""    vs = set()    nodes = {n for e in edges for n in e}    skel = skeleton(edges)    for b in nodes:        pa = sorted(parents(b, edges))        for i in range(len(pa)):            for j in range(i + 1, len(pa)):                x, y = pa[i], pa[j]                if (x, y) not in skel:                    vs.add((x, b, y))    return vs  def markov_equivalent(g1, g2):    """判定两个DAG是否属于同一Markov等价类"""    return skeleton(g1) == skeleton(g2) and v_structures(g1) == v_structures(g2)  if __name__ == "__main__":    chain1 = [("A", "B"), ("B", "C")]      # A -> B -> C    chain2 = [("B", "A"), ("B", "C")]      # A <- B -> C (fork)    chain3 = [("B", "A"), ("C", "B")]      # A <- B <- C    collider = [("A", "B"), ("C", "B")]    # A -> B <- C (v-structure)     print("three chains pairwise equivalent:",          markov_equivalent(chain1, chain2),          markov_equivalent(chain1, chain3))    print("chain vs v-structure equivalent:", markov_equivalent(chain1, collider))    print("v-structure set:", v_structures(collider))

1. s.add((u, v))把无向边双向登记进集合，之后判断“是否相邻”只需一次查表。
2. return {u for u, v in edges if v == node}父结点就是“有向边终点”对应的起点。
3. skel = skeleton(edges)提前算好骨架，供后续判断“两个父结点是否相邻”。
4. for b in nodes:逐个检查每个结点是否充当“漏斗式汇合”的枢纽。
5. if (x, y) not in skel:只有当两个父结点之间没有边时，才算未屏蔽对撞子，即 V 型结构。
6. vs.add((x, b, y))记录三元组 （父1, 对撞点，父2），构成 V 型结构集合。
7. return skeleton(g1) == skeleton(g2) and v_structures(g1) == v_structures(g2)Verma-Pearl 定理的一行落地。

常见误区

面试题