条件独立(Conditional Independence)

发表于   |   分类于

本文主要是PRML一书8.2节的笔记。
条件独立是概率图模型的一个重要概念，它既简化了模型的结构，也简化了学习(learning)、推断(inference)所需要的计算。

1. 概念

给定三个随机变量 $a$，$b$，$c$，如果$$p(a|b,c)=p(a|c)\tag{1}$$对 $c$ 的所有取值都成立，那么就说给定 $c$ 时，$a$ 与 $b$ 条件独立，记作 $a\perp\!\!\!\perp b\mid c$ 。与之等价的一个判定条件是$$p(a,b|c)=p(a|c)p(b|c)\tag{2}$$如果以条件概率乘积的方式给定一个联合分布，我们可以按定义去测试每个可能的条件独立性是否成立。不过这样的方法耗时太大。图模型的一个重要又优雅的特点就是联合分布的条件独立性可以直观地从图中读出，而不需要进行任何算术分析。实现这一点的一般框架称为有向分离（d-separation）。为引出这个概念，我们先来看三个例子。

2. 三个例图

下面来看三个例图，每个图只含三个节点，但代表了三种最基本的情况。

  1. 同父型（common parent）

    图中，$a$ 和 $b$ 的父节点都是 $c$，对应的联合概率可以写成$$p(a,b,c)=p(a|c)p(b|c)p(c)\tag{3}$$如果未观测到任何变量，我们可以通过对上式两边关于 $c$ 边际化，得到$$p(a,b)=\sum_c p(a|c)p(b|c)p(c)$$上面的结果不总能化成 $p(a)p(b)$，因此$$a\not\!\perp\!\!\!\perp b\mid\emptyset$$这里指的是一般地不具有条件独立性，可能对于某些分布或变量取特定值时，条件独立成立。
    如果我们观测到了 $c$，如下图所示（加阴影表示观测到的变量）

    在给定 $c$ 的情况下，结合(3)式可得$$p(a,b|c)=\cfrac{p(a,b,c)}{p(c)}=p(a|c)p(b|c)$$因此$$a\perp\!\!\!\perp b\mid c$$总的来说，当未观察到 $c$ 时，$a$ 和 $b$ 是不独立的；当观察到 $c$ 后，$a$ 和 $b$ 以 $c$ 为条件条件独立。
    可以这样理解：假设变量都是0-1变量，代表事件$A$，$B$，$C$ 的发生和未发生。由图中可以看出，$C$ 的发生与否会直接影响 $A$ 和 $B$ 发生的概率。如果未观察到 $c$，那么 $A$ 发生与否就会提供关于 $C$ 是否发生的信息，使 $C$ 发生与否的概率产生变化，进而影响 $B$ 发生的概率，因此 $a$ 与 $b$ 是不独立的；另一方面，如果已经观察到 $c$，那么 $A$，$B$ 发生与否都不会影响 $c$，进而不会影响对方，所以 $a$，$b$ 是（条件）独立的。
    一种直观的记忆方法是：从 $a$ 到 $b$ 有一条路径，这条路径上的节点 $c$ 连接了两条箭头的尾端（tail-to-tail）。如果有这样一条路径，则 $a$ 和 $b$ 是相互依赖的；当观察到 $c$ 后，这条路径就被 $c$ 阻塞了，所以 $a$ 和 $b$ 就是（条件）独立的。
  2. 顺序型（cascade）

    它对应的联合分布可以写成$$p(a,b,c)=p(a)p(c|a)p(b|c)\tag{4}$$类似地，如果未观测到任何变量，则关于 $c$ 边际化后得到（详细过程在后面）$$p(a,b)=p(a)\sum_c p(c|a)p(b|c)=p(a)p(b|a)$$不能一般地化为 $p(a)p(b)$，所以 $a\not\!\perp\!\!\!\perp b\mid\emptyset$。
    如果观察到了 $c$，应用贝叶斯定理，类似地有$$\begin{array}{r,l}p(a,b|c)&=&\cfrac{p(a,b,c)}{p(c)} \\ &=&\cfrac{p(a)p(c|a)p(b|c)}{p(c)} \\ &=&p(a|c)p(b|c)\end{array}$$同样，也可以认为从 $a$ 到 $b$ 有一条路径，这条路径上的节点 $c$ 连接了一条箭头的尾端和另一条箭头的头端（head-to-tail），当未观察 $c$ 时路径通畅，$a$ 与 $b$ 互相依赖；当观察 $c$ 后路径阻塞，$a$ 与 $b$ （条件）独立。

    $\begin{array}{r,l}\sum\limits_c p(c|a)p(b|c)&=&\sum\limits_c\cfrac{p(a,b,c)}{p(a)}\quad\qquad\text{应用(4)式得} \\ &=&\cfrac{\sum_c p(a,b,c)}{p(a)} \\ &=& \cfrac{p(a,b)}{p(a)} \\ &=&p(b|a)\end{array}$

  3. V型（V-structure）
    最后一个例子与前两个稍稍不同，如下图

    对应的联合分布可以写成$$p(a,b,c)=p(a)p(b)p(c|a,b)\tag{5}$$先考虑未观察到变量的情况，两边关于 $c$ 边际化，得到$$p(a,b)=p(a)p(b)$$与前两个例子不同，此时 $a$ 与 $b$ 独立，记作 $a\perp\!\!\!\perp b\mid\emptyset$。
    再看观察到 $c$ 后，$$\begin{array}{r,l}p(a,b|c)&=&\cfrac{p(a,b,c)}{p(c)} \\ &=&\cfrac{p(a)p(b)p(c|a,b)}{p(c)}\end{array}$$上式不能一般地化成 $p(a)p(b)$，所以 $a\not\!\perp\!\!\!\perp b\mid c$。
    注意到，第三个例子刚好与前两个例子相反，未观察 $c$ 时 $a$ 与 $b$ 间的路径阻塞，$a$ 与 $b$ 独立；观察 $c$ 后路径反而畅通，$a$ 与 $b$（条件）不独立。
    事实上，还有另外一点微小的不同。为了说明这一点，需要引入后代的概念。如果从节点 $x$ 到 节点$y$ 有一条路径，路径上每一步都沿着箭头的方向，那么就说节点 $y$ 是 $x$ 的后代。对V型结构，观察到 $c$ 或 $c$ 的任一后代都可以使路径变为畅通。下图是一个例子

