概要

经典的Elo评价系统(Elo rating systems)被广泛应用于竞技比赛等各类排名场景中，但在处理较复杂的场景时（如多人多队的团队赛），TrueSkill评价系统[1]则更灵活, 易扩展, 也更容易应用。本文就TrueSkill的原理做简单的介绍，增加大家对TrueSkill这类概率图模型的认知，希望对大家的实际工作或研究有所帮助。

1. 关于排名

生活中的排名太多了，简直是无处不在。考试成绩，网页搜索，大学排行等都是排名的结果。对此，我们已司空见惯，但一个排名要有意义，需要满足什么条件呢? 简单的说, 一个有意义的排名必须要和实际情况基本保持一致。具体的，它至少应该满足以下两点。

(1) 排名具有可传递性：如果 A>B,B>C，那么 A>C 。

(2) 排名能反映预期：给定一个排名, 那么任意两者之间对比的结果的期望应和排名顺序基本一致。 例如， 如果A>B>C， 那么A最强， B和C次之；而且如果两两对比， A赢C要比赢B容易一些，因为B比C强。

有些排名可能是存在随机性的，单次的排名结果会可能会受到随机性的影响。例如，每次考试的排名可能会因为题目难易，考生状态等因素产生变化。一个好的排名系统需要从这些排名的结果对排名对象进行合适的评价。下面我们以单次考试为例，从概率的观点来考察排名的随机结果和其有效性。

(1) 以同样的试题，同样的考试环境，统一的评卷标准下得到所有考生的一次的成绩。

(2) 假设考生考试后能够忘记当次的试题和经验，我们可以用同样的试题让每名考生重复考试（如100次，独立同分布试验），集中每人的100次成绩为一个成绩样本（不人道）。 (3) 可以认为每名学生的成绩样本服从正态分布。 (4) 从样本中随机取出一个点（一次的成绩），大概率的情况是这个成绩不会偏离均值太远，那么我们认为这个成绩可以体现考生的学业水平，这样所有的人就能排名了，且单次的排名有效。

通过这个例子，可以看到单次的排名结果只是体现排名对象水平的一个样本点；此外，考试排名这种方式具有一些局限性，这是因为实验条件太过苛刻: 1. 所有人同时进行； 2.必须有精准的排名标准(分数)；3.所有人必须采用一份试卷，否则排名无效等。

对于某些无法应用这种排名方式的场景来说（体育比赛，游戏水平排名等），我们需要新的评价系统。基于上述排名有效性的假设, 经典的Elo评分系统通过多次的两两对抗的结果对所有的排名对象进行评价，而TrueSkill基于概率图模型对Elo评分系统进行了一般化和扩展。

2. Elo评价系统

Elo评价系统的原理：Player 1和Player 2的能力分别由正态分布 N(s_1,eta^2) 和 N(s_2,eta^2) 表示， r_1,r_2in {1,frac{1}{2},-1} 代表各自胜负的结果(1, 1/2, -1分别对应胜，平和负)。 Xsim N(s_1,eta^2)，Ysim N(s_2,eta^2)。

在已知了单次对战结果后，分别对 s_1,s_2 做如下调整。

s_1 leftarrow s_1+Delta_1 ， s_2 leftarrow s_2+Delta_2,

其中

Delta_1=Kigg(r_1-Phi ig(frac{s_1-s_2}{sqrt{2}eta}ig)igg), Delta_2=Kigg(r_2-Phi ig(frac{s_2-s_1}{sqrt{2}eta}ig)igg),

这里Phi(cdot)为标准正态分布的累积分布函数(cdf), K 被称作K-factor，用于控制参数更新的幅度。 Phi(cdot) 的出现是有原因的，注意player 1获胜的概率为

egin{align} Pr(r_1=1) &= Pr(X-Y>0) \ &= Pr igg( frac{X-Y-(s_1-s_2)}{sqrt{2}eta} > -frac{s_1-s_2}{sqrt{2}eta}igg) \ &=1-Phi(-frac{s_1-s_2}{sqrt{2}eta}) \ &=Phi(frac{s_1-s_2}{sqrt{2}eta}). end{align}

类似的，

