关于机器学习:贝叶斯网络的Dseparation详解和Python代码实现

D 拆散（D-Separation）又被称作有向拆散，是一种用来判断变量是否条件独立的图形化办法。相比于非图形化办法，D-Separation 更加直观且计算简略。对于一个 DAG（有向无环图），D-Separation 办法能够疾速的判断出两个节点之间是否是条件独立的。

理解 D 拆散

在贝叶斯网络中，D 拆散到底是什么，它能够用于什么？简略地说，它是一种惯例的确定独立性的办法。如果两个变量 X 和 Y 在有向图中绝对于另外一组变量 Z 是 d 拆散的，那么在这种图能够示意的所有概率分布中都是独立于 Z 的。这是什么意思？这意味着两个变量 X 和 Y 在 Z 上是独立的，如果一旦你晓得了 Z，那么对于 X 的常识是不会给你对于 Y 的任何额定信息的。

要齐全了解它是如何实现的，首先须要介绍 active 和 inactive trails。如果一条门路存在依赖关系，就能够说它是 active。例如，两个变量 X 和 Y 可能通过图中的多个门路连贯。如果没有任何门路处于 active 状态，则 X 和 Y 是 d 分隔的。让咱们看一下四种不同的状况，并确定那些是处于 active 状态：

，Case1：在这种状况下，咱们置信 X 能够通过 Z 来影响 Y。然而如果察看到 Z，X 不会通过 Z 影响 Y，因为 Z 已知。

Case2：这种状况与下面是对称的：如果察看到 Z，X 不能通过 Z 影响 Y，然而如果没有察看到 Z，X 能够通过 Z 影响 Y。

Case3：当且仅当 Z 没有被察看到时，X 能够通过 Z 影响 Y

Case4：如果 Z 没有被察看到，X 就不能影响 Y。这也被称为 v 形构造。

所有这些剖析能够用以下形式总结：

可达性剖析 (RA) 算法

咱们当初能够思考另一种算法，所谓的可达算法（Reachable Algorithm），它用于从给定 Z 的 active 门路寻找 X 可达的节点。算法由:

为了一步一步地了解算法。从算法的输出开始：

输出很好了解，而后该算法将返回从 X 可达到的所有节点。这部分是通过两个阶段来实现的：

• 阶段 1：这是算法的简略局部——找到 Z 中蕴含的所有节点的先人。
• 阶段 2：从 X 开始，找到可达节点——哪些节点能够间接从 X 达到，而后哪些节点能够从这些节点达到。而后循环这个过程。

为了将这个步骤可视化，假如有一个一下的贝叶斯网络：

能够从解决这个问题开始：

这就相当于给出 X_2 和 X_3 来让咱们确认是否有从 X_1 到 X_6 的 active trails。算法从寻找 X_2 和 X_3 的先人开始，能够看到除 X_1 之外它们没有任何先人。因而变量 A 如下：

当初进入第 2 阶段——查看不同的 active trails。因为问题是查看 X_1 和 X_6 之间是否有 active trails，所以这里从 X_1 开始:

这对应于下面的 Case 1 或 2，这不是 active trails。如果再看另一条线索：

这也对应于 Case 1 或 2。因而，咱们在 X_1 和 X_6 之间没有 active trails，它们是 d 拆散的。能够直观地展现这一点：

当初再次思考雷同的贝叶斯网络，但查看以下问题：

这与下面的通过给出 X_1 和 X_6 来询问咱们是否有从 X_2 到 X_3 的 active trails 雷同。算法从查找 X_1 和 X_6 的先人开始，它们须要插入到变量 A 中：

进入第 2 阶段，尝试从 X_2 开始，并从思考门路开始：

找到了 X_6，这意味着这对应于 Case 4。因而能够看到它是一个 active trails。而后咱们能够持续以下门路：

这也是一条 active trail——因为在给定 X_1 和 X_6 的状况下找到了一条从 X_2 到 X_3 的 active trail。当初，是否有可能从另一个办法做到这一点？换句话说，是否能够这样做：

它将等于 Case 3，因为失去了 X_1——因而，它不是一个 active trail：

D 拆散的另一种算法

还有一种比拟常见的 D 拆散算法：

• 绘制先人图，绘制仅蕴含提到的变量及其所有先人的网络的简化版。
• 连贯节点的父节点，为具备独特子节点的变量之间绘制一条无向边。
• 将有向边替换为无向边
• 删除给定节点及其边：例如，在“给定 Z 的状况下，X 和 Y 是否独立？”，则必须删除 Z 及其所有边。
• 剖析这个简化的图，如果图中的变量不相连，则它们是独立的。如果变量 浏览图表——，则不能保障它们是独立的。

上面应用以下的图进行算法的阐明：

当初确认以下问题：

可视化阐明这个过程：

能够看到它们依然是连贯的，这意味着 A 和 B 在给定 C 的状况下不是条件独立的。

再看看另一个问题：

最初失去的后果如下：

没有连贯，这意味着 A 和 B 是独立的。

最初一个例子：

后果如下：

能够看到 D 和 E 通过一条通过 C 的门路相连，因而在给定 A 和 B 的状况下，它们显然是条件独立的。

概念曾经介绍结束了，当初看看如何应用 Python 来实现它。

Python 代码实现

实现图构造

要应用该算法，首先须要有一个图作为解决的数据。导入须要的库：

实现构造时首先须要可能拜访图的边和节点。因为它是有向图，因而可能拜访图中所有节点的父节点和子节点也很有用。此外还须要一个能够可视化图的函数：

实现 D 拆散算法

当初能够编写 D 拆散算法的代码了。

阶段 1，简略地找到给定节点的所有先人——这里给定节点包含开始节点、完结节点和咱们条件的节点。

阶段 2，咱们从起始节点搜寻所有可能的 inactive trails。代码如下：

算法的指标是执行如下的查问：

所以须要扩大下面给出的代码。下面的代码曾经从起始节点找到了所有可能的流动门路——而后只须要查看完结节点是否蕴含在这个列表中就能够了。最初还能够对不同节点进行色彩编码的网络可视化。代码如下：

当初看看代码是否无效。假如有一个贝叶斯网络，如下所示：

咱们来确认：

Are node 4 and 5 d-separated given node 6?

总结

在本文中介绍了 D 拆散的概念及其相应的算法，并且应用 Python 实现了该算法，尽管代码中还有很多能够优化的中央，然而这对于咱们了解算法是一个十分好帮忙，最初在实践中应用咱们编写的代码进行了试验，证实代码是没有问题的。

援用：

• Koller, D., & Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques (1st ed.). The MIT Press.
• Ermon, S. (2022). Bayesian networks. Github. https://ermongroup.github.io/…
• https://www.overfit.cn/post/7247991e27a74d7da6ae97c87a89eb6f

作者：Naja Møgeltoft