我们已经看到，置信传播使我们能够在图 3.10 的模型中计算变量 Jskill 的精确边缘后验分布。虽然 Jskill 的先验分布是一个由两个参数描述的高斯，但后验分布不是高斯，而是一个需要四个参数的更复杂分布。为阻止参数数量在每局游戏后不断增加，我们需要一种方法用具有固定数量参数的分布来近似这个真实的后验，为此我们选择高斯。这样后验分布就会与先验具有相同的函数形式，模仿共轭先验的行为。如果我们能做到这一点，就能把所得的近似后验分布当作下一局游戏的先验分布。这样，每个玩家的技能将始终由一个仅受两个参数支配的高斯分布表示。

第一个问题是如何用一个高斯来近似一个非高斯分布。一个简单的解法是求出该非高斯分布的均值和方差，然后选一个具有相同均值和方差的高斯作为我们的近似。事实证明这是一个合理的近似，它可以通过优化两个概率分布不相似性的某种度量来形式化地推导出来 [Bishop, 2006; Minka, 2005]。

我们也许会因此想干脆直接用一个高斯来近似 Jskill 的精确后验分布。虽然这对图 3.10 的因子图会令人满意地奏效，但当我们转向更复杂的因子图（例如本章后面将遇到的那些）时，它又会失效。具有简单函数形式的消息在穿过因子后往往会变得更复杂。当我们把模型扩展到更大、更精巧的图时，很快就会遇到消息无法被精确计算的情形。这类问题可以通过在每个因子节点处局部地做近似来避免，从而使所有消息都具有所需的分布类型。这确保了只要每个因子都能使用适当的分布类型向所有相邻的变量节点发送近似消息，因子就可以被组合成任意的图。

下面这一小节会深入这类近似推断算法的数学细节。如果你想跳过这些细节，尽可直接看下一节。

推断深入探讨

在这个可选小节中，我们引入期望传播这一近似推断技术，我们将在本书中广泛使用它。如果你想专注于建模，尽可跳过本小节。

回到图 3.12（为方便起见在图 3.21 中重现），我们看到消息 (6) 是我们遇到的第一个非高斯消息。

图 3.21

图 3.21：在应用置信传播计算 Jskill 更新分布时出现的消息。（重现自图 3.12。）

因此我们的目标是用一个高斯来近似消息 (6)，从而确保所有后续消息也都是高斯分布。

尽管这似乎是一个可取的目标，但也似乎存在一个重大障碍——如图 3.17 所示，消息 (6) 的精确形式看起来一点也不像高斯！事实上，它的均值和方差甚至都没有良好定义（两者都是无穷）。找到一个合理高斯近似的关键在于注意到：消息 (6) 的近似版本随后会作为消息 (7) 和 (8) 的修改形式在图中传递，然后会被向下的消息 (9) 相乘，以确定 Jskill 的（近似）后验分布。因此我们的目标将是：让消息 (6)（关于 Jperf）的高斯近似在那些被图中其他部分传来的信息认为更可能的区域上最为精确。然而，正如我们刚刚讨论的，我们需要把近似保持在图中生成该消息的局部区域内。消息 (6) 被发送到节点 Jperf，因此我们可以选择我们的近似，使 Jperf 边缘分布的精度最大化。这通过把消息 (6) 乘以图中同一条边上向下的消息得到，后者可如图 3.22 所示计算。注意，求 Fskill 的后验边缘时也需要这些相同的消息，因此计算它们并不引入额外开销。

图 3.22

图 3.22：计算将用于为消息 (6) 找高斯近似的“上下文”消息。

让我们更详细地考虑因子图中靠近 Jperf 节点的部分，如图 3.23 所示。

图 3.23a

(a)

图 3.23b

(b)

图 3.23：Jperf 节点周围因子图的细节，展示所涉及的消息：(a) 运行置信传播时；(b) 对来自 GreaterThan 因子的向上消息做局部高斯近似时。

