Bradley–Terry–Luce模型的极小极大假设检验

《IEEE Transactions on Information Theory》：Minimax Hypothesis Testing for the Bradley–Terry–Luce Model

本文提出针对BTL模型的假设检验方法，通过定义临界阈值并分析其与观测图结构（主比例、边扩展）的关系，推导出一般观测图的上界和完全诱导图的下界，验证了理论结果。

　　

摘要：

Bradley-Terry-Luce（BTL）模型是一种广泛用于根据物品或代理之间的成对比较对它们进行排序的模型。具体来说，给定n个代理，BTL模型为每个代理i赋予一个潜在的技能分数α_i，并假设在比较中代理i被优先于代理j的概率为α_i/j。在这项工作中，我们的目标是构建一个假设检验，以确定给定的成对比较数据集（每对代理有k次比较）是否源自一个底层的BTL模型。我们从极小极大（minimax）的角度对这个问题进行了形式化，并定义了问题的临界阈值。然后，我们为一般的观察图建立了临界阈值的上界，并强调了这些上界依赖于两个基本的结构属性：主比例（principal ratio）和边扩展（edge expansion）。此外，我们还为完全诱导图（complete induced graphs）的特殊情况推导出了临界阈值的下界，从而证明了在这种情况下临界阈值与Θ = (n/k ? 1)/2成比例。特别是，我们用于确定上界的检验统计量基于我们对一般成对比较模型与BTL模型类别之间分离距离的新近似方法。为了进一步评估我们统计检验的性能，我们证明了错误条件概率的上界。此外，在分析过程中我们还得出了其他几个辅助结果，例如图的主比例界限、模型不匹配情况下BTL参数估计的界限、BTL模型下小模型不匹配情况下排名的稳定性等。最后，我们在合成数据和真实世界数据集上进行了几项实验来验证我们的一些理论结果。此外，我们还提出了一种基于排列检验的方法，以数据驱动的方式确定我们检验的阈值...

显示更多

引言

近年来，成对比较数据的可用性及其后续分析在各个领域显著增加。成对比较数据包括在给定的一组物品或代理之间进行的比较信息。许多现实世界的应用，包括体育比赛、消费者偏好调查和政治投票，都会生成成对比较形式的数据。这类数据集有多种用途，例如对物品进行排序[1]、[2]、[3]、[4]、[5]、[6]、[7]、[8]、[9]、[10]、[11]、分析团队随时间的表现[12]、研究市场或体育竞争力[13]、[14]，甚至使用来自人类反馈的强化学习来微调大型语言模型[15]、[16]。