到目前为止，我们假设已经知道 Jill 和 Fred 的技能，并用这些技能计算了每个玩家成为胜者的概率。在实践中，我们必须反向推理：我们观察到谁赢得了游戏，并需要用这个信息来了解玩家的技能值。因此，我们转向学习玩家技能这一问题。

下棋

在任何游戏中，看到谁胜谁负都会告诉我们关于玩家技能的信息。

给定一局游戏的结果，提高胜者的技能值、降低败者的技能值似乎是合理的。然而，不太清楚的是我们应当做多大的调整。直觉上我们可以这样推理。假设 Jill 是这局游戏的胜者。如果 Jill 的技能显著高于 Fred，那么 Jill 获胜并不令人意外，因此技能值的变化应当相对较小。如果技能相近，那么较大的变化就有道理。然而，如果 Jill 的技能显著低于 Fred，那么这个游戏结果就非常令人意外。这个结果表明我们当前对技能值的评估不太准确，因此我们应当对技能值做大得多的调整。简而言之，意外的程度指示了应当对技能值做多大的改变。我们将看到，在一个合适的模型中执行推断会自动给出这种行为。

建模技能

我们已经指出，技能是一个不确定的量，因此应当作为一个随机变量纳入模型。我们需要为这个变量定义一个合适的先验分布。这个分布捕捉了在玩家玩这一具体对局之前，我们关于其技能的先验知识。对于新玩家，这个分布需要较宽，覆盖该玩家可能具有的全部技能范围。对于更成熟的玩家，我们可能已经对其技能有很好的了解，因此分布会更窄。因为技能是一个连续变量，我们可以再次使用高斯分布来定义这个先验。这代表了对我们第一条建模假设的修改，它变为：

每个玩家都有一个技能值，用一个带有高斯先验分布的连续变量表示。

让我们回到 Jill 与 Fred 之间的那局《光环》。到目前为止我们假设 Jill 和 Fred 的技能值已知，分别为 15 和 12.5。在本章的其余部分，我们将转而假设 Jill 和 Fred 的技能未知，而是具有由高斯分布表示的不确定性。对于 Jill，我们现在假设平均技能为 120、标准差为 40——如果 Jill 是相对较新的玩家、因而其技能存在很大不确定性，通常就会出现这种情况。对于 Fred，我们现在假设平均技能为 100、标准差为 5，如果 Fred 是技能更精确已知的更成熟玩家，这就是合理的。因此，我们必须通过引入另外两个不确定变量 Jskill 和 Fskill（Jill 和 Fred 的技能）来扩展模型。这些变量中的每一个都将有自己的高斯分布，因此在因子图中也有自己的因子。我们扩展后的模型的因子图如图 3.10 所示。

图 3.10

图 3.10：一局游戏中两名技能不确定的玩家的 TrueSkill 模型。变量包括 Jill 的技能 Jskill、Fred 的技能 Fskill、Jill 的表现 Jperf、Fred 的表现 Fperf（均为 double）以及 Jill 是否获胜 Jwins（bool）。这里我们用记号 Gaussian(•, 5²) 描述一个因子，其分布为高斯，均值由父变量（此处为相应的技能变量）给出、标准差为 5。

图 3.10 中的模型由 Herbrich 等人 [2007] 提出，他们称之为 TrueSkill 模型。提醒一下，模型中编码的假设一并展示在图 3.11 中。

  1. 每个玩家都有一个技能值，用一个带有宽泛高斯分布的连续变量表示。
  2. 每个玩家在每局游戏中都有一个表现值，它在不同对局之间是相互独立的，其平均值等于该玩家的技能。表现的变动对所有玩家都相同，围绕均值对称分布，并且更可能接近均值而非远离均值。
  3. 表现值最高的玩家赢得游戏。

图 3.11：我们模型中编码的三条假设。