这里 $e$ 表示此前在图 3.20 中所见的精确消息 (6)，$c$ 表示向下的“上下文”消息，$g$ 表示我们所需的对消息 $e$ 的高斯近似。这些消息都只是变量 Jperf 的函数。我们已经看到，我们不能简单地用高斯来近似消息 $e$，因为消息 $e$ 具有无穷的均值和方差。相反，我们对 Jperf 的边缘分布做高斯近似。精确的边缘由入向消息之积 $ce$ 给出。因此我们把近似消息 $g$ 定义为：使消息 $c$ 与 $g$ 之积给出的 Jperf 边缘分布是对真实边缘的最佳高斯近似，从而

$$cg = \text{Proj}\left( ce \right). \tag{3.14}$$

这里 Proj() 表示“投影”，代表用一个具有相同均值和方差的高斯替换一个非高斯分布的过程。这可以看作把精确消息投影到高斯分布族中“最近”的消息上。两边同除以 $c$，我们于是得到

$$g = \frac{\text{Proj}\left( ce \right)}{c}. \tag{3.15}$$

如何做到这一点的数学细节在 Herbrich 等人 [2007] 中讨论。

因此我们如下为精确消息 (6) 找到一个高斯近似。首先我们像之前一样计算精确的输出消息 (6)。它在图 3.24 中以蓝色显示。

图 3.24

图 3.24：蓝色为精确的输出消息 (6)，红色为入向的上下文消息 $c$，绿色为这两条消息之积。

然后我们把它乘以入向的上下文消息 $c$（在图 3.24 中以红色显示）。这给出一个分布（在图 3.24 中以绿色显示），它是非高斯的，但是局部化的，因此具有有限的均值和方差，从而可以用一个高斯来近似。这条曲线在图 3.25 中重复出现，图 3.25 还展示了具有相同均值和方差的高斯分布。

图 3.25

图 3.25：绿色为从图 3.24 复制来的、真实置信传播消息与入向上下文消息之积。橙色为对此积的高斯近似，即 Gaussian(140.4, 28.5²)。

最后，我们把这个高斯分布除以入向的高斯上下文消息 $c$，以生成我们的近似输出消息。因为两个高斯之比本身也是一个高斯 [Bishop, 2006]，所得的输出消息也将是高斯的，这正是我们最初的目标。对于我们这个具体例子，这条消息是一个均值为 160.8、标准差为 40.2 的高斯。近似消息的计算过程总结于图 3.26。

图 3.26

图 3.26：计算消息 (6) 高斯近似所涉及的步骤。蓝色曲线为精确消息 (6)，红色曲线为入向上下文消息 $c$，橙色曲线为真实消息与上下文消息之积的高斯近似，即 Gaussian(140.4, 28.5²)。最后，紫色曲线为橙色曲线除以红色上下文消息的结果，给出 Gaussian(160.8, 40.2²)。这个高斯随后被用作消息 (6)。

我们看到，总体上我们先乘以入向上下文消息，然后做高斯近似，最后再把上下文消息除掉。因此入向消息所提供的证据仅用于确定高斯近似应当在哪个区域上精确，而不会被直接并入近似消息本身。如果我们恰好有一个共轭分布，那么投影运算就没有必要，上下文消息也不会产生任何影响。

既然我们已经为输出消息 (6) 找到了合适的高斯近似，我们就可以继续沿图传递消息，给出相应的近似消息 (7)，如图 3.27 所示。

图 3.27

图 3.27：计算 Jskill 更新分布时的消息 (5)、(6) 和 (7)。注意以橙色高亮的消息 (6) 和 (7) 不同于图 3.18 中的精确消息，它们均为 Gaussian(160.8, 40.2²)。

对新的（近似）版本消息 (8) 的计算同样涉及一个高斯与一个高斯的卷积，结果如图 3.28 所示。

图 3.28

图 3.28：计算 Jskill 更新分布时的消息 (8) 和 (9)。注意除了消息 (6) 和 (7)，消息 (8)（橙色，Gaussian(160.8, 40.5²)）也不同于图 3.19 中的精确消息。

