Sorting from Noisy Information
Sorting from Noisy Information
复制标题
从噪音信息中排序
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Elchanan Mossel
中科院分区：
文献类型：
--
作者：
M. Braverman;Elchanan Mossel
本文研究了给定噪声信息推断顺序的问题。在这些问题中，$1,...,n$ 表示的 $n$ 个元素上存在未知的顺序（排列）$\pi$。我们假设信息是以与 $\pi$ 相关的方式生成的。目标是在给定观察到的信息的情况下找到最大似然 $\pi^*$。我们将考虑两种不同类型的观察：噪声比较和噪声订单。噪声阶中的数据是由与 \pi 相关的指数分布给出的排列（这也称为 Mallow 模型）。噪声比较中的数据是为每对元素给出的信号，该信号与其真实顺序相关。
在本文中，我们提出了以高概率解决这两个问题的多项式时间算法。作为证明的一部分，我们表明对于这两个模型，最大似然解 $\pi^{\ast}$ 接近原始排列 $\pi$。
我们的结果对排名应用很感兴趣，例如体育排名，或基于专家比较的搜索项目排名。
This paper studies problems of inferring order given noisy information. In these problems there is an unknown order (permutation) $\pi$ on $n$ elements denoted by $1,...,n$. We assume that information is generated in a way correlated with $\pi$. The goal is to find a maximum likelihood $\pi^*$ given the information observed. We will consider two different types of observations: noisy comparisons and noisy orders. The data in Noisy orders are permutations given from an exponential distribution correlated with \pi (this is also called the Mallow's model). The data in Noisy Comparisons is a signal given for each pair of elements which is correlated with their true ordering.
In this paper we present polynomial time algorithms for solving both problems with high probability. As part of our proof we show that for both models the maximum likelihood solution $\pi^{\ast}$ is close to the original permutation $\pi$.
Our results are of interest in applications to ranking, such as ranking in sports, or ranking of search items based on comparisons by experts.