Nov, 2023

基于预测的排序

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

    该论文研究了在不确定性条件下，利用学习增强算法处理排序和超图方向问题，并提出了针对准确和错误预测的性能保证算法，可以通过查询提高不确定性元素的精确度，从而最小化问题求解所需的查询数量。

    May, 2023

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

    通过使用自适应选择的成对比较来学习排名，我们的目标是准确地恢复排名但节省比较样本。对于使用快速排序算法等有效算法的所有比较结果一致的情况，最优解为使用有效排序算法。我们在 Bradley-Terry 模型下给出了 Quicksort 的优异保证，并通过实证证明了排序算法导致了非常简单有效的积极学习策略。

    Feb, 2015

  • 带有预测的在线列表标记

    本论文研究了将预测融入 online list labeling 问题中，提出了一种新的数据结构并给出了 worst-case 和 stochastic error 两种模型的保证，以预测误差作为保证的上界，同时在实验中展示了该数据结构在实际应用中的表现。

    May, 2023

  • 机器学习建议在线缓存的近最优界限

    该论文研究了基于机器学习建议的在线缓存模型，提出了一种新的算法来解决缓存问题，该算法适用于低误差情况下的预测，具有低的竞争比率；通过改进算法和提供下限，有望进一步提高算法性能。

    Oct, 2019

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

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

    Jan, 2018

  • 带有预测的算法学习

    介绍了一种算法设计范例 —— 基于学习预测器的算法，将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度，在构建优美的预测器的同时，在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果，且提供了第一批基于学习理论的担保。

    Feb, 2022

  • 学习增强跳表

    通过将机器学习建议整合到跳跃表的设计中，我们改进了传统数据结构设计，并构建了一种能够在几乎两倍内提供最优预期搜索时间的学习增强型跳跃表，即使预估的搜索查询存在误差，该方法依然能够是唯一最优的，而且如果搜索查询符合普遍存在的齐夫分布，那么我们的跳跃表的预期搜索时间只是常数，与项的总数量无关，而传统跳跃表的预期搜索时间则是对数时间。同时，通过实证研究，我们证明了我们的数据结构在合成和真实数据集上均优于传统跳跃表。

    Feb, 2024

  • 在线度量算法的混合预测

    本文阐述了一种基于多种算法或预测器的学习增强在线算法技术，通过针对在线问题的分析，设计出与动态组合相竞争的算法，能够在多种预测器之间切换，具有灵活性和实用性。

    Apr, 2023

  • 在线优化：与动态比较器竞争

    本文提出了一种完全自适应的方法，适用于在线学习中的动态比较基准，并且应用到了零和博弈中。

    Jan, 2015

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

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

    Sep, 2011