Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot

变压器架构在各种深度学习场景中占据主导地位，因为它具有选择和组合结构信息的异常能力。受到这些能力的启发，Sanford等人提出了稀疏令牌选择任务，在这个任务中，变压器在最坏情况下表现出色，而全连接网络则失败。在此基础上，我们将FCN的下限加强到平均情况，并建立了变压器与FCN之间的算法分离。具体而言，使用梯度下降训练的一层变压器可证明学习稀疏令牌选择任务，并且令人惊讶的是，它表现出强大的超出分布长度的泛化能力。我们提供经验模拟来证明我们的理论发现。

论文旨在探究transformer模型在稀疏token选择任务中的表现，以及相比于全连接网络的优劣。同时，将FCN的下限强化到平均情况下，并建立transformer比FCN更优的算法分离。

论文证明了一个单层的transformer模型可以通过梯度下降学习到稀疏token选择任务，并且表现出强大的长度泛化能力。

论文通过实验和理论证明了transformer模型在稀疏token选择任务中的优越性，同时提出了一种新的算法分离方法。实验使用了多个数据集，并提供了开源代码。

与该论文相关的研究包括：'Attention Is All You Need'、'Sparse Transformers'、'Compressive Transformers for Long-Range Sequence Modelling'等。