条件独立与马尔科夫随机场

本期将介绍的内容是条件独立与马尔科夫随机场。

在概率图模型的推断中，条件独立是不可绕开的话题，它降低了计算量，减少了参数，也增加了图模型的可解释性，这期将重点介绍几种图结构的条件独立性以及如何更好地判断图的条件独立性。

然后，我还会介绍图结构除了有向图模型外的一类模型——无向图模型，在某些情况下，无向图模型能够简化问题的复杂程度。

条件独立

在多变量概率分布中，为了方便对图进行模块化与降低计算量，我们可以引入“条件独立”的概念，考虑有这样的一个图

图片.png

在该图中，有三个变量 $a,b,c$ ，这三个变量满足以下公式：
$p(a|b,c)=p(a|c)\tag{1}$
在这里，当给定变量 $b,c$ 的条件下时， $a$ 的概率分布不依赖于 $b$ 的值。我们可以说，在给定变量 $c$ 的条件下， $a$ 条件独立于 $b$ 。当三个变量满足以上条件时，在给定 $c$ 的条件下，变量 $a$ 和变量 $b$ 的联合概率分布可以分解为 $a$ 的边缘概率分布与 $b$ 的边缘概率分布的乘积，即
$p(a,b|c)=p(a|b,c)p(b|c)=p(a|c)p(b|C)\tag{2}$
注意，在公式（1）中，我们对独立性的定义是对 $c$ 的所有可能取值成立，而不是对 $c$ 的特定值成立。“在给定变量 $c$ 的条件下， $a$ 条件独立于 $b$ ”，可以简记为
$a\perp\!\!\!\!\perp b|c\tag{3}$
在模式识别中，使⽤概率模型时，条件独⽴性起着重要的作⽤。它简化了模型的结构，降低了模型的训练和推断的计算量。

三种图的典型结构

分叉结构（Fork）

图片.png

考虑图中的结构，该结构为分叉结构（Fork），我们可以很容易地得到该图所有变量的联合分布
$p(a,b,c)=p(a|c)p(b|c)p(c)\tag{4}$
当我们需要去除观测变量 $c$ 的混淆影响时，我们可以对对公式（4）进行积分或求和，得到在 $c$ 未被观测的条件下， $a$ 和 $b$ 的联合分布为
$p(a,b)=\sum_cp(a|c)p(b|c)p(c)\tag{5}$
一般地，当 $a$ 和 $b$ 的联合分布无法分解为 $p(a)p(b)$ 时， $a$ 和 $b$ 相互依赖，记为
$a\not\!\!{\perp\!\!\!\!\perp\,} b|\emptyset\tag{6}$
现在我们再计算以 $c$ 为条件， $a$ 和 $b$ 的条件概率分布为
$\begin {aligned} p(a,b|c)&=\frac{p(a,b,c)}{p(c)}\\ &=p(a|c)p(b|c) \end {aligned}\tag{7}$
因此我们可以得到该图结构中的条件独立性质
$a\perp\!\!\!\!\perp b|c\tag{8}$
让我们再考虑这样一条路径，从结点 $a$ 经过 $c$ 到结点 $b$ ，在这条路径中，结点 $c$ 被称为关于这个路径“尾到尾”（tail-to-tail）。通过上述分析我们可以知道，在这条对于结点 $c$ ”尾到尾“的路径中，如果我们已经知道 $c$ 的取值，那相当于”阻断“了从 $a$ 到 $b$ 的路径，使得 $a$ 与 $b$ 之间变得独立了。

链式结构（Chain）

图片.png

如图结构被称为链式结构（Chain），根据概率公式，我们可以很容易得到该图结果的联合概率分布
$p(a,b,c)=p(a)p(c|a)p(b|c)\tag{9}$
同理，为了考察 $a$ 和 $b$ 的独立性，我们可以通过对公式（9）进行加和或积分得到 $a$ 和 $b$ 的联合概率分布，即
$p(a,b)=p(a)=\sum_cp(c|a)p(b|c)\tag{10}$
一般情况下，该分布无法分解为 $p(a)p(b)$ ，故
$a\not\!\!{\perp\!\!\!\!\perp\,} b|\emptyset\tag{11}$
现在，让我们再计算该图的条件独立性，根据公式（9）即贝叶斯公式，我们可以得到
$\begin {aligned} p(a,b|c)&=\frac{p(a,b,c)}{p(c)}\\ &=\frac{p(a)p(c|a)p(b|c)}{p(c)}\\ &=p(a|c)p(b|c) \end {aligned}\tag{12}$
于是我们可以得到条件独立性质
$a\perp\!\!\!\!\perp b|c\tag{13}$
在该图中，存在一条从结点 $a$ 经过 $c$ 到结点 $b$ 的路径，结点 $c$ 关于这条路径“头到尾”。在一条“头到尾”的路径中，如果我们已经观测结点 $c$ ，那相当于”阻断“了从 $a$ 到 $b$ 的路径，使得 $a$ 与 $b$ 之间变得独立。

