ICMLFeb, 2015

简单有效的主动偏好学习方法：只需排序！

PDF
TL;DR通过使用自适应选择的成对比较来学习排名，我们的目标是准确地恢复排名但节省比较样本。对于使用快速排序算法等有效算法的所有比较结果一致的情况，最优解为使用有效排序算法。我们在 Bradley-Terry 模型下给出了 Quicksort 的优异保证，并通过实证证明了排序算法导致了非常简单有效的积极学习策略。
rankingpairwise comparisonssorting algorithmactive learning strategybradley-terry model
发现论文，激发创造
  • 主动偏好学习用于样本内外排序项目

    学习基于有噪声的配对比较的项目顺序，在无法分配具体标签的情况下很有用，尤其是在标注者必须进行主观评估的情况下。本研究在具有上下文属性的有序项目中研究了配对偏好反馈的主动学习，提出了两种算法来贪婪地最小化排序错误，证明了这些算法相对于非上下文排名方法和主动偏好学习基线具有更好的样本效率。

    May, 2024

  • 一种基于成对偏好的主动学习排序算法，具有几乎最优的查询复杂度

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

    Oct, 2010

  • 来自配对比较的主动排序及其在参数假设无法提供帮助时的应用

    文中提出了一种基于序列或主动排名的算法，该算法基于嘈杂的成对比较将一组 n 个项目排名并将这些项根据其得分分成预先指定大小的集合；本文针对这种算法进行了分析，证明了在某些情况下具有最优性并且不需要任何假设，比如在参数模型下进行的排名。

    Jun, 2016

  • 基于预测的排序

    通过学习增强算法的角度探索排序问题，其中算法利用可能存在错误的预测来提高效率。我们考虑了两种不同的情境：在第一种情境中，为每个项目提供了其在已排序列表中的位置预测；在第二种情境中，我们假设存在一种 “快速但不精确” 的方法来比较项目，除此之外还有慢而准确的比较。对于这两种情境，我们设计了新的简单算法，仅使用 O (Σi log ηi) 个精确比较，其中 ηi 是第 i 个元素的适当定义的预测误差。特别是，随着预测质量的下降，比较次数从 O (n) 平滑地降低到 O (nlogn)。我们证明在所考虑的误差度量方面，比较复杂度在理论上是最优的。与现有的自适应和非自适应排序算法进行的实验评估表明了在排序任务中应用学习增强算法的潜力。

    Nov, 2023

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

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

    Jan, 2018

  • SortNet: 通过基于神经网络的排序算法学习排序

    透过使用神经网络作为比较器的排序算法 SortNet，在 LETOR 数据集上展现出与其他先进算法相比具有潜力的性能。

    Nov, 2023

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

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

    Dec, 2015

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

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

    Sep, 2011

  • 应用于大学排名的揭示偏好数据排序

    本文基于内生权重的方法，在考虑对象和消费者的多样性和异质性的基础上对美国大学的排名进行排序，并提出了提高其相对位置的策略，为消费者和政府制定明智的政策决策提供帮助。该方法可以应用于运动队排名、学术期刊排名、选举和实际有效汇率等许多其他领域。

    Mar, 2020

  • 停止依赖无选择，不要重复移动：商品组合优化的最优、高效和实用算法

    我们设计了一种基于 Plackett Luce 的用户选择的快速算法，用于解决主动在线组合优化问题中的后悔最小化问题，并证明了该方法在实践中是有效的、最优的，并且没有现有方法的限制。

    Feb, 2024