一种基于成对偏好的主动学习排序算法,具有几乎最优的查询复杂度
学习基于有噪声的配对比较的项目顺序,在无法分配具体标签的情况下很有用,尤其是在标注者必须进行主观评估的情况下。本研究在具有上下文属性的有序项目中研究了配对偏好反馈的主动学习,提出了两种算法来贪婪地最小化排序错误,证明了这些算法相对于非上下文排名方法和主动偏好学习基线具有更好的样本效率。
May, 2024
通过使用自适应选择的成对比较来学习排名,我们的目标是准确地恢复排名但节省比较样本。对于使用快速排序算法等有效算法的所有比较结果一致的情况,最优解为使用有效排序算法。我们在 Bradley-Terry 模型下给出了 Quicksort 的优异保证,并通过实证证明了排序算法导致了非常简单有效的积极学习策略。
Feb, 2015
本文针对协作排名问题展开研究,通过基于凸优化的算法和 AltSVM 这种大规模非凸实现方式,实现从用户提供的两两偏好比较结果中预测他们对未曾见过物品的偏好,该算法展现出了在多个协作过滤数据集中 NDCG 和排名性能的许多中等规模基线的表现优势。
Jul, 2015
提出一种称为 Pref-Rank 的算法,它利用结构丰富的图形嵌入来预测排名。通过在坐标点上建立强乘积空间,该算法通过 SVM 方法从结果图嵌入中提取关键信息并在两种排序 Loss 上提供了统计一致性。实验结果表明,此算法优于现有的状态 - of-the-art 方法。
Nov, 2018
本研究旨在通过自适应挑选子集并收集偏好反馈,在 Plackett-Luce 模型下解决 PAC 排名问题,提出了新的 pivot trick 技巧,从而实现了在一定概率下识别 n 个项目的 ε- 最优排名,(m-1)/m 降低的样本复杂度和对称排名算法的阶无法提高的。
Oct, 2018
线性效用函数从成对比较查询中的可学习性研究。具体来说,我们考虑两个学习目标:首先是预测成对比较的样本外响应,其次是近似恢复效用函数的真实参数。我们证明在线性效用在被动学习设置下是高效可学习的,无论查询响应是否受到噪声干扰,并且在分布足够 “好” 的条件下,即使存在 Tsybakov 噪声。相比之下,我们证明对于一大类数据分布而言,在没有强建模假设的情况下,即使查询响应是无噪声的,效用参数也无法被学习。接下来,我们分析主动学习设置下的学习问题。在这种情况下,我们证明即使对于第二个目标,也可以高效学习,并提出了适用于无噪声和有噪声查询响应设置的算法。因此,我们的结果展示了成对偏好查询中被动学习和主动学习之间的质的可学习差距,展示了选择成对查询进行效用学习的价值。
May, 2024
本文提出了一种协同偏好完成问题的高效算法,涉及在基于有限数量的观测关联值的情况下,针对一组实体在共享的项目集上联合估计个性化排名。该算法利用了一个观察结论,即虽然偏好通常被记为数字分数,但感兴趣的预测量实际上是底层排名,因此,直接拟合底层偏好顺序的估计器结合核范数约束来鼓励低秩参数。尽管具有广泛适用性,但该算法对于表示总体或区块总体顺序的监督的计算复杂度与基于核范数规则化估计的矩阵完成标准算法相差不大。此外,本文还提出了一项挑战性应用,即协同排名脑区与认知神经科学术语之间的关联。
Nov, 2016
文中提出了一种基于序列或主动排名的算法,该算法基于嘈杂的成对比较将一组 n 个项目排名并将这些项根据其得分分成预先指定大小的集合;本文针对这种算法进行了分析,证明了在某些情况下具有最优性并且不需要任何假设,比如在参数模型下进行的排名。
Jun, 2016