向下的消息 (9) 保持不变，因此我们最终可以把 Jskill 后验分布的高斯近似计算为两个高斯之积，给出最终结果：一个均值为 140.1、标准差为 28.5 的高斯。

这种在消息传递过程中局部近似消息的方法被称为期望传播（expectation propagation，简称 EP），由 Minka [2001] 提出。近似是在因子节点处局部做出的，而且其方式独立于图其余部分的结构。因此，只要每个因子都一致地用所需的分布类型（此处为高斯）发送和接收消息，该技术就可以应用于任意结构的图。期望传播算法总结于算法 3.1，其中与循环置信传播的差异以红色高亮。

算法 3.1：期望传播

输入：因子图、要计算边缘的目标变量列表、消息传递调度、初始消息值（可选）、每条边的近似分布选择。

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

  1. 把所有消息初始化为均匀（或初始值，若已提供）。
  2. 对消息传递调度中的每一条边：发送下面适当的消息——
    • 变量节点消息：在其他边上收到的所有消息之积；
    • 因子节点消息：计算置信传播消息（见算法 2.1）。乘以上下文消息（在这条边上朝该因子传来的消息）。用矩匹配把它投影到这条边所需的分布类型。把上下文消息除掉。
    • 观测节点消息：在观测值处的一个点质量；
  3. 直到所有消息收敛。
  4. 在每个目标变量节点处，把所有入向消息之积计算为边缘分布。

应用期望传播

让我们看看当把期望传播应用于 Jill 与 Fred 之间那局《光环》时，技能分布会发生什么。首先我们假设 Jill 是这局的胜者。在图 3.29 中，我们看到 Jill 和 Fred 技能的先验（虚线）与后验（实线）分布。

图 3.29

图 3.29：对 Jill（蓝色）与 Fred（红色）之间一局游戏应用 TrueSkill 模型、且 Jill 为胜者情形的结果。先验分布以虚线曲线表示，相应的后验分布以实线曲线表示。Jill 初始的宽泛技能分布表明，在这局之前我们并不知道 Jill 的技能比 Fred 高还是低。在看到她赢得这局之后，她的技能分布发生偏移，使大部分面积位于 Fred 曲线的右侧，意味着我们现在认为 Jill 很可能比 Fred 更有技能。因为我们本来就对 Fred 的技能水平相对有信心，所以他的分布几乎没有变化。

因为 Jill 是胜者，Jill 技能分布的均值增大，而 Fred 技能分布的均值减小。均值的增大对 Jill 相当大，而 Fred 的均值几乎没有减小。这个差异源于 Fskill 相比 Jskill 有更大的确定性。直觉上，我们是在用 Fred 更确定的技能来估计 Jill 的技能。我们还从图 3.29 中看到，Jill 技能分布的标准差因这局游戏而减小。这是因为我们已经了解了一些关于她技能的信息，因此不确定性的程度降低了。

或者，如果是 Fred 赢得游戏，我们就得到图 3.30 所示的结果，

图 3.30

图 3.30：与图 3.29 相同，但为 Fred 是胜者的情形。先验分布（虚线）与之前相同。我们关于 Fred 技能的可信部分同样几乎没有变化。但现在 Jill 的后验技能分布发生偏移，使大部分面积位于 Fred 曲线的左侧，意味着我们现在认为 Jill 的技能不如 Fred。

这个结果稍微更令人意外一些，因为我们本来相信 Jill 是更强的玩家，尽管我们对此并不确信。直觉上我们会因此预期技能分布的调整会稍大一些，事实确实如此。我们看到分布均值的偏移比图 3.29 中更大。事实上，Jskill 分布均值的变化如此之大，以至于它现在小于 Fskill 的均值。同样，Jill 技能的标准差减小了，反映出由于并入新证据而带来的不确定性降低。因为 TrueSkill 模型中的技能更新依赖于技能分布的方差，所以 TrueSkill 能够对新玩家的分布做出相对较大的改变。此外，这作为在我们模型中运行推断的结果而自动发生。

