在上一篇文章，「GPT 系列模型从第一性原理看 LLM 演进：GPT-1/2/3 到 InstructGPT 与 LLaMA 2 的范式变迁」，我们详细给大家介绍了奖励模型（Reward Modeling）的作用，并且也梳理了 GPT 系列模型的发展脉络，同时也知道了奖励模型在大模型的训练过程中扮演的是一个裁判员的角色。
奖励模型作为模型对齐时的裁判，它出现在了后续很多大模型训练过程中，包括 InstructGPT、 LLaMa 2、 LLaMa 3、GPT-4 等等，那到底是谁把它引入了大模型的训练过程中呢？然后又是如何一步一步发展到现在这样的呢？
在这篇文章中，将给大家介绍奖励模型中构建目标函数是的核心思想——Bradley-Terry 模型。
关键字：奖励模型、LLM、Bradley-Terry
1. Bradley-Terry 模型#
为了能够更加清楚的介绍后续奖励模型当中目标函数的由来及意义，我们先来简单的看一下 Bradley-Terry 模型，因为它可以说是 成对比较（Paired Comparisons） 模型的开山鼻祖。
1.1 Bradley-Terry 模型思想#
在生活中，我们经常需要对一组对象（比如产品、球队、方案、文稿等）进行比较和排序，比如：
-
球迷在争论梅西和C罗谁更强；
-
消费者在比较两款饮料到底哪个更好喝；
-
NBA 一个赛季结束以后哪个球队更强
我们可以发现，这些比较都有一个显著的共同点，那就是往往都不能给出“绝对的分数”，因为不同的人评价标准和尺度不一致，直接打分可能会带来主观性的偏差。
那对于这样的问题我们应该如何来解决呢？
1952年，Ralph Allan Bradley 和 Milton E. Terry 发表了一篇名为《Rank analysis of incomplete block designs: I. The method of paired comparisons》[1] 的文章来详细的描述了这类问题的解决办法，它是统计学和心理测量学领域里一篇非常经典的论文，其核心思想便是我们现在奖励模型当中构建目标函数时所使用到的 Bradley–Terry 模型。
Bradley-Terry 模型的思想是，假设每个对象 $i$ 都有一个潜在的 “能力” 用参数 $\pi_i (\pi_i > 0)$ 表示，当对象 $i$ 和 $j$ 进行两两比较时，$i$ 被选择的概率定义为
$$ P(i \succ j) = \frac{\pi_i}{\pi_i + \pi_j}\tag{1} $$这里 $\pi_i$ 可以理解为对象 $i$ 的一种能力或置信度，那么如果 $\pi_i = \pi_j$，则两个对象被选中的概率相等；如果 $\pi_i \gg \pi_j$，则对象 $i$ 基本总是胜出。
这样，我们只需要根据若干次对象 $i$ 与 $j$ 之间排序结果，利用最大似然估计便可以估计得到 $P(i \succ j) $ 的概率。
1.2 Bradley-Terry 模型原理#
在式(1)的基础上，为了方便计算和归一化通常将 $\pi_i$ 表示为指数形式，即
$$ \pi_i = e^{\beta_i}\tag{2} $$进一步式(1)可以写为
$$ P(i \succ j) = \frac{e^{\beta_i}}{e^{\beta_i} + e^{\beta_j}}\tag{3} $$此时，设 $n_{ij}$ 和 $n_{ji}$ ，且 $i,j=1,2,...,t$，分别表示在若干对象 $i$ 与 $j$ 之间的对比中 $i$ 获胜的次数和 $j$ 获胜的次数，且每次比较之间相互独立，那么便可以得到如下似然函数
$$ L(\pi_1, \dots, \pi_t) = \prod_{i=1}^{t} \prod_{j=i+1}^{t} \left( \frac{\pi_i}{\pi_i + \pi_j} \right)^{n_{ij}} \left( \frac{\pi_j}{\pi_i + \pi_j} \right)^{n_{ji}}.\tag{4} $$式(4)的含义便是估计得到能够使得已知结果最容易发生的参数 $\pi_i$ 。
进一步，在求解时我们通常会对式(4)取对数操作，此时可得
$$ \begin{aligned} \ell(\pi_1,\dots,\pi_t) &=\sum_{i=1}^t\sum_{j=i+1}^t\Big[ n_{ij}\ln\pi_i + n_{ji}\ln\pi_j -(n_{ij}+n_{ji})\ln(\pi_i+\pi_j) \Big] \end{aligned}\tag{5} $$接着，在式(5)中让 $\ell$ 分别对 $\pi_k$ 求解偏导，可得目标函数 $\ell$ 关于 $\pi_k$ 的偏导数为
$$ \frac{\partial \ell}{\partial \pi_k} = \frac{W_k}{\pi_k} - \sum_{j \neq k} \frac{N_{kj} }{\pi_k + \pi_j}\tag{6} $$其中 $W_k = \sum_{j \neq k} n_{kj}$ 表示对象 $k$ 总的获胜次数， $N_{kj}=n_{kj} + n_{jk}$ 是对象 $k$ 和 $j$ 之间总的对比次数。
关于式(6)的推导过程，将在本文第3节内容中进行介绍。
1.3 Bradley-Terry 模型求解迭代公式#
在得到目标函数 $\ell$ 关于 $\pi_k$ 的梯度以后便可以利用梯度下降算法，即先随机初始化 $\pi_1,..,\pi_t$，然后根据式(7)进行迭代求解
$$ \pi_k^{(t+1)} = \pi_k^{(t)} + \alpha \left( \frac{W_k}{\pi_k^{(t)}} - \sum_{j \neq k} \frac{N_{kj}}{\pi_k^{(t)} + \pi_j^{(t)}} \right)\tag{7} $$因为是最大化 $\ell$ ，所以式(7)的两项之间是加号。
不过，在 Bradley-Terry 模型的特定结构下，使用得更多的是 Majorization-Minimization 迭代公式，因为它收敛通常更稳定。
由式(6)可知，令梯度为零可得
$$ \frac{W_k}{\pi_k} = \sum_{j \neq k} \frac{N_{kj} }{\pi_k + \pi_j}\tag{8} $$此时，式(8)被称为固定点方程（Fixed-point Equation），因为它表示 $\pi_k$ 可以用右侧的表达式来表示自身。
进一步，我们可以使用固定点迭代（Fixed-point Iteration）来求解得到 $\pi_k$，即
$$ \pi_k = \frac{W_k}{\sum_{j \neq k} \frac{N_{kj}}{\pi_k + \pi_j}}\tag{9} $$为了进行迭代，我们引入迭代索引 $t$，且假设在第 $t$ 次迭代时，我们有当前的估计 $\pi_1^{(t)}, \pi_2^{(t)}, \dots, \pi_t^{(t)}$，所以 $\pi_k$ 的第 $t+1$ 次估计为
$$ \pi_k^{(t+1)} = \frac{W_k}{\sum_{j \neq k} \frac{N_{kj}}{\pi_k^{(t)} + \pi_j^{(t)}}}\tag{10} $$这个公式就是 Bradley-Terry 模型的标准迭代公式。
2. Bradley-Terry 模型示例计算#
我们在清楚了 Bradley-Terry 模型的原理以后，我们再来通过一个简单的示例，来手动计算整个过程。
假设我们有 3 个球队：A、B、C，他们进行了如下对局：
-
A vs B：A 赢 3 次，B 赢 1 次
-
A vs C：A 赢 2 次，C 赢 2 次
-
B vs C：B 赢 3 次，C 赢 2 次
那么，A、B、C 三个球队到底谁更厉害呢？
2.1 主观分析#
在利用 Bradley–Terry 模型求解以前，我们先来根据结果描述分析一下，然后感官上给定一个排序。从结果来看 A 最好，因为 A 胜过 B，且平于 C；而 C 平于 A 而输于 B。其次，以 A 为过渡对象，所以可以得出 C 好于 B。 所以，最终排序为 A > C > B 这一结果。
2.2 Bradley–Terry 模型估计#
下面我们用 Bradley–Terry 模型来估计三人的实力。
首先，根据上面的对局情况我们可以得到如下结果表
| A | B | C | |
|---|---|---|---|
| A | — | 3 | 2 |
| B | 1 | — | 3 |
| C | 2 | 2 | — |
根据上表第一行可知，球队 A 一共胜了 $W_1=3+2=5$ 场，同理 $W_2=4$，$W_3=4$ 。同时，$N_{12}=3+1=4$，即球队 A 和 B 之间一共进行了4次比赛，同理 $N_{13}=4$，$N_{23}=5$ 。
进一步，我们随机初始化 $\pi_1=\pi_2=\pi_3=0.3$，分别表示A、B 和 C 这 3 个球队的初始能力。
此时，根据式(10)第 $t=1$ 轮迭代后的结果为
$$ \begin{aligned} \pi_1^{(2)} &= \frac{W_1}{\sum_{j \neq 1}^3 \frac{N_{1j}}{\pi_1^{(1)} + \pi_j^{(1)}}} =\frac{5}{\frac{4}{0.3+0.3}+\frac{4}{0.3+0.3}}\approx0.375\\[4pt] \pi_2^{(2)} &= \frac{W_2}{\sum_{j \neq 2}^3 \frac{N_{2j}}{\pi_2^{(1)} + \pi_j^{(1)}}} =\frac{4}{\frac{4}{0.3+0.375}+\frac{5}{0.3+0.3}}\approx0.281\\[4pt] \pi_3^{(2)} &= \frac{W_3}{\sum_{j \neq 3}^3 \frac{N_{3j}}{\pi_3^{(1)} + \pi_j^{(1)}}} =\frac{4}{\frac{4}{0.3+0.375}+\frac{5}{0.3+0.281}}\approx0.275 \end{aligned} \tag{11} $$同理，在经过2轮迭代后，$\pi_1^{(2)}=0.408$、$\pi_2^{(2)}=0.27$、$\pi_3^{(2)}=0.266$。
最终，经过6轮迭代以后，将会收敛于 $\pi_1=0.434$、$\pi_2=0.261$、$\pi_3=0.261$。
可以发现，在算法看来 B 和 C 的总体能力是相当的，且进一步根据式(1)可得
$$ P(\pi_1 \succ \pi_2) = \frac{\pi_1}{\pi_1 + \pi_2}=\frac{0.434}{0.434+0.261}\approx0.624\tag{12} $$也即球队 A 胜过 球队 B 的概率为 0.624。
3. Bradley-Terry 模型梯度求解#
由式(5)可知，目标函数是一个双重求和，涉及所有 $i = 1, 2, \dots, t$ 和 $j = i+1, \dots, t$ 的配对。每项包含三部分：$n_{ij} \ln \pi_i$ 涉及 $\pi_i$ ，
$n_{ji} \ln \pi_j$ 涉及 $\pi_j$ ，$-(n_{ij} + n_{ji}) \ln (\pi_i + \pi_j)$ 涉及 $\pi_i + \pi_j$。
当我们对 $\pi_k$ 求偏导时，只有包含 $\pi_k$ 的项会产生非零导数，所以我们需要找出所有 $\pi_k$ 出现的项，即
当 $i = k$ 时，$\pi_k$ 出现在 $n_{ij} \ln \pi_i$ 和 $-(n_{ij} + n_{ji}) \ln (\pi_i + \pi_j)$ 这两项中，此时 $j = k+1, \dots, t$
当 $j = k$ 时，$\pi_k$ 出现在 $n_{ji} \ln \pi_j$ 和 $-(n_{ij} + n_{ji}) \ln (\pi_i + \pi_j)$ 这两项中，此时 $i = 1, \dots, k-1$
因此，偏导数 $\frac{\partial \ell}{\partial \pi_k}$ 将由以下两部分组成：
① $i = k, j > k$ 的项。
② $j = k, i < k$ 的项。
为了计算 $\frac{\partial \ell}{\partial \pi_k}$，我们将目标函数分成两部分
① 当 $i = k, j = k+1, \dots, t$，对应的项为
$$ \sum_{j=k+1}^t \left[ n_{kj} \ln \pi_k + n_{jk} \ln \pi_j - (n_{kj} + n_{jk}) \ln (\pi_k + \pi_j) \right]\tag{13} $$② 当 $j = k, i = 1, \dots, k-1$，对应的项为
$$ \sum_{i=1}^{k-1} \left[ n_{ik} \ln \pi_i + n_{ki} \ln \pi_k - (n_{ik} + n_{ki}) \ln (\pi_i + \pi_k) \right]\tag{14} $$将这两部分合并，目标函数中涉及 $\pi_k$ 的项为
$$ \begin{aligned} \ell_{\pi_k} =& \sum_{j=k+1}^t \left[ n_{kj} \ln \pi_k + n_{jk} \ln \pi_j - (n_{kj} + n_{jk}) \ln (\pi_k + \pi_j) \right] \\[4pt] +& \sum_{i=1}^{k-1} \left[ n_{ik} \ln \pi_i + n_{ki} \ln \pi_k - (n_{ik} + n_{ki}) \ln (\pi_i + \pi_k) \right] \end{aligned} \tag{15} $$进一步，根据式(15)有
$$ \begin{aligned}\frac{\partial \ell}{\partial \pi_k} &= \left( \frac{1}{\pi_k} \sum_{j=k+1}^t n_{kj} - \sum_{j=k+1}^t \frac{n_{kj} + n_{jk}}{\pi_k + \pi_j} \right) + \left( \frac{1}{\pi_k} \sum_{i=1}^{k-1} n_{ki} - \sum_{i=1}^{k-1} \frac{n_{ik} + n_{ki}}{\pi_i + \pi_k} \right)\\[6pt] &=\frac{1}{\pi_k}\left(\sum_{j=k+1}^t n_{kj} + \sum_{i=1}^{k-1} n_{ki}\right)-\left(\sum_{j=k+1}^t \frac{n_{kj} + n_{jk}}{\pi_k + \pi_j} +\sum_{i=1}^{k-1} \frac{n_{ik} + n_{ki}}{\pi_i + \pi_k}\right) \end{aligned} \tag{16} $$经过分析我们可以知道，式(16)中第1项的括号里的表示对象 $k$ 击败其他选手的总胜场数，记为 $W_k$ ，则有
$$ W_k = \sum_{j=k+1}^t n_{kj} + \sum_{i=1}^{k-1} n_{ki} = \sum_{j \neq k} n_{kj}\tag{17} $$式(16)中第2项可以合并为（大家可以举例进行实验）
$$ \sum_{j \neq k} \frac{n_{kj} + n_{jk}}{\pi_k + \pi_j}\tag{18} $$因此，最终可得偏导数为
$$ \frac{\partial \ell}{\partial \pi_k} = \frac{W_k}{\pi_k} - \sum_{j \neq k} \frac{n_{kj} + n_{jk}}{\pi_k + \pi_j}\tag{19} $$引用#
[1] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika, 39(3/4):324–345, 1952.
[2] https://en.wikipedia.org/wiki/Bradley%E2%80%93Terry_model
[3] https://web.stanford.edu/class/archive/stats/stats200/stats200.1172/Lecture24.pdf