可微排名与排序的最优输运算法
本文提出了首个具有 O (n log n) 时间和 O (n) 空间复杂度的可微分排序和排名操作,并通过在排列凸包上的投影和使用保序优化减少来实现此操作。实验证明,该方法比现有方法快一个数量级,并展示了两个新颖的应用程序:可微 Spearman 秩相关系数和最小修剪的平方。
Feb, 2020
研究了 top-k 运算在使用算法实现后无法通过梯度下降算法从端到端训练的问题,提出了基于最优输运的平滑近似 SOFT top-k operator,并在 k 最近邻居和 Beam Search 算法中应用,改善了性能。
Feb, 2020
本研究提出了一种基于 Nesterov 的平滑技术的新算法,通过近似 Log-Sum-Exp 函数来平滑 Kantorovich 势的非平滑 c-transform,并将此平滑后的 Kantorovich 泛函应用于快速的 FISTA 算法以提高计算效率和精确度。实验结果表明,该方法相较于 Sinkhorn 算法在相同参数下具有更快的收敛速度和更高的准确性。
Apr, 2021
本文提出了 NeuralSort 算法,将排序操作的输出从置换矩阵松弛到单峰行随机矩阵的集合,使得任意计算图都可以进行端到端梯度优化;并且使用这种松弛方式,针对全排列空间提出了重参数化梯度估算器,展示了该框架在高维对象学习语义排序方面的实用性。
Mar, 2019
本文研究了满足等式和不等式约束条件下的熵正则化的最优输运问题,并提出了一种基于 Sinkhorn 算法的对应解法。通过理论保证,我们首先得出在解决问题时通过熵正则化所带来的近似误差随着参数增加而指数级减小。此外,通过描述具有李雅普诺夫函数的优化过程,我们证明了 Sinkhorn 算法在对偶空间中具有亚线性一阶收敛速度。为了在弱熵正则化下实现快速、高阶收敛,我们通过动态正则化调度和二阶加速技术来改进 Sinkhorn 算法。总体而言,本文将熵最优输运的最近理论和数值进展与约束情况相结合,使从业者能够在复杂场景中得到近似的输运计划。
Mar, 2024
本研究分析了逼近两个离散分布之间的一般最优运输(OT)距离的两种算法,并证明了复杂度界限,其中一种基于 Sinkhorn 算法,另一种基于 Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) 算法。与先前的最优界限相比,我们的算法具有更好的复杂度界限,更好地依赖于 ε,同时可用于各种正则项。
Feb, 2018
提出了一种新的可微的代理损失函数 PiRank,它使用基于 NeuralSort 的连续、温度控制放松来排序操作符,最终在公共互联网规模的学习排序基准测试中明显提高了可比较方法的性能。
Dec, 2020
本短篇论文着重回顾了优化输运相关理论(Optimal transport theory)及其在数据科学中的应用,重点在于阐述其针对分类、回归、密度拟合等机器学习等领域的优势,介绍了它的数值方法,并介绍了一些学术性质。
Mar, 2018