简单、健壮且最优排名的配对比较
文中提出了一种基于序列或主动排名的算法,该算法基于嘈杂的成对比较将一组 n 个项目排名并将这些项根据其得分分成预先指定大小的集合;本文针对这种算法进行了分析,证明了在某些情况下具有最优性并且不需要任何假设,比如在参数模型下进行的排名。
Jun, 2016
使用少于 $n log_2 n$ 次的自适应选择的成对比较,该算法可特征一系列对象的排序,前提条件是该对象在 $d$ 维欧几里得空间中,其排名反映了相对于 $R^d$ 中的公共参考点的相对距离。
Sep, 2011
本文关注 Bradley-Terry-Luce 模型中的成对比较问题,并通过对图论的分析,提出了能够在有限条件下对排名进行准确估计的算法,并在大规模实验中证实了该算法的可行性。
Apr, 2023
本文考虑使用参数有序模型处理成对比较数据,给出在该模型下最优误差的紧密上下界以及选择两两比较的指导方针,同时与基于基数的测量模型进行比较,结果表明在有序和基数设置下误差率具有相同的比例尺。
May, 2015
本文提出了一种新的概率偏好模型 f-BTL,它能更精确地推断带有特征的物品的偏好,在此基础上提出了一个新的最小二乘算法 fBTL-LS,其采样复杂度较低,依赖于物品的特征表述。这项工作展示了排名问题真正的复杂性,并证明了恢复潜在排名所需的样本复杂度的信息论下界。在合成和现实数据上进行了实验验证。
Aug, 2018
给定多个项目之间的成对比较,如何对它们进行排名,以使得排名与观察结果相匹配?本研究关注基于 Erdos-Renyi 异常值(ERO)模型的排名问题,在该问题中,每个成对比较都是真实分数差异的损坏副本。通过研究基于非归一化和归一化数据矩阵的谱排名算法,我们提供了每个项目从观察数据中恢复出其潜在分数的性能,并得出了非归一化 / 归一化数据矩阵的最大特征向量与其总体对应物之间的逐项扰动误差界限。通过留一法技术,我们提供了更精确的最大特征向量的 l∞范数扰动界限,并在只有 Ω(nlogn) 个样本的情况下导出了每个项目的最大偏移误差界限。理论分析在样本复杂度方面改进了现有技术的结果,并通过数值实验验证了这些理论发现。
Sep, 2023
本文提出了一种迭代的排名聚合算法 ——Rank Centrality,该算法基于随机游走解释,用于发现从成对比较中学习出的对象分数。该算法的有效性以 Bradley-Terry-Luce(BTL)模型为例,并通过边界收敛速度分析方法估计出了对 BTL 模型假定分数与算法估计分数之间的有限样本误差率。
Sep, 2012
提出一种称为 Pref-Rank 的算法,它利用结构丰富的图形嵌入来预测排名。通过在坐标点上建立强乘积空间,该算法通过 SVM 方法从结果图嵌入中提取关键信息并在两种排序 Loss 上提供了统计一致性。实验结果表明,此算法优于现有的状态 - of-the-art 方法。
Nov, 2018