Noisy Sorting Without Resampling

Mark Braverman; Elchanan Mossel

paper

Noisy Sorting Without Resampling

arXiv:0707.1051

Abstract

In this paper we study noisy sorting without re-sampling. In this problem there is an unknown order $a_{π (1)} < ... < a_{π (n)}$ where $π$ is a permutation on $n$ elements. The input is the status of $(2 n)$ queries of the form $q (a_{i}, x_{j})$ , where $q (a_{i}, a_{j}) = +$ with probability at least $1/2+\ga$ if $π (i) > π (j)$ for all pairs $i \neq = j$ , where $\ga > 0$ is a constant and $q (a_{i}, a_{j}) = - q (a_{j}, a_{i})$ for all $i$ and $j$ . It is assumed that the errors are independent. Given the status of the queries the goal is to find the maximum likelihood order. In other words, the goal is find a permutation $σ$ that minimizes the number of pairs $σ (i) > σ (j)$ where $q (σ (i), σ (j)) = -$ . The problem so defined is the feedback arc set problem on distributions of inputs, each of which is a tournament obtained as a noisy perturbations of a linear order. Note that when $\ga < 1/2$ and $n$ is large, it is impossible to recover the original order $π$ . It is known that the weighted feedback are set problem on tournaments is NP-hard in general. Here we present an algorithm of running time $n^{O (γ^{- 4})}$ and sampling complexity $O_{γ} (n lo g n)$ that with high probability solves the noisy sorting without re-sampling problem. We also show that if $a_{σ (1)}, a_{σ (2)}, ..., a_{σ (n)}$ is an optimal solution of the problem then it is ``close'' to the original order. More formally, with high probability it holds that $\sum_{i} ∣ σ (i) - π (i) ∣ = Θ (n)$ and $max_{i} ∣ σ (i) - π (i) ∣ = Θ (lo g n)$ . Our results are of interest in applications to ranking, such as ranking in sports, or ranking of search items based on comparisons by experts.

Noisy Sorting Without Resampling

Abstract

Cited by in corpus (42)