概要

經典的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


推薦閱讀：
相关文章