Efficient Probabilistic Inference with Partial Ranking Queries

Jonathan Huang, Ashish Kapoor, Carlos E. Guestrin
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:403-410, 2011.

Abstract

Distributions over rankings are used to model data in various settings such as preference analysis and political elections. 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 efficient 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 favorite movies, what are his preferences over remaining movies?). In this paper, we argue that riffled independence factorizations proposed in recent literature [7, 8] are a natural structural assumption for ranking distributions, allowing for particularly efficient processing of partial ranking queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-huang11a, title = {Efficient Probabilistic Inference with Partial Ranking Queries}, author = {Huang, Jonathan and Kapoor, Ashish and Guestrin, Carlos E.}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {403--410}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/huang11a/huang11a.pdf}, url = {https://proceedings.mlr.press/r9/huang11a.html}, abstract = {Distributions over rankings are used to model data in various settings such as preference analysis and political elections. 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 efficient 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 favorite movies, what are his preferences over remaining movies?). In this paper, we argue that riffled independence factorizations proposed in recent literature [7, 8] are a natural structural assumption for ranking distributions, allowing for particularly efficient processing of partial ranking queries.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficient Probabilistic Inference with Partial Ranking Queries %A Jonathan Huang %A Ashish Kapoor %A Carlos E. Guestrin %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-huang11a %I PMLR %P 403--410 %U https://proceedings.mlr.press/r9/huang11a.html %V R9 %X Distributions over rankings are used to model data in various settings such as preference analysis and political elections. 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 efficient 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 favorite movies, what are his preferences over remaining movies?). In this paper, we argue that riffled independence factorizations proposed in recent literature [7, 8] are a natural structural assumption for ranking distributions, allowing for particularly efficient processing of partial ranking queries. %Z Reissued by PMLR on 04 October 2026.
APA
Huang, J., Kapoor, A. & Guestrin, C.E.. (2011). Efficient Probabilistic Inference with Partial Ranking Queries. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:403-410 Available from https://proceedings.mlr.press/r9/huang11a.html. Reissued by PMLR on 04 October 2026.

Related Material