Efficient Probabilistic Inference with Partial Ranking Queries

Jonathan Huang, Ashish Kapoor, and Carlos Ernesto Guestrin
The 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011), July, 2011.


Download
  • Adobe portable document format (pdf) (1MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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 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 favorite movies, what are his preferences over remaining movies?). 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 efficient processing of partial ranking queries.

Notes
Number of pages: 8

Text Reference
Jonathan Huang, Ashish Kapoor, and Carlos Ernesto Guestrin, "Efficient Probabilistic Inference with Partial Ranking Queries," The 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011), July, 2011.

BibTeX Reference
@inproceedings{Huang_2011_6868,
   author = "Jonathan Huang and Ashish Kapoor and Carlos Ernesto Guestrin",
   title = "Efficient Probabilistic Inference with Partial Ranking Queries",
   booktitle = "The 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011)",
   month = "July",
   year = "2011",
}