原作者：Wojciech Zaremba 和 Ilya Sutskever

原文链接

摘要

拥有长短期记忆单元 (LSTM) 的循环神经网络 (RNN) 使用广泛，因为它们表达能力强且容易训练。我们这里要做的是，通过经验的方式来评估 LSTM 在序列到序列领域的表达能力和学习能力，方法是训练它们对简短计算机程序求值，这是一个传统认为对神经网络太复杂的范畴。我们考虑一类可以使用恒定内存以及从左到右单次扫描求值的简单程序。主要结果是，LSTM 可以学会把以字符表示的这种程序映射为它们的正确输出。值得注意的是，必须使用课程学习，并且虽然课程学习已经被证明是无效的，我们发展了一种课程学习的新的变型，提高了我们的网络在所有实验条件下的性能。改进后的课程对一个加法问题效果显著，让训练一个 LSTM 以 99% 的精度做两个 9 位数的加法成为可能。

引言

计算机程序的执行涉及到一些非平凡的概念。为了执行一个程序，系统必须理解数值操作，if 语句，变量赋值，操作符合，以及许多别的东西。

我们展示带有长短期记忆的循环神经网络在 Sutskever et al. (2014) 的序列到序列框架内可以准确对简短程序求值。LSTM 一个字一个字地读入程序并计算其输出。我们考虑一类特别的计算机程序，它们可以在线性时间内求值并且只需要恒定的内存；这是因为 LSTM 只读入程序一次，并且其存储容量有限。

我们发现训练 LSTM 执行程序是件困难的事情，于是我们使用课程学习来简化学习问题。我们设计了一个课程程序，其性能超过了不使用课程学习的传统方法，以及 Bengio et al. (2009) 的朴素课程学习策略 (第 4 节)。我们提供了一个关于为什么我们的程序比朴素课程策略有效的可能解释 (第 7 节)。

最后，在课程学习策略之外，我们考虑了两种进一步简化序列到序列学习问题的简单变换。结果表明，在许多情形，反转输入序列 (Sutskever et al. 2014) 以及复制输入序列提高了 LSTM 在记忆任务上的表现。

重现本工作大部分实验的源代码可在 这个链接找到。 

#Input:
    j=8584
    for x in range(8):
        j+=920
    b=(1500+j)
    print((b+7567))
#Target: 25011.

#Input:
    i=8827
    c=(i-5347)
    print((c+8704) if 2641<8500 else 5308)
#Target: 12184.

图 1: 用来训练 LSTM 的程序示例。每个程序的输出是一个整数。整数结尾的“点”表示结束，LSTM 必须要能给出这个点。

相关的工作

已经有相关研究使用树状神经网络 (也叫递归神经网络) 对符号数学表达式和逻辑公式求值 (Zaremba et al. 2014a; Bowman et al. 2014; Bowman 2013)，这些工作精神上与本工作相近。计算机程序比数学或逻辑表达式更复杂，因为后两者都可被合适的计算机程序模拟。

从方法论的角度看，我们使用循环神经网络 (Sutskever 2014; Mikolov 2012; Sutskever 2013; Pascanu et al. 2013) 把程序求值任务表述为一个序列到序列学习问题。循环神经网络的其它有趣应用包括语言识别 (Robinson et al. 1996; Graves et al. 2013)，机器翻译 (Cho et al. 2014; Sutskever 2014)，手写识别 (Pham et al. 2013; Zaremba et al. 2014b)，以及其它更多。

Maddison & Tarlow (2014) 训练了一个程序文本的语言模型，而 Mou et al. (2014) 使用一个神经网络来判定两个程序是否等价。这两种方法都需要程序的语法树，而我们的模型只需要程序源代码作为字符串输入。

程序输出的预测要求模型能处理变量赋值导致的长程依赖。为此我们使用了长短期记忆模型 (Hochreiter & Schmidhuber 1997)，尽管有许多循环神经网络的其它变型在长程依赖任务上表现不错 (Cho et al. 2014; Jaeger et al. 2007; Koutnik et al. 2014; Martens 2010; Bengio et al. 2013)。

起初我们发现难以训练 LSTM 精确对程序求值。程序的组合性质提示我们如果事先教会 LSTM 关于每个运算符的知识以及组合规则，应该能让它们学习更快。这个方法可以通过课程学习实现 (Bengio et al. 2009; Kumar et al. 2010; Lee & Grauman 2011)，具体做法就是制定一套逐渐提高提供给 LSTM 的样本的难度等级的规则。这部分地受到人类和动物的启发，在面对艰难但可以处理的任务时科学学得更快。可惜的是，Bengio et al. (2009) 的朴素的课程学习策略有时候反而有害。我们的一个主要贡献是构建了一套新的课程学习策略，极大地提高了我们考虑的每个实验设置中训练的速度和质量。

特定类型的程序

