A Multiresolution Analysis Framework for the Statistical Analysis of Incomplete Rankings

Abstract

Though the statistical analysis of ranking data has been a subject of interest over the past centuries, especially in economics, psychology or social choice theory, it has been revitalized in the past 15 years by recent applications such as recommender or search engines and is receiving now increasing interest in the machine learning literature. Numerous modern systems indeed generate ranking data, representing for instance ordered results to a query or user preferences. Each such ranking usually involves a small but varying subset of the whole catalog of items only. The study of the variability of these data, i.e. the statistical analysis of incomplete rank-ings, is however a great statistical and computational challenge, because of their heterogeneity and the related combinatorial complexity of the problem. Whereas many statistical methods for analyzing full rankings (orderings of all the items in the catalog) are documented in the dedicated literature, partial rankings (full rankings with ties) or pairwise comparisons, only a few approaches are available today to deal with incomplete ranking, relying each on a strong specific assumption. It is the purpose of this article to introduce a novel general framework for the statistical analysis of incomplete rankings. It is based on a representation tailored to these specific data, whose construction is also explained here, which fits with the natural multi-scale structure of incomplete rankings and provides a new decomposition of rank information with a multiresolu-tion analysis interpretation (MRA). We show that the MRA representation naturally allows to overcome both the statistical and computational challenges without any structural assumption on the data. It therefore provides a general and flexible framework to solve a wide variety of statistical problems, where data are of the form of incomplete rankings.

References in corpus (9)

• Collaborative Filtering and the Missing at Random Assumption
• Models for Paired Comparison Data: A Review with Emphasis on Dependent Data
• Noisy Sorting Without Resampling
• An Active Learning Algorithm for Ranking from Pairwise Preferences with an Almost Optimal Query Complexity
• Preference Elicitation For General Random Utility Models
• An Algorithm for the Optimal Consistent Approximation to a Pairwise Comparisons Matrix by Orthogonal Projections
• Consensus ranking under the exponential model
• Spectra of Symmetrized Shuffling Operators
• Multiresolution Analysis of Incomplete Rankings