Aug, 2018

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

PDF
TL;DR本文提出了一种新的概率偏好模型 f-BTL，它能更精确地推断带有特征的物品的偏好，在此基础上提出了一个新的最小二乘算法 fBTL-LS，其采样复杂度较低，依赖于物品的特征表述。这项工作展示了排名问题真正的复杂性，并证明了恢复潜在排名所需的样本复杂度的信息论下界。在合成和现实数据上进行了实验验证。
pairwise comparisonsf-btl modelleast squares algorithmsample complexity bounditem dependencies
发现论文，激发创造
  • 归纳式成对排名：突破 nlog (n) 的限制

    该研究提出了路面低秩（FLR）模型，通过矩阵完成技术和的 FLR 模型中的侧面信息开发 归纳成对排名（IPR）算法，在 FLR 模型下有证据表明它以样本高效的方式学习用于排名的 FLR 模型。

    Feb, 2017

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

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

    Apr, 2023

  • 私人成对排名的速率最优等级聚合

    采用随机响应机制来保护原始的成对排序，确保在下游排序聚合中对真实偏好和排序进行一致估计，并建立了隐私保护的最优保证与估计误差之间的最小最大速率。

    Feb, 2024

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

    提出一种称为 Pref-Rank 的算法，它利用结构丰富的图形嵌入来预测排名。通过在坐标点上建立强乘积空间，该算法通过 SVM 方法从结果图嵌入中提取关键信息并在两种排序 Loss 上提供了统计一致性。实验结果表明，此算法优于现有的状态 - of-the-art 方法。

    Nov, 2018

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

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

    Dec, 2015

  • 基于成对比较的排名中心度

    本文提出了一种迭代的排名聚合算法 ——Rank Centrality，该算法基于随机游走解释，用于发现从成对比较中学习出的对象分数。该算法的有效性以 Bradley-Terry-Luce（BTL）模型为例，并通过边界收敛速度分析方法估计出了对 BTL 模型假定分数与算法估计分数之间的有限样本误差率。

    Sep, 2012

  • 具有上下文依赖显著特征的偏好建模

    该论文研究了如何通过具有噪声的成对比较数据和项特征来估计排名，提出了凸显特征偏好模型，并使用最大似然估计学习模型参数和排名，实验证明了该模型表现强大，解释了系统性不对称性。

    Feb, 2020

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

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

    Jul, 2015

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

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

    Oct, 2018

  • 基于成对比较的估计：具有拓扑相关性的尖锐极小极值界限

    本文考虑使用参数有序模型处理成对比较数据，给出在该模型下最优误差的紧密上下界以及选择两两比较的指导方针，同时与基于基数的测量模型进行比较，结果表明在有序和基数设置下误差率具有相同的比例尺。

    May, 2015