基于一般多方比较的谱排序推理

Aug, 2023

Spectral Ranking Inferences based on General Multiway Comparisons

Jianqing Fan, Zhipeng Lou, Weichen Wang, Mengxin Yu

TL;DR该论文研究了在一般和更实际的设置中使用光谱方法估计和不确定性量化未观察到的被比较实体的偏好分数的性能，其中比较图包含可能具有异构大小的超边，并且对于给定超边，比较的数量可以低至一次。此外，在适用 BTL 或 PL 模型的情况下，我们揭示了光谱估计量与最大似然估计量之间的关系。我们发现，使用从等权重光谱方法估计的最优加权的两步光谱方法可以达到与 MLE 相同的渐近效率。鉴于估计的偏好分数的渐近分布，我们还介绍了一个全面的框架，可以在固定和随机图设置中进行一样本和两样本排名推断。值得注意的是，这是首次提出有效的双样本排名测试方法。最后，我们通过全面的数值模拟验证了我们的发现，然后应用我们开发的方法对统计学期刊和电影排名进行统计推断。

Abstract

This paper studies the performance of the spectral method in the estimation and uncertainty quantification of the unobserved preference scores of compared entities in a very general and more realistic setup in wh

spectral method uncertainty quantification hyper-edges maximum likelihood estimator two-sample rank testing

发现论文，激发创造

基于谱最大似然估计的 Top-K 等级聚合方法，来自于成对比较

本文探讨了基于偏好的 top-K 排名聚合问题，并使用 Bradley-Terry-Luce 模型来表征隐含的偏好分数，提出了一种名为 Spectral MLE 的几乎线性时间排名方案，并揭示了可靠排名所需的最小采样复杂度和分离测度之间的关系。

Apr, 2015

谱方法和正则化极大似然估计在 Top-K 排序中都是最优的

本文介绍一种基于 Bradley-Terry-Luce 模型的方法，使用 pairwise comparisons 进行 top-K ranking，证明 spectral method alone 和 regularized MLE alone 在特定 dynamic range 内的样本复杂度最小，并通过数值实验验证了它们的低误差。

Jul, 2017

普通图和局部图的成对比较排名

本文关注 Bradley-Terry-Luce 模型中的成对比较问题，并通过对图论的分析，提出了能够在有限条件下对排名进行准确估计的算法，并在大规模实验中证实了该算法的可行性。

Apr, 2023

与递增对手的前 K 名排名

本文研究了具有单调对手的前 K 名排名问题，在随机生成的比较图的基础上，统计学家的目标是根据半随机比较图中的成对比较，准确地确定前 K 名的首选项目。主要贡献是开发了一种加权的最大似然估计器，它在样本复杂度方面实现了接近最优的性能，最多有对数因子 (log^2 (n))，其中 n 是比较的项目数量。通过分析和算法创新的组合实现了这一目标。

Feb, 2024

通过谱方法改进的排名聚合的理论保证

给定多个项目之间的成对比较，如何对它们进行排名，以使得排名与观察结果相匹配？本研究关注基于 Erdos-Renyi 异常值（ERO）模型的排名问题，在该问题中，每个成对比较都是真实分数差异的损坏副本。通过研究基于非归一化和归一化数据矩阵的谱排名算法，我们提供了每个项目从观察数据中恢复出其潜在分数的性能，并得出了非归一化 / 归一化数据矩阵的最大特征向量与其总体对应物之间的逐项扰动误差界限。通过留一法技术，我们提供了更精确的最大特征向量的 l∞范数扰动界限，并在只有 Ω(nlogn) 个样本的情况下导出了每个项目的最大偏移误差界限。理论分析在样本复杂度方面改进了现有技术的结果，并通过数值实验验证了这些理论发现。

Sep, 2023

在没有标签数据的情况下对多个预测器进行排名和组合

本文介绍了一种基于谱方法的元学习器，可以在只有多个分类器的推荐或预测的情况下，可靠地排名它们，并构建一个比大多数组合中的分类器更准确的元分类器。该方法假设分类器之间具有条件独立性，并通过计算其协方差矩阵和特征向量进行排名，并进一步引入谱元学习器作为组合加权分类器。该方法在模拟和真实数据上达到了比大多数分类器更高的准确性。

Mar, 2013

频谱增强的成对学习排序

通过使用超图结构的波谱特征来模拟用户的偏好和商品的特性，并将其结合到矩阵分解模型中来增强推荐系统的性能，并且使用波谱特征来优化贝叶斯个性化排序，以丰富用于无显示反馈数据中的正样本。

May, 2019

部分排名下的极小最优推断

本研究研究基于部分排名来推测全局偏好的问题，重点关注如何最优地为排名分配物品及数量，以达到目标估计误差，并提出了一种随机分配方案，实验证实了理论发现。

Jun, 2014

随机块模型的渐近有效估计器：朴素最大似然估计、带秩约束的最大似然估计和谱估计

使用谱嵌入来估计随机块模型图中的块概率矩阵 B，在平均度数以 n 的 Ω(√n) 的速率增长时，我们建立了渐进正常性结果；当 B 是全秩的时，从谱嵌入得到的 B 的估计是渐近有效的；当 B 是奇异的时，从谱嵌入得到的估计可以比在没有排名假设的情况下最大化对数似然获得的估计具有更小的均方误差，并且可以几乎像假定已知 rk (B) 的真实 MLE 一样有效。

Oct, 2017

利用序列法进行频谱排名

本文提出了一种用于排序一系列物品的序列算法，将基于成对比较构建相似性矩阵后使用序列方法进行排序。在排名恢复和噪声处理方面，它比传统评分方法更具鲁棒性，并且还可以解决半监督排名问题。使用该算法进行排名的表现竞争性更好。

Jun, 2014