MRA-based Statistical Learning from Incomplete Rankings
Eric Sibony, Stéphan Clemençon, Jérémie Jakubowicz
Abstract
Statistical analysis of rank data describing preferences over small and variable subsets of a potentially large ensemble of items 1, ..., n is a very challenging problem. It is motivated by a wide variety of modern applications, such as recommender systems or search engines. However, very few inference methods have been documented in the literature to learn a ranking model from such incomplete rank data. The goal of this paper is twofold: it develops a rigorous mathematical framework for the problem of learning a ranking model from incomplete rankings and introduces a novel general statistical method to address it. Based on an original concept of multi-resolution analysis (MRA) of incomplete rankings, it finely adapts to any observation setting, leading to a statistical accuracy and an algorithmic complexity that depend directly on the complexity of the observed data. Beyond theoretical guarantees, we also provide experimental results that show its statistical performance.
BibTeX
@InProceedings{pmlr-v37-sibony15,
title = {MRA-based Statistical Learning from Incomplete Rankings},
author = {Sibony, Eric and Clemençon, Stéphan and Jakubowicz, Jérémie},
booktitle = {Proceedings of the 32nd International Conference on Machine Learning},
pages = {1432--1441},
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/sibony15.pdf},
url = {https://proceedings.mlr.press/v37/sibony15.html},
abstract = {Statistical analysis of rank data describing preferences over small and variable subsets of a potentially large ensemble of items 1, ..., n is a very challenging problem. It is motivated by a wide variety of modern applications, such as recommender systems or search engines. However, very few inference methods have been documented in the literature to learn a ranking model from such incomplete rank data. The goal of this paper is twofold: it develops a rigorous mathematical framework for the problem of learning a ranking model from incomplete rankings and introduces a novel general statistical method to address it. Based on an original concept of multi-resolution analysis (MRA) of incomplete rankings, it finely adapts to any observation setting, leading to a statistical accuracy and an algorithmic complexity that depend directly on the complexity of the observed data. Beyond theoretical guarantees, we also provide experimental results that show its statistical performance.}
}