.png){kind=icon}
返回
OPTIMAL FULL RANKING FROM PAIRWISE COMPARISONS
.png){kind=icon}
OA
AI
DOI：10.1214/22-AOS2175.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We consider the problem of ranking n players from partial pairwise comparison data under the Bradley-Terry-Luce model. For the first time in the literature, the minimax rate of this ranking problem is derived with respect to the Kendall's tau distance that measures the difference between two rank vectors by counting the number of inversions. The minimax rate of ranking exhibits a transition between an exponential rate and a polynomial rate depending on the magnitude of the signal-to-noise ratio of the problem. To the best of our knowledge, this phenomenon is unique to full ranking and has not been seen in any other statistical estimation problem. To achieve the minimax rate, we propose a divide-and-conquer ranking algorithm that first divides the n players into groups of similar skills and then computes local MLE within each group. The optimality of the proposed algorithm is established by a careful approximate independence argument between the two steps.
Keyword:
Full ranking
Bradley-Terry-Luce model
divide-and-conquer
minimax risk
期刊
IF:
3.7
论文数:
2.8K
被引数:
2.9W
机构
引用论文
分享收藏Identification of Protein Subcellular Localization With Network and Functional Embeddings基于网络和功能嵌入的蛋白质亚细胞定位鉴定OAAI
OAAI分享收藏Increased Rate of Sialylation of Colonic Mucin by Cultured Ulcerative Colitis Mucosal Explants.png)
Digestion
DigestionIF0
PREAI
分享收藏
查看更多内容