D-分离#

D-分隔集#

在这里，我们简要概述了 D-分离及与其理解相关的概念

D-分离和 D-连接的概念与路径是开放还是阻塞有关。

• “路径”是按顺序由边连接的节点序列。与大多数图论分析不同，边的方向被忽略。因此，路径可以被视为图的无向版本上的传统路径。

• “候选 D-分隔集” z 是一个节点集合，被认为是可能阻塞两个指定节点集合 x 和 y 之间所有路径的集合。我们将候选 D-分隔集中的每个节点称为“已知”。

• 路径上的“碰撞点”（collider）节点是指其在路径上的两个相邻节点的后继节点。也就是说，如果路径上的边的方向看起来像 ... u -> c <- v ...，则 c 是一个碰撞点。

• 如果碰撞点节点或其任何后代节点是“已知”的，则该碰撞点称为“开放碰撞点”。否则，它是“阻塞碰撞点”。

• 任何路径都可以通过两种方式“阻塞”。如果路径包含一个不是碰撞点的“已知”节点，则该路径被阻塞。此外，如果路径包含一个不是“已知”节点的碰撞点，则该路径也被阻塞。

• 如果路径未被阻塞，则该路径是“开放的”。也就是说，如果路径中的每个节点要么是开放碰撞点，要么不是“已知”的，则路径是开放的。换句话说，路径中每一个“已知”的节点都是碰撞点，并且每一个碰撞点都是开放的（包含一个“已知”的后代，包括自身）。“开放路径”的概念旨在证明给定预设知识（“已知”节点）下两个节点之间存在概率上的条件依赖性。

• 如果节点集 z 阻塞了 x 中的节点与 y 中的节点之间的所有路径，则称集合 x 和 y 被 z “D-分离”。也就是说，如果从 x 中的任何节点到 y 中的任何节点都没有开放路径，则称它们被 D-分离。这样的集合 z 是 x 和 y 的一个“D-分隔集”。

• “最小 D-分隔集”是指一个 D-分隔集 z，从中移除任何节点或节点子集后，它就不再是 D-分隔集。

D-分隔集阻塞了 x 和 y 之间的某些路径，但可能开放其他路径。如果 D-分隔集中的节点不是碰撞点，它们会阻塞路径。但是，如果碰撞点或其后代节点在 D-分隔集中，则这些碰撞点是开放的，允许路径通过该碰撞点。

D-分离的例子说明#

如果从节点 u 到 v 存在一条未被阻塞的路径，则称节点对 u 和 v 是 D-连接的。这意味着从 u 到 v 存在一条开放路径。

例如，如果 D-分隔集是空集，则 u 和 v 之间的以下路径是开放的

• u <- n -> v

• u -> w -> … -> n -> v

另一方面，如果 n 在 D-分隔集中，则 n 会阻塞 u 和 v 之间的那些路径。

如果碰撞点及其后代不包含在 D-分隔集中，它们会阻塞路径。当 D-分隔集为空时被阻塞的路径示例是

• u -> w -> … -> n <- v

节点 n 是此路径中的一个碰撞点，并且不在 D-分隔集中。因此 n 阻塞此路径。然而，如果 n 或其后代被包含在 D-分隔集中，那么通过 n 处的碰撞点（… -> n <- …）的路径是“开放的”。

D-分离关注的是阻塞从 x 到 y 之间所有节点的路径。 x 和 y 之间的 D-分隔集是指所有路径都被阻塞的集合。

D-分离及其在概率中的应用#

D-分离常用于概率因果图模型。D-分离将概率“依赖性”的概念与图中的分离联系起来。如果假设因果马尔可夫条件 [5]（每个节点在其父节点已知的情况下，条件独立于其非后代节点），那么 D-分离意味着概率分布中的条件独立性。对称地，D-连接意味着依赖性。

直觉如下。因果图上的边表示哪些节点直接影响其他节点的结果。从 u 到 v 的边意味着事件 u 的结果影响事件 v 结果的概率。当然，知道 u 会改变对 v 的预测。但知道 v 也会改变对 u 的预测。结果是相互依赖的。此外，从 v 到 w 的边意味着 w 和 v 是依赖的，因此 u 可以间接影响 w。