不道德结构（Immorality）

图片.png

如图结构为不道德结构（Immorality），显然我们可以得到联合概率分布
$p(a,b,c)=p(a)p(b)p(c|a,b)\tag{14}$
对公式（14）关于 $c$ 进行加和或积分
$p(a,b)=p(a)p(b)\tag{15}$
当 $c$ 没有被观测时， $a$ 和 $b$ 是独立的
$a\perp\!\!\!\!\perp b|\emptyset\tag{16}$
当 $c$ 被观测到时， $a$ 和 $b$ 的条件概率分布为
$\begin {aligned} p(a,b|c)&=\frac{p(a,b,c)}{p(c)}\\ &=\frac{p(a|c)p(b|c)p(c|a,b)}{p(c)} \end {aligned}\tag{17}$
一般无法分解为 $p(a)p(b)$ ，因此
$a\not\!\!{\perp\!\!\!\!\perp\,} b|c\tag{18}$
在该图中，我们说结点 $c$ 关于从 $a$ 到 $b$ 的路径是“头到头”的。在一条“头到头”的路径中，当结点 $c$ 未被观测时，该路径被“阻断”，从⽽变量 $a$ 和 $b$ 是独立的。

d-分离（d-separationn）

为了能更加简便地分析概率图，我们引入了d-分离的概念。

d-分离的概念

在一个有向无环图中，有 A、B、C 是任意无交集的结点集合。为了分析图模型是否暗示了一个特定的条件依赖表述 $A\perp\!\!\!\!\perp B|C$ ，我们考虑从 A 中的任意结点到 B 中的任意结点的所有可能路径。如果一条路径包含一个结点满足下面两个特性中的任何一个，则我们说这条路径被“阻断”：

路径的箭头以头到尾（ $a\rightarrow b\rightarrow c$ ）或者尾到尾（ $a\leftarrow b\rightarrow c$ ）的方式交汇于这个结点，且这个结点在集合 $C$ 中
路径的箭头以头到头（ $a\rightarrow b\leftarrow c$ ）的方式交汇（或对撞）于这个结点，且这个结点和它的所有后继结点都不再集合 $C$ 中

如果所有路径都被“阻断”，那么我们说 $A$ 和 $B$ 在 $C$ 的条件下是d-分离的，因此有 $A\perp\!\!\!\!\perp B|C$

d-分离的例子

考虑如下图结构

图片.png

为了考察条件独立规则 $a\perp\!\!\!\!\perp b|c$ 是否成立，我们考虑从 $a$ 到 $b$ 的路径，首先考虑结点 $f$ ，由于这个结点是一个尾到尾的结点且未被观测到，根据上述d-分离的规则 1 ，结点 $f$ 无法阻断路径；再考虑结点 $e$ ，由于该结点为头到头的结点（对撞结构），我们采用规则 2 ，可以看到，虽然结点 $e$ 未被观测到，但其后继结点 $c$ 被观测到，所以 $e$ 也没有阻断这条路径，因此，规则 $a\perp\!\!\!\!\perp b|c$ 在图中不成立。

我们再考虑第二个图结构

图片.png

在该图中，结点 $f$ 被观测到，由于该结点为尾到尾的结点，所以根据d-分离的规则我们可以知道结点 $f$ 截断了路径，从而得到条件独立规则 $a\perp\!\!\!\!\perp b|f$

马尔科夫毯（Markov blanket）

为了针对某一结点研究其条件独立性，我们可以引入马尔科夫毯（Markov blanket）的概念。

