一掩蛤、前言

現(xiàn)實生活中個體間的差異與優(yōu)劣往往是以兩兩比對的形式進行鸵熟，但是兩個個體間的比對有時候會出現(xiàn)如下的困境：設(shè)想有下面這一種循環(huán)的情況摘投， a 個體戰(zhàn)勝了 b 個體献幔，而 b 個體又戰(zhàn)勝了 c 個體懂傀，且 c 個體戰(zhàn)勝了 a 個體，它們的實力應(yīng)該如何評估呢蜡感？又設(shè)想一下我們的跆拳道比賽蹬蚁，足球比賽，勝負輸贏情況繁復(fù)郑兴，我們又以怎樣的標準來評估各個體的實力值呢犀斋？

簡單來說，我們完成的是一個基于 Mongo DB 和 Node.js 的后端框架情连，提供 API 用于實現(xiàn)這種兩兩比對之后的實力值評估叽粹。

二、問題定義

1却舀、輸入

我們程序的輸入包含每場比賽的輸贏情況：比如記錄了三場賽事虫几， a 戰(zhàn)勝了 b ， a 戰(zhàn)勝了 c 挽拔， b 戰(zhàn)勝了 c 持钉，那么我們只需要提供一串包含這些比賽信息的字符串“0 a b|1 a c|2 b c”作為輸入即可，數(shù)字表示比賽的 ID 號篱昔，重復(fù)提交相同 ID 的比賽每强，后一個數(shù)據(jù)項會覆蓋前一個數(shù)據(jù)項。當然州刽，我們也提供刪除比賽的 API 空执，如果想刪除比賽 0 ， 1 和 4 穗椅，那么我們只需要提供字符串“0|1|4”即可辨绊。輸入方式為將上述指定的字符串通過 POST 的方式發(fā)送到服務(wù)器對于 URL 即可。

具體來說匹表，想要添加比賽的輸贏情況门坷， POST 上述規(guī)定的字符串到“/add”；想要刪除比賽的輸贏情況袍镀， POST 上述規(guī)定的字符串到“/delete”默蚌。

2、輸出

我們程序的輸出包含了各個個體的實力值苇羡，格式為 JSON 绸吸。

也許這么解釋會過于的抽象，更多的信息請參考我們已經(jīng)完成的一個前端的 Demo 源碼，里面使用了每一條 API 指令锦茁，并有詳細的注釋攘轩。

三、算法描述

我們設(shè)計的思想來自于圍棋 AI 的選子算法码俩，所參考的論文是《Factorization Ranking Model for Move Prediction in the Game of Go》度帮。在論文中，作者利用 MM 算法構(gòu)建了一個排序算法來對復(fù)雜化的 BT 模型（也就是論文中的 FBT 模型）進行排序稿存。

1笨篷、知識鋪墊

1.1 BT 模型

BT 模型是一種用來預(yù)測比較結(jié)果的概率模型，全稱是 Bradley-Terry 模型挠铲。下面我將舉出一個形象化的例子冕屯，假設(shè)有兩個個體 i 和 j 寂诱， Pi 和 Pj 分別表示這兩個個體的實力值拂苹，那么在一次比賽中， i 戰(zhàn)勝 j 的概率就可以用下面這個式子來表示：

事實上痰洒， BT 模型可以有很多參數(shù)化的表示瓢棒，比如我們可以用 e 的 n 次冪的形式來替代簡單的線性形式：

BT 模型之所以那么構(gòu)建，有著嚴謹?shù)臄?shù)據(jù)論證[1]丘喻，這里不再贅述脯宿。

1.2 MM 算法

MM 算法準確來說不是一種算法，它其實是對如何得出優(yōu)秀算法的一種描述泉粉。 MM 是 majorize/minimize 或者 minorize/maximize 的縮寫连霉，兩者的區(qū)別僅在于一個試圖求出最大值，一個試圖求出最小值嗡靡，兩者所用到的方法是完全相同的跺撼，下面我將以 minorize/maximize 為例，簡單地介紹一下 MM 算法：

如果存在一個函數(shù) M(θ|θ_m) 滿足：

對于所有的 θ 讨彼，有 M(θ│θ_m) ≤ f(θ)

且 M(θ_m│θ_m) = f(θ_m)

那么我們就稱它 minorize 了函數(shù) 歉井。

此時，我們?nèi)〕龊瘮?shù) M(θ|θm) 的最大值 θ(m+1) 哈误，并在該點構(gòu)建新的函數(shù) M(θ|θ_(m+1)) 以此不斷地迭代哩至， θ_m 將會趨于函數(shù) f(θ) 的最大值，我們的目的也便達成蜜自。我們再來用一張圖來表示這個具體的過程：

[圖1 MM 算法的迭代]

