######################################################## 因子图 ######################################################## 至此我们已经讨论了概率图模型的两类图形--有向图和无向图,这两类都是从条件独立性的角度表征概率分布。 本章节我们开始讨论另一类图模型--因子图(Factor graph),因子图不关注条件独立属性,直接表达概率分布的因子分解。 因子图的定义 ######################################################## 有向图和无向图都使得若干个变量的一个全局函数(联合概率分布)表示为这些变量子集上的因子的乘积。 因子图显示的表示出了这个分解,方法是:在表示变量的结点的基础上,引入额外的结点表示因子本身。 因子图能够用来表达上述传统的有向和无向图模型无法表达的结构。 一个因子图包含一个随机变量集合 :math:`\mathbf{x}=\left(\mathrm{x}_{1}, \dots, \mathrm{x}_{N}\right)` 以及 一张图 :math:`\mathcal{G}=(\mathcal{V}, \mathcal{E}, \mathcal{F})` , 除了变量结点集合 :math:`\mathcal{V}` 以外还含有因子结点集合 :math:`\mathcal{F}` 。 此外,该图被约束为变量节点和因子节点之间的二分图,即 **仅有变量结点和因子结点之间存在边** 。 .. figure:: pictures/4_1.jpg :scale: 30 % :align: center 一般因子图。 :math:`f_a` 是关于 :math:`X_1` 和 :math:`X_3` 的函数, :math:`f_b` 是关于 :math:`X_3` 和 :math:`X_4` 的函数, :math:`f_c` 是关于 :math:`X_2,X_4` 和 :math:`X_5` 的函数, :math:`f_d` 是关于 :math:`X_1` 和 :math:`X_3` 的函数, 其中,圆形结点代表随机变量,方形结点代表"因子",所谓"因子(factor)"其实就是定义在一些变量上的函数,可以类比于无向图中的势函数 :math:`\psi` 。 与因子图相关联的联合概率分布由下式给出,联合概率分布就是图中所有因子的乘积乘以一个归一化系数Z。 .. math:: p\left(x_{1}, \ldots, x_{N}\right)=\frac{1}{Z} \prod_{j=1}^{m} f_{j}\left(x_{f_{j}}\right) .. topic:: 因子图上的一些约束 - 这些因子函数的值必须是非负的,除此条件外我们可以自由选择它们。这点类似无向图中的势函数 :math:`\psi` 。 - 我们也可以将配分函数Z转换为其中一个因子,这将限制其中一个因子。 因子图直接表达概率分布的分解方式,因子图中因子函数不需要像无向图那样定义在团(clique)上的, 也不需要向有向图那样定义在局部条件概率上。每个因子函数可以定义在任意结点上, 同一个节点集上也可以定义多个不同的因子。相比有向图和无向图,能表达出更细粒度的分解。 因子图的这个特性,使得编码某些类型(特别是代数)约束非常容易。 图模型之间的转换 ######################################################## 转换为因子图 =================================== .. figure:: pictures/4_3.png :scale: 30 % :align: center 用因子图表达无向图 首先,我们先写出上图中无向图(左)的概率分布的因子分解式: .. math:: 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)。 通常,我们可以通过为每个最大团定义因子节点,将无向图模型转换为因子图。 类似的,为了将有向图转换为因子图,变量结点维持不变,我们添加额外的因子结点对应于条件概率分布,最后添加上合适的边。 **同一个无向图可能存在多个不同的因子图。同一个有向图也可能存在多个不同的因子图。** .. figure:: pictures/4_a1.png :scale: 30 % :align: center (a)一个无向图,仅有一个最大团的 :math:`\psi\left(x_{1}, x_{2}, x_{3}\right)` 。 (b)表示和无向图相同概率分布的因子图,其因子满足 :math:`f\left(x_{1}, x_{2}, x_{3}\right)=\psi\left(x_{1}, x_{2}, x_{3}\right)` 。 (c)表示相同概率分布的另一个的因子图,其因子满足 :math:`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)` 。 .. figure:: pictures/4_a2.png :scale: 30 % :align: center (a)一个有向图,可以分解为 :math:`p\left(x_{1}\right) p\left(x_{2}\right) p\left(x_{3} | x_{1}, x_{2}\right)` 。 (b)一个因子图,表示相同的概率分布,它的因子满足 :math:`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)另一个因子图,表示相同的概率分布,其因子满足 :math:`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)` 因子图转换为有向图 =================================== 选定拓扑顺序为 :math:`\mathrm{x}_{1}, \ldots, \mathrm{x}_{n}` 的一系列结点。 按照顺序对于每个结点,找到一个最小的集合 :math:`U \subset\left\{\mathrm{x}_{1}, \ldots, \mathrm{x}_{i-1}\right\}` 使得 :math:`\mathrm{x}_{i} \perp \!\!\! \perp \left\{\mathrm{x}_{1}, \ldots \mathrm{x}_{i-1}\right\}-U | U` 得到满足,并且把 :math:`U` 中的结点设置为 :math:`\mathrm{x}_{i}` 的父结点。 这相当于使用因子图所暗示的条件独立性尽可能地减少每个 :math:`p(\mathrm{x}_i | \mathrm{x}_1,...,\mathrm{x}_{i-1})` 的复杂性。参考图3的示例。 .. figure:: pictures/4_5.png :scale: 30 % :align: center 把一个因子图转换为一个有向图,然后再把有向图转换为无向图 图模型的评价 ######################################################## .. important:: **重要的是要认识到转换过程不是无损的。** 在这些构造中,原始图形满足转换图形所隐含的任何条件独立性。 但是,通常,转换后的图形不会包含原始图形中包含的某些条件独立性。 我们怎么知道我们已经提出了“好”的转换。 我们希望转换的图形接近原始图形以获得一些接近的定义。 我们将通过I-maps,D-maps和P-map探索这些概念。 I-map =================================== 考虑一个概率分布D和一个图模型 :math:`\mathcal{G}` ,令 :math:`CI(D)` 表示分布D满足的条件独立性集合, 令 :math:`CI(\mathcal{G})` 表示图 :math:`\mathcal{G}` 实现的条件独立性集合。 **定义1 I-map**: 如果满足 :math:`CI(\mathcal{G}) \subset CI(D)` ,我们说图 :math:`\mathcal{G}` 是分布D的一个 **独立图(independence map)** 或者说是 I-map 。 换句话说,图 :math:`\mathcal{G}` 所暗含的每个条件独立性 ,分布D也同样都满足。*分布是超集,图是子集。* 完全图始终是任何分布的I-map的示例,因为它意味着没有条件独立性。 D-map =================================== **定义2 D-map**: 如果满足 :math:`CI(\mathcal{G}) \supset CI(D)` ,我们说图 :math:`\mathcal{G}` 是分布D的一个 **依赖图(dependence map)** 或者说是 D-map。换句话说,分布D所满足的所有条件独立性图 :math:`\mathcal{G}` 也满足。 *分布是子集,图是超集。* 没有边的图是任何分布的D图的示例,因为它意味着每个结点都条件独立性。 P-map =================================== **定义3 P-map**: 如果满足 :math:`CI(\mathcal{G}) = CI(D)` ,我们说图 :math:`\mathcal{G}` 是分布D的一个 **完美图(perfect map)** 或者说是 P-map。 示例: 考虑三个不同的分布,分别具有如下因子: .. math:: \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} 下图中,左(a)是 :math:`p_1` 的一个I-map,是 :math:`p_3` 的一个D-map, :math:`p_2` 的一个P-map; 根据,Hammersley-Clifford定理右(b)是下面分布的一个I-map。 .. math:: p(x, y, w, z)=\frac{1}{Z} f_{1}(x, w) f_{2}(w, y) f_{3}(z, y) f_{4}(x, z) .. figure:: pictures/4_7.png :scale: 30 % :align: center 两个图例。