在明确陈述了建模假设之后，值得花点时间回顾它们。假设 3.1 说一个玩家在某一特定类型游戏中的能力可以表达为单个连续变量。这在大多数情形下似乎是合理的，但我们可以设想对玩家能力更复杂的描述，例如区分其进攻技能与防守技能。这在团队游戏（稍后讨论）中可能很重要，那里一支强队可能需要在进攻能力强的玩家与防守能力好的玩家之间取得平衡。我们还为技能变量假设了高斯先验。这是我们对连续技能变量所能采用的最简单的概率模型，它带来了一些良好的解析和工程性质。然而，如果我们观察一大群玩家的技能，可能会发现技能的分布相当不服从高斯分布，例如，新玩家往往技能较低，但如果他们此前玩过类似游戏，偶尔也可能技能很高。

类似地，假设 3.2 考虑单个表现变量，并再次假设它服从高斯分布。玩家有时确实可能会有严重“失常”的一天，其表现远低于其技能值，而玩家表现远高于其技能值则极不可能。这表明表现分布可能是非对称的。另一个可以改进的方面是“方差对所有玩家都相同”这一假设——某些玩家很可能比其他玩家更稳定，因此会有相应更低的方差。

最后，假设 3.3 说游戏结果纯粹由表现值决定。如果我们引入多个变量来刻画一个玩家的技能，那么它们大概各自会有一个相应的表现变量（例如玩家在进攻或防守中的表现如何），而我们就需要定义如何把这些组合起来以决定一局游戏的结果。

TrueSkill 模型中的推断

一局游戏结束后，我们的目标是利用游戏结果来推断玩家更新后的技能分布。这涉及求解一个概率推断问题，以计算每个玩家技能的后验分布，同时考虑游戏结果所提供的新信息。虽然先验分布是高斯的，但事实证明相应的后验分布并不是高斯的。下一小节展示如何计算技能的后验分布以及为什么它不是高斯的——如果你愿意，尽可跳过它或稍后再回来看。

推断深入探讨

在这个可选小节中，我们看看如何在到目前为止所定义的模型中进行精确推断，然后看看为什么精确推断在实践中不可用。如果你想专注于建模，尽可跳过本小节。

既然我们已经有了描述模型的因子图，我们就可以根据观测到的游戏结果设置变量 Jwins，并运行推断以计算技能变量 Jskill 和 Fskill 的边缘后验分布。这个图具有树结构（没有环），因此正如我们已经在第 2 章中看到的，我们可以用置信传播来求解这个问题。

考虑在 Jill 赢得游戏（Jwins 为 true）的情形下计算 Jskill 的后验分布。使用置信传播算法，我们必须计算图 3.12 所示的消息。

图 3.12

图 3.12：在应用置信传播计算 Jskill 的更新分布时出现的消息 (1)–(9)。

消息 (1) 就由高斯因子本身给出。类似地，消息 (2) 就是 Fskill 节点其他边上所有入向消息的乘积，由于只有一条入向消息，它就直接被复制为输出消息。这最初的两条消息总结在图 3.13 中。

图 3.13

图 3.13：应用置信传播计算 Jskill 更新分布时的消息 (1) 和 (2)：均为 Gaussian(100, 5²)。

接下来我们必须计算图 3.12 中的消息 (3)。置信传播算法告诉我们，把入向消息 (2) 乘以高斯因子，然后对变量 Fskill 求和。在这里，由于 Fskill 是连续变量，求和变成了积分。我们可以再次通过考虑基于采样的生成式视角来对这一步获得一些洞见。设想我们从关于 Fskill 的高斯分布中抽取样本。每个样本是 Fskill 的一个具体值，并构成关于 Fperf 的一个高斯分布的均值。在图 3.14a 中，我们考虑 Fskill 的三个样本，并画出相应的关于 Fperf 的分布。为计算所需的输出消息，我们随后对这些样本求平均，得到图 3.14b 所示的结果。这代表了对 Fskill 边缘化的一个近似，如果我们考虑无穷多个样本而不只是三个，它就会变得精确。