但是讀者可能會問了菩貌，求函數(shù)的最值何必那么復(fù)雜呢，求出函數(shù)的導(dǎo)數(shù)畫出函數(shù)的圖像不就可以十分精確地求出極大值了么重荠？誠然菜谣，對于一些簡單的函數(shù)比如初等函數(shù)或是初等函數(shù)的復(fù)函數(shù)我們確實可以通過求導(dǎo)的方式輕松地解決最值問題，但是如果一個函數(shù)是離散的，甚至說一個函數(shù)的自變量根本不是一個數(shù)尾膊，那么它的導(dǎo)數(shù)也便無從定義了媳危。在我們的算法中， θ 便不是一個數(shù)字冈敛，你可以將其看做是一個高維的向量待笑，或者是數(shù)的集合，這個時候我們需要用 MM 算法不斷迭代抓谴，以求出近似的最值暮蹂。

1.3 超平面上的凸函數(shù)

超平面是 n 維歐氏空間中余維度等于一的線性子空間。這是平面中的直線癌压、空間中的平面之推廣仰泻。

它有如下性質(zhì)，如果 h(x) 是一個凸函數(shù)滩届，那么有：

這里涉及到的是純數(shù)學集侯，其論證仍不在這里贅述[2]。

2帜消、對自己算法的描述

有了上面的鋪墊棠枉，我們就可以理解 MM 算法是如何對 BT 模型進行排序的了。我們假設(shè)有很多支足球隊泡挺，其中有兩支球隊被標記為 i 和 j 辈讶，我們先假定它們的實力值為 Pi 和 Pj （在程序之初所有隊伍的實力值被初始化為一個常數(shù)，經(jīng)過我們的多次嘗試娄猫，為了達到一個最令人舒適的結(jié)果贱除，我們將其初始化為 100 ），那么根據(jù)我們前面提到的對 BT 模型的線性定義媳溺， i 球隊戰(zhàn)勝 j 球隊的概率就可以被表示為：

現(xiàn)在我們將這個思路拓展到任意兩支球隊月幌，設(shè)置計數(shù)器 bij 為 i 戰(zhàn)勝 j 的次數(shù)，那么一張任意的輸贏表（一個歷史戰(zhàn)局褂删，比如一場世界杯結(jié)束后所有的輸贏情況飞醉，這里可能會比較難理解）就可以被表示為：

眾所周知，計算機的計算精度極其有限的屯阀，如果比賽場次眾多缅帘，假如有100場比賽，其中每支隊伍的實力值均相等难衰，那么這個概率 L(θ) 就等于 0.5^100 钦无，這個數(shù)字普通的 PC 不通過特殊的算法已經(jīng)很難表示，因此我們對這個概率值取對數(shù)盖袭。依賴于對數(shù)函數(shù)良好的單調(diào)性失暂，我們只需要求出對數(shù)函數(shù)最值時的自變量即是使概率最大化的自變量彼宠。

讀者可能又會問了，這樣對 L(θ) 的表示不把一支球隊自己踢自己的情況計算進去了弟塞？的確如此凭峡，所以我們需要使用算法者格外小心地維護自己的數(shù)據(jù)：一個合法的數(shù)據(jù)是不存在自己戰(zhàn)勝自己的情況的，即 bij 為 0 决记，任何數(shù)的 0 次冪均為 1 摧冀，它并不影響求積結(jié)果。

正如上面所述系宫，我們對 L(θ) 取對數(shù)索昂，并定義為 f(θ) ，則：

根據(jù)前面對 MM 算法的描述扩借，我們需要找到一個函數(shù) M(θ|θ_m) 讓其和 f(θ) 滿足對 MM 算法的定義椒惨。我們考慮“放縮” -ln?(θ_i+ θ_j) ，不妨設(shè)為 h(x) = -ln?x 潮罪。那么根據(jù)超平面上凸函數(shù)的性質(zhì)康谆，有下面這個不等式成立：

令 y= θ_i^n +θ_j^n ， x 仍滿足我們之前的定義 x= θ_i +θ_j 错洁，帶入上面 f(θ) 的表達式秉宿，則有：

這里 n 表示第 n 次迭代戒突，并不是指 n 次冪屯碴； θ_i^n 和 θ_j^n 是上一次的計算結(jié)果，在我們的程序中被初始化為了 100 膊存； θ 可以被看做是一個高維的向量导而，或者是數(shù)的集合，而等式右側(cè)的 θ_i 和 θ_j 為其中的一項隔崎。

我們對上面得到的這個 M(θ│θ_n ) 稍作檢查今艺，便可以發(fā)現(xiàn)它滿足 MM 算法的要求，也就是說它 minorize 了函數(shù) f(θ) 爵卒。根據(jù)一些巧妙的運算虚缎，我們就可以得到：

