Belief propagation for permutations, rankings, and partial orders
This provides a method for ranking inference in domains like sports or recommendations, but it is incremental as it builds on existing probabilistic models and belief propagation techniques.
The paper tackles the problem of inferring rankings from partial pairwise comparisons, such as game outcomes or user preferences, by defining a continuous spin system whose Gibbs distribution represents the posterior over permutations. The result is a belief propagation algorithm that computes marginal position distributions and approximates the number of linear extensions, enabling model selection between probabilistic models like Bradley-Terry-Luce.
Many datasets give partial information about an ordering or ranking by indicating which team won a game, which item a user prefers, or who infected whom. We define a continuous spin system whose Gibbs distribution is the posterior distribution on permutations, given a probabilistic model of these interactions. Using the cavity method we derive a belief propagation algorithm that computes the marginal distribution of each node's position. In addition, the Bethe free energy lets us approximate the number of linear extensions of a partial order and perform model selection between competing probabilistic models, such as the Bradley-Terry-Luce model of noisy comparisons and its cousins.