样本最优的大规模最优子集选择
本文探讨了在存在噪声评估的情况下,选择替代方案子集的问题,并证明在噪声水平足够高时,直观方法提供了最优解。我们扩展了有关选择单一替代方案以及通过强度识别隐藏排名的经典结果。大量实验表明,我们的方法在实际环境中表现良好。
Oct, 2012
在满足强随机可转性和随机三角不等式的概率模型中,本研究考虑了$(\epsilon,\delta)$-PAC最大选择和排名问题。提出了一种基于淘汰赛的选择算法和一般框架来改进排名算法,结合归并排序和二分查找,得到了一个优化性能的排名算法。
May, 2017
该研究引入了PAC Battling-Bandit问题,通过Plackett-Luce子集选择模型在在线学习框架中寻找高置信度的最佳物品,对不同反馈模型下的样本复杂度进行研究,发现利用排名顺序反馈可以从统计效率上提高样本复杂度。
Aug, 2018
本研究旨在通过自适应挑选子集并收集偏好反馈,在Plackett-Luce模型下解决PAC排名问题,提出了新的pivot trick技巧,从而实现了在一定概率下识别n个项目的ε-最优排名,(m-1)/ m降低的样本复杂度和对称排名算法的阶无法提高的。
Oct, 2018
本文研究自适应地从 K 个分布(臂)中抽样,以确定任意两个相邻均值之间的最大差距,即最大间隙赌博机问题。作者提出消除与UCB风格的算法,并证明了它们是极小化的最优解。实验结果表明,UCB风格的算法需要的样本数量比非自适应抽样少6-8倍。
Jun, 2019
本文提出了一个新颖的基于Bayesian优化(top-k ranking BO)的算法,该算法能够处理top-k ranking和tie/indifference observations,具有信息熵的预测搜索功能(MPES)。通过在多个综合基准数据集上的实验评估,MPES的性能优于现有的贪心算法。
Dec, 2020
本文通过研究subset selection问题中的系统性和无意识偏见,探讨了在加入公平性约束条件下如何提高选择结果的质量,发现这与使用multiwinner得分函数的方式有很大关系,有些函数只需要少量排名即可达到近似最佳解,而对于其他函数却需要大量排名进行修正,并提供了工具进行实证验证。
Jun, 2023
介绍了AlphaRank,一种用于解决固定预算排名和选择问题的人工智能方法。使用蒙特卡罗模拟的策略为顺序采样决策建立马尔可夫决策过程,并利用经典的排名和选择程序作为基本策略来高效学习随机动态规划的价值函数。通过使用深度强化学习在给定先验的情况下对神经网络模型进行离线预训练来加速在线样本分配。还提出了一个可并行计算的框架来处理大规模问题,通过“分而治之”和“递归”相结合,提高了可扩展性和效率。数值实验证明了AlphaRank相比基本策略的显著改进,这可能归因于AlphaRank在平均值、方差和相关性权衡上的卓越能力,而这些特性通常被其他现有策略所忽略。
Feb, 2024
本研究解决了机器学习模型训练数据对模型行为的影响归因问题,特别是无法捕捉样本集的复杂影响。提出了最具影响力子集选择(MISS)问题,并分析了现有方法的优缺点,发现影响基贪婪启发式算法在某些情况下的不足之处。实验证明了一种自适应算法能够有效捕捉样本间的相互作用,从而在复杂场景中提升性能。
Sep, 2024