具體的計算過程仍為數(shù)學過程，這里也不多贅述钓株。

照此不斷迭代实牡，我們便可以得到“可能性”的最大值，這意味著什么呢轴合？讓我們再次來梳理一下邏輯：我們首先假定每支球隊的實力均為 100 创坞，依此計算出了發(fā)生輸入的這張輸贏表發(fā)生的概率，然后我們通過 MM 算法不斷地迭代受葛，修改每支球隊的實力值以使這張輸贏表發(fā)生的概率增大题涨，可能性越大偎谁，便可說明我們對每支隊伍的實力評估越接近現(xiàn)實，當達到一定精度的時候纲堵，我們便可以根據(jù)實力值巡雨，得出排名。這就是利用 MM 算法對 BT 模型的排序席函。

四鸯隅、實驗結(jié)果

1、用 C / C++ 完成的簡單測試

為了確保算法的有效性向挖，我們沒有十分魯莽地直接用它來搭建服務(wù)器蝌以，而是先寫了一個 C / C++ 的小程序來進行測試。我們測試的思路是這樣的：

我們先用隨機數(shù)產(chǎn)生了 100 個個體何之，每個個體有 0 到 99 之間整數(shù)的實力值跟畅。我們根據(jù)這個實力值利用 BT 模型來模擬比賽，比賽的輸贏概率遵從 BT 模型線性形式的定義溶推，兩兩個體之間比賽 100 場徊件。

上述過程是我們程序的預(yù)處理階段，接下來我們便用這 100 場比賽的輸贏情況來評估每個個體的實力蒜危，如果我們評估出的實力與我們設(shè)定的相似虱痕，則說明我們算法是有效的。輸出結(jié)果如下：

[圖2 MM 算法對 BT 模型排序 C / C++ 實驗]

輸出分為四列辐赞，第一列為個體的序號部翘，第二列為我們給它設(shè)定的實力值，第三列為我們給它的評分响委，第四列為個體被設(shè)定的實力值與我們給它評定的實力值的比值新思。我們可以看到，第四列的值穩(wěn)定在 0.4 左右赘风，說明我們對各個體實力評估是相當準確的夹囚。這里沒必要展示所有的 100 項結(jié)果，所以上圖僅展示其中的前 20 項邀窃。

2荸哟、后端框架

我們收集了最近 3 屆世界杯（不含預(yù)選賽）的所有比賽數(shù)據(jù)，依次為據(jù)給每支球隊打分并排序瞬捕，數(shù)據(jù)總結(jié)如下：

[圖3 世界杯數(shù)據(jù)文件]

讀者可能會發(fā)現(xiàn)這個文件的格式并不符合論文第二部分里的定義鞍历，我們寫了一個簡單的程序來轉(zhuǎn)換格式，由于程序十分簡單山析，這里也不多說堰燎。

程序的具體啟動方法將在附錄中進行詳細的說明，這里只做展示笋轨。

[圖4 啟動數(shù)據(jù)庫 Mongo DB ]

[圖5 啟動服務(wù)器]

[圖6 進入“demo/”文件夾]

演示的樣例在項目的“demo/”文件夾中秆剪，確保服務(wù)器正確運行之后赊淑，雙擊其中的“index.html”文件即可運行網(wǎng)站，網(wǎng)站上則會顯示世界杯前 10 名的排名：

[圖7 世界杯前 10 及其實力值]

在這里只顯示了前 10 名仅讽，如果你想知道其他球隊的排名陶缺，在右上角的搜索框中搜索即可：

[圖8 搜索未參與近年世界杯的球隊]

[圖9 搜索參與過近年世界杯的球隊]

我們對比了世界足聯(lián)給出的官方數(shù)據(jù)，發(fā)現(xiàn)我們的評分是可靠的洁灵。

最后饱岸，我們再簡單的介紹一下源碼[3]，以分析其實如何工作的徽千。后端框架的代碼比較復(fù)雜苫费，也是我們程序的核心，但是它不是展示的內(nèi)容双抽，有興趣的讀者可以下載之后自行研究百框，我們這里只講講前端代碼是如何工作的。

打開“demo/js/footballRank.js”牍汹，代碼如下：

[圖10 Demo 的 js 文件]

第 5 行我們將最近三屆所有世界杯輸贏信息 POST 到了服務(wù)器铐维，第 8 行我們通過 GET 方法從服務(wù)器獲取每支隊伍的實力值，第 27 行開始為我們事先搜索框邏輯部分的代碼慎菲。

五嫁蛇、總結(jié)

在我們?nèi)粘Ｉ钪校芏啾容^都是兩兩個體之間進行的：

