Spectral MLE: Top-K rank aggregation from pairwise comparisons

Yuxin Chen, Changho Suh

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

37 Scopus citations

Abstract

This paper explores the preference-based top-A' rank aggregation problem. Suppose that a collection of items is repeatedly compared in pairs, and one wishes to recover a consistent ordering that emphasizes the top-.ft' ranked items, based on partially revealed preferences. We focus on the Bradley-Terry-Luce model that postulates a set of latent preference scores underlying all items, where the odds of paired comparisons depend only on the relative scores of the items involved. We characterize the minimax limits on identifi-ability of top-AT ranked items, in the presence of random and non-adaptive sampling. Our results highlight a separation measure that quantifies the gap of preference scores between the Kth and (AT + 1)th ranked items. The minimum sample complexity required for reliable top-A' ranking scales inversely with the separation measure. To approach this minimax limit, we propose a nearly linear-time ranking scheme, called Spectral MLE, that returns the indices of the top-K items in accordance to a careful score estimate. In a nutshell, Spectral MLE starts with an initial score estimate with minimal squared loss (obtained via a spectral method), and then successively refines each component with the assistance of coordinate-wise MLEs. Encouragingly, Spectral MLE allows perfect top-A' item identification under minimal sample complexity. The practical applicability of Spectral MLE is further corroborated by numerical experiments.

Original languageEnglish (US)
Title of host publication32nd International Conference on Machine Learning, ICML 2015
EditorsFrancis Bach, David Blei
PublisherInternational Machine Learning Society (IMLS)
Pages371-380
Number of pages10
ISBN (Electronic)9781510810587
StatePublished - Jan 1 2015
Externally publishedYes
Event32nd International Conference on Machine Learning, ICML 2015 - Lile, France
Duration: Jul 6 2015Jul 11 2015

Publication series

Name32nd International Conference on Machine Learning, ICML 2015
Volume1

Other

Other32nd International Conference on Machine Learning, ICML 2015
CountryFrance
CityLile
Period7/6/157/11/15

All Science Journal Classification (ASJC) codes

  • Human-Computer Interaction
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Spectral MLE: Top-K rank aggregation from pairwise comparisons'. Together they form a unique fingerprint.

  • Cite this

    Chen, Y., & Suh, C. (2015). Spectral MLE: Top-K rank aggregation from pairwise comparisons. In F. Bach, & D. Blei (Eds.), 32nd International Conference on Machine Learning, ICML 2015 (pp. 371-380). (32nd International Conference on Machine Learning, ICML 2015; Vol. 1). International Machine Learning Society (IMLS).