AAAINov, 2018

我们需要多少两两比较偏好才能一致地排名图表？

PDF
TL;DR提出一种称为 Pref-Rank 的算法，它利用结构丰富的图形嵌入来预测排名。通过在坐标点上建立强乘积空间，该算法通过 SVM 方法从结果图嵌入中提取关键信息并在两种排序 Loss 上提供了统计一致性。实验结果表明，此算法优于现有的状态 - of-the-art 方法。
rankinggraph embeddingsvmkendall's tauspearman's footrule
发现论文，激发创造
  • 一种基于成对偏好的主动学习排序算法，具有几乎最优的查询复杂度

    本文解决了学习如何从成对偏好中排名的问题，并提出一种主动学习算法来优化线性排序的查询复杂度，同时尽可能地减少成对偏好标签的不一致性。

    Oct, 2010

  • 基于部分排序的偏好值补全

    本文提出了一种协同偏好完成问题的高效算法，涉及在基于有限数量的观测关联值的情况下，针对一组实体在共享的项目集上联合估计个性化排名。该算法利用了一个观察结论，即虽然偏好通常被记为数字分数，但感兴趣的预测量实际上是底层排名，因此，直接拟合底层偏好顺序的估计器结合核范数约束来鼓励低秩参数。尽管具有广泛适用性，但该算法对于表示总体或区块总体顺序的监督的计算复杂度与基于核范数规则化估计的矩阵完成标准算法相差不大。此外，本文还提出了一项挑战性应用，即协同排名脑区与认知神经科学术语之间的关联。

    Nov, 2016

  • 使用成对比较的主动排名

    使用少于 $n log_2 n$ 次的自适应选择的成对比较，该算法可特征一系列对象的排序，前提条件是该对象在 $d$ 维欧几里得空间中，其排名反映了相对于 $R^d$ 中的公共参考点的相对距离。

    Sep, 2011

  • 基于成对比较的大规模协作排名偏好数据填充

    本文针对协作排名问题展开研究，通过基于凸优化的算法和 AltSVM 这种大规模非凸实现方式，实现从用户提供的两两偏好比较结果中预测他们对未曾见过物品的偏好，该算法展现出了在多个协作过滤数据集中 NDCG 和排名性能的许多中等规模基线的表现优势。

    Jul, 2015

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

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

    Sep, 2023

  • 特征排序：算法和图论分析

    本文提出了一种新的概率偏好模型 f-BTL，它能更精确地推断带有特征的物品的偏好，在此基础上提出了一个新的最小二乘算法 fBTL-LS，其采样复杂度较低，依赖于物品的特征表述。这项工作展示了排名问题真正的复杂性，并证明了恢复潜在排名所需的样本复杂度的信息论下界。在合成和现实数据上进行了实验验证。

    Aug, 2018

  • 简单、健壮且最优排名的配对比较

    本研究旨在通过成对比较的数据形式，使用 Copeland 计数算法实现对 n 个项目的排序，使其具有计算效率高，鲁棒性强，接近信息论极限等特点，并将结果扩展到汉明距离度量下的近似恢复问题和任意错误要求条件下的恢复问题。

    Dec, 2015

  • 具有子集评价偏好的主动排名

    本研究旨在通过自适应挑选子集并收集偏好反馈，在 Plackett-Luce 模型下解决 PAC 排名问题，提出了新的 pivot trick 技巧，从而实现了在一定概率下识别 n 个项目的 ε- 最优排名，（m-1）/m 降低的样本复杂度和对称排名算法的阶无法提高的。

    Oct, 2018

  • GNNRank：通过有向图神经网络从成对比较中学习全局排名

    本研究利用神经网络提出了一个名为 GNNRank 的训练框架，用于从成对比较中恢复全局排名，该框架涉及一种排名得分估计方法以及一种形成可学习相似矩阵的图形构建方法，实验结果表明该方法能够获得优秀的性能和有希望的转移能力。

    Feb, 2022

  • 基于配对比较的近似排名

    研究在机器学习中，基于两两比较对一组 n 个项目进行排名的问题，提出了一种基于置信区间的活跃排名算法，通过近似排序来减少比较次数。

    Jan, 2018