图 3.14a

(a) 3 个样本

图 3.14b

(b) 3 个样本（求平均）

图 3.14c

(c) 6 个样本（求平均）

图 3.14d

(d) 100 个样本（求平均）

图 3.14：对图 3.12 中消息 (3) 计算的采样近似示意。(a) 展示三个高斯，其均值本身是从 Gaussian(100, 5²) 采样得到的；(b) 展示这三个样本的平均。随着我们增加样本数，平均逐渐接近高斯，如 (c) 和 (d) 所示。

如图 3.14c 和图 3.14d 所示，随着样本数增加，采样近似变得更加精确。在最后这张图中，所得分布看起来几乎是高斯的。这并非巧合，事实上输出消息的计算可以精确求出（见 Bishop [2006] 中的方程 (2.115)），结果是输出消息也是一个高斯，其均值为 Fskill 分布的均值，其方差为 Fskill 和 Fperf 方差之和：$5^2 + 5^2$。这种用一个高斯把另一个高斯“抹开”的过程，是一种叫作卷积的数学运算的例子。消息 (4) 只是消息 (3) 的一份副本，因为 Fperf 节点只有一条入向消息。由于我们观测到 Jwins 为 true，消息 (5) 是在值 true 处的一个伯努利点质量。这三条消息示意于图 3.15。

图 3.15

图 3.15：计算 Jskill 更新分布时的消息 (3)、(4) 和 (5)。其中 (3) 与 (4) 为 Gaussian(100, 5² + 5²)，(5) 为 Bern(1.0)。

现在让我们转向计算消息 (6)。Jill 获胜（Jwins = true）这一观测施加了一个约束：Jill 的表现必须高于 Fred 的表现，即 $\text{Jperf} > \text{Fperf}$。当我们在 Jwins 被设为 true 的情况下乘入 GreaterThan 因子时，就施加了这个约束。图 3.16 展示了把这个约束乘到来自 Fperf 的高斯消息上的效果。在图中，对角线下方——换句话说，$\text{Jperf} \le \text{Fperf}$ 处——乘积始终为零。这个区域被置零，因为它对应 Fred 获胜，而这具有零概率，因为它与我们“Jill 获胜”的观测相矛盾。于是我们最终得到一个在对角线处被截断的高斯“隆起”。

图 3.16

图 3.16：把 GreaterThan 因子乘以消息 (4) 和 (5) 再对消息 (5) 求和的结果图。注意此图表示一个未归一化的分布，因此未显示纵轴刻度。

要计算消息 (6)，我们必须把图 3.16 中的乘积对 Fperf 积分，从而得到一个作为 Jperf 函数的消息。你可以这样直观理解这条消息：想象从 Jill 表现轴的方向看这个被截断的高斯隆起，并对从每一点所能看到的部分求和。所得消息在约 80 以下为零，然后在约 120 处向上弯曲到接近一，并从那里一直保持到无穷，如图 3.17 所示。

图 3.17

图 3.17：从 GreaterThan 因子到 Jperf 变量的精确置信传播消息 (6)，它由一个累积高斯给出。

读者应当花点时间确认，这个函数的形状正是对图 3.16 关于变量 Fperf 积分所应期望的。数学上，对每一个 Jperf 值都在对一个被截断的高斯分布积分，这等价于计算我们此前在方程 (3.10) 中引入的累积高斯，因此这条消息可以解析地求出（实际上，图 3.17 正是这样画出来的）。

对这条消息形状的另一种解读：假设我们已知 Fperf 恰好是 100。既然 Jill 获胜，这告诉我们 Jill 的表现 Jperf 必定是某个大于 100 的数。这将意味着一条阶跃形状的消息，在 100 以下取值为零、以上取某个正常数。由于我们并不知道 Fperf 恰好是 100，而只知道它很可能接近 100，这就把阶跃抹开成图 3.17 那条光滑函数。

