Top-K Rank Aggregation From M-Wise Comparisons

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 33
  • Download : 0
Suppose one aims to identify only the top-K among a large collection of n items provided M-wise comparison data, where a set of M items in each data sample are ranked in order of individual preference. Natural questions that arise are as follows: 1) how one can reliably achieve the top-K rank aggregation task; and 2) how many M-wise samples one needs to achieve it. In this paper, we answer these two questions. First, we devise an algorithm that effectively converts M-wise samples into pairwise ones and employs a spectral method using the refined data. Second, we consider the Plackett-Luce (PL) model, a well-established statistical model, and characterize the minimal number of M-wise samples (i.e., sample complexity) required for reliable top-K ranking. It turns out to be inversely proportional to M. To characterize it, we derive a lower bound on the sample complexity and prove that our algorithm achieves the bound. Moreover, we conduct extensive numerical experiments to demonstrate that our algorithm not only attains the fundamental limit under the PL model but also provides robust ranking performance for a variety of applications that may not precisely fit the model. We corroborate our theoretical result using synthetic datasets, confirming that the sample complexity decreases at the rate of 1/M. Also, we verify the applicability of our algorithm in practice, showing that it performs well on various real-world datasets.
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date
2018-10
Language
English
Article Type
Article
Keywords

UTILITY; CHOICE; MODELS

Citation

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, v.12, no.5, pp.989 - 1004

ISSN
1932-4553
DOI
10.1109/JSTSP.2018.2834864
URI
http://hdl.handle.net/10203/246313
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0