在对系统没有任何了解的情况下（候选 D-分隔集为空），因果图 u -> v -> w 使得所有三个节点都可能相互依赖。但是，如果我们知道 v 的结果，那么 u 和 w 结果的条件概率彼此独立。也就是说，一旦我们知道 v 的结果，w 的概率就不再依赖于 u 的结果。这就是当 v 是“已知”的（在候选 D-分隔集中）时，v 阻塞路径背后的思想。

同样的论点适用于边的方向都向左，以及两条箭头都从中点向外发出。路径上的“已知”节点会阻塞非碰撞点的路径，因为这些关系使得条件概率相互独立。

因果边的方向确实会影响依赖性，尤其是在碰撞点的情况下，例如 u -> v <- w。在这种情况下，u 和 w 都影响 v。但它们之间没有直接影响。因此，在不知道任何结果的情况下，u 和 w 是相互独立的。这就是碰撞点阻塞路径背后的思想。但是，如果 v 是已知（观测到）的，则 u 和 w 的条件概率可能变得依赖。这就是伯克森悖论 [6] 的核心。例如，假设 u 和 w 是布尔事件（它们发生或不发生），并且 v 表示“至少一个 u 和 w 发生”的结果。那么，知道 v 为真会使得 u 和 w 的条件概率变得依赖。本质上，知道其中至少一个发生会提高各自的概率。但进一步知道 w 为真（或为假）会将 u 的条件概率改变为原始值或 1。因此，尽管 u 和 w 之间没有因果关系，但 u 的条件概率依赖于 w 的结果。当碰撞点已知时，通过该碰撞点的路径可能会产生依赖性。这就是开放碰撞点不阻塞路径的原因。

此外，即使 v 不是“已知”的，如果它的后代之一是“已知”的，我们可以利用该信息更多地了解 v，这再次使得 u 和 w 可能相互依赖。假设当 v 发生时（即“至少一个 u 和 w 发生”），n 发生的概率要高得多。那么，如果我们知道 n 发生了，那么 v 发生的可能性就更大，这使得 u 和 w 相互依赖的概率增加。这就是为什么如果碰撞点的任何后代是“已知”的，碰撞点不会阻塞路径背后的思想。

当两个节点集合 x 和 y 被集合 z D-分离时，这意味着在给定 z 中节点结果的条件下，x 中节点结果的概率独立于 y 中节点结果的概率，反之亦然。

示例#

一个包含 5 个观测状态和 5 个隐藏状态的隐马尔可夫模型，其中隐藏状态存在因果关系形成路径，从而得到以下因果网络。我们检查路径上的早期状态是否被中间隐藏状态的 D-分隔集与路径上的晚期状态分离。因此，如果我们以中间隐藏状态为条件，早期状态的概率独立于晚期状态的结果。

>>> G = nx.DiGraph()
>>> G.add_edges_from(
...     [
...         ("H1", "H2"),
...         ("H2", "H3"),
...         ("H3", "H4"),
...         ("H4", "H5"),
...         ("H1", "O1"),
...         ("H2", "O2"),
...         ("H3", "O3"),
...         ("H4", "O4"),
...         ("H5", "O5"),
...     ]
... )
>>> x, y, z = ({"H1", "O1"}, {"H5", "O5"}, {"H3"})
>>> nx.is_d_separator(G, x, y, z)
True
>>> nx.is_minimal_d_separator(G, x, y, z)
True
>>> nx.is_minimal_d_separator(G, x, y, z | {"O3"})
False
>>> z = nx.find_minimal_d_separator(G, x | y, {"O2", "O3", "O4"})
>>> z == {"H2", "H4"}
True

如果不存在最小 D-分隔集，则返回 None

>>> other_z = nx.find_minimal_d_separator(G, x | y, {"H2", "H3"})
>>> other_z is None
True

参考文献#