nips nips2008 nips2008-106 nips2008-106-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Srikanth Jagabathula, Devavrat Shah
Abstract: Motivated by applications like elections, web-page ranking, revenue maximization etc., we consider the question of inferring popular rankings using constrained data. More specifically, we consider the problem of inferring a probability distribution over the group of permutations using its first order marginals. We first prove that it is not possible to recover more than O(n) permutations over n elements with the given information. We then provide a simple and novel algorithm that can recover up to O(n) permutations under a natural stochastic model; in this sense, the algorithm is optimal. In certain applications, the interest is in recovering only the most popular (or mode) ranking. As a second result, we provide an algorithm based on the Fourier Transform over the symmetric group to recover the mode under a natural majority condition; the algorithm turns out to be a maximum weight matching on an appropriately defined weighted bipartite graph. The questions considered are also thematically related to Fourier Transforms over the symmetric group and the currently popular topic of compressed sensing. 1
[1] C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation revisited. In Proceedings of WWW10, 2001.
[2] Yiling Chen, Lance Fortnow, Evdokia Nikolova, and David M. Pennock. Betting on permutations. In EC ’07: Proceedings of the 8th ACM conference on Electronic commerce, pages 326–335, New York, NY, USA, 2007. ACM.
[3] J. Huang, C. Guestrin, and L. Guibas. Efficient Inference for Distributions on Permutations. In Advances in Neural Information Processing Systems (NIPS), 2007.
[4] R. Kondor, A. Howard, and T. Jebara. Multi-object tracking with representations of the symmetric group. In Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, 2007.
[5] P. Diaconis. Group Representations in Probability and Statistics. IMS Lecture Notes-Monograph Series, 11, 1988.
[6] E.J. Candes and T. Tao. Decoding by linear programming. Information Theory, IEEE Transactions on, 51(12):4203–4215, Dec. 2005.
[7] G. Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman Rev. Ser. A, 5:147– 151, 1946.
[8] J. Edmonds and R. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Jour. of the ACM, 19:248–264, 1972.
[9] M. Bayati, D. Shah, and M. Sharma. Max-product for maximum weight matching: convergence, correctness and lp duality. IEEE Transactions on Information Theory, March 2008. 8