Sep, 2023

关于 Sinkhorn 算法和选择建模

PDF
TL;DR基于路斯选择公理的广泛类选择和排名模型，包括布拉德利 - 特里 - 路斯和普拉克特 - 路斯模型，我们证明相关的最大似然估计问题等同于具有目标行列和的经典矩阵平衡问题。这种观点打开了两个看似无关的研究领域之间的门槛，并使我们能够将选择建模文献中的现有算法统一为 Sinkhorn 的矩阵平衡算法的特殊实例或类比。我们从这些联系中获得启发，并解决了关于 Sinkhorn 算法的重要开放问题。我们首先证明了对于非负矩阵，只要矩阵平衡问题存在有限解，Sinkhorn 算法在全局上是线性收敛的。我们用数据构造的双部分图将这种全局收敛速率以代数连通性的形式刻画出来。接下来，我们还推导了尖锐的渐近线性收敛速率，这推广了 Knight（2008）的经典结果，但使用了更明确的分析方法来利用内在的正交结构。据我们所知，这是 Sinkhorn 算法在一般非负矩阵和正边缘情况下的第一个定量线性收敛结果。我们在本文中建立的矩阵平衡和选择建模之间的联系可以有助于在两个方向上进一步传递思想和有趣的结果。
发现论文，激发创造
  • Lifted Assignment 问题的 Sinkhorn 算法

    本论文提出了将 Sinkhorn 算法用于解决 QAP 的 JA 松弛的一般化算法，该算法基于 Bregman 投影算法，并构建了一种高维的局部单侧版本用于 Bregman 投影，从而比标准方法更稳定和精确地解决了原始线性规划问题。

    Jul, 2017

  • 矩阵缩放与 Sinkhorn 正常形式在矩阵和正态映射中的应用综述

    通过在非负矩阵 $A$ 内找到对角矩阵 $D_1,~D_2$，可以得到 $D_1AD_2$ 是双重随机的 Sinkhorn 定理，这篇文章评述了 70 多年来的矩阵缩放，重点关注围绕该问题及其解决方案的数学领域以及扩展至矩阵代数之间的正态映射，几乎不包含任何不普遍的未发表结果。

    Sep, 2016

  • Sinkhorn 算法作为随机镜像下降的一种特殊情形

    通过将 Kullback-Leibler divergence 应用于 mirror map 和目标函数中，我们发现 Sinkhorn 算法是增量 / 随机镜像下降的一种特例。该发现使我们能够提出一种新方法，扩展了 Sinkhorn 算法超出两个约束。

    Sep, 2019

  • 使用 Gumbel-Sinkhorn 网络学习潜在的置换

    介绍了一系列以连续 Sinkhorn 运算符来近似离散最大权匹配的新方法，应用在排序数字，拼图和鉴别神经信号等任务中，并且在竞争基线上取得了更好的效果。

    Feb, 2018

  • 使用 Sinkhorn 算法快速解决公平排序问题

    在线跳蚤市场等双边市场中，为消费者提供个性化项目排名的推荐系统在促进提供者和消费者之间的交易中起着关键作用。然而，双边市场面临平衡消费者满意度和公平性以刺激项目提供者活动的问题。本文提出了一种快速的基于影响力公平排名问题的解决方案，通过将公平排名问题转化为无约束的优化问题，并设计了一种反复执行 Sinkhorn 算法的梯度上升方法。实验结果表明，我们的算法能够提供高质量的公平排名，并且比商业优化软件的应用快约 1000 倍。

    Jun, 2024

  • 通过对角缩放算法解决最优配对问题

    通过将变形参数趋向于正无穷，最优分配问题的解可以由最大熵问题的解趋向得出，从而可以应用最大熵算法来求解最优分配问题。其中 Sinkhorn 算法导致了一种可并行化的方法，可用作处理大规模密集最优分配问题的预处理。此并行预处理允许删除不属于最优排列的条目，从而导致减少内存要求的可解实例。

    Apr, 2011

  • Sinkhorn Flow: Sinkhorn 算法的连续时间框架解读与推广

    机器学习中的熵正则最优传输问题可以通过 Sinkhorn 算法进行求解，而该研究介绍了 Sinkhorn 算法的连续时间模拟以及其在噪声和偏差容忍性方面的改进，同时与机器学习和数学领域中其他动态方法提供了统一的视角。

    Nov, 2023

  • 稀疏牛顿迭代加速 Sinkhorn 算法

    通过引入早停止和牛顿类型子程序，Sinkhorn-Newton-Sparse（SNS）算法提供了超指数收敛，并且在实际情况下收敛速度比 Sinkhorn 算法快几个数量级，包括离散密度的经验分布之间的最优输运和计算 Wasserstein W1，W2 距离。

    Jan, 2024

  • 基于盒约束牛顿法和内点方法的矩阵缩放和平衡

    本篇论文提出了一种新的二阶优化框架，用于处理矩阵缩放和平衡问题，提出了可以忽略对数因子的算法，可以在几乎线性时间内解决这些问题，同时提供了一种使用内部点方法的单独算法，以及广泛适用的第二阶鲁棒函数最小化方法。

    Apr, 2017

  • Schrödinger 桥问题的最优输运方法和 Sinkhorn 算法的收敛性

    该论文利用了 Schr"odinger 桥问题和熵惩罚的最优输运之间的等价性，以寻找一种与最优输运相似的新的方法来探究二者间的对偶性。该方法提供了一些先验估计并且在正则化参数趋于零的极限情况下一致。该方法还适用于多个数据边缘的情况，证明了 Sinkhorn 算法的新的收敛性质。

    Nov, 2019