Mar, 2020

具有不受信任预测的在线度量算法

PDF
TL;DR本文提出了适用于任意度量任务系统（MTS）（例如缓存、k-server 和凸体追逐）和在线匹配的预测模型，并利用在线算法理论的结果来展示如何使模型更具鲁棒性，其中特别针对缓存问题，本文提出的算法相对于一般 MTS 问题可使得其性能的预测误差表现成指数级别提升。最后，我们使用实际数据集对所提出的方法进行了实证评估，并得出实用性较好的结论。
machine learningprediction setuponline matchingcachingonline algorithms
发现论文，激发创造
  • 在线度量算法的混合预测

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

    Apr, 2023

  • 在线图算法预测

    本文研究具有预测的在线图形问题，提出了一个新的度量误差的定义 (metric error)，并给出了一个通用框架，用于在线预测算法。采用这个框架，我们能够获得关于竞争比率的紧密限制，并将其作为度量误差的函数来描述。

    Dec, 2021

  • 减少预测数量的缓存和 MTS 算法

    使用预测的 ML 增强算法对缓存和 MTS 进行研究，提出了具有一致性和平滑性参数的节俭算法，能够在预测准确性下提高性能。

    Apr, 2024

  • 带有预测的算法学习

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

    Feb, 2022

  • 多预测在线算法

    本文研究了在多个机器学习预测的基础上增强的在线算法。我们提出了一个通用的算法框架，用于多重预测的在线覆盖问题，该算法能够获得与最佳预测器性能相竞争的在线解决方案。该算法还能够同时使竞争性达到最佳预测和最佳在线算法的性能水平，并应用于解决一些经典问题。

    May, 2022

  • 具有不确定性量化预测的在线算法

    如何在设计在线算法中最佳利用不确定性量化预测，以及如何利用更一般形式的不确定性量化，提出了基于在线学习的框架来在多实例场景中学习如何充分利用不确定性量化作出最佳决策。

    Oct, 2023

  • 学习增强在线算法的最优韧性 - 一致性平衡

    研究如何将机器学习预测融入在线算法以提高性能，并提供非平凡的下界来衡量竞争分析的最优权衡.

    Oct, 2020

  • 在线算法的机器学习预测定制化

    本研究探讨在机器学习算法中加入优化基准以提高在线算法的预测性能，以租赁或购买问题为例，并通过理论边界和数值模拟能够支持此发现。

    May, 2022

  • 基于机器学习建议的秘书问题和在线匹配问题

    通过机器学习算法，结合在线算法，可以提高选择问题中的服务质量，并且能够在预测准确的情况下最大化竞争力。

    Jun, 2020

  • 多专家在线覆盖

    设计在线算法，利用机器学习预测，以超越最坏情况范例，解决各种实际相关在线问题（如调度、缓存、聚类、滑雪租赁等）。通过研究设计具备多个专家的在线算法，以超越静态最佳专家的贪心基准。在新的动态基准中提出了具有 O（log K）性能保证的竞争算法，其中 K 是专家数量，适用于 0-1 在线优化问题。此外，我们的多专家方法提供了一种在线组合多个在线算法的新视角，这是在线算法研究社区长期的核心主题。

    Dec, 2023