因子图介绍

2.1k words in total, 8 minutes required.

在概率图中，求某个变量的边缘分布是常见的问题。这问题有很多求解方法，其中之一就是把贝叶斯网络或马尔科夫随机场转换成因子图，然后用sum-product算法求解。换言之，基于因子图可以用sum-product算法（也称为信念传播算法）高效的求各个变量的边缘分布^[2]。

1. 因子图定义

参见Wiki的定义^[1]，将一个具有多变量的全局函数因子分解，得到几个局部函数的乘积，以此为基础得到的一个双向图叫做因子图（Factor Graph）。

对于函数$g(X_1, \ldots, X_n)$，有以下式子成立：

$g(X_1, \ldots, X_n) = \prod_{j=1}^{m}f_{j}(S_j)$
其中，$S_j \subseteq \{ X_1, \ldots, X_n \}$。

由以上，我们可以将因子图表示为三元组 $G = (X, F, E)$：

• $X = \{ X_1, \ldots, X_n \}$ 表示变量结点（variable vertices）
• $F = \{f_1, \ldots, f_m \}$ 表示因子结点（factor vertices）
• $E$为边的集合，如果某一个变量结点$X_k$被因子结点$f_j$的集合$S_j$包含，那么就可以在$X_k$和$f_j$之间加入一条无向边

2. 举例

引用自^[2]中的例子，现在有一个全局函数$g(x_1, \ldots, x_5)$，其因式分解方程为:

$g(x_1, x_2, x_3, x_4, x_5) = f_A(x_1)f_B(x_2)f_C(x_1, x_2, x_3)f_D(x_3, x_4)f_E(x_3, x_5)$

其中，各函数表述变量间的关系，可以是条件概率或者其他关系（例如在马尔科夫随机场中的势函数）。

则其对应的因子图如下图所示。

因子图示例

也可以等价于：

在因子图中，所有的顶点不是变量结点就是因子结点，边表示它们之间的函数关系。

3. 有向图、无向图和条件随机场

接下来，我们再来了解一下概率图模型中的有向图、无向图，及其其对应的各类模型结构。

• 有向图模型，又称作贝叶斯网络（Directed Graphical Models, DGM, Bayesian Network）

贝叶斯网络的有向图模型

• 但在某些情况下，强制加入结点的边方向是不合适。无向图模型（Undirected Graphical Model, UGM），又称作马尔科夫随机场或者马尔科夫网络（Markov Random Field, MRF or Markov Network）

马尔科夫随机场的无向图模型

• 设$\mathbf{X} = (X_1, \ldots, X_n)$和$\mathbf{Y} = (Y_1, \ldots, Y_m)$都是联合随机变量，若随机变量$\mathbf{Y}$构成一个无向图$G = (V, E)$表示的马尔科夫随机场，则条件概率分布$P(\mathbf{Y} \mid \mathbf{X})$称之为条件随机场（Conditional Random Field, CRF）。

线性链条件随机场的无向图模型

4. 因子图的转换

4.1 贝叶斯网络示例

给出上面图中的贝叶斯网络，根据各个变量间的关系，我们可以得到

$p(u,w,x,y,z) = p(u)p(w)p(x \mid u,w)p(y \mid x)p(z \mid x)$

表示为因子图，以下两种形式皆可：

由上述例子总结出由贝叶斯网络构造因子图的方法：

• 贝叶斯网络中的一个因子（可以理解为函数）对应因子图中的一个结点
• 贝叶斯网络中的每一个变量在因子图上对应边或者半边
• 结点$g$和边$x$相连当且仅当变量$x$出现在因子$g$中。

4.2 马尔科夫链示例

以下是一个马尔科夫链转换的示例：

其对应的全局函数可以表示为：

$p_{XYZ}(X,Y,Z) = p_{X}(X)p_{XY}(Y \mid X)p_{YZ}(Z \mid Y)$

4.2 隐马尔可夫模型示例

其对应的全局函数可以表示为：

$p(X_0, \ldots, X_n, Y_1, \ldots, Y_n) = p(X_0)\prod_{k=1}^{n}p(X_k \mid X_{k-1})p(Y_{k} \mid X_{k-1})$

5. Sum-product算法

有了因子图，我们可以利用Sum-product算法，根据联合概率分布求出边缘概率分布（先验分布）。

5.1 边缘概率的求解

