arXiv:2504.04702v1 宣告类型: cross 摘要：基于Transformer的架构的最近进步在自然语言处理任务中取得了令人印象深刻的突破，如GPT-4、Claude和Gemini等模型展示了human-level的推理能力。然而，尽管这些模型具有高性能，人们仍然对其固有的局限性有所担心，尤其是在学习基本逻辑函数方面。虽然从复杂理论分析表明，Transformer可以通过其属于$\mathsf{TC}^0$类的本质来表示简单的逻辑函数（例如，$\mathsf{AND}$，$\mathsf{OR}$ 和大多数门），这些结果假设了理想参数设置，并未考虑到基于梯度下降的训练方法所施加的约束。在本工作中，我们探讨了Transformer在使用基于梯度的方法训练时，是否能够真正学习简单的大多数函数。我们关注简化版的Transformer架构，并考虑了两种情况：$n=\mathrm{poly}(d)$和$n=\exp(\Omega(d))$数量的训练样本，其中每个样本是一个$d$大小的二进制字符串，以及一个基本的大多数函数的输出。我们的分析表明，即使进行了$\mathrm{poly}(d)$次梯度查询，Transformer模型的泛化误差仍然显著较大，并且随着$d$的增加而指数增长。这项工作突显了训练Transformer进行最简单的逻辑推理任务时的基本优化挑战，并提供了对其理论限制的新见解。