#Input:
vqppkn
sqdvfljmnc
y2vxdddsepnimcbvubkomhrpliibtwztbljipcc
#Target: hkhpg

图 2: 一个样例程序及其输出；字符都是乱的。这个示例阐释了我们的神经网络面临的难题。

我们用一类可用线性时间和恒定内存求值的短程序来训练循环神经网络。这个限制来自 RNN 自身的计算结构，它只能对程序扫描一次，且其存储空间有限。我们的程序使用 Python 的语法，并且基于少量操作及其复合 (嵌套) 构造。我们允许下述操作：加，减，乘，变量赋值，if 语句，for 循环，但禁用了双重循环。每个程序以单个 print 指令结束，其输出是个整数。图 1 给出了两个例子。

我们从以长度和嵌套深度作为参数的一族分布中选取程序。长度参数是出现在程序中的整数的数字个数 (所以整数从 \([1,10^{\text{length}}]\) 中均匀采样)。附录给出了产生程序的伪代码。比如，图 1 给出的两个程序对应于长度为 4 以及嵌套深度为 3。

我们对乘法的操作数和 for 循环的范围做出了限制，因为它们对模型提出较多难题。我们限制乘法的一个操作数和 for 循环的范围从 \([1, 4\cdot\text{length}]\) 中随机取出。我们之所以这么做，是因为我们的模型可以执行线性时间计算，而一般的整数乘法需要超线性时间。相同的理由适用于 for 循环，因为嵌套循环可以实现整数乘法。

嵌套参数是我们允许把各种操作相互组合的最大次数。较深的嵌套意味着较深的语法树。对于 LSTM 来说嵌套让任务变得更难，因为 LSTM 没有一个自然的办法来处理复合性，不像树状神经网络。令人吃惊的倒是 LSTM 竟然能处理嵌套表达式。程序也不接受外部输入。

值得强调的是 LSTM 每次读入输入的一个字符，并且每次输出一个字符。对模型来说一开始这些字符是没有含义的；比如，模型不知道“+”表示加法，或者 6 后面是 7。事实上，打乱输入的字符不会影响模型的解题能力。图 2 给出了一个这样的例子，展示了这个任务的难点。

最后，我们希望确认我们的程序不是可以平凡求值的，方法是保证来自 Benford 定律 (Hill 1995) 的偏向不是太强。我们的设置有 12 个可能的输出字符，包含 10 个数字，一个结尾标记，一个负号。输出的分布不是均匀的，这可通过注意到负号和点号与其它数字出现的频率不同。如果我们假定输出字符相互独立，猜中正确字符的概率是～8.3%。最常出现的数字是 1，其出现几率对所有输出是 12.7%。

但是，首字符的分布存在偏向。存在 11 个可能性，随机猜中的几率为 9%。最常见的字符是 1，它在第一位出现的几率是 20.3%，这意味着强烈偏向性。但这个值仍然远小于我们的模型预测精度。并且，第一个输出位置的第二可能字符的出现几率是 12.6%，与其它位置的字符概率分布不可区分。最后一个字符总是结束符。倒数第二个位置最常见的是 4，出现几率为 10.3%。这些统计通过 10000 个随机生成的程序组成，长度为 4，嵌套为 1。不存在强烈偏向意味着当嵌套更深以及字符更长时偏向会更少，这点得到了数值验证。

译者注：窃以为这个分析意义不大。我觉得更应该看的是，是否程序的结果可以在完全不理解程序的前提下就能得到正确答案，比如有没有可能通过把第一个出现的数字加上第二个出现的数字与第三个数字的乘积就得到正确答案，换句话说有没有可能神经网络只是计算了程序中出现的数字的简单函数？我们期望的应该是，神经网络能够不仅仅只是计算了程序源代码中出现的数字的某种简单函数。 

#Input:
print(398345+425098)
#Target: 823443

图 3: 对于加法任务的典型例子。

加法任务

不容易直观地评判一个 LSTM 在程序求值任务上的精度。比如，不清楚 50% 的精度是否让人印象深刻。因此，我们用更熟悉的加法任务来评估我们的模型，难度通过输入的长度来判定。我们只考虑两个相同长度的数的加法 (图 3)，两个数从 \([1,10^{\text{length}}]\) 里均匀取出。相同长度的数的加法比不同长度的加法容易，因为模型不需要对齐它们。

记忆任务

就是把输入原封不动输出。还考虑了两种简单的提高性能的办法：输入反转 (Sutskever et al. 2014) 和输入倍增。

输入反转是在把输入颠倒后仍然要求输出颠倒之前的。这样做增加了许多短程依赖，让 LSTM 更容易学习。

输入倍增是把输入重复两遍，而仍然要求输出倍增之前的。这可以提高性能，因为相当于增加了纠错能力。

课程学习

当长度和嵌套深度两个参数变大，学习问题将会变得几乎不可实现。这提示也许应该先从小的长度和嵌套深度开始学习。