总结一下：一个tail-to-tail或tail-to-head的节点只有在被观察后才会阻塞路径，一个head-to-head的节点只有其或其后代节点被观察后才不会阻塞路径。

3. 道德图

除了上面的方法，还可以将有向图转换成无向的道德图来判断条件独立性。
转换方法如下：
(1) 找出有向图中所有V型结构，在V型结构的两个父节点之间加上一条无向边
(2) 将所有有向边改为无向边
判断方法：假定道德图中有变量 $x$，$y$ 和变量集合 $\mathbf{z}=\{z_i\}$，若变量 $x$ 和 $y$ 能在图上被 $\mathbf{z}$ 分开，即从道德图中将变量集合 $\mathbf{z}$ 去除后，$x$ 和 $y$ 分属两个连通分支，则 $x\perp\!\!\!\perp y\mid \mathbf{z}$ 成立。
需要注意的是，用道德图判断出来的条件独立性在原有向图中一定是成立的，但反之则不然，有向图中的一些条件独立性不一定能从道德图中判断出来。

4. 有向分离

现在，我们可以给有向分离一个一般化的定义。考虑一个一般的有向图，$A$，$B$，$C$ 是其中任意不交的三个节点集合。我们希望确定在给定的一个有向图中 $A\perp\!\!\!\perp B\mid C$ 是否成立。为此，我们需要考察 $A$ 中任一节点到 $B$ 中任一节点的所有可能路径。称一条路径是阻塞的如果它包含满足下列任意一个条件的一个节点：
(a) 这个节点连接的两个箭头为“尾尾”型或“头尾”型，且这个节点在集合 $C$ 中
(b) 这个节点连接的两个箭头为“头头”型，且它及它的任意一个后代节点均不在集合 $C$ 中
如果所有路径都是阻塞的，就说 $A$ 与 $B$ 被 $C$ 有向分离。

一个有向图既可以表示联合概率的某种展开方式 $\Phi$，也可以表示一系列条件独立性质 $S$。为了形象地说明这一点，我们可以将一个有向图看作一个过滤器（filter）。一方面，输入任意的分布 $p(\mathbf{x})$，有且仅有那些满足展开方式 $\Phi$ 的分布才可以通过，记为 $\mathcal{DF}$；另一方面，输入 $p(\mathbf{x})$，只有满足所有条件独立性质 $S$ 的分布才可以通过，通过的分布实际上就是 $\mathcal{DF}$。如下图所示

5. 马尔科夫毯（Markov blanket）

最后介绍一点马尔科夫毯的概念。考虑一个由含 $D$ 个节点的有向图表示的分布 $p(\mathbf{x}_1,\cdots,\mathbf{x}_D)$，考察下面这个条件分布$$\begin{array}{r,l}p(\mathbf{x}_i|\mathbf{x}_{\{j\neq i\}})&=&\cfrac{p(\mathbf{x}_1,\cdots,\mathbf{x}_D)}{\displaystyle\int p(\mathbf{x}_1,\cdots,\mathbf{x}_D)\mathrm{d}\mathbf{x}_i} \\ &=&\cfrac{\displaystyle\prod_k p(\mathbf{x}_k|\mathrm{pa}_k)}{\displaystyle\int \prod_k p(\mathbf{x}_k|\mathrm{pa}_k)\mathrm{d}\mathbf{x}_i}\end{array}$$

对于连续变量，上式的积分换为求和

注意到，分母中任何与 $\mathbf{x}_i$ 没有函数依赖关系的 $p(\mathbf{x}_k|\mathrm{pa}_k)$ 都可以提到积分外面来，从而与分子上对应的项抵消。最后，式子中将只剩下 $p(\mathbf{x}_i|\mathrm{pa}_i)$ 项和所有 $\mathbf{x}_i$ 以作父节点的 $p(\mathbf{x}_k|\mathrm{pa}_k)$ 项。其中，$p(\mathbf{x}_i|\mathrm{pa}_i)$ 依赖于 $\mathbf{x}_i$ 的父节点，$p(\mathbf{x}_k|\mathrm{pa}_k)$ 不仅依赖于 $\mathbf{x}_i$ 的子节点，也依赖于共父节点（co-parent）。包含父节点、子节点、共父节点的集合称为马尔科夫毯，如下图所示

可以把节点 $\mathbf{x}_i$ 对应的马尔科夫毯看作是将这个节点与图其他部分分割开的最小节点集合。

参考资料

  1. Pattern Recognition and Machine Learning (PRML)
  2. 《机器学习》by 周志华
  3. Structured Representations