기본 정보
연구 분야
프로젝트
발행물
구성원
article|
인용수 8
·2018
Top-$K$ Rank Aggregation From $M$-Wise Comparisons
Minje Jang, Sunghyun Kim, Changho Suh
IF 13.7IEEE Journal of Selected Topics in Signal Processing
초록

Suppose one aims to identify only the top- <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K$</tex-math></inline-formula> among a large collection of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula> items provided <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$M$</tex-math></inline-formula> -wise comparison data, where a set of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$M$</tex-math></inline-formula> 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- <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K$</tex-math></inline-formula> rank aggregation task; and 2) how many <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$M$</tex-math></inline-formula> -wise samples one needs to achieve it. In this paper, we answer these two questions. First, we devise an algorithm that effectively converts <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$M$</tex-math></inline-formula> -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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$M$</tex-math> </inline-formula> -wise samples (i.e., sample complexity) required for reliable top- <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$K$</tex-math></inline-formula> ranking. It turns out to be inversely proportional to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$M$</tex-math></inline-formula> . 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\frac{1}{M}$</tex-math></inline-formula> . Also, we verify the applicability of our algorithm in practice, showing that it performs well on various real-world datasets.

키워드
NotationRank (graph theory)MathematicsAlgorithmComputer scienceCombinatoricsArithmetic
타입
article
IF / 인용수
13.7 / 8
게재 연도
2018