arXiv:2410.01686v2 更新类型: 替换-交叉 摘要：神经网络执行算法任务（例如，算术运算、总结统计和排序）的能力正日益引起人们的兴趣。本文的目标是更好地理解 Transformer 在执行算法任务中的作用。算法执行的重要性已经通过使用并行计算模型的理论和实验证明。值得注意的是，许多并行算法仅使用位置信息在处理器之间进行通信。受到这一观察的启发，我们研究了 Transformer 如何使用位置注意力执行算法，其中注意力权重仅依赖于位置编码。我们证明，使用位置注意力（位置 Transformer）的 Transformer 在相对于输入长度而言具有对数深度成本的情况下，保留了与并行计算模型相同的表达能力。我们分析了它们在训练数据中的可学习性，并探讨了位置注意力中的参数范数如何影响样本复杂性。我们的结果表明，位置 Transformer 引入了学习权衡：虽然它们在参数范数上的理论依赖性表现更好，但在某些任务中可能需要更多的层，这又可能增加样本复杂性。最后，我们通过实验研究了位置 Transformer 的泛化性能，并发现它们在依赖位置信息的算法解决方案的任务中表现良好。