多局游戏

到目前为止，在本节中我们为 Jill 与 Fred 之间的单局《光环》游戏开发了一个概率模型。在实践中，我们会有一大批玩家，而各局游戏在该批玩家中的两两之间进行。当我们试图评估某个玩家的技能时，我们潜在地拥有该玩家对阵一系列不同对手所打过的所有游戏的结果。我们可能还拥有那些对手所打过的所有游戏的结果，其中许多可能涉及另外的玩家，依此类推。原则上，所有这些信息都是相关的，都可能帮助我们评估最初那个玩家的技能。此外，每当有一个新的游戏结果时，我们就可以纳入这个额外信息并更新该玩家的技能，即使他们本人没有打任何新的游戏。这个新信息可能是相关的，即使它涉及其他玩家之间的一局游戏，因为它可能影响对那些玩家技能的评估，从而影响我们这个玩家的相对技能。

原则上，我们可以通过构建一个非常大的、表达迄今为止所打过的所有游戏的因子图来处理这一点。每个玩家会有单个变量表示其技能值，但有多个变量（他们打过的每一局各一个）表示他们在每局游戏中的表现。这将是一个带有多个环的复杂图，我们可以运行（循环）期望传播，以把消息保持在高斯分布族内，直到满足某个合适的收敛准则。这将给出每个玩家的后验技能分布，同时考虑所打过的所有游戏。如果随后打了一局新游戏，我们就要用一个新的、更大的因子图重新开始，并重新运行推断，以获得每个玩家新的后验分布。这种方法实现起来会很复杂，而且每增加一局新游戏就会变得越来越慢。每天有数以百万计的游戏在进行，这完全不可行。

相反，我们可以使用一种称为在线学习（有时称为滤波，filtering）的近似推断方法，其中每个玩家的技能分布只在获得涉及该玩家的游戏结果时才更新。因此我们只需为每个玩家存储高斯技能分布的均值和方差。当某玩家打一局新游戏时，我们用这个当前的高斯技能分布作为先验来运行推断，所得的后验分布随后被存储，并构成下一局游戏的先验。因此每一局游戏都由图 3.10 所示形式的一个图来描述。

这种特定形式的在线推断算法——基于向高斯分布的局部投影、其中每个数据点（即游戏结果）只被使用一次——也被称为高斯密度滤波（Gaussian Density Filtering）[Maybeck, 1982; Opper, 1998]。它可以看作期望传播的一个特例，其中对消息传递调度做了一个特定选择：即消息只在时间上从较旧的游戏向较新的游戏向前传递，而绝不反向传递。

值得注意的是，如果我们考虑描述迄今为止所打过所有游戏的完整因子图，那么那些游戏被打的顺序本来是无关紧要的。然而，在做在线学习时，顺序变得重要，并且可以影响所评估的技能。不过我们只能接受这一点，因为在实际系统中只有在线学习才是可行的。

我们可以用取自 Xbox Live 上《光环 2》游戏的数据来说明在线学习在我们模型中的行为。我们使用一个涉及 1,650 名玩家的数据集，其中包含 5,915 局游戏的结果。每一局都是一对玩家彼此对战的一对一较量。图 3.31 展示了两位顶尖玩家的技能分布如何随两位玩家各自所打游戏局数变化。为拟合我们的模型，这些结果忽略了以平局结束的游戏——我们将在本章后面看到如何处理平局游戏。

图 3.31

图 3.31：《光环 2》一对一数据集中两位顶尖玩家技能分布的轨迹，展示了均值和正负一个标准差的包络。横轴表示相应玩家所打的游戏局数。

我们看到，初始的技能分布是相同的，因为在打任何游戏之前，所有玩家技能都有相同的先验分布。随着所打游戏局数不断增加，我们看到技能分布的标准差减小。这种因观测游戏结果而带来的不确定性降低，正是我们前面在图 3.29 和图 3.30 中看到的效应。

