Multiresolution analysis of incomplete rankings with applications to prediction
Eric Sibony, Stéphan Clémençon, Jérémie Jakubowicz · 2014
Data representing preferences of users are at the core of many Big Data modern applications, such as recommender systems or search engines. While most of the introduced machine learning approaches are designed to handle preference data under the form of cardinal scores, such as ratings given by the users to the items, many situations require to deal with ordinal preferences, coming from implicit feedback data for instance. Methods relying on the analysis of ranking data are best suited for these situations, but they face a great computational challenge insofar as the number of ways to express ordinal preferences on a catalog of n items explodes with n. It is the main purpose of this paper to promote a new representation of preference data when they come under the form of incomplete rankings, that is to say ordinal preferences on small subsets of items. The representation exploits the “multiscale” structure of incomplete rankings and though it relies on recent results in algebraic topology, it is used and interpreted similar to classic wavelet multiresolution analysis on a Euclidean space. We apply it to the problem of incomplete rankings prediction and show at the same time that it is statistically consistent and that it can be computed at a reasonable cost given the complexity of the original data. It is illustrated by very encouraging empirical work based on real datasets.