考虑一个联合概率分布 $p(x_1,\dots,x_D)$ ，它由一个具有 $D$ 个结点的有向图表示。考虑变量 $x_i$ 对应的结点上的条件概率分布，其中条件为所有剩余的变量 $x_{j\neq i}$ ，我们可以进行概率分解
$\begin {aligned} p(x_i|x_{j\neq i})&=\frac{p(x_1,\dots,x_D)}{\int p(x_1,\dots,x_D)d\,x_i}\\ &=\frac{\prod_kp(x_k|pa_k)}{\int\prod_kp(x_k|pa_k)d\,x_i} \end{aligned}\tag{19}$
对于这个式子，我们现在观察到任何与 $x_i$ 没有函数依赖关系的因子都可以提到 $x_i$ 的积分外，从而在分子与分母之间消去。剔除掉多余的因子后，剩下的因子可以分为两部分：

结点 $x_i$ 本身的条件概率分布 $p(x_i|pa_i)$ ，条件概率分布 $p(x_i|pa_i)$ 依赖于 $x_i$ 的父结点
条件概率分布 $p(x_k|pa_k)$ ，其中 $x_k$ 是 $x_i$ 的子结点。条件概率分布 $p(x_k|pa_k)$ 依赖于 $x_i$ 的子结点以及同父结点（co-parents），即那些对应于 $x_k$ （而不是 $x_i$ ）的父结点的变量。

由上述的推导，我们可以得到马尔科夫毯的概念：对于一个结点，由其父结点、子结点、同父结点组成的结点集合，如下图所示。

图片.png

马尔科夫毯的性质为：以图中所有剩余结点为条件， $x_i$ 的条件概率依赖于马尔科夫毯中的变量。

马尔科夫随机场

承接上一篇博客贝叶斯网（有向图模型）的内容，我们来介绍图模型的第二大类，使用无向图描述的图模型。

一个马尔科夫随机场（Markov random field），也称为马尔科夫网络（Markov network）或者无向图模型（undirected graphical model），包含一组结点，每个结点都对应一个变量或一组变量。结点之间的链接是无向的，马尔科夫随机场的分解方式允许我们使用无向图来表示一组条件独立关系。

条件独立性质

在有向图模型中，我们通常采用d-分离来判断一个特定的条件独立性质，但由于头到头结点的存在，阻断的定义难免有些复杂。于是我们可以用另一种概率分布的图语义表示，使得条件独⽴性由单⼀的图划分确定。在有向图模型中，边的方向性被移除，父结点和子结点的非对称性也被移除，因此头到头的微妙性不再存在。

假设在一个有向图中，我们有 A、B、C 任意无交集的三个结点集合，考察条件独立性质
$A\perp\!\!\!\!\perp B|C$
为了判断由图定义的概率分布是否满足这个性质，我们需要考虑连接集合 $A$ 和 $B$ 的结点的所有路径：

如果所有这些路径都通过 $C$ 中的一个或多个结点，那么所有这样的路径都被“阻断”，则条件独立性成立
如果存在至少一条未被阻断的路径，则条件独立性未必成立

如下图所示的图结构，即为 $A\perp\!\!\!\!\perp B|C$ 成立的一个例子

图片.png

由于结点只条件依赖于相邻结点，⽽条件独⽴于任何其他的结点，我们可以得到无向图模型的马尔科夫毯：对于⼀个⽆向图，结点 $x_i$ 的马尔科夫毯由相邻结点的集合组成。其性质与有向图模型的马尔科夫毯类似：以图中所有剩余结点为条件， $x_i$ 的条件概率依赖于马尔科夫毯中的变量。

图片.png

分解性质

为了进行无向图的概率计算，我们需要将联合概率分布 $p(x)$ 分解为在图的局部范围内的变量集合上定义的函数的乘积。

我们先考虑在有向图中的两个结点 $x_i$ 和 $x_j$ ，它们不存在链接。由条件独立性质，我们可以知道，给定图中的所有其他结点，这两个结点⼀定是条件独⽴的，可以表示为
$p(x_i,x_j|\boldsymbol x_{/\{i,j\}})=p(x_i|\boldsymbol x_{/\{i,j\}})p(x_j|\boldsymbol x_{/\{i,j\}})$
显然可知联合概率分布的分解⼀定要让 $x_i$ 和 $x_j$ 不出现在一个影子中，从⽽让属于这个图的所有可能的概率分布都满⾜条件独⽴性质。

于是，我们引入了团块（clique）的概念：在无向图中，包含的每对结点之间都存在链接的结点子集，即为团块。此外，还有最⼤团块（maximal clique）的性质如下：不可能将图中的任何⼀个其他的结点包含到这个团块中而不破坏团块的性质。

