The Kendall and Mallows Kernels for Permutations

Yunlong Jiao, Jean-Philippe Vert
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1935-1944, 2015.

Abstract

We show that the widely used Kendall tau correlation coefficient is a positive definite kernel for permutations. It offers a computationally attractive alternative to more complex kernels on the symmetric group to learn from rankings, or to learn to rank. We show how to extend it to partial rankings or rankings with uncertainty, and demonstrate promising results on high-dimensional classification problems in biomedical applications.

Cite this Paper


BibTeX
@InProceedings{pmlr-v37-jiao15, title = {The Kendall and Mallows Kernels for Permutations}, author = {Jiao, Yunlong and Vert, Jean-Philippe}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1935--1944}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/jiao15.pdf}, url = {https://proceedings.mlr.press/v37/jiao15.html}, abstract = {We show that the widely used Kendall tau correlation coefficient is a positive definite kernel for permutations. It offers a computationally attractive alternative to more complex kernels on the symmetric group to learn from rankings, or to learn to rank. We show how to extend it to partial rankings or rankings with uncertainty, and demonstrate promising results on high-dimensional classification problems in biomedical applications.} }
Endnote
%0 Conference Paper %T The Kendall and Mallows Kernels for Permutations %A Yunlong Jiao %A Jean-Philippe Vert %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-jiao15 %I PMLR %P 1935--1944 %U https://proceedings.mlr.press/v37/jiao15.html %V 37 %X We show that the widely used Kendall tau correlation coefficient is a positive definite kernel for permutations. It offers a computationally attractive alternative to more complex kernels on the symmetric group to learn from rankings, or to learn to rank. We show how to extend it to partial rankings or rankings with uncertainty, and demonstrate promising results on high-dimensional classification problems in biomedical applications.
RIS
TY - CPAPER TI - The Kendall and Mallows Kernels for Permutations AU - Yunlong Jiao AU - Jean-Philippe Vert BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-jiao15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1935 EP - 1944 L1 - http://proceedings.mlr.press/v37/jiao15.pdf UR - https://proceedings.mlr.press/v37/jiao15.html AB - We show that the widely used Kendall tau correlation coefficient is a positive definite kernel for permutations. It offers a computationally attractive alternative to more complex kernels on the symmetric group to learn from rankings, or to learn to rank. We show how to extend it to partial rankings or rankings with uncertainty, and demonstrate promising results on high-dimensional classification problems in biomedical applications. ER -
APA
Jiao, Y. & Vert, J.. (2015). The Kendall and Mallows Kernels for Permutations. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1935-1944 Available from https://proceedings.mlr.press/v37/jiao15.html.

Related Material