Jun, 2018

基于成对和列表查询的 PAC 排名：下界和上界

PDF
TL;DR本文研究了使用多项式逻辑模型下的 $l（l≥2$)$-wise$ ($l≥2$) 比较的积极 PAC top-k 排名（即 top-k 项目选择）和总排名问题，通过自适应地选择查询组并观察每个查询的最受欢迎项的嘈杂结果，我们要设计排名算法，使用尽可能少的查询来恢复 top-k 或总排名。
adaptive pac rankingmultinomial logit modelsample complexitytop-k item selectionplackett-luce model
发现论文，激发创造
  • 具有子集评价偏好的主动排名

    本研究旨在通过自适应挑选子集并收集偏好反馈，在 Plackett-Luce 模型下解决 PAC 排名问题，提出了新的 pivot trick 技巧，从而实现了在一定概率下识别 n 个项目的 ε- 最优排名，（m-1）/m 降低的样本复杂度和对称排名算法的阶无法提高的。

    Oct, 2018

  • 在 Plackett-Luce 模型中应对 Bandits 问题的 PAC 方法

    该研究引入了 PAC Battling-Bandit 问题，通过 Plackett-Luce 子集选择模型在在线学习框架中寻找高置信度的最佳物品，对不同反馈模型下的样本复杂度进行研究，发现利用排名顺序反馈可以从统计效率上提高样本复杂度。

    Aug, 2018

  • 使用成对比较从群众中高效学习 PAC

    本文基于两种算法（一个可直接恢复出真实标签，另一个则可以在标注标签子集的情况下可靠地推断出大型实例集的真实标签）从而开发利用配对比较查询可在指数级减少标签复杂性的方法，用于众包 PAC 学习阈值函数的设定，并在保留整体查询复杂性和运行时间的同时，可以成功地处理来自可能反对者的注释。

    Nov, 2020

  • 嘈杂比较下的最大选择和排名

    在满足强随机可转性和随机三角不等式的概率模型中，本研究考虑了 $(\epsilon,\delta)$-PAC 最大选择和排名问题。提出了一种基于淘汰赛的选择算法和一般框架来改进排名算法，结合归并排序和二分查找，得到了一个优化性能的排名算法。

    May, 2017

  • 基于配对偏好的公平主动排名

    透过自适应调用两两比较来研究可能近似正确且公平（PACF）排名问题，目标是根据我们提出的公平目标函数找出一个（ϵ，δ）-PACF 排名。我们使用的目标函数要求最小化组的误差 lq 范数，其中组的误差是组内所有项误差的 lp 范数，p,q≥1。我们提供了群体不可见和群体感知算法，并分析了其样本复杂度。我们对真实数据集和合成数据集进行了全面的实验以补充我们的理论结果。

    Feb, 2024

  • 随机效用模型下的子集选择最佳项学习

    我们提出了一种基于 PAC 学习的随机效用模型（RUM）的新学习算法，通过使用分层消除和基于两两相对比较的临界统计值进行训练，可以在 O (n/(c^2ε^2) log (k/δ)) 轮内识别出一个具有 ε 优异度的项，其中对于足够敏感于项参数之间的差距 c 的 RUM 的最差情况下双方优势。

    Feb, 2020

  • 非均匀收敛下的最优 PAC 上界

    本研究提出一种新的框架，超越了传统统一收敛方法的限制，将排列不变预测器的交叉检验误差转化为高概率风险界，并通过 Haussler, Littlestone, 和 Warmuth 的一种算法在二元分类中实现了最优 PAC 界限。在多类分类、部分假设分类和实现有限的回归等三种不同场合中，我们证明了该框架的优越性能。

    Apr, 2023

  • 一层 ReLU 网络的 PAC 学习算法和 SQ 下界

    本论文研究了具有 $k$ 个隐藏单元的一层 ReLU 网络在高斯边缘下学习的问题，并提出了适用于正系数情况的首个多项式时间算法，解决了此前在 $k≤3$ 情况下无多项式时间算法的开放性问题。然而，对于具有任意实系数的一层 ReLU 网络的 PAC 学习问题，则证明了一个统计查询下界，说明其难以在多项式时间内得到解决。

    Jun, 2020

  • 简单、健壮且最优排名的配对比较

    本研究旨在通过成对比较的数据形式，使用 Copeland 计数算法实现对 n 个项目的排序，使其具有计算效率高，鲁棒性强，接近信息论极限等特点，并将结果扩展到汉明距离度量下的近似恢复问题和任意错误要求条件下的恢复问题。

    Dec, 2015

  • 来自配对比较的主动排序及其在参数假设无法提供帮助时的应用

    文中提出了一种基于序列或主动排名的算法，该算法基于嘈杂的成对比较将一组 n 个项目排名并将这些项根据其得分分成预先指定大小的集合；本文针对这种算法进行了分析，证明了在某些情况下具有最优性并且不需要任何假设，比如在参数模型下进行的排名。

    Jun, 2016