如下图所示，图中有五个具有两个结点的团块，即 $\{x_1, x_2\}, \{x_2, x_3\}, \{x_3, x_4\}, \{x_4, x_2\}, \{x_1, x_3\}$ ，还有两个最大团块 $\{x_1, x_2, x_3\}$ 和 $\{x_2, x_3, x_4\}$

图片.png

于是，让我们把团块记作 $C$ ，将团块中的变量集合记作 $\boldsymbol x_C$ ，联合概率分布可以写成图的最⼤团块的势函数 $\psi_C(\boldsymbol x_C)$ 的乘积的形式
$p(\boldsymbol x)=\frac1Z\prod_C\psi_C(\boldsymbol x_C)\tag{20}$
这里， $Z$ 有时被称为划分函数，是一个归一化常数，等于
$Z=\sum_{\boldsymbol x}\prod_C\psi_C(\boldsymbol x_C)\tag{21}$
由于无向图模型并不要求势函数是具有具体的概率含义，所以我们需要采用公式（21）的函数进行归一化处理。归⼀化常数的存在是⽆向图的⼀个主要的缺点。如果我们的模型中有 $M$ 个离散结点，每个结点有 $K$ 个状态，那么归⼀化项的计算涉及到对 $K^M$ 个状态求和，因此（在最坏的情况下），其时间复杂度是指数级的。

无向图模型要求势函数被限制为严格大于零的，因此将势函数表示为指数的形式更方便，即
$\psi_C(\boldsymbol x_C)=\exp\{-E(\boldsymbol x_C)\}\tag{22}$
其中 $E(\boldsymbol x_C)$ 被称为能量函数，指数表示被称为玻尔兹曼分布。联合概率分布被定义为势函数的乘积，因此总的能量可以通过将每个最⼤团块的能量（势函数的中的指数）相加的方法得到。

图像去噪

无向图模型可用于图像去噪，这里不过多赘述，具体见 PRML

将有向图转换为无向图

考虑下面的问题：取⼀个使用有向图描述的模型，尝试将其转化为无向图

首先考虑如下图（a）的有向图结构

图片.png

明显其联合概率分布可以表示为
$p(\boldsymbol x)=p(x_1)p(x_2|x_1)p(x_3|x_2)\cdots p(x_N|x_{N-1})\tag{23}$
现在我们需要将其转换为无向图结构，在无向图中，最大团块为相邻结点对。根据公式（20），我们希望得到下列联合概率分布形式
$p(\boldsymbol x)=\frac1Z\psi_{1,2}(x_1,x_2)\psi_{2,3}(x_2,x_3)\cdots\psi_{N-1,N}(x_{N-1},x_N)$
这里，我们只需令（假设划分函数为1）
$\begin {aligned} \psi_{1,2}(x_1,x_2)&=p(x_1)p(x_2|x_1)\\ \psi_{2,3}(x_2,x_3)&=p(x_3|x_2)\\ \vdots\\ \psi_{N-1,N}(x_{N-1},x_N)&=p(x_N|x_{N-1})\\ \end{aligned}$
注意，这里将第⼀个结点的边缘概率分布 $p(x_1)$ 放到了第⼀个势函数中

于是我们可以将有向图转换为无向图，如上图（b）

接下来，让我们推广这一规律，考虑下列有向图

图片.png

我们可以进行类似上述的分解方式，为了保证转换过程的合法性，我们必须保证在每个条件概率分布的变量中的集合时无向图中至少一个团块的成员。

在链式结构中，由于有向图每个结点最多只有一个父结点，可以通过将有向链接替换为无向链接的方式完成。但对于有向图中具有多个父结点的结点来说，还需要考虑其他要素。我们先写出该有向图的联合概率分布
$p(\boldsymbol x)=p(x_1)p(x_2)p(x_3)p(x_4|x_1x_2x_3)$
我们看到条件概率分布涉及到四个变量 $x_1,x_2,x_3,x_4$ ，所以这四个变量必须是至少一个团块中的成员，为了确保这一点，我们将 $x_4$ 的所有父结点之间添加额外的链接，于是我们得到

图片.png

这个在父结点之间添加链接的过程称为“伦理”，去掉箭头后生成的无向图被称为道德图。很重要的⼀点是，这个例子中的道德图是完全链接的，因此没有表现出条件独立性质，这与原始的有向图相反。