nips nips2009 nips2009-206 nips2009-206-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jonathan Huang, Carlos Guestrin
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, which encompasses 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. 1
[1] D. Bayer and P. Diaconis. Trailing the dovetail shuffle to its lair. The Annals of Probability, 1992.
[2] P. Diaconis. Group Representations in Probability and Statistics. IMS Lecture Notes, 1988.
[3] Persi Diaconis. A generalization of spectral analysis with application to ranked data. The Annals of Statistics, 17(3):949–979, 1989.
[4] J. Fulman. The combinatorics of biased riffle shuffles. Combinatorica, 18(2):173–184, 1998.
[5] D. P. Helmbold and M. K. Warmuth. Learning permutations with exponential weights. In COLT, 2007.
[6] J. Huang, C. Guestrin, and L. Guibas. Efficient inference for distributions on permutations. In NIPS, 2007.
[7] J. Huang, C. Guestrin, and L. Guibas. Fourier theoretic probabilistic inference over permutations. JMLR, 10, 2009.
[8] J. Huang, C. Guestrin, X. Jiang, and L. Guibas. Exploiting probabilistic independence for permutations. In AISTATS, 2009.
[9] S. Jagabathula and D. Shah. Inferring rankings under constrained sensing. In NIPS, 2008.
[10] Toshihiro Kamishima. Nantonac collaborative filtering: recommendation based on order responses. In KDD, pages 583–588, 2003.
[11] R. Kondor. Group Theoretical Methods in Machine Learning. PhD thesis, Columbia University, 2008.
[12] R. Kondor and K. M. Borgwardt. The skew spectrum of graphs. In ICML, pages 496–503, 2008.
[13] R. Kondor, A. Howard, and T. Jebara. Multi-object tracking with representations of the symmetric group. In AISTATS, 2007.
[14] G. Lebanon and Y. Mao. Non-parametric modeling of partially ranked data. In NIPS, 2008.
[15] M. Meila, K. Phadnis, A. Patterson, and J. Bilmes. Consensus ranking under the exponential model. Technical Report 515, University of Washington, Statistics Department, April 2007.
[16] J. Petterson, T. Caetano, J. McAuley, and J. Yu. Exponential family graph matching and ranking. CoRR, abs/0904.2623, 2009.
[17] D.B. Reid. An algorithm for tracking multiple targets. IEEE Trans. on Automatic Control, 6:843–854, 1979.
[18] J. Shin, N. Lee, S. Thrun, and L. Guibas. Lazy inference on object identities in wireless sensor networks. In IPSN, 2005. 9