具有子集评价偏好的主动排名
通过使用自适应选择的成对比较来学习排名,我们的目标是准确地恢复排名但节省比较样本。对于使用快速排序算法等有效算法的所有比较结果一致的情况,最优解为使用有效排序算法。我们在Bradley-Terry模型下给出了Quicksort的优异保证,并通过实证证明了排序算法导致了非常简单有效的积极学习策略。
Feb, 2015
文中提出了一种基于序列或主动排名的算法,该算法基于嘈杂的成对比较将一组n个项目排名并将这些项根据其得分分成预先指定大小的集合;本文针对这种算法进行了分析,证明了在某些情况下具有最优性并且不需要任何假设,比如在参数模型下进行的排名。
Jun, 2016
在满足强随机可转性和随机三角不等式的概率模型中,本研究考虑了$(\epsilon,\delta)$-PAC最大选择和排名问题。提出了一种基于淘汰赛的选择算法和一般框架来改进排名算法,结合归并排序和二分查找,得到了一个优化性能的排名算法。
May, 2017
本文研究了使用多项式逻辑模型下的$l(l≥2$)$-wise$ ($l≥2$)比较的积极PAC top-k排名(即top-k项目选择)和总排名问题,通过自适应地选择查询组并观察每个查询的最受欢迎项的嘈杂结果,我们要设计排名算法,使用尽可能少的查询来恢复top-k或总排名。
Jun, 2018
该研究引入了PAC Battling-Bandit问题,通过Plackett-Luce子集选择模型在在线学习框架中寻找高置信度的最佳物品,对不同反馈模型下的样本复杂度进行研究,发现利用排名顺序反馈可以从统计效率上提高样本复杂度。
Aug, 2018
我们提出了一种基于PAC学习的随机效用模型(RUM)的新学习算法,通过使用分层消除和基于两两相对比较的临界统计值进行训练,可以在O(n/(c^2ε^2)log(k/δ)) 轮内识别出一个具有ε优异度的项,其中对于足够敏感于项参数之间的差距c的RUM的最差情况下双方优势。
Feb, 2020
本文介绍PL-Rank-3算法,该算法具有可比较于最佳排序算法的计算复杂度,并且可以在任何标准排序可行的情况下应用于学习排序领域。该算法能够通过无偏梯度估计提高优化时间,而不损失性能。
Apr, 2022
透过自适应调用两两比较来研究可能近似正确且公平(PACF)排名问题,目标是根据我们提出的公平目标函数找出一个(ϵ,δ)-PACF排名。我们使用的目标函数要求最小化组的误差lq范数,其中组的误差是组内所有项误差的lp范数,p,q≥1。我们提供了群体不可见和群体感知算法,并分析了其样本复杂度。我们对真实数据集和合成数据集进行了全面的实验以补充我们的理论结果。
Feb, 2024
本文针对传统的排序与选择方法的不足,提出了一种解决大规模最优子集选择问题的新方法。通过设计一种基于启发式的贪婪选择机制,研究证明了该方法在样本选择上的最优性和一致性,能有效地支持决策者作出更明智的选择,并在不增加额外成本的情况下提供无差异排序的功能。
Aug, 2024