9. 加和乘积算法(sum-product algorithm)

本章我们开始讨论消元算法的一个改进版本–加和乘积算法(sum-product algorithm)或者和积算法，又称为置信传播(belief propagation)算法。 前文我们说过消元算法每次查询都要执行一遍，当我们需要查询图中每个节点的边缘概率时效率就非常低下。和积算法就是对这个问题的改进， 一次可以计算出图中全部节点的边缘概率。

在消元算法中，当我们需要计算多个不同变量的边缘概率分布，我们需要每次从头开始重新运行消元法，这仍然需要庞大的计算量 ^注解 。 已经得到证明，我们可以把消元法改写成节点之前的信息传递方法，并且这些信息可以在多次的边缘化查询中进行重复利用，以此来降低多次边缘化查询的计算量 ， 这样的改进算法称为 加和乘积算法 。

备注

不是一次计算多个变量的联合边缘概率分布，而是分别独立计算。 比如对于 图 9.2.1 中5个变量的概率图， 当我们需要计算 $p(x_1)=\sum _{x_2,x_3,x_4,x_5}p(x1,x2,x3,x4,x5)$ 和 $p(x_2)=\sum _{x_1,x_3,x_4,x_5}p(x1,x2,x3,x4,x5)$ 两个变量的边缘概率分布时， 需要独立执行两次消元算法，而这两次执行中有一些重复的计算。

消元算法适用于任意的图形，然而和积算法只能应用在树形结构模型。虽然和积算法的应用范围变小了，但是其价值仍然是很大的。 日常应用中，我们见到的图形结构大部分都是树形结构的图形。 在本章中，我们学习在树结构图形上加和乘积算法，在稍后的章节中我们在扩展到更一般的图形中。 同时，也会看到相似的算法应用到最大后验估计(MAP)中。

9.1. 树结构

首先我们介绍一下什么是树形结构图模型，以及树模型的一些特性。 在无向图中，树(tree)被定义成图中任意两个节点有且仅有一条 路径 (注意不是边)的无向图。 如果一个有向图的道德图(moralized graph)是一个无向树，那么这个有向图就是有向树。 或者说，一个有向图，如果仅有一个根节点(root node)，并且根节点以外的其它所有节点都只有一个父节点，那么这个有向图是树。 如果一个有向图，存在具有多个父节点的节点，那么这个有向图是一个多重树(polytree)，注意不是多棵树(multiple trees)。 树(tree)和多重树(polytree)是显著不同的。

图 9.1.3 (a)无向树；(b)有向树；(c)多重树(polytree)

任意的无向树可以转换为一个有向树，任意选择一个节点作为根节点(root)，所有无向边都改成从根节点出发向外扩散的有向边。 在图模型的表达和推断方面，有向树和无向树没有显著差异。 一个有向树和它对应的无向树(有向边转换成无向边)具有相同的条件独立属性，此外两者的参数化(因子分解)表示本质上也是一样的。

现在我们考虑无向树概率分布的参数化(因子分解)表达，无向树中只有两个节点或者单个节点组成的团， 所以一个无向树模型 $\mathcal{T}(\mathcal{V},\mathcal{E})$ 的联合概率可以表示为单个节点的势函数 $\{{\psi }_i(x_i)\}$ 和两个节点的势函数 $\{{\psi }_{ij}(x_i,x_j)\}$ 的乘积。

(9.1.36)$$p(x)=\frac{1}{Z}(\prod _{i\in \mathcal{v}}{\psi }_i(x_i)\prod _{(i,j)\in \mathcal{E}}{\psi }_{ij}(x_i,x_j))$$

对于有向树模型，联合概率可以表示为一个边缘概率(根节点r) $p(x_r)$ ， 和一些局部条件概率 $p(x_j|x_i)$ 的乘积，节点i是节点j的父节点。

(9.1.37)$$p(x)=p(x_r)\prod _{(i,j)\in \mathcal{E}}p(x_j|x_i)$$

有向树的因子分解式 公式(9.1.37) 可以看成是无向树因子分解式 公式(9.1.36) 的一个特例，可以通过如下方式进行转换。

(9.1.38)$$\begin{array}{r}\begin{array}{c}{\psi }_r(x_r)=p(x_r)\\ {\psi }_{ij}(x_i,x_j)=p(x_j|x_i)\\ Z=1\end{array}\end{array}$$