<img src='http://upload-images.jianshu.io/upload_images/3433108-68afd58aaf25aa6a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240' width='24%'/>
<img src='http://upload-images.jianshu.io/upload_images/3433108-d0df0f4253b844a1.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240' width='24%'/>
<img src='http://upload-images.jianshu.io/upload_images/3433108-c6df6006fc1ae3ed.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240' width='24%'/>
<img src='http://upload-images.jianshu.io/upload_images/3433108-1776c095d3c87de3.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240' width='24%'/>

[圖11 日常生活中兩兩比較的競爭]

比如游戲中的圍棋露该、爐石傳說睬棚，體育中的足球、跆拳道等有决，我們應(yīng)該如何對玩家或選手進行排位闸拿？如何去評估他們的實力呢空盼？比較簡單的方法有以下幾個书幕，我將一一的指出它們的缺點，并闡述為什么說我們提供的算法是可靠的揽趾。

按照個體的勝率台汇？ 假設(shè)有這樣一種情況，一個個體僅參加過幾次比賽篱瞎，而他恰巧遇到的對手都是實力很弱的苟呐，假設(shè)這個個體贏得了比賽，那么他的勝率會是100%俐筋，但事實上他的實力并不一定強牵素。

按照個體獲勝的場數(shù)？ 假設(shè)有這樣一種情況澄者，圍棋高手李世石和 Alpha Go 過招笆呆， Alpha Go 屢次戰(zhàn)勝李世石请琳，顯然它的實力高過李世石，但是如果以獲勝場數(shù)來評估赠幕，李世石會被錯誤地評估為比 Alpha Go 更強俄精。

按照獲勝加分？輸場扣分榕堰？ 上面李世石和 Alpha Go 的例子仍能駁倒這種評分方法竖慧。

那么我們憑什么說用 MM 算法對 BT 模型排序就是極優(yōu)的呢？我們還是舉出一個例子來證明逆屡， Alpha Go 屢次戰(zhàn)勝李世石說明其水平更高圾旨，盡管其參加的比賽場次數(shù)很少，在我們的算法中魏蔗， Alpha Go 初始實力為 100 碳胳，假設(shè)李世石實力已有 500， 那么 Alpha Go 戰(zhàn)勝李世石的概率僅有 沫勿，這并不能讓概率達到較大的值挨约，所以在迭代時為了使 BT 模型概率最大化， MM 算法會不斷調(diào)高 Alpha Go 實力值以達到最優(yōu)产雹，我們的算法僅需2诫惭、3次就可以讓 Alpha Go 實力值超越李世石，這與事實的客觀實力估計是十分契合的蔓挖。

六夕土、附錄

1、實驗環(huán)境

我們沒有進行性能方面的比較瘟判，因此我們也不詳細說明電腦的配置了怨绣。我們的程序運行在一臺 Macbook Pro 以及一臺 Macbook Air 上，操作系統(tǒng)均為 OS X El Capitan 版本 10.11.5 拷获，使用的編輯器為 Sublime Text 3篮撑，瀏覽器為 Chrome。

2匆瓜、如何運行程序

正如在第四部分中所講的那樣赢笨，我們的代碼分為兩個部分： C++ 的簡單測試程序以及我們的后端服務(wù)器框架。

對于前者驮吱，只需要簡單的編譯運行即可茧妒；對于后者，想要運行起來會比較困難左冬，但是如果電腦上已經(jīng)安裝過 Mongo DB 和 Node.js 桐筏，那么運行也就很簡單了。 Mongo DB 和 Node.js 是目前Web很通用的兩款工具拇砰，具體的安裝過程網(wǎng)上提供了很多的教程梅忌，在這里也不再贅述绊袋。

安裝好這兩款工具后，在命令行中打開工程目錄铸鹰，運行“mongod -dbpath data/”癌别，確保數(shù)據(jù)庫正常運行起來之后，新建命令行窗口蹋笼，運行“node index.js”即可啟動服務(wù)器展姐。

我們提供了一個 Demo 網(wǎng)站，在完成服務(wù)器的啟動之后直接運行 Demo 的 HTML 頁面即可剖毯，你可以通過瀏覽器的 Network 監(jiān)視來進一步地了解這個網(wǎng)站工作的原理圾笨。

3、參考

1. 對于 BT 模型的更多信息可以參考它的維基百科：https://en.wikipedia.org/wiki/Bradley%E2%80%93Terry_model
2. 對于超平面的更多信息可以參考它的危機百科：https://en.wikipedia.org/wiki/Hyperplane
3. 我們的項目代碼請從 Github 上下載逊谋，如果覺得有意思的話歡迎點贊：https://github.com/An0nym6/Bradley-TerryRankingTemplate

在我博客上面的鏈接：傳送門