Top-K ranking: An information-theoretic perspective

Yuxin Chen, Changho Suh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We develop an information-theoretic framework that explores the identifiability of top-K ranked items. The goal of the problem considered herein is to recover a consistent ordering that emphasizes the top-K ranked items, based on partially revealed preferences. Under the Bradley-Terry-Luce model that postulates a set of latent preference scores underlying all items and the odds of paired comparisons depend only on the relative scores of the items involved, we characterize the fundamental limits (up to some constant gap) on the amount of information required for reliably identifying the top-K ranked items. Here we introduce an information-theoretic notion of reliable ranking, meaning that the probability of the estimated ranking being inconsistent with the ground truth can be made arbitrarily close to zero. We single out one significant measure that plays a crucial role in determining the limits: the separation measure that quantifies the gap of preference scores between the Kth and (K + 1)th ranked items. We show that the minimum sample complexity required for reliable top-K ranking scales inversely with the separation measure.

Original languageEnglish (US)
Title of host publicationITW 2015 - 2015 IEEE Information Theory Workshop
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages212-213
Number of pages2
ISBN (Electronic)9781467378529
DOIs
StatePublished - Dec 17 2015
Externally publishedYes
EventIEEE Information Theory Workshop, ITW 2015 - Jeju Island, Korea, Republic of
Duration: Oct 11 2015Oct 15 2015

Publication series

NameITW 2015 - 2015 IEEE Information Theory Workshop

Other

OtherIEEE Information Theory Workshop, ITW 2015
CountryKorea, Republic of
CityJeju Island
Period10/11/1510/15/15

All Science Journal Classification (ASJC) codes

  • Information Systems

Cite this

Chen, Y., & Suh, C. (2015). Top-K ranking: An information-theoretic perspective. In ITW 2015 - 2015 IEEE Information Theory Workshop (pp. 212-213). [7360765] (ITW 2015 - 2015 IEEE Information Theory Workshop). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITWF.2015.7360765