神经 GPU 学习算法
Neural GPUs Learn Algorithms
Łukasz Kaiser · Ilya Sutskever
中文摘要
从示例中学习算法是一个被广泛研究的基础问题。近期用神经网络处理该问题,尤其是神经图灵机(Neural Turing Machines, NTM)。这类完全可微的计算机通过反向传播学习自身编程。尽管有吸引力,NTM 因顺序性存在弱点:不并行,且展开时深度大而难以训练。提出一种神经网络架构解决该问题:神经 GPU(Neural GPU)。它基于一种卷积门控循环单元,与 NTM 一样具有计算通用性。与 NTM 不同,神经 GPU 高度并行,更易训练且运行高效。算法的一个关键特性是能处理任意大小的输入。神经 GPU 可在算法任务的短实例上训练,并成功泛化到长实例。在多项任务上验证,包括二进制表示数字的长加法与长乘法。在最多 20 位的数字上训练神经 GPU,测试时即使数字长得多也未观察到任何错误。为取得这些结果,引入一种训练深度循环网络的技术:参数共享松弛(parameter sharing relaxation)。还发现少量 dropout 与梯度噪声对学习和泛化有很大正面影响。
关键要点
- 01问题:NTM 因顺序性不并行、展开深度大而难训练,需并行且计算通用的架构。
- 02方法:提出基于卷积门控循环单元的神经 GPU,高度并行且计算通用。
- 03结果:在最多 20 位二进制数上训练,测试更长数字的长加法与长乘法均无错误。
- 04技术:引入参数共享松弛训练深度循环网络,少量 dropout 与梯度噪声提升学习与泛化。
解读
内容由 AI 生成,仅供参考。如发现错误,欢迎反馈。
原始英文摘要
Learning an algorithm from examples is a fundamental problem that has been widely studied. Recently it has been addressed using neural networks, in particular by Neural Turing Machines (NTMs). These are fully differentiable computers that use backpropagation to learn their own programming. Despite their appeal NTMs have a weakness that is caused by their sequential nature: they are not parallel and are are hard to train due to their large depth when unfolded. We present a neural network architecture to address this problem: the Neural GPU. It is based on a type of convolutional gated recurrent unit and, like the NTM, is computationally universal. Unlike the NTM, the Neural GPU is highly parallel which makes it easier to train and efficient to run. An essential property of algorithms is their ability to handle inputs of arbitrary size. We show that the Neural GPU can be trained on short instances of an algorithmic task and successfully generalize to long instances. We verified it on a number of tasks including long addition and long multiplication of numbers represented in binary. We train the Neural GPU on numbers with upto 20 bits and observe no errors whatsoever while testing it, even on much longer numbers. To achieve these results we introduce a technique for training deep recurrent networks: parameter sharing relaxation. We also found a small amount of dropout and gradient noise to have a large positive effect on learning and generalization.
1. 问题与价值
这篇论文要解决的是「让神经网络从例子中学会可泛化的算法」这一类问题。具体目标不是只记住训练样本,而是训练短序列后,能在明显更长的输入上仍按同一算法给出正确输出。论文重点验证的是二进制长加法和二进制长乘法:输入是两个以低位优先排列的二进制数,中间用分隔符连接;输出是加法或乘法结果的二进制串。
这个问题重要,是因为普通序列到序列模型擅长统计模式,却不一定擅长需要精确状态传递的算法任务。长乘法尤其关键,因为它的计算量随输入长度超线性增长,且需要跨位传递进位、部分积和最终求和。若一个神经网络能在 20 位数字上训练,却在 2000 位数字上仍无错误,说明模型学到的不是局部模式,而是某种可外推的计算结构。
受益对象可以分三类理解:
2. 已有工作的不足
在 Neural GPU 之前,论文讨论了几类代表性做法,它们的不足不是「完全不能用」,而是在算法泛化、并行性和可训练性上各有硬伤。
LSTM+A:注意力机制允许解码时查看输入任意位置,解决了固定瓶颈,但论文实验显示它在算法任务上仍不稳定。原文表格中,badd@25只有 73% 完全正确,badd@100降到 0%;长乘法bmul@20也是 0%,甚至不能拟合训练数据。LSTM+A更适合某些算法任务,论文报告它在加法上能到 100 位时仍有 88% 完全正确,但到 200 位降到 0%,且不能用于长乘法任务。因此,旧方法的具体不足可以概括为:注意力模型不够精确,NTM 太串行太深,stackRNN 泛化长度有限,硬注意力模型训练困难。
3. 重建作者的思考路径
如果从旧方法的不足出发,而不是直接接受 Neural GPU,思路可能会这样展开。
第一步,会先问:为什么
LSTM+A学不会长乘法?它已经能看输入任意位置,问题可能不在「看不到」,而在「没有可并行推进的内部状态」。长乘法需要同时维护许多部分积、进位和中间结果。单条循环状态每步只更新一个向量,要把这些信息都塞进一个向量,长度一长就崩溃。第二步,会想到 NTM。NTM 有外部记忆,理论上能模拟程序。但矛盾马上出现:NTM 的记忆读写是顺序的,每一步依赖上一步,训练时展开成很深的时间序列,梯度路径很长;软注意力又要求每步扫描全部记忆,计算和内存开销都高。也就是说,NTM 获得了表达力,却牺牲了并行性和优化稳定性。
第三步,可能会想:能不能把「程序状态」从一维向量变成二维图像?因为许多算法天然有二维结构,例如乘法可以看成部分积按位错位排列,加法可以看成相邻位之间的局部进位传递。如果状态是二维的,就可以用局部卷积更新,而不是让一个循环单元串行处理所有位。
第四步,会撞上可微性矛盾。离散自动机擅长表达算法,但不可微;普通卷积网络可微,但没有时间状态和门控。于是会考虑把卷积和门控循环单元结合:每个位置都有一个状态,下一步状态由局部邻域卷积和门控更新决定。这样既保留可微性,又让大量位置可以并行更新。
第五步,会撞上训练深度问题。即使每一步是并行的,时间步仍然多,参数又需要在时间上共享。参数共享让模型能处理任意长度,但也让优化更困难:同一个参数要同时负责早期进位、中期部分积、后期归约,梯度可能互相冲突。于是会想到「先放松共享,再拉回共享」:训练时让不同时间步使用不同参数副本,降低优化难度;同时加入一个把各副本拉向平均值的项,最后再合并成共享参数。
第六步,会撞上泛化脆弱问题。论文报告只有少数随机种子能泛化到 2000 位。为了让更多模型稳定泛化,会尝试正则化和噪声。常规经验认为循环连接上的 dropout 有害,但这里状态是二维图像且每步都作用在整体状态上,小比例 dropout 反而迫使内部表示冗余化,提升泛化。
与论文实际路径的差异:上面这条推演从「注意力不够精确」推到「二维并行状态」,再推到「放松参数共享」和「小 dropout」。论文实际路径大体也沿这个方向,但更强调与离散二维自动机的类比,并用 Atrubin 算法说明二维并行计算可以完成长乘法;同时论文把参数共享松弛、curriculum、gradient noise、dropout 作为一个整体训练制度,而不是单独一个技巧。
4. 核心 intuition
可以把 Neural GPU 想象成一排排工人同时处理一条长流水线。每个工人只看自己和左右邻居手里的零件,但所有工人每一步同时更新自己的记录。这样,信息不需要靠一个人从头跑到尾,而是像波纹一样在二维状态里传播。
这个类比能对上机制:
kw = kh = 3。m维向量。长加法中,进位就是相邻工人之间传递的小纸条;长乘法中,部分积错位相加就是多行工人同时搬运、合并。并行局部更新让原本需要长串行程序的操作变成许多短局部操作,这正是它比 NTM 更容易训练、也更容易泛化的直觉来源。
5. 方法 pipeline 举例
用论文给出的加法例子走一遍:
输入:
1 0 1 0 + 0 1 1 1输出:
1 1 0 0 1它表示低位优先二进制下:
1 0 1 0对应1 + 4 = 50 1 1 1对应2 + 4 + 8 = 141 1 0 0 1对应1 + 2 + 16 = 195 + 14 = 19完整流程如下。
s0。论文配置中宽度w = 4,每个位置有m = 24维向量。这个例子每个数有 4 个比特,序列长度按论文公式n = 2d + 1计算,得到2 × 4 + 1 = 9。因此s0的形状可理解为4 × 9 × 24。E写入第一列。论文写法是s0[0, k, :] = E[i_k],其余位置为 0。这里i_k是第k个输入符号,例如0、1、+。s0连续应用n = 9步时间更新。每一步内部先经过第 1 层 CGRU,再经过第 2 层 CGRU:s_{t+1} = CGRU_2(CGRU_1(s_t))其中每个 CGRU 会看局部邻域,更新每个位置的状态。此时中间结果无法用简单文字精确列出,因为它是4 × 9 × 24的连续张量;定性上,它表示「每一位及其邻域在时间上的进位和求和状态」。s_fin的第一列,对每个位置乘以输出矩阵O得到 logits:l_k = O s_fin[0, k, :]然后选择最大项作为输出符号:o_k = argmax(l_k)1 1 0 0 1。模型若在训练后对这类短例子完全正确,再经 curriculum 和参数共享松弛训练,论文报告它能泛化到 20 位训练长度,并在测试中到 2000 位仍无错误。如果用乘法例子:
输入:
0 1 1 0 · 0 1 0 1输出:
0 0 1 1 1它表示:
0 1 1 0对应2 + 4 = 60 1 0 1对应2 + 8 = 106 × 10 = 6060 = 32 + 16 + 8 + 4,低位优先二进制为0 0 1 1 1Neural GPU 的处理方式仍然是把输入嵌入到二维 mental image,用局部卷积和门控在多个时间步传播部分积与进位,最后从第一列读出输出。
6. 核心数学推导
这里假设读者有本科线性代数和概率论基础。论文公式在提取中有少量损坏,下面只解释能辨认的部分;无法辨认处会明确说明。
GRU 的基础
GRU 接收输入向量
x和当前状态向量s,输出新状态。论文给出:GRU(x, s) = u ⊙ s + (1 − u) ⊙ tanh(W x + U (r ⊙ s) + B)其中:
x是当前输入向量。s是当前状态向量。u是 update gate,取值在 0 到 1 之间,控制保留多少旧状态。r是 reset gate,控制计算候选状态时使用多少旧状态。⊙是逐元素乘法。W、U、B是可学习参数。tanh把候选状态压到负一到一之间。1 − u表示不保留旧状态的比例。门由下式产生:
u = σ(W′ x + U′ s + B′)r = σ(W″ x + U″ s + B″)其中
σ是 sigmoid,W′、U′、B′、W″、U″、B″是可学习参数。一句话总结:GRU 用两个门决定「保留多少旧状态」和「用多少旧状态参与新计算」。
从 GRU 到 CGRU
Neural GPU 不用一维状态,而用二维 mental image
s,形状可理解为w × h × m。论文中h对应输入长度方向,w是额外宽度,m是每个位置的向量维度。CGRU 形式为:
CGRU(s) = u ⊙ s + (1 − u) ⊙ tanh(U ∗ (r ⊙ s) + B)其中:
U ∗ s表示卷积核组U对状态s做卷积。u和r仍然是门。x不再每步提供新输入;所有输入一开始就写入s0。门为:
u = σ(U′ ∗ s + B′)r = σ(U″ ∗ s + B″)卷积定义为:
U ∗ s[x, y, i] = ∑_{u=⌊−kw/2⌋}^{⌊kw/2⌋} ∑_{v=⌊−kh/2⌋}^{⌊kh/2⌋} ∑_{c=1}^{m} s[x + u, y + v, c] · U[u, v, c, i]符号解释:
x和y是 mental image 中的位置坐标。i是输出通道编号。kw和kh是卷积核宽和高。c是输入通道编号。s[x + u, y + v, c]是邻域位置上的旧状态。U[u, v, c, i]是卷积核参数。一句话总结:CGRU 把 GRU 中的矩阵乘法换成了局部空间卷积,让每个位置根据邻域并行更新。
时间展开
论文配置中层数
l = 2,时间步数等于输入长度n。更新为:s_{t+1} = CGRU_l(CGRU_{l−1} ... CGRU_1(s_t) ...)最终状态是
s_fin = s_n。输出读取为:
l_k = O s_fin[0, k, :]o_k = argmax(l_k)训练损失是对 logits 做 softmax,然后使用目标符号的负对数概率。
门截断
论文使用标准 sigmoid 的截断版本:
σ′(x) = max(0, min(1, 1.2σ(x) − 0.1))这里:
1.2和0.1是论文给出的常数。参数共享松弛
论文没有给出完整公式;原文此处公式无法辨认。其机制可用符号表达为:训练时使用
r组参数副本,第t步使用第i组,当t mod r = i。论文说常用r = 6。为了最终合并参数,可以想象在任务损失上加一个拉回项:
L = L_task(θ_1, ..., θ_r) + pull · ∑_i ∥θ_i − θ_avg∥^2其中:
θ_i是第i组参数。θ_avg是所有组的平均参数。pull是 relaxation pull。∥ · ∥表示某种距离范数。论文说
pull为 0 时各副本近似独立;pull大时损失迫使参数统一。训练过程中,每当 curriculum 推进,就把pull乘以一个 relaxation pull factor;达到最大长度后,平均所有副本并继续用单组共享参数训练。一句话总结:参数共享松弛先把「一个参数负责所有时间步」的难题拆成多个较容易的局部参数,再把它们拉回同一个可泛化参数。
7. 实验设计
论文实验围绕算法任务泛化展开。
数据集与任务
badd:输入两个同长度二进制数,中间用+分隔,低位优先。符号集为{0, 1, +, PAD}。两个d位数的完整序列长度按论文公式为n = 2d + 1。bmul:输入两个同长度二进制数,中间用·分隔,低位优先。符号集为{0, 1, ·, PAD}。序列长度同样为n = 2d + 1。2 × 20 = 40位;测试输入最多 2000 位。基线模型
LSTM+A:带注意力的序列到序列 LSTM,3 层,每层每单元 64 个 LSTM 单元,论文说约 200k 参数。stackRNN:来自 Joulin 与 Mikolov 的 stack-augmented recurrent network,只用于加法比较。论文说它按原代码方式训练,nmax = 41,并运行 729 次取最好结果。m = 24,论文说约 30k 参数。指标
主要指标是完全正确输出序列的比例,即一个测试样本的每一位都必须正确。原文表格中:
badd@20:Neural GPU 100%,stackRNN 100%,LSTM+A 100%badd@25:Neural GPU 100%,stackRNN 100%,LSTM+A 73%badd@100:Neural GPU 100%,stackRNN 88%,LSTM+A 0%badd@200:Neural GPU 100%,stackRNN 0%,LSTM+A 0%badd@2000:Neural GPU 100%,stackRNN 0%,LSTM+A 0%bmul@20:Neural GPU 100%,stackRNN 不适用,LSTM+A 0%bmul@25:Neural GPU 100%,stackRNN 不适用,LSTM+A 0%bmul@200:Neural GPU 100%,stackRNN 不适用,LSTM+A 0%bmul@2000:Neural GPU 100%,stackRNN 不适用,LSTM+A 0%消融与附加实验
36 = 729,上标在提取中损坏,无法完全辨认;但729本身出现,论文说明每次报告结果对应 729 个模型运行。m = 24的 Neural GPU 难以拟合训练集;有它,729 次运行中几乎所有模型能拟合训练数据。m变化:论文尝试m = 24、m = 32、m = 64、m = 128,结果类似;m = 128使更多模型泛化。m = 64的模型,也能泛化到 2000 位乘法。m = 128可学会其他十进制任务。10000 × 20 = 200000个训练样本。论文还尝试每长度 100 个样本,合计约100 × 20 = 2000个样本;加法可泛化到 200 位,但乘法不行。实验能否支撑结论
能支撑的核心结论是:在该实验设置下,Neural GPU 比
LSTM+A和 stackRNN 更能从短训练长度泛化到长测试长度,尤其在长乘法上达到 2000 位无错误。但支撑范围有限:
8. take-aways
可以带走的结论如下。
LSTM+A在 20 位就为 0%,说明注意力序列模型在这里无法拟合或泛化。LSTM+A强,但泛化边界明显:badd@100为 88%,badd@200降到 0%;Neural GPU 在badd@2000仍为 100%。m = 24的模型难以拟合训练集;有它时 729 次运行中几乎所有模型能拟合训练数据。10000 × 20 = 200000个样本;进一步降到每长度 100 个样本,合计约100 × 20 = 2000个样本时,加法仍可泛化到 200 位,但乘法不行。9. 最脆弱的假设
最脆弱的假设是:短序列上观察到的无错误泛化,可以外推到任意长度或至少远超 2000 位的长度。论文证据是经验性的:在实现允许范围内测试到 2000 位乘法,并报告 100% 完全正确;其他任务测试到 4001 位,也报告未发现错误。序列长度 4001 可由论文公式得到:
2 × 2000 + 1 = 4001。但这个证据不等于数学证明。一旦输入长度超过模型训练和测试覆盖范围,局部卷积传播、门控饱和、curriculum 推进和参数共享合并都可能失效。尤其论文自己报告 729 次运行中只有少数模型能泛化到 2000 位,说明泛化对随机种子和超参数敏感。
其他脆弱假设包括:
w = 4、m = 24、kw = kh = 3、l = 2等配置是经验选择。论文说宽度 1 加m = 64也能工作,但并未证明这些配置对所有算法任务最优。pull和 factor 需要课程推进。若 curriculum 阈值设置不当,模型可能过早合并参数或过晚拟合。论文是否给出这些假设成立的证据?对 2000 位乘法,它给出了测试证据;对「任意长度泛化」,它没有给出证明。对「十进制也能工作」,实验反而给出负面证据。对「所有随机种子都稳定泛化」,论文讨论部分报告通常只有少数模型能到 2000 位,因此也不成立。
10. 一周最小复现
如果只有一张 24GB 消费级显卡和一周,不建议直接复现 2000 位乘法,因为时间展开长、网格搜索大、随机种子敏感。更稳的最小复现目标是复现「短训练长度到较长测试长度的泛化」,优先做二进制加法。
具体步骤如下。
l = 2w = 4m = 24kw = kh = 3ε的写法提取损坏,无法辨认;复现时可按工程默认或自行选择,但不应声称与原文完全一致d = 20n = 2 × 20 + 1 = 41100个样本,总训练样本约100 × 20 = 200010000个样本,总训练样本约10000 × 20 = 200000r = 6组参数副本,逐步增大 relaxation pull,最后平均合并3 × 4 = 12个配置badd@20应接近 100% 完全正确badd@200达到 100%badd@100或badd@200都大幅下降,说明复现失败,应检查 CGRU 并行更新、curriculum、参数共享松弛和 dropoutbmul@20m = 24难以拟合训练集,因此乘法最小复现必须包含松弛机制11. 反例设计
要推翻本文核心主张,可以设计一个「独立复现失败」实验。核心主张是:Neural GPU 在短训练长度上学到的长乘法算法,能在远大于训练长度的输入上无错误泛化。论文证据是训练到 20 位,测试到 2000 位完全正确。
反例实验如下。
l = 2w = 4m = 24kw = kh = 32 × 20 + 1 = 412000 + 1 = 2001位这个反例实验成功的关键不是证明 Neural GPU 一定错,而是证明论文主张的边界比标题式结论更窄:它可能只在特定二进制任务、特定超参数、特定随机种子集合和特定长度范围内成立。
12. 落地判断
这项成果离普通用户「直接可用」还较远,但对研究团队和应用开发者有明确参考价值。
普通用户能拿到什么
普通用户不能把这篇论文中的模型直接当成长二进制计算器使用。原因包括:
普通用户能得到的主要是认知更新:神经网络可以通过并行局部更新学习某些精确算法,而不是只能做统计近似。
应用开发者能拿到什么
应用开发者可以把 Neural GPU 当作一种候选架构,用于以下场景:
距离可用还差几步:
100 × 20 = 2000个样本可泛化到 200 位,但乘法需要更大规模;论文主实验约为10000 × 20 = 200000个样本。研究团队能拿到什么
研究团队可以拿走三个可继续推进的方向:
成本量级
论文给出的成本线索是:
LSTM+A约 200k。n = 32、m = 64、2 层模型展开后有 128 层 CGRU,前后向一步约 0.6 秒;这是论文实验硬件上的报告,不能直接外推到所有设备。10000 × 20 = 200000,但 2000 位泛化需要 729 次运行中的少数成功模型。因此成本不是「模型参数量大」,而是「搜索空间大、时间展开长、成功种子少」。
最大的坑
最大的坑是:把论文中的 100% 当成架构必然性质。实际报告依赖小 dropout、gradient noise、curriculum、参数共享松弛和大量随机运行。若只训练一个模型、只用默认超参数、或换到十进制输入,很可能无法复现长乘法无错误泛化。另一个坑是长度外推没有理论保证;论文测试到 2000 位,不能证明 2001 位或更长输入仍安全。