Learning Compositional Functions with Transformers from Easy-to-Hard Data

基于 Transformer 的语言模型在各种复杂的推理任务中展现了令人印象深刻的性能。先前关于 Transformer 表达能力的理论研究已证明，它们能够高效执行涉及可并行计算的多步推理任务。然而，这类结构的学习能力，尤其是数据分布中的哪些条件能够通过基于梯度的优化实现高效学习，仍然是一个开放问题。为了解答这一问题，本文研究了 $k$-重组合任务的学习能力。该任务要求计算 $k$ 个输入排列和 $k$ 个隐藏排列的交错组合，并且可以用具有 $O(\log k)$ 层的 Transformer 表达。从负面结果来看，我们证明了一个统计查询（SQ）下界，表明任何对 $k$-重组合任务分布仅进行多项式数量查询的 SQ 学习者，其样本复杂度必须是 $k$ 的指数级，从而揭示了一个统计与计算之间的差距。另一方面，我们展示了通过两种不同的课程学习策略，使用梯度下降方法可以在深度为 $O(\log k)$ 的 Transformer 上以多项式时间（相对于 $k$）和样本复杂度高效学习这一函数类：一种策略是按难度递增顺序逐步提供包含 $k' \le k$ 的 $k'$-重组合函数的数据；另一种策略是同时呈现所有此类数据。我们的研究阐明了数据分布中同时包含简单和复杂示例对于 Transformer 学习复杂组合任务的必要性和充分性。

该论文探讨了Transformer模型在学习复杂多步推理任务（如k-fold composition任务）时的可学习性问题，特别是数据分布对基于梯度优化方法的影响。这是一个尚未完全解决的问题，涉及统计与计算之间的权衡。

论文通过研究k-fold composition任务，证明了Transformer可以通过O(log k)层网络高效表达此类任务，但存在统计-计算差距（即SQ算法需要指数级样本）。同时，提出两种基于课程学习的策略（逐步增加难度和一次性展示所有难度），使Transformer能够通过梯度下降以多项式时间完成学习任务，揭示了数据分布中难易样本的重要性。

1. 提出了针对k-fold composition任务的理论分析，包括SQ下界和课程学习的有效性；2. 实验设计验证了两种课程学习策略在不同数据分布下的表现；3. 强调了难易样本结合对于复杂任务学习的关键作用；4. 没有提到具体使用哪些数据集或是否开源代码，但为未来研究提供了方向，例如探索更多实际应用场景中的课程学习策略。

相关研究包括：1.《On the Expressive Power of Transformers》——研究Transformer的表达能力；2.《Understanding Generalization in Deep Learning via Statistical Mechanics》——从统计力学角度分析深度学习泛化；3.《Curriculum Learning》——Yoshua Bengio等人提出的课程学习理论；4.《Statistical Query Lower Bounds for Tensor PCA》——探讨Tensor PCA问题中的SQ下界。