Kantorovich Distances Between Rankings with Applications to Rank Aggregation
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.
Cite
Text
Clémençon and Jakubowicz. "Kantorovich Distances Between Rankings with Applications to Rank Aggregation." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010. doi:10.1007/978-3-642-15880-3_22Markdown
[Clémençon and Jakubowicz. "Kantorovich Distances Between Rankings with Applications to Rank Aggregation." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010.](https://mlanthology.org/ecmlpkdd/2010/clemencon2010ecmlpkdd-kantorovich/) doi:10.1007/978-3-642-15880-3_22BibTeX
@inproceedings{clemencon2010ecmlpkdd-kantorovich,
title = {{Kantorovich Distances Between Rankings with Applications to Rank Aggregation}},
author = {Clémençon, Stéphan and Jakubowicz, Jérémie},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2010},
pages = {248-263},
doi = {10.1007/978-3-642-15880-3_22},
url = {https://mlanthology.org/ecmlpkdd/2010/clemencon2010ecmlpkdd-kantorovich/}
}