論文の概要: Minimax Hypothesis Testing for the Bradley-Terry-Luce Model
- arxiv url: http://arxiv.org/abs/2410.08360v1
- Date: Thu, 10 Oct 2024 20:28:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-10-31 03:46:24.287648
- Title: Minimax Hypothesis Testing for the Bradley-Terry-Luce Model
- Title（参考訳）: Bradley-Terry-Luceモデルのためのミニマックス仮説テスト
- Authors: Anuran Makur, Japneet Singh,
- Abstract要約: ブラッドリー・テリー・ルーシ(Bradley-Terry-Luce、BTL)モデルは、アイテムやエージェントのコレクションをランク付けする最も広く使われているモデルの一つである。
与えられたペア比較データセットとエージェントペアあたりの$k$の比較が、基礎となるBTLモデルに由来するかどうかを判定する仮説テストを提案する。
- 参考スコア（独自算出の注目度）: 6.5990719141691825
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Bradley-Terry-Luce (BTL) model is one of the most widely used models for ranking a collection of items or agents based on pairwise comparisons among them. Given $n$ agents, the BTL model endows each agent $i$ with a latent skill score $\alpha_i > 0$ and posits that the probability that agent $i$ is preferred over agent $j$ is $\alpha_i/(\alpha_i + \alpha_j)$. In this work, our objective is to formulate a hypothesis test that determines whether a given pairwise comparison dataset, with $k$ comparisons per pair of agents, originates from an underlying BTL model. We formalize this testing problem in the minimax sense and define the critical threshold of the problem. We then establish upper bounds on the critical threshold for general induced observation graphs (satisfying mild assumptions) and develop lower bounds for complete induced graphs. Our bounds demonstrate that for complete induced graphs, the critical threshold scales as $\Theta((nk)^{-1/2})$ in a minimax sense. In particular, our test statistic for the upper bounds is based on a new approximation we derive for the separation distance between general pairwise comparison models and the class of BTL models. To further assess the performance of our statistical test, we prove upper bounds on the type I and type II probabilities of error. Much of our analysis is conducted within the context of a fixed observation graph structure, where the graph possesses certain ``nice'' properties, such as expansion and bounded principal ratio. Additionally, we derive several auxiliary results, such as bounds on principal ratios of graphs, $\ell^2$-bounds on BTL parameter estimation under model mismatch, stability of rankings under the BTL model, etc. We validate our theoretical results through experiments on synthetic and real-world datasets and propose a data-driven permutation testing approach to determine test thresholds.
- Abstract（参考訳）: Bradley-Terry-Luceモデル(BTLモデル、英: Bradley-Terry-Luce model)は、アイテムやエージェントのコレクションをペア比較に基づいてランク付けする最も広く使われているモデルの1つである。
エージェント$n$が与えられた場合、BTLモデルは、各エージェント$i$に遅延スキルスコア$\alpha_i > 0$を付与し、エージェント$i$がエージェント$j$よりも好まれる確率が$\alpha_i/(\alpha_i + \alpha_j)$であることを示す。
本研究の目的は,与えられた一対比較データセットと一対のエージェント毎の$k$の比較が,基礎となるBTLモデルから生じるか否かを決定する仮説テストの定式化である。
我々はこのテスト問題をミニマックスの意味で定式化し、問題の臨界しきい値を定義する。
次に、一般誘導観測グラフの臨界しきい値上の上限(軽微な仮定を満たす)を確立し、完全誘導グラフの下位境界を開発する。
我々の境界は、完全誘導グラフに対して、臨界しきい値がミニマックスの意味で$\Theta((nk)^{-1/2})$としてスケールすることを証明している。
特に、上界のテスト統計は、一般対比較モデルとBTLモデルのクラスとの分離距離を推定する新しい近似に基づく。
統計的検査の結果,I型とII型は誤差の確率に上限があることが判明した。
解析の多くは、グラフが拡張や有界主比といった特定の 'nice'' 特性を持つ固定された観測グラフ構造の文脈内で行われる。
さらに、グラフの主比のバウンダリ、モデルミスマッチによるBTLパラメータ推定における$\ell^2$-bounds、BTLモデルによるランク付けの安定性など、いくつかの補助的な結果を得る。
合成および実世界のデータセットに関する実験を通じて理論的結果を検証し、テストしきい値を決定するためのデータ駆動型置換テスト手法を提案する。
関連論文リスト
- $O(d/T)$ Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions [6.76974373198208]
我々は、最小限の仮定の下で、人気のあるSDEベースのサンプルラーに対して高速収束理論を確立する。
解析の結果, スコア関数の$ell_2$-accurate推定値が与えられた場合, 対象分布と生成分布の総変動距離は$O(d/T)$で上限値となることがわかった。
これは、逆プロセスの各ステップでエラーがどのように伝播するかの詳細な特徴を提供する、新しい分析ツールセットによって達成される。
論文 参考訳（メタデータ） (2024-09-27T17:59:10Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Collaborative non-parametric two-sample testing [55.98760097296213]
目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。
グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。
提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
論文 参考訳（メタデータ） (2024-02-08T14:43:56Z) - Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph $\boldsymbolβ$-Model [4.540236408836132]
複数層からなるハイパーグラフ $boldsymbolbeta$-model について検討した。
最大極大推定値(ML)の収束率を導出し,その最小値の最適性を確立する。
また、ハイパーグラフ $boldsymbolbeta$-model における適合性の問題についても考察する。
論文 参考訳（メタデータ） (2023-07-06T07:23:06Z) - Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative
Models [49.81937966106691]
我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。
従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
論文 参考訳（メタデータ） (2023-06-15T16:30:08Z) - 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) - The Performance of the MLE in the Bradley-Terry-Luce Model in
$\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。
導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
論文 参考訳（メタデータ） (2021-10-20T23:46:35Z) - Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。
テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。
以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
論文 参考訳（メタデータ） (2020-06-22T21:12:31Z) - On the Discrepancy between Density Estimation and Sequence Generation [92.70116082182076]
log-likelihoodは、同じファミリー内のモデルを考えるとき、BLEUと非常に相関している。
異なる家族間でのモデルランキングの相関はみられない。
論文 参考訳（メタデータ） (2020-02-17T20:13:35Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。
統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。
また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
論文 参考訳（メタデータ） (2020-02-05T00:24:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。