提出检验数据是否符合BTL排名模型的极小极大方法,可判断排名数据真伪。
Minimax Hypothesis Testing for the Bradley-Terry-Luce Model
- 基于配对比较数据构造新统计量,通过分离距离逼近检验模型
- 证明完全图下临界阈值为 Θ((nk)^{-1/2}),误差率可控
- 适用于有结构的观测图,适合验证排名数据可信度的研究者
Bradley-Terry-Luce(BTL)模型是基于成对比较进行项目或参与者排名的常用模型。给定 n 个参与者,该模型为每个参与者 i 赋予一个隐含技能分数 α_i > 0,认为参与者 i 比 j 更受青睐的概率为 α_i/(α_i + α_j)。本文目标是构建一种假设检验方法,判断一组成对比较数据(每对间有 k 次比较)是否来自真实的 BTL 模型。我们在极小极大框架下形式化该问题,并定义其临界阈值。针对满足弱假设的一般诱导图,建立了上界;针对完全图,给出了下界。结果表明,在完全图情形下,临界阈值在极小极大意义下为 Θ((nk)^{-1/2})。上界所用的检验统计量基于我们推导的通用成对比较模型与 BTL 模型之间分离距离的新近似。此外,我们还证明了第一类与第二类错误概率的上界。分析在固定观测图结构下进行,该图具有扩张性、主比有界等良好性质。同时推导若干辅助结果,包括图的主比界、模型误设下的 BTL 参数 ℓ^2 估计界、以及排名稳定性等。通过合成与真实数据集实验验证理论结果,并提出一种数据驱动的置换检验方法以确定测试阈值。
原文摘要 · Abstract (English)
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 $α_i > 0$ and posits that the probability that agent $i$ is preferred over agent $j$ is $α_i/(α_i + α_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 $Θ((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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。