Top-K Rank Aggregation From M-Wise Comparisons

Cited 2 time in webofscience Cited 0 time in scopus
  • Hit : 460
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorJang, Minjeko
dc.contributor.authorKim, Sunghyunko
dc.contributor.authorSuh, Changhoko
dc.date.accessioned2018-11-12T04:18:15Z-
dc.date.available2018-11-12T04:18:15Z-
dc.date.created2018-10-22-
dc.date.created2018-10-22-
dc.date.issued2018-10-
dc.identifier.citationIEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, v.12, no.5, pp.989 - 1004-
dc.identifier.issn1932-4553-
dc.identifier.urihttp://hdl.handle.net/10203/246313-
dc.description.abstractSuppose 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.-
dc.languageEnglish-
dc.publisherIEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC-
dc.subjectUTILITY-
dc.subjectCHOICE-
dc.subjectMODELS-
dc.titleTop-K Rank Aggregation From M-Wise Comparisons-
dc.typeArticle-
dc.identifier.wosid000446341300013-
dc.identifier.scopusid2-s2.0-85046714933-
dc.type.rimsART-
dc.citation.volume12-
dc.citation.issue5-
dc.citation.beginningpage989-
dc.citation.endingpage1004-
dc.citation.publicationnameIEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING-
dc.identifier.doi10.1109/JSTSP.2018.2834864-
dc.contributor.localauthorSuh, Changho-
dc.contributor.nonIdAuthorKim, Sunghyun-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorOptimal sample complexity-
dc.subject.keywordAuthorM-wise measurements-
dc.subject.keywordAuthortop-K ranking-
dc.subject.keywordAuthorPlackett-Luce models-
dc.subject.keywordAuthorspectral methods-
dc.subject.keywordPlusUTILITY-
dc.subject.keywordPlusCHOICE-
dc.subject.keywordPlusMODELS-
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 2 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0