因为消息 (6) 一直延伸到无穷，它构成了我们所说的非正常分布，即面积无法归一化到总和为一的分布。在置信传播中，允许消息是非正常的，只要它们不会导致后验边缘分布变得非正常。例如，在这里，这条非正常消息将被乘以一条正常的归一化消息，给出一个可以归一化因而是正常的后验。

消息 (7) 只是消息 (6) 的一份副本，因为 Jperf 节点只有一条入向消息。这些消息示意于图 3.18。

图 3.18

图 3.18：计算 Jskill 更新分布时的消息 (6) 和 (7)，均为 CumGauss((x − 100)/5√2)。

消息 (8) 是通过把描述表现变动性的高斯因子乘以入向消息 (7)、然后对 Jperf 积分求得的。这同样是一个卷积，同样有一个精确解，形式仍是累积高斯。实际上它是入向累积高斯消息的一个模糊版本，被高斯表现因子的方差抹开。最后，消息 (9) 是技能先验的高斯分布。这些消息总结于图 3.19。

图 3.19

图 3.19：计算 Jskill 更新分布时的消息 (8) 和 (9)。其中 (8) 为 CumGauss(•)，(9) 为 Gaussian(120, 40²)。

为得到 Jskill 的边缘分布，我们随后把消息 (8) 和 (9) 相乘。因为这是一个高斯与一个累积高斯的乘积，结果是一个非对称的隆起状分布，因此不是高斯。这些消息以及所得的 Jskill 边缘分布展示在图 3.20 中。

图 3.20

图 3.20：蓝色为精确消息 (8)，红色为精确消息 (9)。绿色为这两条消息的乘积，给出关于 Jskill 的精确边缘。注意这个精确边缘是非高斯的。

我们似乎已经解决了求 Jskill 后验分布的问题。我们也可以沿图向相反方向传递消息，以得到 Fskill 相应的后验分布。这些后验分布可以精确地表达为一个高斯与一个累积高斯的乘积，因此需要四个参数来描述它们，其中两个额外的参数来自累积高斯。

使用精确推断的一个问题

我们现在有了一种方法来计算关于玩家技能的后验分布。问题在于这些后验分布不是高斯的。相反，它们具有一种更复杂的分布形式，需要四个数字来表达，而高斯只需两个。如果我们设想 Jill 接下来与一名新玩家再玩一局，这个差异就会造成一个大问题。在与 Fred 对局之前，我们对 Jskill 值的不确定性表达为一个高斯分布，它有两个参数（均值和方差）。在她与 Fred 对局之后，相应的后验分布表达为一个有四个参数的更复杂分布。现在假设 Jill 又与 Alice 玩一局《光环》。我们可以再次用一个类似图 3.10 的因子图来表示它，只不过描述我们当前对 Jskill 不确定性的因子现在是与 Fred 对局所产生的后验分布。当我们在这个新图中运行推断以考虑与 Alice 对局的结果时，新的后验边缘将是一个更加复杂的分布，需要六个参数（具体来说，是一个高斯与两个不同累积高斯的乘积）。每次 Jill 玩一局《光环》，关于她技能的分布都会变得更加复杂。

注意，如果所关心变量的后验分布与先验分布具有相同的形式，这个问题就不会出现。在某些概率模型中，我们能够选择一种称为共轭先验的先验分布形式，使得后验最终与先验具有相同的形式。看看专栏 3.2，可以了解更多关于共轭分布的内容。

从消息传递的视角看，共轭性意味着到达某个变量节点的所有消息之积与先验消息具有相同的形式。这一般意味着所有入向消息都与先验消息具有相同的形式。在我们的模型中，来自 GreaterThan 因子的向上消息不是高斯的，因此传到 Jskill 变量的消息也不是。这意味着先验高斯分布不是 Jskill 的共轭分布。

