学习增强优先级队列
基于预测模型的最优调度决策在服务系统中的关键是理解预测误差对其他作业的延迟产生的外部性对拥塞的影响。我们在应用中考虑了预测模型与人类服务器交互的情况(例如内容审查),设计了一个基于指标的策略,以近乎最优的方式结合了预测的类别信息,通过对重负载下拥塞成本的特征化来指导预测模型的设计,并针对基于人工智能的任务划分设计了一种新颖的排队系统。我们以实际在线评论为基础,通过微调大型语言模型构建鉴别有毒性的分类器,展示了我们的框架。
Jun, 2024
介绍了一种算法设计范例 —— 基于学习预测器的算法,将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度,在构建优美的预测器的同时,在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果,且提供了第一批基于学习理论的担保。
Feb, 2022
利用机器学习模型从过去和现在的数据中获得的预测,近期算法设计的先进方法已经显示出提高性能的潜力,并在预测失败时提供最坏情况保证,本文研究在线问题,着重于将学习问题与算法挑战相互整合,并设计了专为所需算法任务而量身定制的在线学习算法,通过细致设计的明确学习算法提出了优化总体性能的新算法,并证明了我们方法的潜力通过改进以前研究中建立的性能界限。
Mar, 2024
通过将机器学习建议整合到跳跃表的设计中,我们改进了传统数据结构设计,并构建了一种能够在几乎两倍内提供最优预期搜索时间的学习增强型跳跃表,即使预估的搜索查询存在误差,该方法依然能够是唯一最优的,而且如果搜索查询符合普遍存在的齐夫分布,那么我们的跳跃表的预期搜索时间只是常数,与项的总数量无关,而传统跳跃表的预期搜索时间则是对数时间。同时,通过实证研究,我们证明了我们的数据结构在合成和真实数据集上均优于传统跳跃表。
Feb, 2024
该论文研究了在不确定性条件下,利用学习增强算法处理排序和超图方向问题,并提出了针对准确和错误预测的性能保证算法,可以通过查询提高不确定性元素的精确度,从而最小化问题求解所需的查询数量。
May, 2023
本论文研究了将预测融入 online list labeling 问题中,提出了一种新的数据结构并给出了 worst-case 和 stochastic error 两种模型的保证,以预测误差作为保证的上界,同时在实验中展示了该数据结构在实际应用中的表现。
May, 2023
从人类反馈中学习偏好模型一直是人工智能领域最近进展的核心。本研究通过推广最优设计的概念,研究了用于学习偏好模型的数据收集问题,并提出了面向排名列表的有效算法,证明了模型估计器随更多数据而改善,估计器下的排名误差也随之减少,并在多个合成和真实数据集上进行实验以展示算法的统计效率。
Apr, 2024
通过学习增强算法的角度探索排序问题,其中算法利用可能存在错误的预测来提高效率。我们考虑了两种不同的情境:在第一种情境中,为每个项目提供了其在已排序列表中的位置预测;在第二种情境中,我们假设存在一种 “快速但不精确” 的方法来比较项目,除此之外还有慢而准确的比较。对于这两种情境,我们设计了新的简单算法,仅使用 O (Σi log ηi) 个精确比较,其中 ηi 是第 i 个元素的适当定义的预测误差。特别是,随着预测质量的下降,比较次数从 O (n) 平滑地降低到 O (nlogn)。我们证明在所考虑的误差度量方面,比较复杂度在理论上是最优的。与现有的自适应和非自适应排序算法进行的实验评估表明了在排序任务中应用学习增强算法的潜力。
Nov, 2023