Abstract
The goal of this paper is threefold. It first describes a novel way of measuring disagreement between rankings of a finite set \(\mathcal{X}\) of n ≥ 1 elements, that can be viewed as a (mass transportation) Kantorovich metric, once the collection rankings of \(\mathcal{X}\) is embedded in the set \(\mathcal{K}_{n}\) of n×n doubly-stochastic matrices. It also shows that such an embedding makes it possible to define a natural notion of median, that can be interpreted in a probabilistic fashion. In addition, from a computational perspective, the convexification induced by this approach makes median computation more tractable, in contrast to the standard metric-based method that generally yields NP-hard optimization problems. As an illustration, this novel methodology is applied to the issue of ranking aggregation, and is shown to compete with state of the art techniques.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aslam, J.A., Montague, M.: Models for metasearch. In: SIGIR 2001: Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM Press, New York (2001)
Bansal, M.S., Fernandez-Baca, D.: Computing distances between partial rankings. Information Processing Letters 109, 238–241 (2009)
Bonnans, J.F., Gilbert, J.C., Lemaréchal, C., Sagastizábal, C.A.: Numerical optimization. Universitext. Springer, Berlin (2003)
Clémençon, S., Vayatis, N.: Tree-based ranking methods. IEEE Transactions on Information Theory 55(9), 4316–4336 (2009)
Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer, Heidelberg (2009)
Diaconis, P.: A generalization of spectral analysis with application to ranked data. The Annals of Statistics 17(3), 949–979 (1989)
Fishburn, P.: The Theory of Social Choice. University Press, Princeton (1973)
Fagin, R., Kumar, R., Mahdian, M., Sivakumar, D., Vee, E.: Comparing and aggregating rankings with ties. In: Proceedings of the 12th WWW conference, pp. 366–375 (2003)
Fagin, R., Kumar, R., Mahdian, M., Sivakumar, D., Vee, E.: Comparing partial rankings. SIAM J. Discrete Mathematics 20(3), 628–648 (2006)
Hüllermeier, E., Fürnkranz, J., Cheng, W., Brinker, K.: Label ranking by learning pairwise preferences. Artificial Intelligence 172, 1897–1917 (2008)
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)
Howie, J.: Hyperbolic groups. In: Metaftsis, V. (ed.) Groups and Applications, Ekdoseis Ziti, Thessaloniki, pp. 137–160 (2000)
Hudry, O.: NP-hardness results for the aggregation of linear orders into median orders. Ann. Oper. Res. 163, 63–88 (2008)
Järvelin, K., Kekäläinen, J.: Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems (TOIS) 20(4), 446 (2002)
Kemeny, J.G.: Mathematics without numbers. Daedalus 88, 571–591 (1959)
Korte, B., Vygen, J.: Combinatorial optimization. Algorithms and Combinatorics, vol. 21. Springer, Berlin (2000)
Lebanon, G., Lafferty, J.: Conditional models on the ranking poset. In: Proceedings of NIPS 2003 (2003)
Luce, R.D.: Individual Choice Behavior. Wiley, Chichester (1959)
Liu, T.Y., Xu, J., Qin, T., Xiong, W., Li, H.: Letor: Benchmark dataset for research on learning to rank for information retrieval. In: Proceedings of SIGIR 2007 Workshop on Learning to Rank for Information Retrieval, pp. 3–10 (2007)
Mallows, C.L.: Non-null ranking models. i. Biometrika 44(1-2), 114–130 (1957)
Mandhani, B., Meila, M.: Tractable search for learning exponential models of rankings. In: Proceedings of AISTATS. JMLR:W&CP 5, vol. 5 (2009)
Meila, M., Phadnis, K., Patterson, A., Bilmes, J.: Consensus ranking under the exponential model. In: Conference on Artificial Intelligence (UAI), pp. 729–734 (2007)
Munkres, J.: Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics 5(1), 32–38 (1957)
Plackett, R.L.: The analysis of permutations. Applied Statistics 2(24), 193–202 (1975)
Rachev, S.T.: Probability Metrics and the Stability of Stochastic Models. Wiley, Chichester (1991)
Rachev, S.T., Rüschendorf, L.: Mass Transportation Problems. Theory, vol. I. Springer, Heidelberg (1998)
Villani, C.: Optimal transport. Grundlehren der Mathematischen Wissenschaften, vol. 338. Springer, Heidelberg (2009)
Wakabayashi, Y.: The complexity of computing medians of relations. Resenhas 3(3), 323–349 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Clémençon, S., Jakubowicz, J. (2010). Kantorovich Distances between Rankings with Applications to Rank Aggregation. In: Balcázar, J.L., Bonchi, F., Gionis, A., Sebag, M. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2010. Lecture Notes in Computer Science(), vol 6321. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15880-3_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-15880-3_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15879-7
Online ISBN: 978-3-642-15880-3
eBook Packages: Computer ScienceComputer Science (R0)