ICMLFeb, 2020

快速可微排序和排名

PDF
TL;DR本文提出了首个具有 O (n log n) 时间和 O (n) 空间复杂度的可微分排序和排名操作，并通过在排列凸包上的投影和使用保序优化减少来实现此操作。实验证明，该方法比现有方法快一个数量级，并展示了两个新颖的应用程序：可微 Spearman 秩相关系数和最小修剪的平方。
sortingdifferentiable operatorspermutahedronisotonic optimizationspearman's rank correlation coefficient
发现论文，激发创造
  • 可微排名与排序的最优输运算法

    提出了一种基于最优传输问题的算法可微分排序框架，包括基于 Kantorovich 公式的算子对于 CDFs 和 quantiles 的推广，以及基于这一框架在量子回归和神经网络中的应用

    May, 2019

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

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

    Dec, 2020

  • 单调可微排序网络

    本研究提出了一种基于 sigmoid 函数的可微分排序网络的单调松弛方法，该方法可以保证梯度始终具有正确的符号，提高了基于梯度的优化效果。

    Mar, 2022

  • 可微分排序网络用于可扩展的排序和排名监督

    该研究提出可微分的排序网络来训练神经网络，能够在排序约束条件下进行端到端的训练，此方法能够在不需要绝对数值监督的情况下，实现对神经网络的训练和优化，并探究多层神经网络训练时可能产生的梯度消失和模糊化等问题，证明了拟制的依次比较和比特位排序网络在大规模数据集上的优越表现。

    May, 2021

  • SoDeep: 一种用于学习排名损失替代的深度排序网络

    本研究提出了一种新的基于深度架构的方法，学习非可微分目标函数的近似值，应用于需要排序的三个任务中并取得了很好的效果。

    Apr, 2019

  • Diffsurv: 适用于截尾生存时间数据的可微分排序

    提出一种名为 Diffsurv 的新方法，扩展可区分排序方法以处理被剪枝任务，通过预测考虑剪枝样本引入的标签不确定性的可能排列矩阵来解决此限制，进而在各种模拟和现实风险预测场景中优于现有基准，并通过提出一种新的 top-k 风险预测方法展示了 Diffsurv 启用的算法监督的优点。

    Apr, 2023

  • 通过连续松弛的随机优化排序网络

    本文提出了 NeuralSort 算法，将排序操作的输出从置换矩阵松弛到单峰行随机矩阵的集合，使得任意计算图都可以进行端到端梯度优化；并且使用这种松弛方式，针对全排列空间提出了重参数化梯度估算器，展示了该框架在高维对象学习语义排序方面的实用性。

    Mar, 2019

  • 统计排名与组合霍奇理论

    使用图 Helmholtzian 和组合 Hodge 理论，基于边缘流的成对排名可以解析为两个正交成分，其中一个表示 L2 最优全局排名，而另一个表示无旋转流，同时还可以通过线性最小二乘回归计算离散的 Hodge 分解。

    Nov, 2008

  • 基于预测的排序

    通过学习增强算法的角度探索排序问题，其中算法利用可能存在错误的预测来提高效率。我们考虑了两种不同的情境：在第一种情境中，为每个项目提供了其在已排序列表中的位置预测；在第二种情境中，我们假设存在一种 “快速但不精确” 的方法来比较项目，除此之外还有慢而准确的比较。对于这两种情境，我们设计了新的简单算法，仅使用 O (Σi log ηi) 个精确比较，其中 ηi 是第 i 个元素的适当定义的预测误差。特别是，随着预测质量的下降，比较次数从 O (n) 平滑地降低到 O (nlogn)。我们证明在所考虑的误差度量方面，比较复杂度在理论上是最优的。与现有的自适应和非自适应排序算法进行的实验评估表明了在排序任务中应用学习增强算法的潜力。

    Nov, 2023

  • 直接优化排序度量

    介绍了一种新的优化丢失功能的方法以提高 Web 页面排名和协同过滤的性能，并使用结构化估计在希尔伯特空间中进行直接优化，所提出的算法被证明是快速且表现良好。

    Apr, 2007