• 联合概率表示两个事件共同发生的概率，如A和B共同发生的概率为$P(A \cap B)$
• 边缘概率是某个事件发生的概率
  • 边缘概率是通过边缘化（marginalization）得到的：在联合概率中，把最终结果中不需要的那些事件合并成其事件的全概率而消失（对离散随机变量用求和得全概率，对连续随机变量用积分得全概率）

某个随机变量$x_k$的边缘概率可由$x_1, \ldots, x_n$的联合概率求得：

$\overline{f_k}(x_k) \overset{\triangle}{=} \sum\limits_{x_1, \ldots, x_n~\text{except}~x_k}f(x_1, \ldots, x_n)$

假定现在我们需要计算如下式子的结果：

$\overline{f_3}(x_3) \overset{\triangle}{=} \sum\limits_{x_1, \ldots, x_7~\text{except}~x_3}f(x_1, \ldots, x_7)$

假设因子图如下：

可以提取公因子，得到如下的分解图：

因为变量的边缘概率等于所有与它相连的函数传递过来的消息的积，所以计算得到：

仔细观察上述计算过程，可以发现，其中用到了类似“消息传递”的思想，且总共两个步骤：

第一步，对于$f$的分解图，根据蓝色虚线框、红色虚线框围住的两个box外面的消息传递：

计算得到：

第二步，根据蓝色虚线框、红色虚线框围住的两个box内面的消息传递：

根据$\overset{\rightarrow}{u}_{X_1}(x_1) \overset{\triangle}{=} f_1(x_1)$和$\overset{\leftarrow}{u}_{X_2}(x_2) \overset{\triangle}{=} f_{2}(x_2)$，计算得到：

这样的话，上述计算过程将一个概率分布写成两个因子的乘积，而这两个因子可以继续分解或者通过已知得到。这种利用消息传递的观念计算概率的方法便是sum-product算法。前面说过，基于因子图可以用sum-product算法高效求解各个变量的边缘分布。

5.2 Sum-product算法的概念

Sum-product算法，也叫belief propagation，有两种消息：

• 一种是变量（Variable）到函数（Function）的消息，$m_{x \rightarrow f}$
• 一种是函数（Function）到变量（Variable）的消息，$m_{f \rightarrow x} = f(x)$

5.3 算法总体框架

• 给定如下因子图：

• Sum-product算法的消息计算规则为：

  $\overset{\rightarrow}{u}_{X}(x) = \sum\limits_{y_1, \ldots, y_n}g(x, y_1, \ldots, y_n) \overset{\rightarrow}{u}_{Y_1}(y_1) \cdot \ldots \cdot \overset{\rightarrow}{u}_{Y_n}(y_n)$

• 根据sum-product定理，如果因子图中的函数$f$没有周期，则有：

  $\overline{f}_{X}(x) = \overset{\rightarrow}{u}_{X}(x) \overset{\leftarrow}{u}_{X}(x)$

5.4 概率图中出现环的情况

如果因子图是无环的，则一定可以准确的求出任意一个变量的边缘分布，如果是有环的，则无法用sum-product算法准确求出来边缘分布。

一个贝叶斯网络的例子

转换为因子图后

若贝叶斯网络中存在“环”（无向），则因此构造的因子图会得到环。而使用消息传递的思想，这个消息将无限传输下去，不利于概率计算。

解决方法有三个：

• 删除贝叶斯网络中的若干条边，使得它不含有无向环
  最大权生成树算法
  • 最大权生成树算法MSWT（详细过程参见引用^[3]）：通过此算法，树的近似联合概率$P’(x)$和原贝叶斯网络的联合概率$P(x)$的相对熵（KL散度）^[4]最小。
• 重新构造没有环的贝叶斯网络
• 选择loopy belief propagation算法（可简单理解为sum-product算法的递归版本^[2]）：该算法一般选择环中的某个消息，随机赋个初值，然后用sum-product算法，迭代下去，因为有环，一定会到达刚才赋初值的消息，然后更新那个消息，继续迭代，直到没有消息再改变为止。缺点是不确保收敛（此算法在绝大多数情况下是收敛的^[2]）。

5.5 Max-product算法

除了sum-product算法，还有max-product算法。Max-product算法可以理解为sum-product算法的基础上把求和符号换成求最大值max的符号。
Sum-product和max-product算法也能应用到隐马尔科夫模型上。

引用

---

• ← Previous Post
• Next Post→