Sequential Group Composition: A Window into the Mechanics of Deep Learning

神经网络在序列数据上训练时，如何获得执行结构化运算（例如算术运算、几何运算及算法运算）的能力？为深入理解这一问题，我们提出了“序列群合成任务”（sequential group composition task）。在此任务中，网络接收一段由有限群元素构成的序列，这些元素被编码为实向量空间中的向量，网络需预测该序列元素的累积群乘积。该任务对输入顺序敏感，且必须借助非线性网络架构才能被成功学习。我们的分析厘清了群结构、编码统计特性以及序列长度三者在塑造学习过程中的各自作用。我们证明：双层网络以群的不可约表示为单位，逐个学习该任务，其学习顺序由编码方式的傅里叶统计特性所决定。此类网络虽可完美完成该任务，但要实现这一点，其隐层宽度需随序列长度 $k$ 指数级增长。相比之下，我们进一步表明，更深的模型可利用该任务固有的结合律性质，显著改善上述复杂度缩放关系：循环神经网络（RNN）通过 $k$ 步依次合成元素；而多层网络则可在 $\log k$ 层内并行地两两合成相邻元素。总体而言，“序列群合成任务”为探究深度学习内在机制提供了一个切实可行、易于分析的研究窗口。

论文旨在探究神经网络如何在序列学习中获得执行结构化操作（如算术、几何和算法计算）的能力，具体通过新提出的‘顺序群组合任务’（sequential group composition task）来验证：给定有限群元素的向量编码序列，网络需预测其累积群乘积。该任务是顺序敏感、非线性且结构化的，用于系统解构深度网络学习结构化计算的机制。这是一个新颖的、可控的理论驱动型基准任务，而非传统黑箱序列建模问题。

核心思想是将群表示论与深度学习动力学相结合：证明两层网络按群不可约表示的傅里叶统计（即编码分布的频谱权重）顺序逐个学习表示；而深层模型（RNN或并行多层网络）则显式利用群运算的结合律，将O(k)串行计算压缩为O(log k)并行层——首次从理论层面揭示‘深度’如何通过分解结合性结构实现指数级样本/宽度效率提升。

理论贡献突出：给出了两层网络学习顺序的严格傅里叶排序定理，并证明其隐藏层宽度需指数级于序列长k才能完美泛化；对比揭示RNN（k步串行）与并行多层网络（log k层）的计算复杂度差异；任务完全可控（可任意选择群如Z_n、S_3、D_4）、编码可解析设计（如随机正交、傅里叶基）；虽未报告开源代码，但任务生成器可完全复现；后续值得研究方向包括：连续群推广、噪声鲁棒性、与符号推理系统的接口、以及在真实算法任务（如排序、动态规划）中的迁移验证。

‘Neural Turing Machines’ (Graves et al., 2014); ‘The Neural Noisy Channel’ (Hahn & Keller, 2019); ‘On the Computational Power of Transformers’ (Pérez et al., 2021); ‘Inductive Biases for Deep Learning of Higher-Level Concepts’ (Lake et al., 2017); ‘Learning to Execute’ (Zaremba & Sutskever, 2014); ‘Group Equivariant Convolutional Networks’ (Cohen & Welling, 2016)