Tractable Search for Learning Exponential Models of Rankings

This work introduces the first nontrivial heuristic function for the Generalized Mallows model, which represents a probability distribution over all possible permutations of a given set of objects, and demonstrates its effectiveness and shows that it is superior to existing techniques for learning the GM model.

Abstract

We consider the problem of learning the Generalized Mallows (GM) model of [Fligner and Verducci, 1986], which represents a probability distribution over all possible permutations (or rankings) of a given set of objects. The training data consists of a set of permutations. This problem generalizes the well known rank aggregation problem. Maximum Likelihood estimation of the GM model is NP-hard. An exact but inefficient searchbased method was recently proposed for this problem. Here we introduce the first nontrivial heuristic function for this search. We justify it theoretically, and show why it is admissible in practice. We experimentally demonstrate its effectiveness, and show that it is superior to existing techniques for learning the GM model. We also show good performance of a family of faster approximate methods of search. 1