Efficient Probabilistic Inference with Partial Ranking Queries

The factorial size of the space of rankings, however, typically forces one to make structural assumptions, such as smoothness, sparsity, or probabilistic independence about these underlying distributions. We approach the modeling problem from the computational principle that one should make structural assumptions which allow for ecient calculation of typical probabilistic queries. For ranking models, typical queries predominantly take the form of partial ranking queries (e.g., given a user's top-k fa In this paper, we argue that ried independence factorizations proposed in recent literature [7, 8] are a natural structural assumption for ranking distributions, allowing for particularly ef-cient processing of partial ranking queries. 1 Intr Both problems are challenging because of the fact that, as the number of items being ranked increases, the number of possible rankings increases factorially. The key to ecient representations and reasoning is to identify exploitable problem structure, and to this end, there have been a number of smart structural assumptions proposed by the scientic community. These assumptions have typically been designed to reduce the number of necessary parameters of a model and have ranged from smoothness [10], to sparsity [11], to exponential family parameterizations [14].