The Robotics Institute

Carnegie Mellon Robotics Institute

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

Representing distributions over permutations can be a daunting task due to the fact that the number of permutations of n objects scales factorially in n. One recent way that has been used to reduce storage complexity has been to exploit probabilistic independence, but as we argue, full independence assumptions impose strong sparsity constraints on distributions and are unsuitable for modeling rankings. We identify a novel class of independence structures, called riffled independence, encompassing a more expressive family of distributions while retaining many of the properties necessary for performing efficient inference and reducing sample complexity. In riffled independence, one draws two permutations independently, then performs the riffle shuffle, common in card games, to combine the two permutations to form a single permutation. In ranking, riffled independence corresponds to ranking disjoint sets of objects independently, then interleaving those rankings. We provide a formal introduction and present algorithms for using riffled independence within Fourier-theoretic frameworks which have been explored by a number of recent papers.

Notes

Text Reference

Jonathan Huang and Carlos Ernesto Guestrin, "Riffled Independence for Ranked Data," Advances in Neural Information Processing Systems (NIPS 2009) , December, 2009.

BibTeX Reference

@inproceedings{Huang_2009_6473,
   author = "Jonathan Huang and Carlos Ernesto Guestrin",
   title = "Riffled Independence for Ranked Data",
   booktitle = " Advances in Neural Information Processing Systems (NIPS 2009) ",
   month = "December",
   year = "2009",
}

The Robotics Institute

Menu