现在让我们把模型稍微扩展一下，添加第四道需要两项技能的题目。这张新的因子图如图 2.14 所示，我们为这道新题添加了新的 isCorrect4 和 hasSkills4 变量。在这张仅仅略微变大的图上，我们当然也可以用置信传播来做推断吧？其实，我们不能。

飞机航迹环

环可能很棘手。

问题在于，置信传播只有在某个（未观测）节点的所有其它边上都收到了消息之后，才能从该节点发出一条消息（算法 2.1）。在这个约束下，只有当图中没有环时，我们才能把图中的所有消息都发送出去；这里的环是指一条穿过图、从同一个节点出发又回到该节点的路径（且不重复经过同一条边）。如果图中有一个环，那么我们无法沿着环上的任何一条边发送消息，因为这总是要求先计算出环上的另一条消息。

图 2.14

图 2.14：四题测试的因子图。这张图包含一个环（用红色标出），这意味着我们无法应用置信传播。

如果你回头看旧的三题因子图（图 2.5），会发现它没有任何环（没有环的图称为树），所以置信传播可以毫无问题地运行。然而，我们的新图确实有一个环，在图 2.14 中用红色标出。要在这样一个有环图上做推断，我们需要超越标准的置信传播。

要在有环图上进行推断，我们需要设法消除这些环。在这个玩具例子中，我们可以注意到 hasSkills3 和 hasSkills4 是相同的，从而去掉其中一个。这样简单的解决办法在真实问题中不太可能出现。相反，有多种通用方法可以消除环，如专栏 2.2 所述。不幸的是，当处理大型因子图时，所有这些方法通常都会变得太慢而不实用。在大多数真实应用中，图非常大，但推断又需要快速完成。结果就是，这类精确推断方法通常太慢，派不上用场。

专栏 2.2：有环图中的精确推断

要在有环图中精确地进行推断计算，我们需要找到一种方法来消除环，从而把图转换成树。一旦有了树，我们就可以照常运行置信传播。从有环图中消除环有两种常见方法：

1. 通过合并变量来消除环

在我们的例子中，我们可以把变量 csharp 和 sql 替换为一个具有四种状态 $FF, TF, FT, TT$ 的单一变量。我们还需要修改、并在某些情况下合并与这两个变量之一相连的所有因子。这样得到的因子图将不再包含环。这种方法是联合树算法（junction tree algorithm）[Lauritzen and Spiegelhalter, 1988] 的基础，它通过合并变量来创建一棵联合树，然后在其上应用置信传播。联合树算法曾成功应用于许多早期的机器学习应用，但当需要合并大量变量时（这在当今的应用中很常见），它会慢到无法使用。这是因为合并后节点的状态数是各个变量状态数的乘积。随着合并的变量越来越多，这个乘积会迅速膨胀到无法管理的地步。

2. 通过观测环中的某个变量来消除环

如果我们把 csharp 观测为 true，那么从 csharp 变量发出的向外消息就可以发送了，因为它们只是点质量。这样做的效果是切断了环。缺点是，为了得到任何一个边缘分布，你现在必须运行两次推断：一次把 csharp 设为 true，一次设为 false，然后把两个答案组合起来。对于有很多环的图，我们需要观测多个变量以确保所有环都被切断。这是一种称为割集条件化（cutset conditioning）[Pearl, 1988; Suermondt and Cooper, 1990] 的方法的基础，其中割集是为了切断所有环而被观测（条件化）的那组变量。和联合树算法一样，当割集很大时，割集条件化会慢到无法使用，因为我们需要为割集中变量的每一种配置重新运行一次推断。割集的配置数同样是各个变量状态数的乘积，随着割集中变量数量的增加，它会迅速膨胀到无法管理的地步。

另一种选择是考察那些计算所需边缘分布的近似、但能在少得多的时间内完成的方法。在本书中，我们将聚焦于这类近似推断方法，因为它们已被证明在广泛的应用中极为有用。对于这个特定的有环图，我们将引入一种称为循环置信传播（loopy belief propagation）的近似推断算法。

循环置信传播

（深入探讨） 在这个可选小节中，我们定义循环置信传播算法，并用它在我们的有环模型中进行推断。如果你想专注于建模，可以放心跳过本节。

循环置信传播 [Frey and MacKay, 1998] 与置信传播完全相同，直到我们遇到一条因为处于环中而无法计算的消息为止。到那时，循环置信传播算法会无论如何都把这条消息算出来——对于任何尚不可用的消息，它使用一个合适的初始值。

所以，在循环置信传播中，当我们想计算一条依赖于其它尚未计算出的消息的消息 $m$ 时，我们为那些不可用的消息使用一个特殊的初始消息值。这个初始值通常是均匀分布（例如 $\text{Bernoulli}(0.5)$），但在某些情况下，使用其它由用户提供的分布可能更可取。这些初始消息值让我们能够打破环并计算出 $m$。一旦算出了 $m$，我们就能计算环上的其它消息，最终又回到最初的那个节点。此时，计算 $m$ 所需的所有输入消息都已算出，所以我们可以用这些值（而不是初始值）重新计算 $m$。但由于 $m$ 的值已经改变，我们又可以绕着环再把所有消息都计算一遍。这又会把我们带回到重新计算 $m$，如此循环往复。绕环若干次迭代之后，这个过程往往会导致消息 $m$ 的值不再改变——我们称它已经收敛。此时，我们可以停止发送任何进一步的消息，因为计算出的边缘分布不会再有任何变化。

