Bayesian Ranking using Factor Graphs and Expectation Propagation

par/by Dumitru Erhan
Département d'Informatique et de Recherche Opérationnelle
Université de Montréal

We investigate the problem of ranking a set of objects and its solution of tracking belief distributions over the value of the ranks. We present a general framework for constructing and visualizing dependencies between variables and data and between variables themselves. Inference in these so-called Factor Graphs can be done efficiently, even when the one needs to resort to approximations. In the latter case, we apply the well-known Expectation Propagation algorithm. Several case studies are presented: one is that of TrueSkill, a system for ranking players in the context of the Xbox online gaming service. The other is named tentatively TrueChess and is a generalization of the ELO system that compares more accurately and in a fairer manner chess players from the past 100 years.

Notes:

(1) This bas been done at Microsoft Research in Cambridge (UK) by Ralf Hebrich and Thore Graepel.

(2) http://research.microsoft.com/%7Ecmbishop/PRML/Bishop-PRML-sample.pdf contains a good and very readable introduction to Factor Graphs and the sum-product algorithm (pages 400 and onwards). I recommend skimming through it before the talk.