Fugu-MT 論文翻訳(概要): Optimal Full Ranking from Pairwise Comparisons

論文の概要: Optimal Full Ranking from Pairwise Comparisons

arxiv url: http://arxiv.org/abs/2101.08421v1
Date: Thu, 21 Jan 2021 03:34:44 GMT
ステータス: 処理完了
システム内更新日: 2021-03-21 07:46:09.329295
Title: Optimal Full Ranking from Pairwise Comparisons
Title（参考訳）: 対数比較による最適フルランキング
Authors: Pinhan Chen, Chao Gao, Anderson Y. Zhang
Abstract要約: ランキングの最小最大レートは、問題の信号対雑音比の大きさに応じて指数レートと率の間の遷移を示す。ミニマックスレートを達成するために,まず,n$ プレーヤーを類似したスキルのグループに分割し,次に各グループ内のローカル mle を計算する分割・コンクエストランキングアルゴリズムを提案する。
参考スコア（独自算出の注目度）: 16.852801934478475
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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.
Abstract（参考訳）: ブラッドリー・テリー・ルースモデルに基づく部分対比較データからn$プレイヤーをランク付けする問題を考える。文献の中で初めて、このランキング問題の最小値は、逆数を数えて2つのランクベクトル間の差を測定するケンドールのタウ距離について導出される。ランキングの最小レートは、問題の信号対雑音比の大きさに応じて指数率と多項式率の遷移を示す。我々の知る限りでは、この現象は完全なランキングに特有であり、他の統計的推定問題では見られていない。ミニマックスレートを達成するために,まず,n$ プレーヤーを類似したスキルのグループに分割し,次に各グループ内のローカル mle を計算する分割・コンクエストランキングアルゴリズムを提案する。提案アルゴリズムの最適性は、2つのステップ間の注意深い近似独立性論によって確立される。