7. 因子图¶

至此我们已经讨论了概率图模型的两类图形–有向图和无向图，这两类都是从条件独立性的角度表征概率分布。本章节我们开始讨论另一类图模型–因子图(Factor graph)，因子图不关注条件独立属性，直接表达概率分布的因子分解。

7.1. 因子图的定义¶

有向图和无向图都使得若干个变量的一个全局函数(联合概率分布)表示为这些变量子集上的因子的乘积。因子图显示的表示出了这个分解，方法是：在表示变量的结点的基础上，引入额外的结点表示因子本身。因子图能够用来表达上述传统的有向和无向图模型无法表达的结构。

一个因子图包含一个随机变量集合 \(\mathbf{x}=\left(\mathrm{x}_{1}, \dots, \mathrm{x}_{N}\right)\) 以及一张图 \(\mathcal{G}=(\mathcal{V}, \mathcal{E}, \mathcal{F})\) ，除了变量结点集合 \(\mathcal{V}\) 以外还含有因子结点集合 \(\mathcal{F}\) 。此外，该图被约束为变量节点和因子节点之间的二分图，即 仅有变量结点和因子结点之间存在边 。

../_images/4_1.jpg — 图 7.1.1 一般因子图。 \(f_a\) 是关于 \(X_1\) 和 \(X_3\) 的函数， \(f_b\) 是关于 \(X_3\) 和 \(X_4\) 的函数， \(f_c\) 是关于 \(X_2,X_4\) 和 \(X_5\) 的函数， \(f_d\) 是关于 \(X_1\) 和 \(X_3\) 的函数，¶

其中，圆形结点代表随机变量，方形结点代表”因子”，所谓”因子(factor)”其实就是定义在一些变量上的函数，可以类比于无向图中的势函数 \(\psi\) 。与因子图相关联的联合概率分布由下式给出，联合概率分布就是图中所有因子的乘积乘以一个归一化系数Z。

(7.1.24)¶\[p\left(x_{1}, \ldots, x_{N}\right)=\frac{1}{Z} \prod_{j=1}^{m} f_{j}\left(x_{f_{j}}\right)\]

因子图直接表达概率分布的分解方式，因子图中因子函数不需要像无向图那样定义在团(clique)上的，也不需要向有向图那样定义在局部条件概率上。每个因子函数可以定义在任意结点上，同一个节点集上也可以定义多个不同的因子。相比有向图和无向图，能表达出更细粒度的分解。因子图的这个特性，使得编码某些类型（特别是代数）约束非常容易。

7.2. 图模型之间的转换¶

7.2.1. 转换为因子图¶

首先，我们先写出上图中无向图(左)的概率分布的因子分解式:

(7.2.10)¶\[p_{\mathbf{x}}(\mathbf{x}) \propto f_{134}\left(x_{1}, x_{3}, x_{4}\right) f_{234}\left(x_{2}, x_{3}, x_{4}\right)\]

直观的看上去，无向图的因子分解式和因子图的分解式具有相同的模式，我们只需要把势函数(potentials)看做是因子结点(factor nodes)。通常，我们可以通过为每个最大团定义因子节点，将无向图模型转换为因子图。

类似的，为了将有向图转换为因子图，变量结点维持不变，我们添加额外的因子结点对应于条件概率分布，最后添加上合适的边。 同一个无向图可能存在多个不同的因子图。同一个有向图也可能存在多个不同的因子图。

../_images/4_a1.png — 图 7.2.3 (a)一个无向图，仅有一个最大团的 \(\psi\left(x_{1}, x_{2}, x_{3}\right)\) 。 (b)表示和无向图相同概率分布的因子图，其因子满足 \(f\left(x_{1}, x_{2}, x_{3}\right)=\psi\left(x_{1}, x_{2}, x_{3}\right)\) 。 (c)表示相同概率分布的另一个的因子图，其因子满足 \(f_{a}\left(x_{1}, x_{2}, x_{3}\right) f_{b}\left(x_{1}, x_{2}\right)=\psi\left(x_{1}, x_{2}, x_{3}\right)\) 。¶