没有共轭性，就有必要引入某种形式的近似，以使 Jskill 的后验保持为高斯。在下一节中，我们将描述一个强大的算法，它扩展了置信传播，允许在消息即使不共轭时也能被近似。这个算法不仅会解决这个模型的推断问题，而且事实证明它也适用于种类繁多的其他概率模型——包括本书中的每一个模型！

专栏 3.2：共轭分布

我们可以通过考虑下面的例子来说明共轭分布的思想。假设我们正通过一个网页销售商品，我们想知道用户点击“购买”按钮的概率。我们把这个概率记为 $x$。那么他们不点击的概率就是 $1 - x$。注意这正是我们在第 1 章中见过的伯努利分布。

假设我们从多个网页访客那里收集数据，发现其中有 $N$ 个人点击了按钮、$M$ 个人没有点击。如果我们假设对网页的访问是相互独立的，那么在给定 $x$ 值的情况下，看到这些数据的条件概率通过把每次点击/不点击事件的概率相乘得到，于是

$$P(\text{data} \mid x) = x^N (1-x)^M. \tag{3.11}$$

如果我们希望从这些数据中学习 $x$ 的值，我们需要定义一个先验概率密度 $p(x)$。这个先验有一种特定的形式使计算格外容易，即如果我们选择 $p(x)$ 与方程 (3.11) 具有相同的形式，也就是：

$$p(x) \propto x^A (1-x)^B \tag{3.12}$$

其中 $A$ 和 $B$ 是参数。在这种情况下，由贝叶斯法则，相应的后验分布就是

$$\begin{aligned} p(x \mid \text{data}) & \propto P(\text{data} \mid x) \times p(x) \\ & \propto x^{A+N} (1-x)^{B+M} \end{aligned} \tag{3.13}$$

因此后验分布与先验分布具有相同的函数形式，只是 $A$ 被替换为 $A+N$、$B$ 被替换为 $B+M$。先验分布 (3.12) 被称为与伯努利分布共轭。事实上，你可以看出这个先验分布正是我们在第 2.6 节中引入的beta 分布。

共轭分布还有许多其他例子 [Bishop, 2006]。例如，高斯均值的共轭先验就是另一个高斯，而高斯精度的共轭先验被称为 Gamma 分布，我们将在第 4 章中遇到它。对于第 1 章那个简单的谋杀之谜，先验分布是一个伯努利，它与表示“给定凶手身份时凶器概率”的条件分布共轭。

在因子图上运行推断时，我们可以把共轭性看作节点对之间的一种局部性质。为防止消息复杂度增长，每当父分布与相应子分布之间存在非共轭关系时，我们就需要为输出消息找到一个近似。

本页引入概念回顾

卷积（convolution）：函数 $f$ 与函数 $g$ 的卷积衡量 $f$ 与被平移了量 $a$ 的 $g$ 版本之间的重叠。它被表达为 $a$ 的函数。更多信息见 Wikipedia。

非正常分布（improper distribution）：面积之和不为一的分布。

共轭分布（conjugate distribution）：对于给定的似然函数，如果相应的后验分布与先验具有相同的函数形式，则称该先验分布是共轭的。

自我评估 3.2

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

  1. 复现图 3.14，方法是画出若干高斯分布的平均，每个高斯的标准差为 5、均值由 Gaussian(100, 5²) 的一个样本给出。分别对 $K=3$、$K=6$ 和 $K=100$ 个样本这样做。
  2. 参考专栏 3.2，用贝叶斯定理计算：在 $N=20$ 个人点击按钮、$M=100$ 个人不点击的情况下，关于 $x$（点击购买按钮的概率）的后验分布。假设一个 Beta(1,1) 先验分布。注意这是一个共轭先验，因此后验分布也是一个beta 分布。
  3. 【进阶】证明两个高斯分布的卷积也是一个高斯分布，其方差为两个原始分布方差之和。Bishop [2006] 中的第 2.3.3 节应会有所帮助。

参考文献

[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.

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

下一节：一个解法：期望传播