回忆一下，在消元法的章节中，我们用证据势函数(evidence potential function)表示条件变量。 如果我们想要查询图模型中的条件概率 $p(x_F|x_E)$ ，其中变量子集E是条件变量（证据变量，亦或者称为观测变量）集合， 我们定义证据势函数 $\delta (x_i,{\overline{x}}_i),i\in E$ ，并且把它乘到联合概率的因子表达式中。 我们定义：

(9.1.39)$$\begin{array}{r}{\psi }_i^E(x_i)\triangleq \{\begin{array}{rlr}{\psi }_i(x_i)\delta (x_i,{\overline{x}}_i)& & i\in E\\ {\psi }_i(x_i)& & i\notin E\end{array}\end{array}$$

用其替换 公式(9.1.36) 可得条件概率：

(9.1.40)$$p(x_F|{\overline{x}}_E)=\frac{1}{Z^E}(\prod _{i\in \mathcal{v}}{\psi }_i^E(x_i)\prod _{(i,j)\in \mathcal{E}}{\psi }_{ij}(x_i,x_j))$$

乘上 $\delta (x_i,{\overline{x}}_i),i\in E$ 就相当于把 $x_i$ 的值限定为 ${\overline{x}}_i$ ， 也就是变成了以 $x_i={\overline{x}}_i$ 为条件的条件概率。 其中 $Z^E=\sum _x(\prod _{i\in \mathcal{v}}{\psi }_i^E(x_i)\prod _{(i,j)\in \mathcal{E}}{\psi }_{ij}(x_i,x_j))$ ，是分子的求和(积分)，原来的Z被消除掉了，如果不是很理解，请回顾一下消元法章节。 总之，树模型上的条件分布和非条件分布的表达式拥有相同的形式。 通过引入证据势函数，我们把条件变量的值限定操作转换成了求和消除操作，条件变量可以和其他被边缘化消除的变量在操作上同等看待， 这样一来在图模型上进行条件概率查询也可以看做是进行边缘概率查询，因为两者在计算上是等价的。 也就是说我们可以把 $p(x_F|{\overline{x}}_E)$ 和 $p(x_F)$ 都当成是在求边缘概率， 在图模型的推断算法的讨论中，我们将不再区分两者，都会按照边缘概率查询来讨论。

9.2. 从消元法到信息传播

和积算法是消元法的一个改进版本，在正式介绍和积算法前，我们先来回顾一下消元算法，以及在树结构上执行消元算法有什么特点。 消元法的步骤是：(1) 选定一个消元顺序 $I$，要查询的节点 ${\mathrm{x}}_1$ 在最后。 (2)把所有的势函数(包含证据势函数)加入到一个激活列表中。(3)依照顺序 $I$ 进行节点消除：对于 $I$ 中的每个节点i，从激活列表中取出包含变量 ${\mathrm{x}}_i$ 的所有因子，在这些因子的乘积上对 $x_i$ 进行求和消除掉，生成一个新的中间因子 $m_i(\cdot )$ ，把这个因子加入到激活列表中。 下面我们举例说明这个算法的效率依赖于消元顺序的选择。

图 9.2.1 一个树形概率图模型

图 9.2.2 一个树形概率图模型

如 图 9.2.1 所示的树结构图模型，假设我们想要用消元法计算图中的 $x_1$ 的边缘概率 $p(x_1)$ ，如果我们选择消元顺序(2,4,5,3,1)，消元法的执行过程将如 图 9.2.3 所示。在第一步之后， ${\mathrm{x}}_2$ 被消除，得到一个三个节点的信息量 $m_2(x_1,x_4,x_5)$ ，回想一下消元法章节中的例子， 一个包含三个变量的函数 $m_2(x_1,x_4,x_5)$ 是一个规模为 $|\mathcal{X}{|}^3$ 的概率分布表， 这相当于 $x_2$ 的邻居都相连接形成一个新的因子函数。

图 9.2.3 消元顺序为(2, 4, 5, 3, 1)的算法执行过程

考虑另一个极端的例子，如 图 9.2.4 所示的星型结构图，如果我们首先消除变量 $x_1$ ，将导致剩余的变量形成一个全连接的图， 一个规模为 $|\mathcal{X}{|}^{N-1}$ 可怕存在。 不适当的消元顺序，将导致更加复杂的计算。

图 9.2.4 一个星型结构的图，在消去变量 $x_1$ 之后形成的复杂结构。

幸运的是，对于树结构图，我们很容易能找到一个不需要增加边的消元顺序。明显的，从图的”边缘”开始进行消除是一个最优选择， 对于树形结构来说，图的”边缘”就是叶子节点，从叶子节点开始消元是最优的，或者说是 深度优先 的顺序。实际上，如果从叶子节点开始， 每一次消元后，剩余的图形仍然是树形结构。所以，我们可以每次消元都选择叶子节点进行（注意，根节点必须是最后一个）。 针对图1所示的例子，这样的消元顺序应该是(4,5,3,2,1)，其过程如 图 9.2.5 所示。

图 9.2.5 按照(4, 5, 3, 2, 1)的消元过程。

在一个树图中，每一条边都组成了图中的最大团（maximal clique），图 9.2.1 的因子表达式为：

(9.2.9)$$p_{\mathbf{x}}(\mathbf{x})=\frac{1}{Z}{\psi }_1(x_1){\psi }_2(x_2){\psi }_3(x_3){\psi }_4(x_4){\psi }_5(x_5){\psi }_{24}(x_2,x_4){\psi }_{25}(x_2,x_5){\psi }_{21}(x_2,x_1){\psi }_{13}(x_1,x_3)$$

在这个算法过程中，产生的信息如下:

(9.2.10)$$\begin{array}{r}\begin{array}{rl}{m}_4\left(x_2\right)& =\sum _{x_4}{\psi }_4\left(x_4\right){\psi }_{24}(x_2,x_4)\\ m_5\left(x_2\right)& =\sum _{x_5}{\psi }_5\left(x_5\right){\psi }_{25}(x_2,x_5)\\ m_3\left(x_1\right)& =\sum _{x_3}{\psi }_3\left(x_3\right){\psi }_{13}(x_1,x_3)\\ m_2\left(x_1\right)& =\sum _{x_2}{\psi }_2\left(x_2\right){\psi }_{12}(x_1,x_2)m_4\left(x_2\right)m_5\left(x_2\right)\end{array}\end{array}$$

最后，通过把 $x_1$ 接收到信息和 ${\psi }_1(x_1)$ 连乘，就得到了 $x_1$ 的边缘概率分布。

(9.2.11)$$p_{x_1}\left(x_1\right)\propto {\psi }_1\left(x_1\right)m_2\left(x_1\right)m_3\left(x_1\right)$$

在树结构进行消元算法时，如果每次都是消除叶子节点，那么在计算 $m_i(\cdot )$ 时最多只会包含两个变量，并且其中一个是要进行求和消除的， 这样生成的中间因子 $m_i(\cdot )$ 只包含一个变量，这将极大的降低我们的计算复杂度。 生成的中间因子m都有 $|\mathcal{X}|$ 个值，而生成每个值需要 $|\mathcal{X}|$ 次求和计算。 需要为每条边(N-1)计算一次m，共计N-1次，所以整体的时间复杂度是 $O\left(N|\mathcal{X}{|}^2\right)$ 。

现在我们讨论下消元过程中产生的中间因子 $m(\cdot )$ ，我们发现在树结构上，如果我们按照从叶子到根的顺序进行消元时， 中间因子 $m(\cdot )$ 有如下特点， 注意这些在非树形结构的图模型上是不成立的 。

1. 计算 $m(\cdot )$ 时只涉及到两个变量，其中一个是需要进行消除叶子节点，另一个是这个叶子节点的”父节点”。

2. 生成的 $m(\cdot )$ 是一个关于”父节点”的单变量因子函数。

3. $m(\cdot )$ 传递方法是从叶子节点到其”父节点” 。

鉴于此，我们定义一个新的符号 $m_{ji}(x_i)$ 表示 $m(\cdot )$ ，其下标表示这个因子是从节点j传递到节点i的， 节点j是已经被消除的节点，节点i是节点j的”父节点” ，并且我们把这个中间因子称为信息(message)， $m_{ji}(x_i)$ 可以看成是节点j向节点i传递的信息量。

图 9.2.6 一个无向树的片段(a)节点i和节点j是邻居，节点i更接近根节点，可以把节点i看成节点j的”父节点”。 (b)当节点k和l被消除时，信息量的传播方向。

现在我们详细讨论下信息 $m_{ji}(x_i)$ 的计算过程。 信息 $m_{ji}(x_i)$ 是我们消除节点j之后，节点j通过边(j,i)传递给节点i的信息量。 当我们消除节点j时，是从激活列表中选出包含变量 $x_j$ 的所有势函数， 其中可能有 ${\psi }_{ij}(x_i,x_j)$ 和 ${\psi }_j(x_j)$ (如果 $x_j$ 是条件(证据)变量，就是 ${\psi }_j^E(x_j)={\psi }_j(x_j)\delta (x_j,{\overline{x}}_j)$ ， 以及节点j的其他邻居节点(不包括节点i)传递给节点j的信息量 $m_{kj}(x_j),k\in \mathcal{N}(j)\mathrm{\setminus }i$ ， $\mathcal{N}(j)$ 表示节点j的邻居节点集合。因此，节点j传递给节点i的信息量的一般式为：

(9.2.12)$$m_{ji}(x_i)=\sum _{x_j}({\psi }_j(x_j){\psi }_{ij}(x_i,x_j)\prod _{k\in \mathcal{N}(j)\mathrm{\setminus }i}{m}_{kj}(x_j))$$

最后，消元顺序 $I$ 中只剩下了需要查询的变量(根节点)的 $x_f$ ，其他变量都被消除掉了， 并且f的邻居节点传递给F的信息量都被计算了出来 $m_{ef}(x_f),e\in \mathcal{N}(f)$ ， 最后 $x_f$ 的边缘概率为：

(9.2.13)$$p(x_f)=\frac{1}{Z}{\psi }_F(x_f)\prod _{e\in \mathcal{N}(f)}{m}_{eF}(x_f)$$

也就是说在树结构执行边缘概率查询时，我们只需要把要查询的节点f当做是根节点，然后使用深度优先的顺序先消除叶子节点。 消元过程中每个被消除的节点会向它的”上一级”节点传递一个消息m，这个消息的组成是由 公式(9.2.12) 给出。 那如果我想分别查询图中两个节点的边缘概率，比如 $p(x_g)$ 和 $p(x_h)$ ， 那么就需要分别以这两个节点为根节点，执行两次消元算法。 如果需要查询图中每个节点的边缘概率，就需要对每个节点执行一次这个过程， 在图模型规模很大时，这仍然是不小的代价， 下一节的和积算法就是为了解决这个问题。

9.3. 树模型的和积算法

上一节我们讲到，如果需要查询图中每个节点的边缘概率，就需要为每个节点执行一次消元法，这个成本是非常高昂的。 事实上，我们可以只执行两次消元法，就能求出图中每个节点的边缘概率。

图 9.3.1 (a)计算边缘概率 $p(x_1)$ 时需要的消息。 (b)计算边缘概率 $p(x_2)$ 时需要的消息。 (c)计算边缘概率 $p(x_4)$ 时需要的消息。 (d)计算全部单一节点的边缘概率时需要的消息。

考虑 图 9.3.1 (a)所示的树结构片段，用消元法计算边缘概率 $p(x_1)$ 的过程中，需要先消除变量 ${\mathrm{x}}_3$ 和 ${\mathrm{x}}_4$ ，这过程中计算出发送给节点 ${\mathrm{x}}_2$ 消息量有 $m_{32}(x_2)$ 和 $m_{42}(x_2)$ ，然后我们消除节点 ${\mathrm{x}}_2$ ， 这时产生发送给节点 ${\mathrm{x}}_1$ 的信息 $m_{21}(x_1)$ 。

现在假设我们需要计算节点 ${\mathrm{x}}_2$ 的边缘概率 $p(x_2)$ ，这过程中产生的消息量如 图 9.3.1 (b)所示。同理，计算节点 ${\mathrm{x}}_4$ 的边缘概率 $p(x_4)$ 时产生的信息如 图 9.3.1 (c)所示。我们发现三次过程中，存在一些重复的信息量的，比如三次过程中都需要 $m_{32}(x_2)$ ， 我们把三次过程中所需要的所有信息量都合并到一张图中，如 图 9.3.1 (d)所示， 每条边会有往返两次消息 。回想一下 公式(9.2.13) ， 计算一个节点的边缘概率时需要用到这个节点的所有邻居节点发送过来的消息 $m_{eF}(x_f)$ ， 那么如果我们把每条边上往返两次的消息量都记录下来，就可以计算图上任意一个节点的边缘概率。

算法关键在于”信息”可以重复使用，和积算法就是基于 公式(9.2.12) 和 公式(9.2.13) ，以及一个”信息传播协议”。 计算出图中每条边上往返两次消息量，然后重复利用这些消息。

信息传播协议

一个节点可以向它的一个邻居发送一条消息当且仅当它收到了 其它所有邻居 节点的消息。

这个协议有两个重点，一是一个节点需要向所有的邻居发送消息，二是需要收到其它所有邻居（不包括要发送消息的目标邻居）的消息后才能向目标邻居发送消息。 这个协议有两个主流的实现方式，一个是顺序执行，一个是同步并行法。

我们先说并行的方法，我们把每个节点看做是一个”处理器”，它会重复的轮询检测它的每条边，假设一个节点有d条边(度为d)， 当检测到其中任意d-1条边收到消息后，就向剩余的那条边发送消息，直到d条边都发送过消息。 图 9.3.2 是一个例子，我们假设每个节点是独立运行的，因为叶子节点只有一条边， 不需要等待别的节点向他发送消息，它们可以直接向唯一的一条边发送消息，如 图 9.3.2 (b)所示。 然后中间节点也满足了发送条件，可以互相发送一条消息，如 图 9.3.2 (c)所示， 然后中间节点也满足了向外层叶子节点发送消息的条件，随即向叶子节点发送消息如 图 9.3.2 (d)所示。 最终图中每条边都完成了往返两次的消息，算法结束。

图 9.3.2 同步并行的信息传播算法。实线箭头表示当前论的消息传递方向，虚线箭头表示上一轮的消息传递。

消息传播的另一种实现方式是串行法，按照一个特定的顺序依次计算边上的消息。实践中最常用的是两段法， 第一阶段，从图中任意选择一个节点作为根节点，假设计算这个节点的边缘概率，然后用上一节的深度优先的消元法计算出 图中每条边从叶子节点向着根节点方向发送的信息。第二阶段，反向计算，从根节点出发，计算从根节点向叶子节点方向的信息。

前文已经说过有向树和无向树没有本质的差异，二者可以看成是的等同的， 所以在有向树和无向树上执行和积算法是一样的过程，无非就是势函数和局部条件概率的差异。

9.4. 因子图的和积算法

现在我们开始讨论因子图的推断问题，像之前一样，我们的目标是在联合概率分布因子分解表达式的基础上，计算其中每个变量的边缘概率。 同样，因子图上的和积算法也是建立在树形结构的因子图上，首先我们看下因子树的定义。

如果一个因子图，我们忽略其中因子节点和变量节点的区别，而形成的无向图是一颗无向树，那么这个因子图就是因子树。 也就是说，我们把因子图看做是一个无向图，而这个无向图是一颗树，那么这个因子图就是因子树。 在因子树中有两种类型的消息(message)：从变量节点传递到因子节点的消息 $v$ ；从因子节点传递到变量节点的消息 $u$ 。 如 图 9.4.1 (a)所示，从变量节点i流向因子节点 $s$ 的信息 $v_{is}(x_i)$ 的计算公式为：

(9.4.1)$$v_{is}(x_i)=\prod _{t\in \mathcal{N}(i)\mathrm{\setminus }s}{u}_{ti}(x_i)$$

等式右侧是除了因子节点s外变量节点i的其他邻居节点流向变量节点i信息量的乘积，这和无向树上的信息计算方法非常的类似。 同样的，如 图 9.4.1 (b)所示，因子节点s传递给变量节点i的信息量的计算公式为：

(9.4.2)$$u_{si}(x_i)=\sum _{x_{N(s)\mathrm{\setminus }i}}(f_s(x_{\mathcal{N}(s)})\prod _{j\in \mathcal{N}(s)\mathrm{\setminus }i}{v}_{js}(x_j))$$

这里注意，从因子节点流向变量的节点的信息，需要乘上当前因子的因子函数，并且要对因子函数中除变量i以外的变量进行求和消元。

图 9.4.1 (a)从变量节点i到因子节点 $s$ 的信息量 $v_{is}(x_i)$ 的计算方法。 (b)从因子节点 $s$ 到变量节点i的信息量 $u_{si}(x_i)$ 的计算方法。

因子树上信息量的计算方法和无向树是非常相似的，同样的，因子树上的信息传播协议和上一节树模型上的定义是完全一样的。 在因子树上，这个协议对于变量节点和因子节点都成立。

信息传播协议

一个节点可以向它的一个邻居发送一条消息当且仅当它收到了 其它所有邻居 节点的消息。

最后，当一个变量节点收到了到其所有邻居节点的信息，我们就可以计算出这个变量节点边缘概率。

(9.4.3)$$p(x_i)\propto \prod _{s\in \mathcal{N}(i)}{u}_{si}(x_i)$$

和 公式(9.4.1) 结合一下，可以得到：

(9.4.4)$$p(x_i)\propto v_{is}(x_i)u_{si}(x_i)$$

我们通过 图 9.4.2 演示一下因子树上和积算法的计算过程。 图 9.4.2 (a) 是一个简单的三节点无向树，其对应的因子图如 图 9.4.2 (b)所示， 当然这个因子图是符合因子树的定义的，现在我们开始在在这个因子树上执行和积算法。

图 9.4.2 因子图和积算法的过程。

第一步，我们以节点 ${\mathrm{x}}_2$ 为根节点，从叶子节点开始，计算叶子节点向外传递的信息量， 图 9.4.2 (c)所示。 此因子树的叶子节点有三个，分别是因子节点a、b和c，根据公式 公式(9.4.2) 进行计算。 这三个叶子节点不存在其它的输入，所以公式中的连乘式是不存在的，只需要分别对因子函数进行消元处理即可。 然而，三个因子函数中不存在需要消元的对象，所以最终信息量为 $u_{a1}(x_1)=f_a(x_1),u_{b2}(x_2)=f_b(x_2),u_{c3}(x_3)=f_c(x_3)$ 。

第二步，如 图 9.4.2 (d)所示，节点变量 ${\mathrm{x}}_1,{\mathrm{x}}_3$ 可以分别输出信息量。 根据 公式(9.4.1) ，节点 ${\mathrm{x}}_1$ 向外输出的信息量为 $v_{1d}(x_1)=u_{a1}(x_1)=f_a(x_1)$ ， 节点 ${\mathrm{x}}_3$ 向外输出的信息量为 $v_{3e}(x_3)=u_{c3}(x_3)=f_c(x_3)$ 。

第三步，如 图 9.4.2 (e)所示，计算因子节点 $f_d$ 和 $f_e$ 向变量节点 ${\mathrm{x}}_2$ 传输的信息量。 根据 公式(9.4.2) ，$u_{d2}(x_2)=\sum _{x_1}{f}_d(x_1,x_2)v_{1d}(x_1)$ ， $u_{e2}(x_2)=\sum _{x_3}{f}_e(x_3,x_2)v_{3e}(x_3)$ 。

至此，我们完成了以 ${\mathrm{x}}_2$ 为根节点，从叶子节点往根节点方向传播的信息量的计算。 我们和无向树 图 9.4.2 (a)上的和积算法对比一下可以发现 $u_{d2}(x_2)=m_{12}(x_2),u_{e2}(x_2)=m_{32}(x_2)$ 。

然后我们需要计算从根节点 ${\mathrm{x}}_2$ 出发向叶子节点方向传播的信息量， 如 图 9.4.2 (f)(g)(h)所展示的过程。类似的我们可以发现，其中 $u_{d1}(x_1)=m_{21}(x_1)$ 以及 $u_{e3}(x_3)=m_{2}3(x_3)$ 。 从中我们同样发现了与无向图上信息量的关系，对比下 图 9.4.2 (a)， 可以发现： $u_{d1}(x_1)=m_{21}(x_1),u_{e3}(x_3)=m_{23}(x_3)$ 。

图 9.4.3 (a)一个无向树的片段 (b)相关联的因子树

更一般的，如果我们从一个无向树开始，并且把这个无向图转换成了因子图，我们会发现无向树上和积算法产生的”m信息量”和 因子图上和积算法产生的”u信息量”存在直接的对应关系。 考虑 图 9.4.3 (a)所示的无向树片段及其对应的因子图片段 图 9.4.3 (b)， 无向图上的信息量 $m_{ji}(x_i)$ 等价于因子图上的信息量 $u_{si}(x_i)$ 。

(9.4.5)$$\begin{array}{r}\begin{array}{rl}{u}_{si}(x_i)& =\sum _{x_{\mathcal{N}(s)\mathrm{\setminus }i}}(f_s(x_{\mathcal{N}(s)})\prod _{j\in \mathcal{N}(s)\mathrm{\setminus }i}{v}_{js}(x_j))\\ & =\sum _{x_j}\psi (x_i,x_j)v_{js}(x_j)\\ & =\sum _{x_j}\psi (x_i,x_j)\prod _{t\in \mathcal{N}(j)\mathrm{\setminus }s}{u}_{tj}(x_j)\\ & =\sum _{x_j}(\psi (x_j)\psi (x_i,x_j)\prod _{t\in {\mathcal{N}}^{\prime }(j)\mathrm{\setminus }s}{u}_{tj}(x_j))\end{array}\end{array}$$

我们发现这个公式和 公式(9.2.12) 是等价的。 通过这些观测不难证明，在由无向树转换成的因子树上执行因子树和积算法是成立的，当然实际上在任何因子树上都是成立的。

9.5. 类树结构图模型

考虑 图 9.5.1 (a)所示的图形，这是一个无向图，其并不符合树(tree)的定义，所以其不是无向树，并不能直接应用和积算法。 中心三个节点组成了一个团，我们假设这个团上定义了一个整体的势函数 $\psi (x_2,x_3,x_4)$ ，并没有被分解成更细的势函数。 那么这个无向图的联合概率可以表示为：

(9.5.1)$$p(x)\propto \psi (x_1,x_2)\psi (x_3,x_5)\psi (x_4,x_6)\psi (x_2,x_3,x_4)$$

为了简单起见，我们忽略了其中单个变量上的势函数因子。虽然这个无向图不是一个树结构，但如果我们把其中心的团看做是一个整体， 它就是一个”近似”树结构。具体的，我们用一个新的”超级变量” $\mathrm{z}$ 替换三个节点 ${\mathrm{x}}_2,{\mathrm{x}}_3,{\mathrm{x}}_4$ ，$\mathrm{z}$ 的值就是这三个变量的笛卡尔积。 如 图 9.5.1 (b)所示，通过创建新的势函数， $\psi (x_1,z),\psi (x_5,z),\psi (x_6,z),\psi (z)$ ， 可以模拟因子分解式 公式(9.5.1) ，并且这个新的图形称为了一颗树形结构。

图 9.5.1 (a)一个无向树的片段 (b)相关联的因子树

更进一步，我们可以用因子图的方式表示， 图 9.5.1 (a)的无向图直接转换成的因子图为 图 9.5.1 (c)， 这个因子图符合因子树的定义，可以直接应用因子图上的和积算法。我们看到”类树”结构的无向图可以直接转换成因子树，并且不需要引入 新的节点和势函数。 更一般的，如果一个无向图中的所节点都被分成不重叠的团，并且每个团都是定义一个整体的势函数，则其相关的因子图是树形结构，可以应用和积算法。

9.6. 多重树(polytrees)

我们已经讲过消元法可以应用于任何的图模型，然而和积算法只能应用于树结构的图模型， 有向树和无向树本质上是等价的，所以可以应用相同的和积算法，因子树的和积算法稍有些不同，但是和无向树也有共同的地方。 一些 类树结构的无向图 可以转换成因子树进而可以应用和积算法。 本节我们讨论一类特别的 类树结构的有向图 ，同样可以转换成因子树图。

首先回顾一下有向树的定义：除了根节点以外的所有节点有且仅有一个父节点的有向图称为有向树。 如果有向图中一些节点拥有多个父节点，就成为多重树(polytree)。注意，我们这里讨论的都是有向无环图。 多重树是一种类树结构，其对应的因子图是树形结构。

图 9.6.1 (a)一颗有向多重树 (b)多重树对应的因子树

如 图 9.6.1 当我们把一颗多重树，转换成因子图时，因子图拥有树形结构。 转换过程中，局部条件概率用定义在节点及其父节点上的因子函数替代，并且可以额外追加定义在单个变量节点上的因子（比如根节点的边缘概率）。 多重树本身是无法应用和积算法的，但是通过转换为因子树图，我们就可以应用和积算法进行模型推断。

9.7. 总结

• 加和乘积算法是消元法的”信息化”改进，主要优点是可以复用”信息(message)”，降低在多次求边缘概率时的计算量。