../_images/4_a2.png — 图 7.2.4 (a)一个有向图，可以分解为 \(p\left(x_{1}\right) p\left(x_{2}\right) p\left(x_{3} | x_{1}, x_{2}\right)\) 。 (b)一个因子图，表示相同的概率分布，它的因子满足 \(f\left(x_{1}, x_{2}, x_{3}\right)=p\left(x_{1}\right) p\left(x_{2}\right) p\left(x_{3} | x_{1}, x_{2}\right)\) 。 (c)另一个因子图，表示相同的概率分布，其因子满足 \(f_{a}\left(x_{1}\right)=p\left(x_{1}\right), f_{b}\left(x_{2}\right)=p\left(x_{2}\right), f_{c}\left(x_{1}, x_{2}, x_{3}\right)=p\left(x_{3} | x_{1}, x_{2}\right)\)¶

7.2.2. 因子图转换为有向图¶

选定拓扑顺序为 \(\mathrm{x}_{1}, \ldots, \mathrm{x}_{n}\) 的一系列结点。按照顺序对于每个结点，找到一个最小的集合 \(U \subset\left\{\mathrm{x}_{1}, \ldots, \mathrm{x}_{i-1}\right\}\) 使得 \(\mathrm{x}_{i} \perp \!\!\! \perp \left\{\mathrm{x}_{1}, \ldots \mathrm{x}_{i-1}\right\}-U | U\) 得到满足，并且把 \(U\) 中的结点设置为 \(\mathrm{x}_{i}\) 的父结点。

这相当于使用因子图所暗示的条件独立性尽可能地减少每个 \(p（\mathrm{x}_i | \mathrm{x}_1，...，\mathrm{x}_{i-1})\) 的复杂性。参考图3的示例。

../_images/4_5.png — 图 7.2.5 把一个因子图转换为一个有向图，然后再把有向图转换为无向图¶

7.3. 图模型的评价¶

重要

重要的是要认识到转换过程不是无损的。

在这些构造中，原始图形满足转换图形所隐含的任何条件独立性。但是，通常，转换后的图形不会包含原始图形中包含的某些条件独立性。

我们怎么知道我们已经提出了“好”的转换。我们希望转换的图形接近原始图形以获得一些接近的定义。我们将通过I-maps，D-maps和P-map探索这些概念。

7.3.1. I-map¶

考虑一个概率分布D和一个图模型 \(\mathcal{G}\) ，令 \(CI(D)\) 表示分布D满足的条件独立性集合，令 \(CI(\mathcal{G})\) 表示图 \(\mathcal{G}\) 实现的条件独立性集合。

定义1 I-map:

如果满足 \(CI(\mathcal{G}) \subset CI(D)\) ，我们说图 \(\mathcal{G}\) 是分布D的一个 独立图(independence map) 或者说是 I-map 。换句话说，图 \(\mathcal{G}\) 所暗含的每个条件独立性，分布D也同样都满足。分布是超集，图是子集。

完全图始终是任何分布的I-map的示例，因为它意味着没有条件独立性。

7.3.2. D-map¶

定义2 D-map:

如果满足 \(CI(\mathcal{G}) \supset CI(D)\) ，我们说图 \(\mathcal{G}\) 是分布D的一个 依赖图(dependence map) 或者说是 D-map。换句话说，分布D所满足的所有条件独立性图 \(\mathcal{G}\) 也满足。 分布是子集，图是超集。

没有边的图是任何分布的D图的示例，因为它意味着每个结点都条件独立性。

7.3.3. P-map¶

定义3 P-map:

如果满足 \(CI(\mathcal{G}) = CI(D)\) ，我们说图 \(\mathcal{G}\) 是分布D的一个 完美图(perfect map) 或者说是 P-map。

示例：考虑三个不同的分布，分别具有如下因子:

(7.3.1)¶\[\begin{split}\begin{array}{l}{p_{1}=p_{\mathrm{x}} p_{\mathrm{y}} p_{\mathrm{z}}} \\ {p_{2}=p_{\mathrm{z} | \mathrm{x}, \mathrm{y}} p_{\mathrm{x}} p_{\mathrm{y}}} \\ {p_{3}=p_{\mathrm{z} | \mathrm{x}, \mathrm{y}} p_{\mathrm{x} | \mathrm{y}} p_{\mathrm{y}}}\end{array}\end{split}\]

下图中，左(a)是 \(p_1\) 的一个I-map，是 \(p_3\) 的一个D-map， \(p_2\) 的一个P-map；根据，Hammersley-Clifford定理右(b)是下面分布的一个I-map。

(7.3.2)¶\[p(x, y, w, z)=\frac{1}{Z} f_{1}(x, w) f_{2}(w, y) f_{3}(z, y) f_{4}(x, z)\]