d-分离 · aiwiki.page

d-分离是图论中的一种判据，用于确定有向无环图（DAG）所蕴含的条件独立关系。它是贝叶斯网络及其他概率图模型的基础；在这些模型中，顶点代表随机变量。这一判据依据边的排列方式和方向，而非具体的概率数值，来识别在所有按该图分解的分布中都成立的独立关系。“d”表示“有向”（directional）：箭头的方向会影响一条路径是否被阻断。(bayes.cs.ucla.edu)

图上的定义

设 $G=(V,E)$ 为一个 DAG， $A,B,S\subseteq V$ 为两两不相交的顶点集。在考察 $A$ 与 $B$ 中顶点之间的路径时，不要求沿箭头方向行进。不过，箭头方向决定了路径上各内部顶点的类型。当与某个内部顶点相邻的两条边都指向该顶点时，它就是这条路径上的**碰撞点**：

U\rightarrow C\leftarrow W.

否则，它就是非碰撞点。这种分类是相对于某条特定路径而言的，并非顶点本身的固定属性。(cs.cmu.edu)

给定 $S$ ，一条路径是活跃的，也称开放的，当且仅当：

每个内部非碰撞点都不属于 $S$ 。
每个内部碰撞点要么属于 $S$ ，要么有一个后代属于 $S$ 。

后代是指沿一条或多条有向边可以到达的顶点。如果不存在连接 $A$ 中任意顶点与 $B$ 中任意顶点的活跃路径，则称 $A$ 与 $B$ 被 $S$ d-分离，记作

A\perp_G B\mid S.

否则，称它们是 d-连通的。要确立分离关系，必须阻断每一条连接路径；仅找到一条被阻断的路径并不足够。(bayes.cs.ucla.edu)

链、叉与碰撞点

以下三种基本结构可以说明这一判据：

链： $X\rightarrow M\rightarrow Y$ ，或箭头方向全部反转的结构。不以 $M$ 为条件时，路径是开放的；以 $M$ 为条件则会阻断这条路径。
叉： $X\leftarrow C\rightarrow Y$ 。这条经由共同父节点的路径同样会因以 $C$ 为条件而被阻断。
碰撞点： $X\rightarrow C\leftarrow Y$ 。这条路径是被阻断的，除非以 $C$ 或它的某个后代为条件。

对于孤立的链或叉，可以分别推出 $X\perp Y\mid M$ 或 $X\perp Y\mid C$ 。对于孤立的碰撞点结构，在未施加条件时可以推出 $X\perp Y$ ，而以这个共同结果为条件可能会引入依赖关系。(bayes.cs.ucla.edu)

因此，增加条件变量不一定会保持 d-分离。更大的条件集可能阻断某个非碰撞点，同时又使别处的某个碰撞点所在路径开放。这使 d-分离有别于无向图中的普通顶点分离，也解释了为什么不加区分地将更多变量纳入条件集可能改变独立关系。(bayes.cs.ucla.edu)

概率解释

假设一个联合概率分布可以按 $G$ 分解：

p(x_1,\ldots,x_n) =\prod_{i=1}^{n}p(x_i\mid x_{\operatorname{pa}(i)}),

其中， $\operatorname{pa}(i)$ 表示顶点 $i$ 的父节点集合。各因子描述的是条件概率。此时，d-分离蕴含

A\perp_G B\mid S \quad\Longrightarrow\quad X_A\perp X_B\mid X_S.

这就是 DAG 的全局马尔可夫性质。当条件集为空时，它给出通常的统计独立性。(ftp.cs.ucla.edu)

这一判据具有**可靠性（逻辑学），因为它识别出的每一种独立关系，在所有按该图分解的分布中都成立。对于图所蕴含的独立关系，它也具有完备性：如果两个集合是 d-连通的，就存在一个与该图相容的分布，使这两个集合在给定条件下相互依赖。完备性并不**断言这种依赖关系在每个相容分布中都成立。特定的参数选择可能产生图中未编码的额外独立关系。(ftp.cs.ucla.edu)

忠实性与因果解释

如果一个分布的条件独立关系与某个 DAG 的 d-分离关系完全一致，就称该分布对这个 DAG 具有**忠实性**。在忠实性成立时，d-连通意味着该分布中存在依赖关系。没有忠实性，参数效应的相互抵消或其他特殊选择也可能产生独立关系。因此，忠实性是一项额外假设，而不是图定义的一部分。(cs.cmu.edu)

仅凭 d-分离并不能确立因果关系。贝叶斯网络可以表示概率关系，而不要求其箭头具有因果含义。在因果推断中，要赋予图因果解释，还需要对图所表示的机制作出额外假设。基于独立关系的发现方法也可能无法区分若干候选图：属于同一马尔可夫等价类的图编码了相同的独立关系。(cs.cmu.edu)

计算方法

无需显式枚举所有连接路径。**贝叶斯球算法**通过遍历图来进行判断，其遍历规则取决于顶点是否被观测，以及是从父节点还是子节点到达该顶点。通过记录遍历状态，算法可以避免重复计算。其时间复杂度与图的规模呈线性关系，为 $O(|V|+|E|)$ ，并且能够识别与某个推断查询无关的变量。(web.stanford.edu)

另一种方法使用**道德化祖先图**。首先，保留 $A\cup B\cup S$ 中的顶点及其所有祖先。然后，将共享同一个子节点的每一对父节点相连，并把有向边替换为无向边。当且仅当从该图中移除 $S$ 后， $A$ 与 $B$ 之间不再存在连接，d-分离才成立。在道德化之前，必须先将图限制为祖先子图。(cs.cmu.edu)

在因果调整中的作用

在结构因果模型中，阻断规则有助于区分因果路径与产生混杂的路径。后门准则要求调整集不包含暴露变量的任何后代，并阻断每一条通过指向暴露变量的箭头进入该变量的路径。碰撞点的激活在这里至关重要：施加条件可能会产生不希望出现的关联，而不是消除关联。(cs.cmu.edu)

d-分离还为基于约束的因果发现程序提供了图所蕴含的关系。这类程序将数据中的条件独立关系与候选图预测的条件独立关系进行比较，通常假设因果马尔可夫条件和忠实性成立。其输出未必能确定唯一的因果 DAG。(cs.cmu.edu)

参考来源

d-Separation Without Tearsbayes.cs.ucla.edu
d-Separation: From Theorems to Algorithmsftp.cs.ucla.edu
Bayes-Ball: The Rational Pastimeweb.stanford.edu
10-708 PGM: Lecture 2—Bayesian Networkscs.cmu.edu
10-708 PGM: Lecture 8—Causal Discovery and Inferencecs.cmu.edu
The Intuition Behind the Back-Door Criterionbayes.cs.ucla.edu