論文の概要: The Performance of the MLE in the Bradley-Terry-Luce Model in
$\ell_{\infty}$-Loss and under General Graph Topologies
- arxiv url: http://arxiv.org/abs/2110.10825v1
- Date: Wed, 20 Oct 2021 23:46:35 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-22 18:26:06.137995
- Title: The Performance of the MLE in the Bradley-Terry-Luce Model in
$\ell_{\infty}$-Loss and under General Graph Topologies
- Title（参考訳）: 一般グラフトポロジーによる$\ell_{\infty}$-LossにおけるBradley-Terry-LuceモデルにおけるMLEの性能
- Authors: Wanshan Li, Shamindra Shrotriya, Alessandro Rinaldo
- Abstract要約: 我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。
導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
- 参考スコア（独自算出の注目度）: 76.61051540383494
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Bradley-Terry-Luce (BTL) model is a popular statistical approach for
estimating the global ranking of a collection of items of interest using
pairwise comparisons. To ensure accurate ranking, it is essential to obtain
precise estimates of the model parameters in the $\ell_{\infty}$-loss. The
difficulty of this task depends crucially on the topology of the pairwise
comparison graph over the given items. However, beyond very few well-studied
cases, such as the complete and Erd\"os-R\'enyi comparison graphs, little is
known about the performance of the maximum likelihood estimator (MLE) of the
BTL model parameters in the $\ell_{\infty}$-loss under more general graph
topologies. In this paper, we derive novel, general upper bounds on the
$\ell_{\infty}$ estimation error of the BTL MLE that depend explicitly on the
algebraic connectivity of the comparison graph, the maximal performance gap
across items and the sample complexity. We demonstrate that the derived bounds
perform well and in some cases are sharper compared to known results obtained
using different loss functions and more restricted assumptions and graph
topologies. We further provide minimax lower bounds under $\ell_{\infty}$-error
that nearly match the upper bounds over a class of sufficiently regular graph
topologies. Finally, we study the implications of our bounds for efficient
tournament design. We illustrate and discuss our findings through various
examples and simulations.
- Abstract（参考訳）: Bradley-Terry-Luceモデル (BTL) は、ペア比較を用いて興味ある項目の集合のグローバルランキングを推定する一般的な統計手法である。
正確なランキングを確保するためには、$\ell_{\infty}$-loss のモデルパラメータの正確な推定値を得る必要がある。
この作業の難しさは、与えられた項目に対する対比較グラフのトポロジーに大きく依存する。
しかしながら、完全かつ Erd\"os-R\'enyi 比較グラフのような非常によく研究されたケース以外にも、より一般的なグラフトポロジーの下での$\ell_{\infty}$-lossのBTLモデルパラメータの最大極大推定器(MLE)の性能についてはほとんど知られていない。
本稿では,比較グラフの代数的接続性,項目間の最大性能ギャップ,サンプル複雑性に明示的に依存する btl mle の $\ell_{\infty}$ 推定誤差に関する新奇,一般上限を導出する。
異なる損失関数とより制限された仮定とグラフトポロジを用いて得られた既知の結果と比較して、導出境界が良好であり、場合によってはより鋭いことを示す。
さらに、十分正則なグラフトポロジーのクラス上の上界にほぼ一致する$\ell_{\infty}$-errorの下でミニマックス下界を提供する。
最後に,効率的なトーナメント設計における限界の影響について検討する。
様々な例やシミュレーションを通じて,本研究の成果を解説し,議論する。
関連論文リスト
- Minimax Hypothesis Testing for the Bradley-Terry-Luce Model [6.5990719141691825]
ブラッドリー・テリー・ルーシ(Bradley-Terry-Luce、BTL)モデルは、アイテムやエージェントのコレクションをランク付けする最も広く使われているモデルの一つである。
与えられたペア比較データセットとエージェントペアあたりの$k$の比較が、基礎となるBTLモデルに由来するかどうかを判定する仮説テストを提案する。
論文 参考訳（メタデータ） (2024-10-10T20:28:05Z) - Top-$K$ ranking with a monotone adversary [19.871049853222132]
比較グラフがランダムに生成され、敵が任意のエッジを追加することができるシナリオを考える。
統計学者の目標は、ペア比較に基づいて、上位$K$の推奨項目を正確に識別することである。
本論文の主な貢献は, ほぼ最適サンプル複雑性を実現するための重み付き最大極大推定器(MLE)を開発することである。
論文 参考訳（メタデータ） (2024-02-12T06:57:34Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph $\boldsymbolβ$-Model [4.540236408836132]
複数層からなるハイパーグラフ $boldsymbolbeta$-model について検討した。
最大極大推定値(ML)の収束率を導出し,その最小値の最適性を確立する。
また、ハイパーグラフ $boldsymbolbeta$-model における適合性の問題についても考察する。
論文 参考訳（メタデータ） (2023-07-06T07:23:06Z) - Principled Reinforcement Learning with Human Feedback from Pairwise or
$K$-wise Comparisons [79.98542868281473]
RLHF(Reinforcement Learning with Human Feedback)の理論的枠組みを提供する。
学習した報酬モデルに基づいてポリシーをトレーニングする際、MLEは失敗し、悲観的なMLEは特定のカバレッジ仮定の下で性能を改善したポリシーを提供する。
論文 参考訳（メタデータ） (2023-01-26T18:07:21Z) - Uncertainty Quantification of MLE for Entity Ranking with Covariates [3.2839905453386162]
本稿では,ペア比較に基づくランキング問題の統計的推定と推定について検討する。
我々は、有名なBradley-Terry-Luceモデルを拡張した新しいモデルCAREモデルを提案する。
我々は、スパース比較グラフの下で、$alpha_i*_i=1n$と$beta*$の最大確率推定器を導出する。
大規模数値研究による理論結果の検証と相互資金保有データセットへの適用について検討する。
論文 参考訳（メタデータ） (2022-12-20T02:28:27Z) - Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
我々は、$K関連ガウス非巡回グラフ(DAG)の発見問題を考える。
マルチタスク学習環境下では, 線形構造方程式モデルを学習するためのMLE ($l_1/l$-regularized maximum chance estimator) を提案する。
理論的には、関係するタスクにまたがるデータを活用することで、因果順序を復元する際のサンプルの複雑さをより高めることができることを示す。
論文 参考訳（メタデータ） (2021-11-03T22:10:18Z) - Sample-efficient L0-L2 constrained structure learning of sparse Ising
models [3.056751497358646]
スパースイジングモデルの基盤となるグラフを$n$ i.i.d.サンプルから$p$ノードで学習する問題を考察する。
濃度制約 L0 ノルムを有効に利用し、このノルムを L2 ノルムと組み合わせて非零係数をモデル化する。
論文 参考訳（メタデータ） (2020-12-03T07:52:20Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。