Learning Linear Attention in Polynomial Time

先前的研究探讨了Transformer模型在模拟布尔电路或图灵机方面的计算表达能力。然而，这些模拟器从观察数据中学习的能力仍然是一个未解的问题。我们的研究填补了这一空白，首次提供了单层Transformer（具有线性注意力机制）的多项式时间可学习性结果（具体而言是强大的、不可知的PAC学习）。我们表明，线性注意力可以被视为在适当定义的再生核希尔伯特空间（RKHS）中的线性预测器。因此，学习任何线性Transformer的问题可以转化为在扩展特征空间中学习普通线性预测器的问题，而任何这样的预测器都可以转换回多头线性Transformer。在泛化方面，我们展示了如何高效地识别训练数据集，使得每个经验风险最小化器都等价于生成数据的线性Transformer（除了平凡的对称性），从而保证所学模型能够正确地推广到所有输入。最后，我们提供了一些通过线性注意力可表达且因此可在多项式时间内学习的计算示例，包括联想记忆、有限自动机以及具有多项式有界计算历史的一类通用图灵机（UTMs）。我们在三个任务上验证了我们的理论发现：学习随机线性注意力网络、键值关联以及学习执行有限自动机。我们的研究结果弥合了Transformer理论表达能力和可学习性之间的一个关键差距，并表明灵活且通用的计算模型是可以高效学习的。

该论文试图解决Transformer模型在从观察数据中学习布尔电路或图灵机模拟器方面的可学习性问题。这是一个开放性问题，之前的研究虽然探讨了Transformer模型的计算表达能力，但尚未解决其学习效率和泛化能力。

论文的关键思路是证明单层Transformer模型（具有线性注意力机制）可以在多项式时间内强无偏PAC学习。通过将线性注意力机制视为特定定义的RKHS中的线性预测器，可以将学习线性Transformer的问题转换为在扩展特征空间中学习普通线性预测器的问题。这一转换不仅简化了学习过程，还保证了模型的泛化能力。

论文展示了如何高效地识别训练数据集，使得每个经验风险最小化器都等价于生成数据的线性Transformer，从而确保模型在所有输入上正确泛化。此外，论文提供了线性注意力机制能够表达的计算示例，包括联想记忆、有限自动机和一类具有多项式时间限制的通用图灵机。实验部分验证了学习随机线性注意力网络、键值关联和有限自动机执行的能力。论文还提供了开源代码，便于后续研究者复现和扩展。

近期在Transformer模型的可学习性和计算表达能力方面，有以下相关研究：1. 'On the Expressive Power of Transformer Models' - 探讨了Transformer模型的计算能力；2. 'Learning Boolean Circuits with Neural Networks' - 研究了神经网络在学习布尔电路方面的表现；3. 'Efficient Learning of Linear Transformers' - 提出了高效的线性Transformer学习方法。