D-Separation#

有向无环图中的d-分离测试算法。

d-分离 是用于概率分布中条件独立性测试的一种方法，这些概率分布可以通过有向无环图（DAG）进行因子分解。它是一种纯粹的图形测试方法，使用底层图形而不参考实际的分布参数。有关正式定义，请参见 [1]。

该实现基于 [2] 中提出的概念上简单的线性时间算法。有关一些替代算法，请参阅 [3] 和 [4]。

NetworkX 中的功能接口由三个函数组成：

D-分离#

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

d-分离和 d-连接的概念与路径的开放或阻塞有关。

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

  • “候选 d-分离集” z 是正在考虑的一组节点，可能阻塞两个预定集合 x 和 y 之间的所有路径。我们将在候选 d-分离集中的每个节点称为“已知”。

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

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

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

  • 如果路径未被阻塞，则该路径是“开放”的。也就是说，如果路径中的每个节点要么是开放碰撞节点，要么不是“已知”节点，则该路径是开放的。换句话说，路径中的每个“已知”节点都是碰撞节点，并且每个碰撞节点都是开放的（具有“已知”节点的包容性后代）。“开放路径”的概念旨在展示在给定预定知识（“已知”节点）的情况下，两个节点之间的概率条件依赖性。

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

  • “最小 d-分离集”是一个 d-分离集 z ，其中没有任何节点或节点子集可以被移除，而它仍然是一个 d-分离集。

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

D-分离的Examples说明#

一对节点 u 和 v 是 d-连接的，如果从 u 到 v 存在一条未被阻塞的路径。这意味着，从 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 或 n 的后代包含在 d-分离集中，则通过碰撞节点 n 的路径（… -> n <- …）是“开放”的。

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

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

D-分离通常用于概率因果图模型。D-分离将概率“依赖性”与图中的分离联系起来。如果假设因果马尔可夫条件 [Re62631f30934-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-分离集中）时阻塞路径的想法。

无论边的方向是向左还是从中部向外，同样的论证都适用。在路径上有一个“已知”节点阻塞无碰撞节点的路径，因为这些关系使得条件概率独立。

因果边的方向确实在碰撞节点的情况下影响依赖性，例如 u -> v <- w 。在这种情况下， u 和 w 都影响 v 。但它们并不直接影响彼此。因此，在没有任何结果知识的情况下， u 和 w 是独立的。这就是碰撞节点阻塞路径的想法。但是，如果 v 是已知的， u 和 w 的条件概率可能是依赖的。这是 Berkson 悖论 [6] 的核心。例如，假设 u 和 w 是布尔事件（它们发生或不发生）， v 表示结果“ u 和 w 中至少有一个发生”。那么知道 v 为真会使 u 和 w 的条件概率依赖。本质上，知道至少有一个为真会增加每个的概率。但如果进一步知道 w 为真（或假）， u 的条件概率会变为原始值或 1。因此，即使它们之间没有因果关系， u 的条件概率也取决于 w 的结果。当碰撞节点已知时，依赖性可以通过该碰撞节点的路径发生。这就是开放碰撞节点不阻塞路径的原因。

此外，即使 v 不是“已知”的，如果它的一个后代是“已知”的，我们可以使用该信息来了解 v ，这再次使 u 和 w 可能依赖。假设 n 发生的概率在 v 发生时（“ u 和 w 中至少有一个发生”）要高得多。那么如果我们知道 n 发生了，那么 v 发生的概率更高，这使得 u 和 w 的概率依赖。这就是为什么碰撞节点在其任何后代是“已知”时不阻塞路径的原因。

当两个节点集合 x 和 y 被集合 z “d-分离”时，这意味着在给定 z 中的节点结果的情况下， x 中的节点结果的概率与 y 中的节点结果的概率是独立的，反之亦然。

Examples#

一个具有 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

References#

[1]

Pearl, J. (2009). Causality. Cambridge: Cambridge University Press.

[2]

Darwiche, A. (2009). Modeling and reasoning with Bayesian networks. Cambridge: Cambridge University Press.

[3]

Shachter, Ross D. “Bayes-ball: The rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams).” In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI), (pp. 480–487). 1998.

[4]

Koller, D., & Friedman, N. (2009). Probabilistic graphical models: principles and techniques. The MIT Press.

is_d_separator(G, x, y, z)

返回节点集 x 和 y 是否由 z 在 G 中 d-分离。

is_minimal_d_separator(G, x, y, z, *[, ...])

确定 z 是否是 x 和 y 的最小 d-分离器。

find_minimal_d_separator(G, x, y, *[, ...])

返回一个最小化的d-分离集在 x 和 y 之间，如果可能的话
On this page