技术摘要：无监督地从结构中学习排列

问题陈述

许多学习任务涉及在观测时天然无序的数据，需要恢复一个隐藏排列以揭示潜在结构。示例包括排序（恢复单调性）、拼图重建（恢复空间连续性）以及路由问题（如旅行商问题 TSP）。在这些场景中，真实排列往往不可用，因此需要依靠任务特定的结构属性（如平滑性、单调性或几何一致性）而非直接标签监督来驱动无监督学习。

可微排列学习的最新进展，特别是 Gumbel–Sinkhorn 方法，允许将排列视为潜在算子，并通过连续松弛进行优化。这些方法在 Birkhoff 多胞形内使用双随机矩阵来近似离散排列矩阵，并由全局温度参数 $\tau$（或逆温度 $\beta$）控制。然而，随着问题规模和歧义性的增加，出现了一个关键限制：分配矩阵的不同部分以不同的速率收敛。某些行/列在训练早期就变得确定，而其他行/列由于对称性或微弱的结构线索而保持模糊。单一的全局温度迫使所有分配同时锐化或扩散，从而在稳定性和离散化之间造成不可避免的权衡。激进的退火会锁定早期错误，而保守的退火则阻止大型、模糊的排列收敛。

方法论

作者提出了一种熵自适应的 Gumbel–Sinkhorn 公式，用局部变化、行列依赖的逆温度场取代了单一的全局温度。该方法根据当前软排列分配的不确定性来调节温度。

核心机制

1. 熵估计：在每个训练步骤中，使用基础逆温度 $\beta_0(t)$ 计算确定性软分配 $Q$：
   $$Q = \text{Sinkhorn}(\beta_0(t) \cdot \text{stopgrad}(S))$$
   其中 $S$ 表示兼容性得分。stop-gradient 确保熵控制器不会通过温度估计本身进行反向传播。
2. 不确定性计算：从 $Q$ 计算归一化的行熵和列熵（$H^{\text{row}}_i$ 和 $H^{\text{col}}_j$）。接近零的值表示自信的分配，而接近 1 的值表示高不确定性。
3. 自适应温度场：构建一个逐元素的逆温度场 $\beta \in \mathbb{R}^{n \times n}$。对于高熵的行或列，降低逆温度（增加有效温度）以保持探索；对于低熵区域，逆温度保持在基础水平以鼓励离散化。
   $$\beta^{\text{row}}_i = \frac{\beta_0(t)}{1 + b(H^{\text{row}}_i)}, \quad \beta^{\text{col}}_j = \frac{\beta_0(t)}{1 + b(H^{\text{col}}_j)}$$
   其中 $b(\cdot)$ 是一个有界单调函数，仅在熵超过阈值 $H_0$ 时激活。最终的逐元素场为平均值：$\beta_{ij} = \frac{1}{2}(\beta^{\text{row}}_i + \beta^{\text{col}}_j)$。
4. 采样：使用此自适应场采样最终软排列 $P$：
   $$P = \text{Sinkhorn}(\beta \odot (S + g))$$
   其中 $g$ 是 Gumbel 噪声，$\odot$ 表示逐元素乘法。

理论解释

该论文证明，应用带有逐元素逆温度场的 Sinkhorn 归一化等价于求解具有局部重缩放成本的熵正则化分配问题。这提供了一种最优输运解释，其中自适应温度控制在模糊区域延迟对称性破缺，同时允许自信区域集中，同时保持全局双随机约束。

主要贡献

1. 统一框架：一个从重排数据上的任务特定结构损失直接学习排列作为潜在算子的框架，实现了无需真实排列的无监督学习。
2. 熵自适应 Gumbel–Sinkhorn：一种新颖的变体，用源自分配熵的局部变化场取代全局温度。这使得自信的分配能够早期离散化，同时在模糊区域保留探索。
3. 最优输运解释：证明了自适应温度控制等价于 Birkhoff 多胞形上的局部成本重缩放，为该方法的行为提供了理论基础。
4. 实证验证：在排序、拼图重建和无监督 TSP 上的演示表明，与固定或全局退火基线相比，熵自适应控制能产生更可靠的收敛和更高质量的排列，特别是在问题规模（$n$）和分配歧义性增加的情况下。

实验结果

该方法在三个主要任务上进行了评估：

• 列表排序：在具有高歧义性的数据集（值在 $[10, 11]$ 范围内）上，熵自适应温度始终优于全局退火和 NeuralSort。随着 $n$ 增加到 300，性能差距扩大，自适应方法保持了显著更高的 Kendall $\tau$ 分数。
• 拼图重建：在划分为网格（高达 $7 \times 7$）的 CelebA-Test 图像上，与全局退火相比，自适应方法实现了更高的 Kendall $\tau$ 和更稳定的随机种子收敛。改进在边界一致性线索模糊的较大拼图上最为明显。
• 无监督 TSP：应用于 UTSP 协议，该方法（使用基于违规度数的自适应变体）与标准 Gumbel–Sinkhorn 和 UTSP 基线相比，减少了路径长度和最优性差距，特别是在节点数较大（$n=500, 1000$）的情况下。

在所有情况下，自适应方法都表现出对超参数选择（熵阈值 $H_0$ 和最大提升 $b_{\text{max}}$）的鲁棒性，并避免了高歧义性区域中与全局温度调度相关的不稳定性。

意义与主张

该论文主张，从结构中进行有效的排列学习关键取决于管理优化过程中熵在何处以及何时崩溃。通过承认分配不确定性是异质的，所提出的方法解决了全局温度调度中固有的稳定性 - 离散化权衡。

作者将这项工作定位为 Gumbel–Sinkhorn 系列的一个轻量级扩展，在不改变底层松弛几何或收敛属性的情况下提高了可扩展性和稳定性。他们指出，虽然该方法改善了优化稳定性，但它并未解决高度对称或信息量微弱的目标中的根本歧义，某些形式的对称性破缺（例如拼图中的锚定图块）可能仍然是必需的。

建议的未来方向包括端到端地学习熵自适应控制，并将不确定性感知离散化扩展到更复杂的组合结构和多模态匹配问题。