Abstract

Consider a crowd sourcing problem where we have n experts and d tasks. The average ability of each expert for each task is stored in an unknown matrix M, from which we have incomplete and noise observations. We make no (semi) parametric assumptions, but assume that the experts can be perfectly ordered: so that if an expert A is better than an expert B, the ability of A is higher than that of B for all tasks. We either assume the same for the task, or not, depending on the scenario. This implies that if the matrix M, up to permutations of its rows and columns, is either isotonic, or bi-isotonic.

We focus on the problem of recovering the optimal ranking of the experts and/or of the tasks, in l2 norm. We will consider this problem with some side-information — i.e. when the ordering of the tasks (if it exists) is known to the statistician – or not. In other words, we aim at estimating the suitable permutation of the rows of M. We provide a minimax-optimal and computationally feasible method for this problem in three scenarios of increasing difficulty: known order of the task, unknown order of the tasks, no order of the tasks. The algorithms we provide are based on hierarchical clustering, PCA , change-point detection, and exchange of informations among the clusters.

This talk is based on a joint ongoing work with Emmanuel Pilliat, Maximilian Graf and Nicolas Verzelen.