jmlr jmlr2010 jmlr2010-10 jmlr2010-10-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Marina Meilă, Le Bao
Abstract: This paper presents a statistical model for expressing preferences through rankings, when the number of alternatives (items to rank) is large. A human ranker will then typically rank only the most preferred items, and may not even examine the whole set of items, or know how many they are. Similarly, a user presented with the ranked output of a search engine, will only consider the highest ranked items. We model such situations by introducing a stagewise ranking model that operates with finite ordered lists called top-t orderings over an infinite space of items. We give algorithms to estimate this model from data, and demonstrate that it has sufficient statistics, being thus an exponential family model with continuous and discrete parameters. We describe its conjugate prior and other statistical properties. Then, we extend the estimation problem to multimodal data by introducing an Exponential-Blurring-Mean-Shift nonparametric clustering algorithm. The experiments highlight the properties of our model and demonstrate that infinite models over permutations can be simple, elegant and practical. Keywords: permutations, partial orderings, Mallows model, distance based ranking model, exponential family, non-parametric clustering, branch-and-bound
S.F. Altschul, W. Gish, W. Miller, E.W. Myers, and D.J. Lipman. Basic local alignment search tool. Journal of Molecular Biology, 3(213):403–410, 1990. doi:10.1006/jmbi.1990.9999., PMID 2231712. L.M. Busse, P. Orbanz, and J. B¨ hmann. Cluster analysis of heterogeneous rank data. In Proceedu ings of the International Conference on Machine Learning ICML, 2007. M.A. Carreira-Perpi˜ an. Fast nonparametric clustering with gaussian blurring mean-shift. In 23rd n´ International Conference on Machine Learning (ICML), pages 153–160, 2006. Y. Cheng. Mean shift, mode seeking, and clustering. IEEE Trans. Pattern Anal. Mach. Intell., 17 (8):790–799, 1995. ISSN 0162-8828. doi: http://dx.doi.org/10.1109/34.400568. W.C. Cohen, R.S. Schapire, and Y. Singer. Learning to order things. Journal of Artificial Intelligence Research, 10:243–270, 1999. D.E. Critchlow. Metric methods for analyzing partially ranked data. Number 34 in Lecture notes in statistics. Springer-Verlag, Berlin Heidelberg New York Tokyo, 1985. M.H. DeGroot. Probability and Statistics. Addison–Wesley Pub. Co., Reading, MA, 1975. J.K. Eng, A.L. McCormack, and J.R. Yates. An approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database. Journal of the American Society of Mass Spectrometry, 5:976–989, 1994. doi:10.1016/1044-0305(94)80016-2. M.A. Fligner and J.S. Verducci. Distance based ranking models. Journal of the Royal Statistical Society B, 48:359–369, 1986. M.A. Fligner and J.S. Verducci. Multistage ranking models. Journal of the American Statistical Association, 88:892–901, 1988. M.A. Fligner and J.S. Verducci. Posterior probability for a consensus ordering. Psychometrika, 55: 53–63, 1990. K. Fukunaga and L.D. Hostetler. The estimation of the gradient of a density function, with applications in pattern recognition. IEEE Trans. Information Theory, IT-21:32–40, 1975. ISSN 0018-9448. K. Goldberg, T. Roeder, D. Gupta, and C. Perkins. Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval, 4(2):133–151, July 2001. http://goldberg.berkeley.edu/jesterdata/, to cite for Jester data set. I.C. Gormley and T.B. Murphy. Analysis of irish third-level college applications. Journal of the Royal Statistical Society, Series A, 169(2):361–380, 2006. I.C. Gormley and T.B. Murphy. Exploring heterogeneity in irish voting data: A mixture modelling approach. Technical Report 05/09, Department of Statistics, Trinity College Dublin, 2005. 3517 ˘ M EIL A AND BAO G. Lebanon and J. Lafferty. Conditional models on the ranking poset. In Advances in Neural Information Processing Systems, number 15, Cambridge, MA, 2003. MIT Press. R.D. Luce. Individual Choice Behavior. Wiley, New York, 1959. C.L. Mallows. Non-null ranking models. Biometrika, 44:114–130, 1957. B. Mandhani and M. Meil˘ . Better search for learning exponential models of rankings. In David a VanDick and Max Welling, editors, Artificial Intelligence and Statistics AISTATS, number 12, 2009. Y. Mao and G. Lebanon. Non-parametric modelling of partially ranked data. Journal of Machine Learning Research, 9:2401–2429, 2008. URL jmlr.csail.mit.edu/papers/v9/ lebanon08a.html. M. Meil˘ and L. Bao. Estimation and clustering with infinite rankings. In David McAllester and a Petri Millim¨ ki, editors, Proceedings of the 24-th Conference on Uncertainty in Artificial Intellia gence (UAI 2008). AUAI Press, 2008. M. Meil˘ , K. Phadnis, A. Patterson, and J. Bilmes. Consensus ranking under the exponential model. a In Ron Parr and Linda Van den Gaag, editors, Proceedings of the 23rd Conference on Uncertainty in AI, volume 23, page (to appear), 2007. T.B. Murphy and D. Martin. Mixtures of distance-based models for ranking data. Computational Statistics and Data Analysis, 41(3–4):645–655, 2003. J. Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. R.L. Plackett. The analysis of permutations. Applied Statistics, 24:193–202, 1975. N. Quadrianto, A.J. Smola, L. Song, and T. Tuytelaars. Kernelized sorting. IEEE Transactions on Pattern Analysis and Machine Intelligence, (preprint), 2010. R.P. Stanley. Enumerative Combinatorics, volume 1. Cambridge Unversity Press, Cambridge, New York, Melbourne, 1997. E. Thoma. Die unzerlegbaren, positiv-definiten Klassenfunctionen der abz¨ lbar unendlichen, syma metrische Gruppen. Mathematische Zeitschrift, 85:40–61, 1964. A.W. van der Vaart. Asymptotic statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambrigde University Press, 1998. 3518