D-分离

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
Chancychen讨论 | 贡献2021年7月21日 (三) 08:55的版本
跳到导航 跳到搜索

d-分离是一套决定准则:对于给定的因果图,决定在给定变量集合Z的情况下,变量集合X和变量集合Y是否独立[1]

d-分离的基本思想

它的基本想法是将统计意义上的“独立性”与图论中的“分离性”(“非连通性”)联系起来。这个基本想法首先需要我们去定义在给定的有向图中给定结点集Z取值下的“激活路径”。d-分离中的“d”实际上指示了我们讨论的目标为有向图。

d-分离的定义

[math]\displaystyle{ \mathbf{X} }[/math][math]\displaystyle{ \mathbf{Y} }[/math],是图[math]\displaystyle{ \mathcal{G} }[/math]中的三个结点集合。如果在给定Z的条件下,任意[math]\displaystyle{ X \in \mathbf{X} }[/math][math]\displaystyle{ Y \in \mathbf{Y} }[/math]两个结点间没有激活路径,则称[math]\displaystyle{ \mathbf{X} }[/math][math]\displaystyle{ \mathbf{Y} }[/math]是给定[math]\displaystyle{ \mathbf{Z} }[/math]下d-分离的,记作[math]\displaystyle{ d-sep_{\mathcal{G}(\mathbf{X}l\mathbf{Y} \mid \mathbf{Z}) } }[/math]

将结点间的一系列独立性关系记作[math]\displaystyle{ \mathcal{I}(\mathcal{G}) }[/math],从而可将独立性和d-分离联系起来:

[math]\displaystyle{ \mathcal{I}(\mathcal{G}) = \left\{ (\mathbf{X} \perp \!\!\! \perp \mathbf{Y} \mid \mathbf{Z}) : d-sep_{\mathcal{G}(\mathbf{X}l\mathbf{Y} \mid \mathbf{Z}) } \right\} }[/math]

d-分离定义的解释

激活路径的定义

假设[math]\displaystyle{ \mathcal{G} }[/math]是一个贝叶斯网络,[math]\displaystyle{ \mathbf{Z} }[/math]是给定的已观测变量集,我们称一条路径[math]\displaystyle{ \mathbf{X}_1 \leftrightarrow \cdots \leftrightarrow \mathbf{X}_n }[/math]是给定[math]\displaystyle{ \mathbf{Z} }[/math]下激活的,当且仅当:

  • 当路径中出现如此形式的V-结构:[math]\displaystyle{ \mathbf{X}_{i-1} \rightarrow \mathbf{X}_{i} \leftarrow \mathbf{X}_{i+1} }[/math]时,[math]\displaystyle{ \mathbf{X}_{i} }[/math]或它的某个子孙结点在[math]\displaystyle{ \mathbf{Z} }[/math]中。
  • 其它任何路径中的结点都不在[math]\displaystyle{ \mathbf{Z} }[/math]中。

根据激活路径的解释

由d-分离的定义可知,[math]\displaystyle{ d-sep_{\mathcal{G}(\mathbf{X}l\mathbf{Y} \mid \mathbf{Z}) } }[/math]实际上指的就是将所有[math]\displaystyle{ \mathbf{X} }[/math][math]\displaystyle{ \mathbf{Y} }[/math]间的激活路径以及相应激活结点集找出,只要保证[math]\displaystyle{ \mathbf{Z} }[/math]中没有激活节点集中的结点,且不含[math]\displaystyle{ \mathbf{X} }[/math][math]\displaystyle{ \mathbf{Y} }[/math]中结点即可做到d-分离。

根据阻断路径的解释

类似激活路径的定义,我们还可以定义阻断路径:

一条路径被一组结点[math]\displaystyle{ \mathbf{Z} }[/math]阻断,当且仅当:

  • 路径中包含链结构或分叉结构,则中间结点包含在[math]\displaystyle{ \mathbf{Z} }[/math]中。
  • 路径中包含对撞结构,则对撞结点及其子孙结点都不在[math]\displaystyle{ \mathbf{Z} }[/math]中。

有了阻断路径的定义,我们可以重新定义d-分离为:

如果[math]\displaystyle{ \mathbf{Z} }[/math]阻断了[math]\displaystyle{ \mathbf{X} }[/math][math]\displaystyle{ \mathbf{Y} }[/math]之间的每一条路径,则称[math]\displaystyle{ \mathbf{X} }[/math][math]\displaystyle{ \mathbf{Y} }[/math]是给定[math]\displaystyle{ \mathbf{Z} }[/math]下d-分离的,[math]\displaystyle{ \mathbf{X} }[/math][math]\displaystyle{ \mathbf{Y} }[/math]在给定[math]\displaystyle{ \mathbf{Z} }[/math]下条件独立。

  1. Koller D, Friedman N. Probabilistic graphical models: principles and techniques[M]. MIT press, 2009.