基於成對比較和置信傳播的同儕互評系統

Abstract

在本篇論文中，探討使用成對比較（Pairwise Comparison）的同儕互評系統（Peer Evaluation System），並減少以Bradley-Terry模型 預測排名所需觀測的成對比較結果數，不同於固定或隨機取樣，我們提出了以最大權重匹配（Maximum weighted matching）實作瑞士制循環賽(Swiss-system tournament)的取樣策略，並實驗證明此方法能有效減少需觀測的資料量，且提升排名準確率。Bradley-Terry模型是一個用來預測成對比較結果的機率模型，也可以用來預測個體排名。我們也觀察到Bradley-Terry 模型，在有人誤評的情況下，會將錯誤的成對比較結果納入考量並迭代，進而推論出一個較不準確的預測排名。成對比較的結果暗示了彼此之間的優劣關係，除了新的配對取樣策略外，我們也提出一個全新的想法，將成對比較的輸贏結果轉換成0和1，承接低密度同位元檢查碼（Low-Density Parity-Check code；LDPC code）的解碼技巧，利用置信傳播（Belief Propagation）在二分圖（Bipartite Graph）上糾正可能的錯誤成對比較結果，進而使用Bradley-Terry 模型預測更好的排名結果。相較於舊有的演算法，本論文的提出方法有助於減輕每個人需負擔的評鑑數量，並能根據現有資料，動態產生未來排名。

This thesis is task-oriented for increasing the predicted ranking accuracy of pairwise comparison by Bradley-Terry model, a probability model can predict possible rankings and results of pairwise comparisons, on peer evaluation system. In order to reduce the required observations for Bradley-Terry model, we propose a Swiss-system pairing strategy based on maximum weighted matching algorithm which can effectively reduce the observations and predict a more accurate ranking. Moreover, inspired by Low-Density Parity-Check (LDPC) codes, we propose an error-correcting algorithm with belief propagation on bipartite graph, which is specifically tailored for pairwise comparison. We notice that when students do the incorrect evaluations, the Bradley-Terry model will consider the misjudgments thus predicting an inaccurate ranking. Since the results of pairwise comparisons imply the ordering between each individual, in addition to the Swiss system, we transform the observation of pairwise comparisons into binary received codes and perform the error-correcting algorithm. By using iterative belief propagation techniques on the bipartite graph, information of the observations is passed to the belonging check node which filters out all the inconsistent ordering states, finally recover the comparisons and obtain a better predicted ranking by Bradley-Terry model.