算法 2.2：循环置信传播（Loopy Belief Propagation）

输入： 因子图，要为其计算边缘分布的目标变量列表，消息传递计划，以及（可选的）初始消息值。

输出： 各目标变量的边缘分布。

将所有消息初始化为均匀分布（若提供了初始值，则使用初始值）。

重复：

直到 收敛。

在每个目标变量节点处，把所有输入消息相乘，作为边缘分布计算出来。

完整的循环置信传播算法以算法 2.2 的形式给出——它需要一个消息传递计划作为输入，我们很快就会讨论这一点。循环置信传播不保证给出完全正确的结果，但它往往给出非常接近的结果。然而，与精确推断方法不同，循环置信传播在应用于大型模型时仍然很快，这在真实应用中是一个非常理想的性质。

选择消息传递计划

使用循环置信传播的一个重要后果是，我们现在需要提供一个消息传递计划，也就是说，我们需要指定计算消息的顺序。这与置信传播形成对比，在置信传播中计划是固定的，因为一条消息只有在它所依赖的所有输入消息都收到之后才能发送。循环置信传播的计划需要是迭代式的，也就是说，它的某些部分必须重复执行，直到消息传递收敛。

计划的选择会对推断的准确性和收敛速度产生重大影响。选择一个好计划的一些准则如下：

  • 消息计算应尽可能少地使用初始消息值。换句话说，计划应尽可能接近置信传播的计划，只在绝对必要以打破环的地方才使用初始消息值。遵循这条准则往往会使收敛后的边缘分布更准确。
  • 在每次迭代中，消息应沿着环依次发送。遵循这条准则会使推断更快收敛——如果反过来需要两次迭代才能让一条消息绕环一圈，那么推断算法的收敛时间往往会翻倍。

还有其它一些因素可能影响计划的选择：例如，在分布式集群上运行推断时，你可能想尽量减少在集群节点之间传递的消息数量。在复杂的图中手动设计消息传递计划可能颇具挑战——所幸，已经有一些自动调度算法可以为很大范围的因子图生成良好的计划，例如 Infer.NET 中所用的那些 [Minka et al., 2014]。

把循环置信传播应用到我们的模型

现在让我们应用循环置信传播来求解图 2.14 的模型，假设候选人也答错了第四题（因此 isCorrect4 为 false）。我们先把模型以稍微不同的方式排布，以便把环显示得非常清楚——见图 2.15a。现在我们需要为这个模型选择一个消息传递计划。一个遵循上述准则的计划是：

  1. 从被观测的 isCorrect 节点和 $\text{Bernoulli}$ 先验向环发送消息（图 2.15b）；
  2. 沿环顺时针发送消息直到收敛（图 2.15c）。我们需要用一条初始消息来打破环（以绿色显示）；
  3. 沿环逆时针发送消息直到收敛（图 2.15d）。我们同样必须用一条初始消息（同样以绿色显示）。

事实上，顺时针环和逆时针环中的消息互不影响，因为某个特定方向上的消息只依赖于同一方向上的输入消息。所以我们可以以任意顺序（甚至并行地！）执行该计划的第 2 步和第 3 步。

图 2.15a

(a)

图 2.15b

(b)

图 2.15c

(c)

图 2.15d

(d)

图 2.15：四题因子图中的循环置信传播。(a) 把图 2.14 的因子图重新排布，以更清楚地显示环。(b) 循环置信传播的第一阶段，显示消息向环内传递。(c, d) 循环置信传播的第二、第三阶段，其中消息沿环顺时针或逆时针传递。在每种情况下，第一条消息（A 或 A′）都是用一条均匀初始消息（绿色虚线箭头）计算的。

对于计划的第一步，实际传递的消息如图 2.15b 所示。沿环顺时针发送的消息 $A, B, C, D$，在绕环前五次迭代中的取值如表 2.5 所示。到第四次迭代时，消息不再改变，这意味着它们已经收敛（因此我们本可以在四次迭代后就停止）。

表 2.5

表 2.5：在消息传递的前五次迭代中沿环发送的消息——所示数值是每条消息的伯努利分布的参数。到第四次迭代时，消息已停止变化，表明算法迅速收敛。

逆时针环的消息 $A′, B′, C′, D′$ 结果与对应的 $A, B, C, D$ 消息完全相同，因为来自 hasSkills3 和 hasSkills4 的消息是一样的。给定这些消息，剩下唯一的步骤就是把 csharp 和 sql 处的输入消息相乘，得到边缘分布。

