論文の概要: 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つのステップ間の注意深い近似独立性論によって確立される。

関連論文リスト

• Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons [1.5653612447564105]
  最近の研究は、学習に基づく手法を用いてランク付け問題の最先端を推し進めている。 本稿では,MWFASを解くための効率的なアルゴリズムを提案し,ランキング問題に対処する。 実験の結果,これらの単純で学習不要なアルゴリズムは,学習に基づく手法を高速化するだけでなく,より優れたランキング精度が得られることがわかった。
  論文  参考訳（メタデータ） (2024-12-10T16:51:11Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。 本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
  論文  参考訳（メタデータ） (2023-12-19T01:52:13Z)
• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2023-10-24T09:47:32Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Improved theoretical guarantee for rank aggregation via spectral method [1.0152838128195467]
  複数の項目間のペアワイズ比較を与えられた場合、ランキングが観測値と一致するようにランク付けする方法? ランクアグリゲーションとして知られるこの問題は、スポーツ、レコメンデーションシステム、その他のウェブアプリケーションに多くの応用を見出している。 ここで、各ペア比較は真のスコア差の破損したコピーである。
  論文  参考訳（メタデータ） (2023-09-07T16:01:47Z)
• Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality [3.1219977244201056]
  本稿では,古典的Bradley-Terry-Luceモデル(BTL)のペア比較によるランキング問題について検討する。 十分に多くのサンプルを用いて,Cram'er-Rao の下界と一致するエントリワイズ推定誤差が得られることを示す。 我々は、最も広いサンプルを持つ体制においても、同様の保証を確実に達成できる分割対コンカマーのアルゴリズムについて検討する。
  論文  参考訳（メタデータ） (2023-04-13T21:14:30Z)
• Efficient computation of rankings from pairwise comparisons [0.0]
  我々は、同じ結果を返すが、はるかに高速な代替かつ同様の単純なイテレーションについて記述する。 本稿では,このアルゴリズムをサンプルデータセットに適用し,その収束性に関する多くの結果を導出する。
  論文  参考訳（メタデータ） (2022-06-30T19:39:09Z)
• Decreasing Annotation Burden of Pairwise Comparisons with Human-in-the-Loop Sorting: Application in Medical Image Artifact Rating [3.5314411880556063]
  ペア比較によるランキングでは、順序分類よりも信頼性が向上している。 本稿では,定量的な測定値によってランク付けに必要なペアワイズ比較数を減少させる手法を提案する。
  論文  参考訳（メタデータ） (2022-02-10T04:02:45Z)
• Ranking with Confidence for Large Scale Comparison Data [1.2183405753834562]
  本研究では、比較ノイズを考慮した生成データモデルを用いて、ペア比較から高速で正確で情報的なランク付けを行う。 実データでは、PD-Rankは、アクティブな学習方法よりも同じKendallアルゴリズムを達成するのに、計算時間が少ない。
  論文  参考訳（メタデータ） (2022-02-03T16:36:37Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。 本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。 提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
  論文  参考訳（メタデータ） (2021-10-08T13:51:55Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。