Abstract
We propose the use of a genetic algorithm in order to solve the rank aggregation problem, which consists in, given a dataset of rankings (or permutations) of n objects, finding the ranking which best represents such dataset. Though different probabilistic models have been proposed to tackle this problem (see e.g. [12]), the so called Mallows model is the one that has more attentions [1]. Exact computation of the parameters of this model is an NP-hard problem [19], justifies the use of metaheuristic algorithms for its resolution. In particular, we propose a genetic algorithm for solving this problem and show that, in most cases (specially in the most complex ones) we get statistically significant better results than the ones obtained by the state of the art algorithms.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ali, A., Meila, M.: Experiments with kemeny ranking: What works when? Mathematical Social Sciences 64(1), 28–40 (2012)
Borda, J.: Memoire sur les elections au scrutin. Histoire de l’Academie Royal des Sciences
Ceberio, J., Mendiburu, A., Lozano, J.A.: Introducing the mallows model on estimation of distribution algorithms. In: Lu, B.-L., Zhang, L., Kwok, J. (eds.) ICONIP 2011, Part II. LNCS, vol. 7063, pp. 461–470. Springer, Heidelberg (2011)
Chen, H., Branavan, S.R.K., Barzilay, R., Karger, D.R.: Global models of document structure using latent permutations. In: Proceedings of Human Language Technologies, NAACL 2009, pp. 371–379 (2009)
Cohen, W.W., Schapire, R.E., Singer, Y.: Learning to order things. J. Artif. Int. Res. 10(1), 243–270 (1999)
Conitzer, V., Davenport, A.J., Kalagnanam, J.: Improved bounds for computing kemeny rankings. In: AAAI, pp. 620–626 (2006)
Davenport, A.J., Kalagnanam, J.: A computational study of the kemeny rule for preference aggregation. In: AAAI, pp. 697–702 (2004)
Diaconis, P.: A generalization of spectral analysis with application to ranked data. The Annals of Statistics, 949–979 (1989)
Diaconis, P.: Group representations in probability and statistics. Lecture Notes - Monograph Series, vol. 11. Institute of Mathematical Statistics, Harvard (1988)
Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: WWW, pp. 613–622 (2001)
Fligner, M.A., Verducci, J.S.: Distance based ranking models. Journal of the Royal Statistical Society 48(3), 359–369 (1986)
Fligner, M.A., Verducci, J.: Probability models and statistical analyses for ranking data. Springer (1993)
Goldberg, D.: Genetic algorithms in search, optimization and machine learning. Addison-Wesley (1989)
Kamishima, T.: Nantonac collaborative filtering: Recommendation based on order responses. In: The 9th International Conference on Knowledge Discovery and Data Mining (KDD), pp. 583–588 (2003)
Kemeny, J.L., Snell, J.G.: Mathematical models in the social sciences. Blaisdell, New York
Kendall, M.G.: A new measure of rank correlation. Biometrika 30, 81–93 (1938)
Larrañaga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I., Dizdarevic, S.: Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artif. Intell. Rev. 13(2), 129–170 (1999)
Mallows, C.L.: Non-null ranking models. I. Biometrika 44(1-2), 114–130 (1957)
Meila, M., Phadnis, K., Patterson, A., Bilmes, J.: Consensus ranking under the exponential model. In: 22nd Conf. on Uncertainty in Artificial Intelligence (2007)
Miller, B.L., Goldberg, D.E.: Genetic algorithms, tournament selection, and the effects of noise. Complex Systems 9, 193–212 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aledo, J.A., Gámez, J.A., Molina, D. (2013). Computing the Consensus Permutation in Mallows Distribution by Using Genetic Algorithms. In: Ali, M., Bosse, T., Hindriks, K.V., Hoogendoorn, M., Jonker, C.M., Treur, J. (eds) Recent Trends in Applied Artificial Intelligence. IEA/AIE 2013. Lecture Notes in Computer Science(), vol 7906. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38577-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-38577-3_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38576-6
Online ISBN: 978-3-642-38577-3
eBook Packages: Computer ScienceComputer Science (R0)