无课程学习 一开始长度和嵌套深度就固定为给定值。从统计的角度讲这么做是最好的，因为一般应该让训练数据集的分布跟测试分布一样。

朴素课程学习 从长度和嵌套深度为 1 开始。当学习进程不再提高之后，把长度增加 1 直到达到事先给定的长度；然后把嵌套深度增加 1 而把长度设回 1。当然也可以交换两个顺序。这种方法有时候还不如不进行课程学习。

混合策略 为了生成随机样本，先从 \([1,a]\) 中取出随机长度，从 \([1,b]\) 中取出随机嵌套深度，两个值与每个样本独立。混合策略使用容易和困难例子的均衡混合，因此在每次训练，训练样本的一大部分会对 LSTM 有恰当的难度。

结合混合策略与朴素策略 每个训练样本要么来自朴素策略，要么来自混合策略。结果就是，每次网络总是会接触一部分较难的例子，这是与朴素策略的最大不同。这个策略总是比朴素策略好，也一般但不总是比混合策略好。

LSTM

除非特别说明，所有矢量都是 \(n\) 维。令 \(h^l_t\in\mathbb{R}^n\) 是第 \(t\) 步第 \(l\) 层的一个隐含态。令 \(T_{n,m}: \mathbb{R}^n \rightarrow \mathbb{R}^m\) 是一个有偏的线性映射 (\(x\rightarrow W x + b\))。令 \(\odot\) 是按元素的乘法，\(h^0_t\) 是对 LSTM 在第 \(t\) 步的输入。我们使用第 \(L\) 层的活化来预测 \(y_t\)，这里 \(L\) 是 LSTM 的深度。

LSTM 的结构允许它可以相对容易地对长期依赖的问题进行训练。长期记忆存储在记忆单元 \(c^l_t\in\mathbb{R}^n\) 中。尽管许多 LSTM 架构在它们的连接结构和活化函数方面略微不同，所有的 LSTM 都有方便存储长期信息的加性记忆单元。我们使用下面方程描述的 LSTM (来自 Graves et al. 2013)： \[ \text{LSTM}:\ h^{l-1}_t, h^l_{t-1}, c^{l}_{t-1} \rightarrow h^l_t, c^l_t \] \[ \begin{pmatrix} i\\f\\o\\g \end{pmatrix} = \begin{pmatrix} \mathrm{sigmoid}\\ \mathrm{sigmoid}\\ \mathrm{sigmoid}\\ \tanh\\ \end{pmatrix} T_{2n,4n} \begin{pmatrix} h^{l-1}_t\\ h^l_{t-1} \end{pmatrix} \] \[ c^l_t = f \odot c^l_{t-1} + i\odot g \] \[ h^l_t = o \odot \tanh(c^l_t) \]

实验

所有实验用相同的 LSTM 架构。

我们的 LSTM 有两层，每个实验展开 50 步。每层有 400 个单元，参数初始化为 \([-0.08,0.08]\) 之间的随机数。这意味着一共 2.5M 个参数。隐含态初始化为 0。用当前 minibatch 的最终隐含态作为下一个 minibatch 的初始隐含态。这样每个 minibatch 可以分离出程序及其输出。采用的 minibatch 大小为 100。限制梯度 (通过 minibatch 的大小归一化) 不超过 5。学习速率保持为 0.5 直到达到目标长度和嵌套深度。

达到目标精度 (95%) 后我们把学习速率减小 80%，直到对训练集不能再提高；之后再减小，如此进行下去直到学习速率小于 0.001。对于拷贝任务，学习 20 个阶段后停止训练，每个阶段有 0.5M 个样本。

训练从长度和嵌套深度为 1 开始。保证训练、检验，以及测试数据集是分离的。这通过计算程序的 hash 值保证。

关于错误率的重要说明 当预言第 \(i\) 个数字时，LSTM 被提供给了前 \(i-1\) 个数字的正确值。这与之前 Sutskever et al. (2014) 生成整个输出的做法不同，后者的精度肯定会低很多。译者注：这是搞什么鬼？意思是只计算答案的一个数字？作者对最重要的这一点语焉不详。

隐含态分配假设

组合策略降低了改变记忆结构的需求。朴素策略提供的例子有助于学习输入-输出映射的中间表示，而来自混合策略的例子阻止了网络把所有记忆用于简单例子，因此排除了重构记忆的需求。

批判

完美的加法不容易。

如果不要求完美加法，则有各种近似手段。比如忽略进位，或者记住所有的两位数加法，然后把多位数加法分解为两位数加法。

打算今后让训练数据和测试数据来自不同的分布。

译者简评

这篇文章写得不太清楚，比如究竟是如何比较输出结果和正确结果的？另外，我觉得这个神经网络很可能只是提取出程序中的数字做了简单的函数运算，换句话说神经网络并没有“理解”输入程序。这个问题跟围棋程序是否“理解”围棋类似。