⏶1
热带注意力：用于组合算法的神经算法推理
发表
由 
Baran Hashemi 提交
Baran Hashemi 提交作者: Baran Hashemi, Kurt Pasque, Chris Teska, Ruriko Yoshida
Baran Hashemi, Kurt Pasque, Chris Teska, Ruriko Yoshida摘要
组合优化问题的动态规划 (DP) 算法在其递归算法中涉及最大化、最小化和经典加法运算。相关的价值函数对应于最大值加半环中的凸多面体。然而，现有的神经算法推理模型依赖于 softmax 归一化的点积注意力，其中平滑的指数加权会模糊这些尖锐的多面体结构，并在分布外 (OOD) 设置下评估时崩溃。我们引入了 Tropical attention，这是一种新颖的注意力机制，它在热带几何的最大值加半环中原生运行。我们证明 Tropical attention 可以近似 DP 型组合算法的热带电路。然后我们提出，使用 Tropical transformers 可以在算法推理任务上提升长度泛化和价值泛化方面的经验性 OOD 性能，超越 softmax 基线，同时在对抗性攻击下保持稳定。我们还将对抗性攻击泛化作为神经算法推理基准测试的第三个维度。我们的结果表明，Tropical attention 恢复了 softmax 中缺失的尖锐、尺度不变的推理能力。
众所周知，softmax attention会随着序列增长而衰减。这种模糊性正是许多attention机制在算法和推理任务上步履维艰的原因。好的，我们有了一个代数几何热带（Tropical）解决方案。
1️⃣ 我们引入了Tropical Attention——第一个在Tropical半环中运行的神经算法推理器，在执行多个组合算法方面实现了SOTA OOD性能。
2️⃣ 在Tropical (max, +) 几何中，“加法”是max，“乘法”是+。
许多算法已然存在于此，雕刻出精确的多面体决策边界——那么为什么要强制它们通过指数概率呢？
让我们放弃softmax，拥抱Tropical几何。
3️⃣ Tropical Attention在max-plus中原生运行每个头。结果是：
即使在几个算法任务中，包括臭名昭著的Quickselect算法（Michael Galkin识别出的另一个挑战），也能实现强大的OOD长度泛化，并具有清晰的attention图谱。
4️⃣ 我们在11个经典的组合任务上进行了基准测试。Tropical attention在所有三个OOD维度（长度、值和对抗性攻击泛化）上都击败了香草（Vanilla）和自适应softmax attention。
5️⃣ 我们还展示了每个Tropical attention头都可以作为Tropical电路中的一个Tropical门，模拟任何max-plus电路。
6️⃣ 我们的信息是：更好的推理能力可能不是来自更大的模型，而是来自选择正确的代数/几何。