文章链接：
https://dl.acm.org/doi/pdf/10.5555/3122009.3242056
01研究背景
排序问题涉及n个项目的集合，以及这些项目的一些未知的潜在总排序。在许多应用程序中，人们可能会观察到不同的项目对之间的噪声比较。例如：比赛中足球队之间的比赛；消费者在市场营销中的偏好评级；以及政治中某些类型的投票系统。
本文研究的重点问题：
给定一组项目之间的噪声比较，找到所有n个项目的真正潜在排序；更一般地，给定正整数k≤n，以找到k个评级最高的项目。
02模型构建
Problem statement
给定一个整数n≥2，我们考虑一个n个项目的集合，由集合[n]索引：[n]= {1，…，n}。对于每一对i≠j，我们令Mij表示项目i在比较中赢得项目j的概率。我们假设每一次比较必然会产生一个赢家，这意味着
对于任何项目i∈[n]，我们定义一个相关分数：
任何项目i∈[n]的分数对应于项目i击败从所有n个项目中任意选择项目的概率。
这个问题的难度取决于前k个项目和其余项目之间的分离程度：
random-design observation model：可以利用该模型生成两两比较的观测值。每一对项目都与随机数量的噪声比较相关联，遵循参数为(r,p)的二项分布，其中r≥1是试验的次数，p∈(0,1]是在任何给定的试验中进行比较的概率。因此，每一对都与一个参数为的二项随机变量相关联，该参数控制着这对项目之间的比较次数。我们假设不同成对的观测序列是独立的。
pairwise comparison models
不同的两两比较的模型揭示了不同的潜在的项目获胜的概率。大部分参数模型，包括特例Bradley - Terry - Luce ( BTL )模型在内，都假设对每个项目i∈[ n ]存在一个质量参数wi∈R，并假定一个项目打败另一个项目的概率是它们质量参数差值的特定函数。在BTL模型中，i打败j的概率Mij由Logistic模型给出
更一般地说，参数模型假设两两比较概率形式
F : R→[0,1]是一些严格递增的累积分布函数，通常假设函数F是已知的。
Borda counting algorithm
对于每个不同的i，j∈[n]和每一个整数l∈[r]，让Y表示对i和j之间的第l次比较的结果，定义为
对于每个i∈[n]，数量Ni对应项目i的获胜次数
成对比较获胜的数量定义了一个k-sized集合
03代码示例
以下为在python中的代码复现
BTL model with violation of separation condition 的结果：
模拟了BTL模型，但选择的参数并没有满足分离条件，可以观察到，计数算法仍然产生了较低的误差，从而证明了其鲁棒性。
百度网盘链接：
https://pan.baidu.com/s/1YF60nvBdLa5k0pS-gN9Sbw?pwd=0712
提取码：0712
识别二维码关注我们
文章推荐人 | 史珑琳
校对 | 王子川
排版 | 史珑琳
