Tractable Search for Learning Exponential Models of Rankings
; Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:392-399, 2009.
We consider the problem of learning the Generalized Mallows (GM) model of \citefv86, which represents a probability distribution over all possible permutations (aka 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 search-based method was recently proposed for this problem. Here we introduce the first non-trivial 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.