Sorting from Noisy Information

Details Sorting from Noisy Information Sorting from Noisy Information

2009-10-07

arxiv.org/abs/0910.1191v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Sorting from Noisy Information does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sorting from Noisy Information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sorting from Noisy Information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-35828