Document Open Access Logo

On Reconstructing a Hidden Permutation

Authors Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.604.pdf
  • Filesize: 429 kB
  • 14 pages

Document Identifiers

Author Details

Flavio Chierichetti
Anirban Dasgupta
Ravi Kumar
Silvio Lattanzi

Cite AsGet BibTex

Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, and Silvio Lattanzi. On Reconstructing a Hidden Permutation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 604-617, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.604

Abstract

The Mallows model is a classical model for generating noisy perturbations of a hidden permutation, where the magnitude of the perturbations is determined by a single parameter. In this work we consider the following reconstruction problem: given several perturbations of a hidden permutation that are generated according to the Mallows model, each with its own parameter, how to recover the hidden permutation? When the parameters are approximately known and satisfy certain conditions, we obtain a simple algorithm for reconstructing the hidden permutation; we also show that these conditions are nearly inevitable for reconstruction. We then provide an algorithm to estimate the parameters themselves. En route we obtain a precise characterization of the swapping probability in the Mallows model.
Keywords
  • Mallows model; Rank aggregation; Reconstruction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Bartholdi, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(2):157-165, 1989. Google Scholar
  2. N. Bhatnagar and R. Peled. Lengths of monotone subsequences in a Mallows permutation. Probability Theory and Related Fields, To appear. Google Scholar
  3. M. Braverman and E. Mossel. Sorting from noisy information. CoRR, abs/0910.1191, 2009. Google Scholar
  4. W. Cheng and E. Hüllermeier. Instance-based label ranking using the Mallows model. In ECCBR Workshops, pages 143-157, 2008. Google Scholar
  5. P. Diaconis and A. Ram. Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques. The Michigan Mathematical Journal, 48(1):157-190, 2000. Google Scholar
  6. D. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomised Algorithms. Cambridge University Press, 2009. Google Scholar
  7. C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation methods for the web. In WWW, pages 613-622, 2001. Google Scholar
  8. M. A. Fligner and J. S. Verducci. Distance based ranking models. Journal of the Royal Statistical Society B, 48:359-369, 1986. Google Scholar
  9. M. A. Fligner and J. S. Verducci. Multistage ranking models. Journal of the American Statistical Association, 43(403):892-901, 1988. Google Scholar
  10. M. A. Fligner and J. S. Verducci. Posterior probability for a consensus ordering. Psychometrika, 55:53-63, 1990. Google Scholar
  11. A. Gnedin and G. Olshanski. The two-sided infinite extension of the Mallows model for random permutations. Advances in Applied Mathematics, 48(5):615-639, 2012. Google Scholar
  12. W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. Google Scholar
  13. C. Kenyon-Mathieu and W. Schudy. How to rank with few errors. In STOC, pages 95-103, 2007. Google Scholar
  14. A. Klementiev, D. Roth, and K. Small. Unsupervised rank aggregation with distance-based models. In ICML, pages 472-479, 2008. Google Scholar
  15. G. Lebanon and J. Lafferty. Cranking: Combining rankings using conditional probability models on permutations. In ICML, pages 363-370, 2002. Google Scholar
  16. C. L. Mallows. Non-null ranking models I. Biometrika, 44(1-2):114-130, 1957. Google Scholar
  17. Colin McDiarmid. Concentration. In M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics. Springer, 1998. Google Scholar
  18. M. Meila, K. Phadnis, A. Patterson, and J. A. Bilmes. Consensus ranking under the exponential model. In UAI, pages 285-294, 2007. Google Scholar
  19. C. Mueller and S. Starr. The length of the longest increasing subsequence of a random Mallows permutation. Journal of Theoretical Probability, pages 1-27, 2011. Google Scholar
  20. S. Mukherjee. Estimation of parameters in non uniform models on permutations. Technical Report 1307.0978, arXiv, 2013. Google Scholar
  21. T. Qin, X. Geng, and T-Y. Liu. A new probabilistic model for rank aggregation. In NIPS, pages 1948-1956, 2010. Google Scholar
  22. S. Starr. Thermodynamic limit for the Mallows model on S_n. Technical Report 0904.0696, arXiv, 2009. Google Scholar
  23. G. S. Watson. Serial correlation in regression analysis. I. Biometrika, 42(3/4):327-341, 1955. Google Scholar
  24. P. Yin, P. Luo, M. Wang, and W-C. Lee. A straw shows which way the wind blows: Ranking potentially popular items from early votes. In WSDM, pages 623-632, 2012. Google Scholar
  25. H. P. Young. Optimal voting rules. The Journal of Economic Perspectives, 9(1):51-64, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact