×

Probabilistic preference learning with the Mallows rank model. (English) Zbl 1471.62268

Summary: Ranking and comparing items is crucial for collecting information about preferences in many areas, from marketing to politics. The Mallows rank model is among the most successful approaches to analyse rank data, but its computational complexity has limited its use to a particular form based on Kendall distance. We develop new computationally tractable methods for Bayesian inference in Mallows models that work with any right-invariant distance. Our method performs inference on the consensus ranking of the items, also when based on partial rankings, such as top-\(k\) items or pairwise comparisons. We prove that items that none of the assessors has ranked do not influence the maximum a posteriori consensus ranking, and can therefore be ignored. When assessors are many or heterogeneous, we propose a mixture model for clustering them in homogeneous subgroups, with cluster-specific consensus rankings. We develop approximate stochastic algorithms that allow a fully probabilistic analysis, leading to coherent quantifications of uncertainties. We make probabilistic predictions on the class membership of assessors based on their ranking of just some items, and predict missing individual preferences, as needed in recommendation systems. We test our approach using several experimental and benchmark datasets.

MSC:

62F07 Statistical ranking and selection procedures
62H30 Classification and discrimination; cluster analysis (statistical aspects)
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] J. A. Aledo, J. A. G‘amez, and D. Molina. Tackling the rank aggregation problem with evolutionary algorithms. Applied Mathematics and Computation, 222:632 – 644, 2013. · Zbl 1346.68151
[2] A. Ali and M. Meilˇa. Experiments with Kemeny ranking: What works when? Mathematical Social Sciences, 64(1):28 – 40, 2012. · Zbl 1247.91041
[3] M. Alvo and P. L. H. Yu. Statistical Methods for Ranking Data. Frontiers in Probability and the Statistical Sciences. Springer, New York, NY, USA, 2014.
[4] C. Andrieu and G. O. Roberts. The pseudo-marginal approach for efficient Monte Carlo computations. The Annals of Statistics, 37(2):697–725, 2009. · Zbl 1185.60083
[5] D. Asfaw, V. Vitelli, Ø. Sørensen, E. Arjas, and A. Frigessi. Time-varying rankings with the Bayesian Mallows model. Stat, 6(1):14–30, 2017.
[6] J. Bartholdi, C. 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. · Zbl 0672.90004
[7] M.A. Beaumont. Estimation of population growth or decline in genetically monitored populations. Genetics, 164(3):1139–1160, 2003.
[8] S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1):107–117, 1998.
[9] L. M. Busse, P. Orbanz, and J. M. Buhmann. Cluster analysis of heterogeneous rank data. In Proceedings of the 24th International Conference on Machine Learning, ICML ’07, pages 113–120, New York, NY, USA, 2007. ACM.
[10] F. Caron and Y. W. Teh. Bayesian nonparametric models for ranked data. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1520–1528. Curran Associates, Inc., 2012.
[11] F. Caron, Y. W. Teh, and T. B. Murphy. Bayesian nonparametric Plackett-Luce models for the analysis of preferences for college degree programmes. The Annals of Applied Statistics, 8(2):1145–1181, 2014. · Zbl 1454.62153
[12] G. Celeux, M. Hurn, and C. Robert. Computational and inferential difficulties with mixture posterior distribution. Journal of the American Statistical Association, 95(451):957–970, 2000. · Zbl 0999.62020
[13] G. Celeux, F. Forbes, C. P. Robert, and D. M. Titterington. Deviance information criteria for missing data models. Bayesian Analysis, 1(4):651–674, 2006. · Zbl 1331.62329
[14] D. E. Critchlow. Metric methods for analyzing partially ranked data, volume 34. Springer Science and Business Media, 2012. · Zbl 0589.62041
[15] G. Csardi and T. Nepusz. The igraph software package for complex network research. InterJournal, Complex Systems:1695, 2006. URL http://igraph.sf.net. 45
[16] A. P. Dawid. The well-calibrated Bayesian. Journal of the American Statistical Association, 77(379):605–610, 1982. · Zbl 0495.62005
[17] J. C. de Borda. M´emoire sur les ´elections au scrutin, histoire de l’acad´emie royale des sciences. Paris, France, 1781.
[18] R. P. DeConde, S. Hawley, S. Falcon, N. Clegg, B. Knudsen, and R. Etzioni. Combining results of microarray experiments: A rank aggregation approach. Statistical Applications in Genetics and Molecular Biology, 5(1):Article 15, 2006. · Zbl 1166.92306
[19] K. Deng, S. Han, K. J. Li, and J. S. Liu. Bayesian aggregation of order-based rank data. Journal of the American Statistical Association, 109(507):1023–1039, 2014. · Zbl 1368.62122
[20] S. M. Dhanasekaran, T. R. Barrette, D. Ghosh, R. Shah, S. Varambally, K. Kurachi, K. J. Pienta, M. A. Rubin, and A. M. Chinnaiyan. Delineation of prognostic biomarkers in prostate cancer. Nature, 412:822–826, 2001.
[21] P. Diaconis. Group representations in probability and statistics, volume 11 of Lecture Notes - Monograph Series. Institute of Mathematical Statistics, Hayward, CA, USA, 1988.
[22] J. P. Doignon, A. Pekeˇc, and M. Regenwetter. The repeated insertion model for rankings: Missing link between two subset choice models. Psychometrika, 69(1):33–54, 2004. · Zbl 1306.62404
[23] D. Firth and H. L. Turner. Bradley-Terry models in R: the BradleyTerry2 package. Journal of Statistical Software, 48(9), 2012.
[24] M. A. Fligner and J. S. Verducci. Distance based ranking models. Journal of the Royal Statistical Society: Series B (Methodological), 48(3):359–369, 1986. · Zbl 0658.62031
[25] B. Francis, R. Dittrich, and R. Hatzinger. Modeling heterogeneity in ranked responses by nonparametric maximum likelihood: how do Europeans get their scientific knowledge? The Annals of Applied Statistics, 4(4):2181–2202, 2010. · Zbl 1220.62158
[26] J. F¨urnkranz and E. H¨ullermeier. Preference learning: An introduction. Springer, 2010. · Zbl 1214.68285
[27] P. Gopalan, T.S. Jayram, R. Krauthgamer, and R. Kumar. Approximating the longest increasing sequence and distance from sortedness in a data stream. Research Microsoft Publications, 2006.
[28] I. C. Gormley and T. B. Murphy. Analysis of Irish third-level college applications data. Journal of the Royal Statistical Society: Series A (Statistics in Society), 169(2):361–379, 2006.
[29] J. Guiver and E. Snelson. Bayesian inference for Plackett-Luce ranking models. In proceedings of the 26th annual international conference on machine learning, pages 377–384. ACM, 2009.
[30] D. R. Hunter. MM algorithms for generalized Bradley-Terry models. The Annals of Statistics, 32(1):384–406, 2004. 46 · Zbl 1105.62359
[31] E. Irurozki, B. Calvo, and A. Lozano. Sampling and learning the Mallows and generalized Mallows models under the Hamming distance. Bernoulli (submitted), 2014. · Zbl 1433.62047
[32] E. Irurozki, B. Calvo, and A. Lozano. PerMallows: An R package for Mallows and generalized Mallows models. Journal of Statistical Software, 71, 2016a. · Zbl 1433.62047
[33] E. Irurozki, B. Calvo, and A. Lozano. Sampling and learning the Mallows and generalized Mallows models under the Cayley distance. Methodology and Computing in Applied Probability, 2016b. · Zbl 1433.62047
[34] J. Jacques and C. Biernacki. Model-based clustering for multivariate partial ranking data. Journal of Statistical Planning and Inference, 149:201–217, 2014. · Zbl 1285.62069
[35] J. Jacques, Q. Grimonprez, and C. Biernacki. Rankcluster: An R package for clustering multivariate partial rankings. The R Journal, 6(1):10, 2014.
[36] A. Jasra, C.C. Holmes, and D.A. Stephens. Markov chain Monte Carlo methods and the label switching problem in Bayesian mixture modeling. Statistical Science, 20(1):50–67, 2005. · Zbl 1100.62032
[37] T. Kamishima. Nantonac collaborative filtering: Recommendation based on order responses. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 583–588, New York, NY, USA, 2003. ACM.
[38] M. E. Khan, Y. J. Ko, and M. Seeger. Scalable collaborative Bayesian preference learning. In AISTATS, volume 14, pages 475–483, 2014.
[39] G. Lebanon and Y. Mao. Non-parametric modeling of partially ranked data. Journal of Machine Learning Research, 9:2401–2429, 2008. · Zbl 1225.62067
[40] P. H. Lee and P. L. H. Yu. Mixtures of weighted distance-based models for ranking data with applications in political studies. Computational Statistics & Data Analysis, 56(8): 2486–2500, 2012. · Zbl 1252.62010
[41] S. Lin and J. Ding. Integration of ranked lists via cross entropy Monte Carlo with applications to mRNA and microRNA studies. Biometrics, 65(1):9–18, 2009. · Zbl 1159.62077
[42] R. Little. Calibrated Bayes, for statistics in general, and missing data in particular. Statistical Science, 26(2):162–174, 2011. · Zbl 1246.62054
[43] T. Lu and C. Boutilier. Effective sampling and learning for Mallows models with pairwisepreference data. Journal of Machine Learning Research, 15:3783–3829, 2014.
[44] R.D. Luce. Individual choice behavior: A theoretical analysis. Wiley, New York, NY, USA, 1959. · Zbl 0093.31708
[45] J. Luo, D. J. Duggan, Y. Chen, J. Sauvageot, C. M. Ewing, M. L. Bittner, J. M. Trent, and W. B. Isaacs. Human prostate cancer and benign prostatic hyperplasia: Molecular dissection by gene expression profiling. Cancer Research, 61(12):4683–4688, 2001.
[46] C. L. Mallows. Non-null ranking models. I. Biometrika, 44(1/2):114–130, 1957. 47 · Zbl 0087.34001
[47] J. I. Marden. Analyzing and Modeling Rank Data, volume 64 of Monographs on Statistics and Applied Probability. Chapman & Hall, Cambridge, MA, USA, 1995. · Zbl 0853.62006
[48] M. Meilˇa and L. Bao. An exponential model for infinite rankings. Journal of Machine Learning Research, 11:3481–3518, 2010. · Zbl 1242.62017
[49] M. Meilˇa and H. Chen. Dirichlet process mixtures of generalized Mallows models. In Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-10), pages 358–367, Corvallis, OR, USA, 2010. AUAI Press.
[50] D. Meyer and K. Hornik. Generalized and customizable sets in R. Journal of Statistical Software, 31(2):1–27, 2009.
[51] D. Meyer and K. Hornik. relations: Data structures and algorithms for relations. R package version 0.6-3, 2014. URL http://CRAN.R-project.org/package=relations.
[52] S. Mukherjee. Estimation in exponential families on permutations. The Annals of Statistics, 44(2):853–875, 2016. · Zbl 1341.62083
[53] T. B. Murphy and D. Martin. Mixtures of distance-based models for ranking data. Computational Statistics & Data Analysis, 41(3–4):645 – 655, 2003.
[54] I. Murray, Z. Ghahramani, and D. MacKay. MCMC for doubly-intractable distributions. arXiv preprint arXiv:1206.6848, 2012.
[55] P. Papastamoulis.label.switching: An R package for dealing with the label switching problem in MCMC outputs. arXiv:1503.02271v1, 2015.
[56] V. Pihur, S. Datta, and S. Datta. RankAggreg, an R package for weighted rank aggregation. BMC bioinformatics, 10(1):62, 2009.
[57] R. L. Plackett. The analysis of permutations. Journal of the Royal Statistical Society. Series C (Applied Statistics), 24(2):193–202, 1975.
[58] M. Regenwetter, J. C. Falmagne, and B. Grofman. A stochastic model of preference change and its application to 1992 presidential election panel data. Psychological Review, 106 (2):362–384, 1999.
[59] M. G. Schimek, E. Budinsk´a, K. G. Kugler, V. ˇSvendov´a, J. Ding, and S. Lin. TopKLists: a comprehensive R package for statistical inference, stochastic aggregation, and visualization of multiple omics ranked lists. Statistical Applications in Genetics and Molecular Biology, 14(3):311–316, 2015. · Zbl 1329.92008
[60] D. Singh, P. G. Febbo, K. Ross, D. G. Jackson, J. Manola, C. Ladd, P. Tamayo, A. A. Renshaw, A. V. D’Amico, J. P. Richie, E. S. Lander, M. Loda, P. W. Kantoff, T. R. Golub, and W. R. Sellers. Gene expression correlates of clinical prostate cancer behavior. Cancer Cell, 1(2):203 – 209, 2002. ISSN 1535-6108.
[61] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, 2017. URL http://oeis. org. 48 · Zbl 1274.11001
[62] M. Sun, G. Lebanon, and P. Kidwell. Estimating probabilities in recommendation systems. Journal of the Royal Statistical Society, Series C, 61(3):471–492, 2012.
[63] L. True, I. Coleman, S. Hawley, C.Y. Huang, D. Gifford, R. Coleman, T. M. Beer, E. Gelmann, M. Datta, E. Mostaghel, B. Knudsen, P. Lange, R. Vessella, D. Lin, L. Hood, and P. S. Nelson. A molecular correlate to the Gleason grading system for prostate adenocarcinoma. Proceedings of the National Academy of Sciences, 103(29):10991–10996, 2006.
[64] M. N. Volkovs and R. S. Zemel. New learning methods for supervised and unsupervised preference aggregation. Journal of Machine Learning Research, 15:1135–1176, 2014. · Zbl 1318.68158
[65] J. B. Welsh, L. M. Sapinoso, A. I. Su, S. G. Kern, J. Wang-Rodriguez, C. A. Moskaluk, H. F. Frierson, and G. M. Hampton. Analysis of gene expression identifies candidate markers and pharmacological targets in prostate cancer. Cancer Research, 61(16):5974– 5978, 2001.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.