egin{align} Pr(r_2=1) &= Pr(X-Y<0) \ &=Phi(frac{s_2-s_1}{sqrt{2}eta}). end{align}

我们可以看到，给定了比赛结果，根据双方的能力大小双方能力的重估会有所不同。具体来说，如果事先认为的很强的一方战胜很弱的另一方，那么事后对两方能力评估的调整应该非常微小，因为这个结果一点也不令人惊讶。相反，如果事先认为很弱的一方竟然取胜，那么双方的水平重估应变化较大。通过以上的更新式，可以看到这两种极端的情况在Elo评价系统中都有所体现。注意现在有些Elo评价系统使用逻辑分布（logistic distribution）代替了正态分布来描述评价对象的能力，但原理不变更新式也容易推导。

3. TrueSkill概率图模型

Elo评价系统计算简单易用，但主要用于1对1型的对抗结果。如果对战形式是多人多队，或者更复杂的对战形式，Elo评价系统就显得非常局限。另一方面，Elo评价系统涉及多个随机变数（个人能力由某个分布描述和随机对战结果），而随机变数见又存在著明显的依赖关系。显然，这非常适合以贝叶斯概率图模型的观点进行组织建模，在给定了对战结果后给出评价对象能力的后验推断，TrueSkill就提供这样一种解决方案。相较Elo评价系统，TrueSkill的优势在于：

(1) 适用于复杂的组队形式，更具一般性。

(2) 置于更完善的建模体系，容易扩展。(3) 继承了贝叶斯建模的好的特点，如模型选择等。

3.1 TrueSkill的1对1无向图模型表示

概率图模型使用有向图或无向图来表示系统中涉及的随机变数或参数之间的关系。可以被观察到的随机变数以实心节点，不可观察的以空心节点表示。有向图在表示随机变数间的条件依赖(conditional dependency)方面简单直接，而无向图在描述复杂模型和计算方面具有优势。为了更清晰的表达TrueSkill的建模过程，这里给出一个对应Elo评价系统的TrueSkill有向图表示（图1），这也是原始论文没有直接给出的。

图1. 对应Elo的1对1的TrueSkill有向图表示

图1是有向图，因为采用了有向边连接其中的节点。从A指向B的有向边代表B条件依赖于A，即B的值依赖于A的实现值。随机变数 s_1 和 s_2 对应一场比赛中双方的能力，而各自具体的能力发挥对应随机变数 p_1 和 p_2。随机变数 d=p_1-p_2 ，代表双方表现的差值，比赛结果根据 d 的值算出。因为比赛结果是给定的，因此 r 的随机变数是实心节点，而 s_1,s_2,p_1,p_2 是不可观察的是空心节点。这里要注意的是 s_1,s_2和在Elo中的不同：在Elo评价系统中 s_1 和 s_2 是作为参数被直接计算更新的，在TrueSkill中是一个随机变数具有一个先验分布，这样做我们才能在给定赛果后将水平进行后验推断。我们将这个图所表示的过程总结如下：

(1) s_1 sim N(mu_1,sigma_1^2), s_2 sim N(mu_2,sigma_2^2) (2) p_1sim N(s_1,eta^2), p_2sim N(s_2,eta^2) (3) d=p_1-p_2 (4) r=left{ egin{array} &1， & d > epsilon \ frac{1}{2}, &|d| in [-epsilon, epsilon]\ -1, & d <-epsilon end{array} ight.

这里(4)定义了 r 的计算方法（给定 d ），其中有一个容忍参数 epsilon ，表示当两方的表现相差多小时可视作为平局。也许有人会想 d=0 为平局才是自然的，但 d 是两个随机变数的差，严格意义上的 d=0的概率是0，因此需要设定一个很小的容忍的区间（就像C语言里判断两个浮点数相等）。

3.2 TrueSkill的两队多人的无向图模型表示

下面我们考虑一个稍微复杂的对战情况--两队多人。TrueSkill假设每队的发挥是每个成员发挥的总和，这样我们仍然可以用无相图表示。

图2. 两队多人的TrueSkill有向图表示

相较图1，图2增加了随机变数 t_1 和 t_2 , 表示两队的表现，这里 t_1=p_1 , t_2=p_2+p_3 。整个过程可以总结如下：

(1) s_1 sim N(mu_1,sigma_1^2), s_2 sim N(mu_2,sigma_2^2)， s_3 sim N(mu_3,sigma_3^2)

(2) p_1sim N(s_1,eta^2), p_2sim N(s_2,eta^2)， p_3 sim N(s_3,eta^2)

(3) t_1=p_1， t_2=p_2+p_3

(3) d=t_1-t_2,(4) r=left{ egin{array} &1， & d > epsilon \ frac{1}{2}, &|d| in [-epsilon, epsilon]\ -1, & d <-epsilon end{array} ight.

通过这个例子，我们可以看到TrueSkill在处理复杂对战结果的灵活性。类似的，我们可以根据需要扩展出不同的TrueSkill模型来描述实际的对战过程。

3.3 TrueSkill的无向图表示

上面给出了TrueSkill的有向图表示，可以看到有向图能很清楚的表达随机变数间的依赖关系。此外，我们还可以用无向图来表示。无向图对于计算而言具有有向图所没有的优势，这是因为我们可以应用Sum-Product演算法。相应的，无向图除了将有向图中的有向边变为无向边外，还增加了连接无向边的因子(Factor)。

Sum-product演算法的介绍超出了TrueSkill的范围（具体内容请参考教科书如[2]），但这里还是简单说明一下它的用途。Sum-product演算法主要用于计算在一个复杂图模型中某个随机变数的边缘分布（marginal distribution），即假定联合概率分布 p(mathbf{X})=p(X_1,cdots,X_n)，我们想计算 p(X_i)=sum_{mathbf{X}ackslash X_i}p(X_1,cdots,X_n) 。另一方面，p(X_i|mathbf{Y}) propto p(X_i,mathbf{Y})=sum_{mathbf{X}ackslash X_i,mathbf{Y} } p(mathbf{X},mathbf{Y})，如果我们可以准确计算出 p(X_i,mathbf{Y})，那么我们就可以找出后验分布 p(X_i|mathbf{Y}) ，因为它和 p(X_i,mathbf{Y})之间只相差一个正则化因子（normalization factor） sum_{X_i}p(X_i,mathbf{Y}) 。注意为方便表示我们这里假设随机变数是离散型的，对于连续型随机变数原理（求和换作积分）和结论相同。

下面我们给出1对1情况下的TrueSkill无向图模型表示（图3）。从图3可以看到，相比有向图无向图多了由实心方块表示的因子（factor）。每个因子表示了它所连结的随机变数间的计算关系式。所有因子的乘积就是所有随机变数的联合概率密度函数（pdf）。

图3. 1对1情况下的TrueSkill无向图模型表示

类似的，图4给出了一个更复杂的无向图表示。这里有三队，分别包括1，2，1名成员。

图4. 3队多人的TrueSkill无向图模型表示

4. TrueSkill中的后验推论

TrueSkill的后验推断是指给定了对战结果的条件下，对每个人的水平随机变数 s_i 的后验推断。这个结果将被视作以后做后验推论时 s_i 的先验信息。TrueSkill的后验推论不仅应用了Sum-product演算法，还涉及expectation propagation演算法。其中最关键一步是对节点 d 应用moment matching对截断正态分布(Truncated Gaussian)进行近似。

4.1 截断正态分布

具体的，对于随机变数 Xsim N(mu,sigma^2)，将X的取值进行截断后有如下结果[3]：

E(X|a<X<b)=mu+sigmafrac{phi(alpha)-phi(eta)}{Phi(eta)-Phi(alpha)} ,

V(X|a<X<b)=sigma^2igg[ 1+frac{alphaphi(alpha)-etaphi(eta)}{Phi(eta)-Phi(alpha)} -igg( frac{phi(alpha)-phi(eta)}{Phi(eta)-Phi(alpha)} igg)^2 igg],

其中，

alpha=frac{a-mu}{sigma}, eta=frac{b-mu}{sigma}。phi(cdot) 和 Phi(cdot) 分别代表标准正态分布的概率密度函数（pdf）和累计密度函数（cdf）。特别的，我们可以令 a=-infty 或 b=infty，得到单侧截断的结果

E(X|X>a)=mu+sigmafrac{phi(alpha)}{1-Phi(alpha)} ,

V(X|X>a)=sigma^2igg[ 1+frac{alphaphi(alpha)}{1-Phi(alpha)} -igg( frac{phi(alpha)}{1-Phi(alpha)} igg)^2 igg] ,

E(X|X<b)=mu-sigmafrac{phi(eta)}{Phi(eta)} ,

V(X|a<X<b)=sigma^2igg[ 1-frac{etaphi(eta)}{Phi(eta)} -igg( frac{phi(eta)}{Phi(eta)} igg)^2 igg] .

根据以上结果，我们可以使用具有相对应的均值和方差的另一个正态分布对一个具有截断正态分布的随机变数的分布进行近似。这个过程被应用在TrueSkill模型中对随机变数 d 的后验推论的近似。

4.2 高斯乘法公式（Gaussian multiplication formula）

TrueSkill中只涉及正态分布，而后验推论中涉及到的计算会频繁使用到如下的高斯乘法公式（Gaussian multiplication formula）。

N(x;mu_1,sigma_1^2)N(x;mu_2,sigma_2^2)=N(mu_1;m_2,sigma_1^2+sigma_2^2)N(x;u,v),

其中，

v=frac{1}{frac{1}{sigma_1^2}+frac{1}{sigma_2^2}}， u=vigg( frac{mu_1}{sigma_1^2}+frac{mu_2}{sigma_2^2} igg)。

类似的，

frac{N(x;mu_1,sigma_1^2)}{N(x;mu_2,sigma_2^2)}=frac{sigma_2^2N(x;u,v)}{(sigma_2^2-sigma_1^2)N(mu_1;mu_2,sigma_2^2-sigma_1^2)} ,

其中

v=frac{1}{frac{1}{sigma_2^2}-frac{1}{sigma_2^2}} ， u=vigg( frac{mu_1}{sigma_1^2}-frac{mu_2}{sigma_2^2} igg)。

4.2 1对1情况下的TrueSkill后验推论

原著文章[1]给出了针对具体一般性的TrueSkill的后验推论方法，这里我们只给出最简单的1对1的情况下作为示例（如图5所示）。

图5. 1对1情况下的TrueSkill后验推论流程示意图

针对图5的演算法流程是：

（1）从上到下传递消息后近似计算 p(d|r)

（2）从下至上传递消息更新计算 p(s_1|r) 和 p(s_2|r)

这里的消息是指sum-product演算法中的消息，分为两类：从因子到节点（如 m_{f_1 ightarrow s_1}）和从节点到因子（如 m_{p_1 ightarrow g_1}）的消息。因为TrueSkill中只涉及正态分布，这里的消息都可以使用正态分布来表示。为了简洁表示，对于正态分布 N(mu,sigma^2)，引入参数表示法 v=sigma^2， gamma=v^{-1}， lambda=gammamu。基于sum-product演算法，图5中涉及的消息传递过程如下：

针对更一般的多人多队的情况，消息传递的计算的原理和计算也是类似的，不同处在于多队的情况需要消息的多次迭代计算，具体可以参考原文[1]。

5. 模型选择

TrueSkill是概率图模型，因此相比Elo评价系统还具有模型选择上的优势。在经典TrueSkill中，参数 eta 是需要事先给定的。不同的 eta 对应的评估结果可能会不同，那么如何确定合适的eta值呢？基于TrueSkill，我们可以计算给定对战结果 mathbf{X} 的evidence, 即 p(mathbf{X|eta})。这是容易计算的，因为固定 eta 每次对战结果的evidence可以在后验推论中求得。适合的 eta 值应该对应最大的evidence。

6. 模拟实验

在Elo评价系统中，我们可以计算其中一方获胜的概率，基于TrueSkill概率模型这个计算也是可能的。

egin{align} Pr(p_1>p2) &=largeint mathbf{I}(p_1-p_2>0)p(s_1)p(p_1|s_1)p(s_2)p(p_2|s_2)dp_1dp_2ds_1ds_2 \ &=largeint mathbf{I}(p_1-p_2>0)N(s_1;mu_1,sigma_1^2)N(p_1;s_1,eta^2)N(s_2;mu_s,sigma_2^2)N(p_2;s_2,eta^2)dp_1dp_2ds_1ds_2 \ &=largeint mathbf{I}(p_1-p_2>0)N(p_1|mu_1,sigma_1^2+eta^2)N(p_2|mu_2,sigma_2^2+eta^2)dp_1dp_2\ &=Phiigg( frac{mu_1-mu_2}{sqrt{sigma_1^2+sigma_2^2+2eta^2}} igg) end{align}

下面我们就通过几组模拟实验来证实通过TrueSkill我们可以正确估计出各方的胜率。

6.1 实验1 -- 双人对战

首先，我们考虑最简单的情况，即两人对抗，其中player 1的胜率为0.7。我们随机生成服从Bernoulli(0.7)的200个对战结果。在每次对战结束后重新评估双方的能力（固定 eta=4 ），得到以下结果。

图6. 针对两人对抗的TrueSkil评估结果

图6中的第2张图展示了对player 1的胜率的评估，我们可以看到从大约40次对战后胜率的估计开始出现收敛至0.75的趋势，这符合我们实验的设置。

6.2 实验2 -- 多人对战

接下来我们来验证，TrueSkill可以从两两对战的结果中对所有人进行整体排名，并能准确估计两两对战的胜率。

假定4人的对战胜率如下表所示: 第(i, j)个元素表示P(playeri 胜 playerj),i≠j。

图7. 两两对战结果的胜率表

很明显，4人的水平排序应为：player 1 ? player 2 ? player 3 ? player 4。

以下是两张图是每次从四人中随机取出两人并根据上面的对战胜率表生成的比赛结果对这两人的能力进行评估后，对四人的能力进行排名与真实排名的差别和估计能力的评估所估计出的胜率表和真是胜率表之间的 l-2 距离。

图8. 每次对战后对四人的排名与真实排名的差别（上）和估计能力的评估所估计出的胜率表和真是胜率表之间的距离（下）

我们可以看到，当进行40场比赛，排名基本确定；而且当进行100场比赛，胜率表的估计就非常准确了。

6.3 实验3 -- 组队对战

下面我们考虑在组队对抗的情况下，TrueSkill能不能对每个人进行准确的能力评估。模拟数据的生成规则如下：

（1）6人随机组成2队，每队3人，分别表示为 (a_1,a_2,a_3)和 (b_1,b_2,b_3) 。

（2）两队对战，第一队胜率为 frac{1}{9}sum_{i=1}^3sum_{j=1}^3 p_{a_i,b_j}，其中 p_{x,y}代表player x对player y的胜率，具体数值服从下表。

类似实验2的评价方法，我们考虑当个人的能力只能通过团队的表现体现的情况下，TrueSkill能不能对所有人的能力进行正确的排序，和能否正确估计两人之间的相对胜率。

图9. 每次组队赛后参者的排名与真实排名的差别（上）和估计能力的评估所估计出的胜率表和真是胜率表之间的距离（下）

从图9展示的结果，我们可以看到即使是组队赛TrueSkill任然可以对个人进行正确的评估。具体的，70场比赛后，水平排名大致已确定。其中player 3，4，5间顺序的估计较难因此出现了小的波动；70场比赛之后，估计的胜率已很接近真实的胜率表。

6. 讨论

本文介绍了TrueSkill的演算法原理。TrueSkill作为经典演算法Elo的扩展贝叶斯概率图模型，可以更灵活准确的从玩家的对战结果中（组队或单人对抗都可）对玩家能力水平进行评估。由于TrueSkill可以事先计算玩家对战输赢的概率，对于在线游戏等的业务可以起到支持的作用。TrueSkill是基于贝叶斯的概率统计模型，因此容易扩展和改进，并具有模型选择等优势。

参考文献

[1] Herbrich, Ralf, Tom Minka, and Thore Graepel. "TrueSkill?: a Bayesian skill rating system." Advances in neural information processing systems. 2007.

[2] Christopher M. Bishop. Pattern recognition and machine learning, 5th Edition.Information science and statistics, Springer2007, ISBN 9780387310732

[3] https://en.wikipedia.org/wiki/Truncated_normal_distribution


推荐阅读：
相关文章