我添加了一个神经排序算法。它基于稳定扩散中的重参数化技巧构建！叫做Gumbel-Sinkhorn网络。让我们赚钱吧！https://leetarxiv.substack.com/p/gumbel-sinkhorn-neural-sort…

使用Gumbel-Sinkhorn架构对数字进行排序的Python代码

来源：https://leetarxiv.substack.com/p/gumbel-sinkhorn-neural-sort

快速总结

我们使用2018年原始论文中的Gumbel-Sinkhorn架构，在Python中训练一个神经网络来对数字列表进行排序。

论文《使用Gumbel-Sinkhorn网络学习潜在排列》（Mena等人，2018）的摘要

论文《使用Gumbel-Sinkhorn网络学习潜在排列》（Mena等人，2018）1 介绍了一种无需显式标签即可学习排序数据的网络架构。

Sinkhorn-Knopp (https://leetarxiv.substack.com/p/sinkhorn-knopp-algorithm-24d?utm_source=publication-search) 是一种生成类softmax概率的矩阵均衡算法。我们之前 (https://leetarxiv.substack.com/p/sinkhorn-knopp-algorithm-24d?utm_source=publication-search) 已经详细讨论过它：

Sinkhorn Knopp 算法 (https://leetarxiv.substack.com/p/sinkhorn-knopp-algorithm-24d) 信念传播 (https://leetarxiv.substack.com/p/sinkhorn-solves-sudoku?utm_source=publication-search) 算法是梯度下降的替代方案，它使用Sinkhorn-Knopp算法通过机器学习解决数独问题：

信念传播是训练推理模型的反向传播的一种模糊替代方案 (https://leetarxiv.substack.com/p/sinkhorn-solves-sudoku)

Gumbel-Sinkhorn 网络用于解决拼图难题并找到正确的排列。来自 (Fulton & Evans, 2026)

(Mena等人，2018) 将这些想法扩展到 Gumbel-Sinkhorn 网络：通过微分学习排序物品的神经网络。它们基于排列可以用矩阵表示的事实 (Fulton & Evans, 2026)2：

将排列表示为矩阵。来自 (Fulton & Evans, 2026)

代码可在 Google Colab (https://colab.research.google.com/drive/1_386oAXNeaWWhixim8iOuaiutsSeGyxe?usp=sharing) 和 GitHub (https://github.com/MurageKibicho/Neural-Sorting-Algorithms-Gumbel-Sinkhorn-Networks/tree/main) 上找到。

首先，我们将编写 (Mena等人，2018) 中引入的两个基本概念：

1. Sinkhorn 算子：可微分的排列近似。
2. Gumbel-Sinkhorn 分布：与 Gumbel Softmax 分布类似，允许我们执行类似稳定扩散中的重参数化技巧 (https://leetarxiv.substack.com/p/stable-diffusion-from-scratch-1?utm_source=publication-search)。

Sinkhorn 算子的定义。来自 (Mena等人，2018)

Sinkhorn 算子定义在 N 维方阵 X 上。我们之前 (https://leetarxiv.substack.com/p/sinkhorn-knopp-algorithm-24d?utm_source=publication-search) 已经详细讨论过。

以下是快速总结 (Knigge, 2023)3：

1. Sinkhorn 算子就是原始的 1967 年 Sinkhorn-Knopp (https://leetarxiv.substack.com/p/sinkhorn-knopp-algorithm-24d?utm_source=publication-search) 算法。
2. 将任意矩阵输入 Sinkhorn 算子应产生一个双随机矩阵：一个行和与列和都等于 1 的矩阵。
3. Sinkhorn 算子是可微分的，允许我们近似一个排列。 除法等价于对数之间的减法。来自 FRACTRAN 论文 (https://leetarxiv.substack.com/p/fractran-a-simple-universal-programming?utm_source=publication-search)。
4. 原始的 1967 年 Sinkhorn-Knopp (https://leetarxiv.substack.com/p/sinkhorn-knopp-algorithm-24d?utm_source=publication-search) 算法由于除法而不稳定，因此我们倾向于使用对数进行减法而不是除法。
5. 原始的 1967 年 Sinkhorn-Knopp (https://leetarxiv.substack.com/p/sinkhorn-knopp-algorithm-24d?utm_source=publication-search) 类似于一个依赖于温度的 softmax。τ 是温度参数，当其为 0 时，我们获得对应于最大 X 的独热编码。 依赖于温度的 softmax 等价于 Sinkhorn-Knopp

我们在 Python 中实现 Sinkhorn 算子，每次迭代是一个除法（对数之间的减法），并在最后使用 exp 去除对数：

使用对数的 Sinkhorn 算子。 我们编写一个单独的函数来验证所有行和与列和是否为 1：

Sinkhorn 算子测试函数 测试通过！

重参数化技巧 (https://leetarxiv.substack.com/p/stable-diffusion-from-scratch-1?utm_source=publication-search) 允许在前向扩散过程中生成任意的带噪声输入变体。我们之前 (https://leetarxiv.substack.com/p/stable-diffusion-from-scratch-1?utm_source=publication-search) 已经详细讨论过：

从零开始用低级语言实现稳定扩散：C、Ruby 和 Rust 中的噪声生成 (https://leetarxiv.substack.com/p/stable-diffusion-from-scratch-1)

(Mena等人，2018) 从重参数化技巧 (https://leetarxiv.substack.com/p/stable-diffusion-from-scratch-1?utm_source=publication-search) 出发，引入了Gumbel-Matching分布：当我们将 Gumbel 噪声应用于概率矩阵 X 时得到的排列矩阵的分布 (Knigge, 2023)。

Gumbel-Matching 分布。来自 (Knigge, 2023)

然而，(Mena等人，2018) 指出 Gumbel-Matching 分布由于其离散性而不可微分。因此，它们求助于定理 1：

定理 1。来自 (Mena等人，2018)

定理 1 指导推导出 Gumbel-Sinkhorn 分布：离散 Gumbel-Matching 分布的连续松弛。

Gumbel-Matching 分布。来自 (Knigge, 2023)

Gumbel-Sinkhorn 分布是将 Sinkhorn 算子应用于一个未归一化的分配概率矩阵（我们向其添加 Gumbel 噪声）后得到的分布 (Knigge, 2023)。这是可微分的，哈哈！

实现上述功能的 Python 代码是：

生成 Gumbel 噪声并从 Gumbel-Sinkhorn 分布中采样

Gumbel-Sinkhorn 网络建立在 Sinkhorn 算子和 Gumbel-Sinkhorn 采样器之上。我们的指南训练一个简单的 MLP 来将浮点数数组按升序排序。

数字生成器类

接下来，我们编写一个匹配函数，将对数概率的方阵转换为硬排列矩阵，即每行恰好有一个 1：

贪心匹配函数

我们继续编写一个排序 MLP。注意，我们从 Gumbel-Sinkhorn 分布训练，但使用匹配算法进行评估：

带有前向传播逻辑的排序网络

最后，我们编写训练和评估代码：

训练和评估代码

让我们观察一些结果：

太好了！我们的网络学会了按升序对数字进行排序

本节面向好奇者。内容包括：

1. 不使用自动求导的反向传播 Sinkhorn 迭代。

2. 将双随机矩阵转换为排列矩阵。

反向传播非常简单。只需从梯度总和中减去输出的指数：

反向传播推导

但我们需要保存每个归一化后的行和列才能实现这一点。因此训练的正向和反向传播类似于：

训练的正向和反向传播

我们的硬编码反向传播与 PyTorch 的自动求导匹配：

硬编码梯度与 PyTorch 匹配

(Mena等人，2018) 在线性分配问题与给定双随机方阵时选择排列矩阵 P 之间建立了类比 (Knigge, 2018)。

匹配函数的动机

它建立在三个重要概念之上：

1. 排列矩阵是正交的。
2. 正交矩阵的逆是其转置。
3. 双随机矩阵 X 的最佳对应排列矩阵 P 是最大化 trace* of (P^T X) 的排列。*迹是矩阵特征值的和。

在 Python 中，使用 Scipy，这类似于：

使用迹分数的线性分配测试

1. 匈牙利算法 I (https://slm.mba/mmpo-001/step-by-step-guide-hungarian-method/)
2. 匈牙利算法 II (https://neelmishra.github.io/blog/cp/optimization/hungarian-detailed.html)

אגי-e/acc (@murage_kibicho): 我的周末副业项目是把一个文本扩散模型变成一个数据压缩器。 我不认为它会成功，但谁知道呢？