TY - GEN
T1 - Kantorovich distances between rankings with applications to rank aggregation
AU - Clémençon, Stéphan
AU - Jakubowicz, Jérémie
PY - 2010/1/1
Y1 - 2010/1/1
N2 - The goal of this paper is threefold. It first describes a novel way of measuring disagreement between rankings of a finite set of n≥1 elements, that can be viewed as a (mass transportation) Kantorovich metric, once the collection rankings of is embedded in the set 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.
AB - The goal of this paper is threefold. It first describes a novel way of measuring disagreement between rankings of a finite set of n≥1 elements, that can be viewed as a (mass transportation) Kantorovich metric, once the collection rankings of is embedded in the set 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.
U2 - 10.1007/978-3-642-15880-3_22
DO - 10.1007/978-3-642-15880-3_22
M3 - Conference contribution
AN - SCOPUS:78049341982
SN - 364215879X
SN - 9783642158797
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 248
EP - 263
BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2010, Proceedings
PB - Springer Verlag
T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2010
Y2 - 20 September 2010 through 24 September 2010
ER -