循环置信传播给出 csharp 和 sql 的边缘分布分别为 $\text{Bernoulli}(0.809)$ 和 $\text{Bernoulli}(0.010)$。如果我们用一种精确推断方法来计算真正的后验边缘分布，会得到 $\text{Bernoulli}(0.800)$ 和 $\text{Bernoulli}(0.024)$，这表明我们的近似答案与精确解相当接近。就本应用的目的而言，我们关心的是候选人是否具备某项技能，但只要能让系统运行得快，就可以容忍预测概率有一两个百分点的偏差。

这说明了为什么近似推断方法在处理大规模推断问题时会如此有用。然而，考察使用近似推断方法引入了哪些不准确之处，始终是值得的。稍后，在第 2.5 节中，我们将看看一种可行的做法。

使用近似推断方法的另一个理由是，它们让我们能够在比精确推断所能处理的复杂得多的模型中进行推断。使用一个更好、更精确地表示数据的模型所带来的准确性提升，通常远远超过做近似推断所造成的准确性损失。或者用数学家约翰·图基（John Tukey）的话说：

“对正确的问题给出一个近似的答案，远胜于对错误的问题给出一个精确的答案。”

本页引入概念回顾

环（loop）：环是一条穿过图、从同一个节点出发又回到该节点、且不重复经过任何一条边的路径。例如，见图 2.15a 中用红色高亮的环。

树（tree）：不包含任何环的图，例如图 2.4 和图 2.5 的因子图。当一个图是树时，可以用置信传播给出精确的边缘分布。

有环图（loopy graph）：至少包含一个环的图。例如，图 2.14 的图包含一个环，当它按图 2.15a 那样排布时可以看得更清楚。有环图在进行推断计算时带来更大的困难——例如，置信传播不再给出精确的边缘分布。

精确推断（exact inference）：一种精确计算所求后验边缘分布（一个或多个）的推断计算。精确推断通常只对相对较小的模型，或对具有特定结构（例如树）的模型才可行。另见专栏 2.2。

近似推断（approximate inference）：一种旨在紧密逼近所求后验边缘分布的推断计算，在精确推断耗时过长或不可行时使用。对于大多数有用的模型，精确推断要么不可行、要么非常慢，所以需要某种近似推断方法。

循环置信传播（loopy belief propagation）：一种近似推断算法，它把置信传播算法应用到有环图上，方法是在环中初始化消息，然后反复迭代。循环置信传播算法定义于算法 2.2。

收敛（converged）：迭代算法进一步迭代不再带来任何变化时所处的状态。当一个迭代算法已收敛时，再执行更多迭代已无意义，因此算法可以停止。必须使用某种收敛判据来判断算法是否已收敛——这些判据通常允许小幅变化（例如消息的小幅变化），以应对数值上的不精确，或在算法近似收敛时就停止它，以节省计算。

消息传递计划（message-passing schedule）：在消息传递算法中计算和传递消息的顺序。消息传递算法的结果会因消息传递顺序的不同而发生剧烈变化，因此使用一个合适的计划非常重要。计划通常是迭代式的——换句话说，它由一组需要反复计算的消息排序组成，直到算法收敛。

自我评估 2.3

以下练习将帮助你巩固本节所学的概念。在做题时，回顾正文或上面的概念小结可能会有所帮助。

  1. 为一个评估三项技能的六题测试画一张因子图。找出你网络中的所有环。如果没有环，就继续添加题目直到出现环为止。
  2. 为你的六题测试设计一个消息传递计划，使其使用尽可能少的初始消息（每个环一条）。记住，除非某个节点所连的所有边上都收到了消息，否则不能从该节点发出消息（被观测的变量节点除外）。
  3. 扩展你在上一个自我评估中构建的三题 Infer.NET 模型，以纳入图 2.14 的第四题。使用 TraceMessages 属性来查看 Infer.NET 发送了哪些消息，并确认它们与表 2.5 中所示的计划和取值相符。如果你遇到困难，可以参考本章的源代码 [Diethe et al., 2019]。

参考文献

[Lauritzen and Spiegelhalter, 1988] Lauritzen, S. L. and Spiegelhalter, D. J. (1988). Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems. Journal of the Royal Statistical Society, Series B, 50(2):157–224.

[Pearl, 1988] Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Francisco.

[Suermondt and Cooper, 1990] Suermondt, H. and Cooper, G. F. (1990). Probabilistic inference in multiply connected belief networks using loop cutsets. International Journal of Approximate Reasoning, 4(4):283–306.

[Frey and MacKay, 1998] Frey, B. and MacKay, D. (1998). A revolution: Belief propagation in graphs with cycles. In Neural Information Processing Systems, pages 479–485. MIT Press.

[Minka et al., 2014] Minka, T., Winn, J., Guiver, J., Webster, S., Zaykov, Y., Yangel, B., Spengler, A., and Bronskill, J. (2014). Infer.NET 2.6. Microsoft Research Cambridge. http://research.microsoft.com/infernet.

[Diethe et al., 2019] Diethe, T., Guiver, J., Zaykov, Y., Kats, D., Novikov, A., and Winn, J. (2019). Model-Based Machine Learning book, accompanying source code. https://github.com/dotnet/mbmlbook.

下一节：迁移到真实数据