Nov, 2020

通过梯度下降进行降维：高效在线学习最佳排名

HTML
PDF
TL;DR本研究探讨了在线偏好聚合的自然模型，使用广义Min-Sum-Set-Cover问题作为形式化模型，将排序降维到双重随机矩阵空间，并应用在线梯度下降技术以在多项式时间内实现GMSSC低遗憾学习，以提高学习效率。
发现论文，激发创造
  • 一种有效的排名归类简化方法

    本文介绍了一种将排名学习问题有效降至二元分类问题的算法，该算法保证平均成对错误率不超过二进制分类算法误差，适用于更广泛的排名损失函数类，且其时间复杂度在实际应用中较为高效。

    Oct, 2007

  • 使用平滑相对遗憾逼近技术的主动学习及其应用

    我们提出了一种基于池泛型主动学习的不同工具，该工具基于学习器计算假设损失和某个固定“关键”假设之间差异的估计器能力，进而得到一些显著意义上的主动学习界限，尤其对于那些只依赖于不一致性系数限制的方法在某些问题上无法提供有用边界的情况下。

    Oct, 2011

  • 无投影在线学习

    本论文提出采用Frank-Wolfe技术的高效在线学习算法，避免了投影步骤，同时在在线凸优化方面获得了一系列遗憾界，特别是在随机在线平滑凸优化方面。此外，我们的算法具有参数自由性和产生稀疏决策的优点，并将算法应用到协作过滤的计算密集型应用中，并在标准数据集上显示出理论上的改进。

    Jun, 2012

  • 在线排名与Top-1反馈

    本研究探讨了一种在线学习算法，使用新颖的 Top-1 反馈模型，评估对多样性兴趣用户的固定排名商品排名能力，并证明了其对于几种流行的排名度量具有最小化后悔的能力。

    Oct, 2014

  • 基于成对比较的大规模协作排名偏好数据填充

    本文针对协作排名问题展开研究，通过基于凸优化的算法和AltSVM这种大规模非凸实现方式，实现从用户提供的两两偏好比较结果中预测他们对未曾见过物品的偏好，该算法展现出了在多个协作过滤数据集中NDCG和排名性能的许多中等规模基线的表现优势。

    Jul, 2015

  • 数据驱动的排名破坏用于高效的排名聚合

    本文提供了最优的排名破坏估计器，通过处理按拓扑结构不同对待两两比较来实现准确和一致的估计，并确定了精度与复杂度之间的基本权衡以及精度如何取决于相应比较图的谱间隙。

    Jan, 2016

  • 随机排名：无标度离散函数的全局优化

    该研究提出了一个用于直接优化排名度量的高效框架——CatBoost，并介绍了两种重要的技术：随机平滑和基于部分积分的新梯度估计，证明了经典平滑方法可能会引入偏差，并提出了一个通用解决方案进行去偏差，该算法保证全局收敛性并在多个学习排名数据集上优于现有方法。

    Mar, 2020

  • PiRank: 可扩展的可微排序学习

    提出了一种新的可微的代理损失函数PiRank，它使用基于NeuralSort的连续、温度控制放松来排序操作符，最终在公共互联网规模的学习排序基准测试中明显提高了可比较方法的性能。

    Dec, 2020

  • 一种改进的在线最小和集合覆盖算法

    本文探讨基于在线偏好聚合的基础模型，在评估算法的竞争力方面提出了一种新算法，能够实现更强的动态最优解，算法的竞争比由 $O(r^2)$ 到达。

    Sep, 2022

  • 通过谱方法改进的排名聚合的理论保证

    给定多个项目之间的成对比较，如何对它们进行排名，以使得排名与观察结果相匹配？本研究关注基于Erdos-Renyi异常值（ERO）模型的排名问题，在该问题中，每个成对比较都是真实分数差异的损坏副本。通过研究基于非归一化和归一化数据矩阵的谱排名算法，我们提供了每个项目从观察数据中恢复出其潜在分数的性能，并得出了非归一化/归一化数据矩阵的最大特征向量与其总体对应物之间的逐项扰动误差界限。通过留一法技术，我们提供了更精确的最大特征向量的l∞范数扰动界限，并在只有Ω(nlogn)个样本的情况下导出了每个项目的最大偏移误差界限。理论分析在样本复杂度方面改进了现有技术的结果，并通过数值实验验证了这些理论发现。

    Sep, 2023