带有预测的在线列表标记
通过学习增强算法的角度探索排序问题,其中算法利用可能存在错误的预测来提高效率。我们考虑了两种不同的情境:在第一种情境中,为每个项目提供了其在已排序列表中的位置预测;在第二种情境中,我们假设存在一种 “快速但不精确” 的方法来比较项目,除此之外还有慢而准确的比较。对于这两种情境,我们设计了新的简单算法,仅使用 O (Σi log ηi) 个精确比较,其中 ηi 是第 i 个元素的适当定义的预测误差。特别是,随着预测质量的下降,比较次数从 O (n) 平滑地降低到 O (nlogn)。我们证明在所考虑的误差度量方面,比较复杂度在理论上是最优的。与现有的自适应和非自适应排序算法进行的实验评估表明了在排序任务中应用学习增强算法的潜力。
Nov, 2023
在线分类研究中,研究者利用对未来示例的预测来改进在线学习算法,以减小期望遗憾并提高分类准确性。该研究还证明了当未来示例可准确预测时,在线学习可以与转导式在线学习相媲美,从而对近期基于预测和分布假设的在线算法的研究提供了补充。
May, 2024
介绍了一种算法设计范例 —— 基于学习预测器的算法,将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度,在构建优美的预测器的同时,在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果,且提供了第一批基于学习理论的担保。
Feb, 2022
该论文研究了基于机器学习建议的在线缓存模型,提出了一种新的算法来解决缓存问题,该算法适用于低误差情况下的预测,具有低的竞争比率;通过改进算法和提供下限,有望进一步提高算法性能。
Oct, 2019
在线学习环境下的结构化预测问题的理论和算法性框架的研究。通过研究,我们发现我们的算法能够推广到监督学习环境中的优化算法,并且在数据非独立同分布的情况下也能达到相同的风险上界。此外,我们还考虑了一种特别设计用于非平稳数据分布(包括对抗性数据)的第二个算法,并以数据分布的变化为函数界限其随机遗憾。
Jun, 2024
如何在设计在线算法中最佳利用不确定性量化预测,以及如何利用更一般形式的不确定性量化,提出了基于在线学习的框架来在多实例场景中学习如何充分利用不确定性量化作出最佳决策。
Oct, 2023
本文研究了在多个机器学习预测的基础上增强的在线算法。我们提出了一个通用的算法框架,用于多重预测的在线覆盖问题,该算法能够获得与最佳预测器性能相竞争的在线解决方案。该算法还能够同时使竞争性达到最佳预测和最佳在线算法的性能水平,并应用于解决一些经典问题。
May, 2022
研究主动标注流数据的问题,提出了一种基于确定性阈值和时间成本依赖性阈值的算法,并考虑了数据输入属于离散或连续域的情况,得到了上限约束模型。通过模拟实验,并在医学和天文学领域进行实际测试,证明了该算法在实验结果上的优势。
Apr, 2023
在线分类中,学习器根据一系列示例来预测其标签,以在线方式最小化错误总数;在自主学习变体中,学习器事先了解示例池,并可以自适应地选择预测顺序。本文研究了预测顺序选择的能力,并在线性分类的基本任务中首次建立了最差顺序学习和随机顺序学习之间的强分离。
Aug, 2023