我们在本节中构建的模型表示两名玩家之间的单局游戏。然而，Xbox Live 上的许多游戏具有更精细的结构，因此接下来我们转向若干模型扩展，以容纳这些额外的复杂性。

本页引入概念回顾

期望传播（expectation propagation）：一种近似消息传递算法，它扩展了置信传播，允许把消息近似为某个特定族（例如高斯分布）中最接近的分布。做这种近似要么是为了确保推断算法保持可处理，要么是为了加快推断过程。见算法 3.1。

在线学习（online learning）：一种机器学习方法，其中每次考虑一个数据点，并在每个数据点之后更新模型参数分布。

自我评估 3.3

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

  1. 复现图 3.24，方法是在 Jperf 取值为 -50, -49 … 0, 1, 2 … 299, 300 处计算（红色）高斯上下文消息与（蓝色）精确 CumGauss 消息。以 Jperf 为 x 轴、所计算的消息为 y 轴，画出你得到的两条线。你需要对 CumGauss 消息重新缩放以使其适配（记住这条消息的尺度无关紧要，因为它是一个非正常分布）。要得到对应 Jperf 精确边缘的（绿色）乘积消息，先在每个 Jperf 值处把你的两条消息相乘。然后重新缩放结果，使线下面积为 1（你可以大致地通过重新缩放使每个点的值之和等于 1 来实现）。把这个结果作为第三条线画在你的坐标轴上。
  2. 计算你刚刚算出的精确边缘乘积消息的均值和标准差。均值可以很好地近似为：在每个点处把消息乘以该点的 Jperf 值再求和。方差（即标准差的平方）可以用助记口诀“平方的均值减去均值的平方”类似地近似。首先，你需要计算“平方的均值”，它可以近似为：在每个点处把消息乘以该点 Jperf 值的平方再求和。然后减去“均值的平方”，也就是你刚算出的那个均值。这给出方差，你可以对它取平方根得到标准差。你现在已经计算出对 Jperf 边缘的高斯近似的均值和标准差。你可以对照图 3.25 中的高斯来检查你的结果。
  3. 最后，我们需要把这个高斯分布（其均值和标准差你刚在上一题中求出）除以高斯上下文消息。关于如何做到这一点，你可以参考 Bishop [2006]。你可以对照图 3.27 中的消息 (6) 来检查你的结果。恭喜！你现在已经成功计算出了一条期望传播消息！
  4. 现在我们可以用 Infer.NET 来替我们做期望传播计算。在 Infer.NET 中实现 TrueSkill 模型，把 Jill 和 Fred 的技能分布设为本节所用的那些。参考 Infer.NET 文档中关于如何表示大型不规则图的指南。计算 Jill 和 Fred 在“Jill 获胜”与“Fred 获胜”这两种结果下的后验边缘分布。画出你的结果，并对照图 3.29 和图 3.30 检查它们。

参考文献

[Bishop, 2006] Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.

[Minka, 2005] Minka, T. (2005). Divergence Measures and Message Passing. Technical Report MSR-TR-2005-173, Microsoft Research.

[Herbrich et al., 2007] Herbrich, R., Minka, T., and Graepel, T. (2007). TrueSkill(TM): A Bayesian Skill Rating System. In Advances in Neural Information Processing Systems 20, pages 569–576. MIT Press.

[Minka, 2001] Minka, T. P. (2001). Expectation propagation for approximate Bayesian inference. In Uncertainty in Artificial Intelligence, volume 17, pages 362–369.

[Maybeck, 1982] Maybeck, P. S. (1982). Stochastic models, estimation, and control. In Volume 2, volume 141, Part 2 of Mathematics in Science and Engineering, chapter 12 Nonlinear estimation, pages 212–271. Elsevier.

[Opper, 1998] Opper, M. (1998). A Bayesian approach to on-line learning. In Saad, D., editor, On-line Learning in Neural Networks, pages 363–378. Cambridge University Press, New York, NY, USA.

下一节：核心模型的扩展