让AI自行编写程序：神经程序合成近期研究进展综述

点击图片上方蓝色字体“慧天地”即可订阅

（点击图片可放大观看，更多精彩请留意文末推荐)

       让计算机程序自动生成新的程序看起来是一个非常「人工智能」的概念，事实上，它也是众多 AI 研究者们努力的方向。2017 年以来，学界就出现了微软的 RobustFill、Bloomberg 和英特尔的 AI Programmer、谷歌大脑的优先级队列训练（PQT）等程序生成方法。近日，来自 UC Berkeley 的 Neel Kant 对于近期神经网络程序生成的发展进行了概述。

       作为一个总体领域，程序合成可以被定义为发展一个满足一系列要求与限制的算法。因为限制条件是被用来确定正确性的标准，所以限制条件是用来定义这个算法的。这些条件可能包括了如速度，空间复杂性还有输入输出正确与否等等运行时间内性能。对于计算机科学系的学生来说，这个概念很熟悉，考试中会经常需要直接写下三元快速排列的代码或者填充不全一段算法的代码。

程序合成有很大的市场。成功的程序在未来可以操控现在人的工作：计算机编程。想象一个可以不用人来调试，重构，转化及整合的世界。甚至可能会出现电脑程序本身不能直接解决问题，但可以提出编程问题并加以解决的世界。在数学和物理学科里，理论证明是需要人来根据已经存在的定理来产生新视角的例子。一个完整的程序合成系统可以跑一个程序来证明或推翻同样的预测，然后这个任务可以被看成非常创新。当计算机视觉瞄准自动化一个生物复杂精细的感知系统，系统合成就是一个瞄准解决问题，逻辑和自动化它自己的领域。

这些非常强大的程序合成系统的应用使这一领域变得非常让人着迷，但是它可能会花费几十年的研究才能达到我们之前所展望的程度。相似的，深度学习已经得到了非常大的关注，而且已经被当成一种重要工具在每一种认知任务中被尝试使用。这篇文章会总结一下这两个领域最近的突破。我们可以看到，这里成就及挑战并存，我们应该谦虚的去追求我们的目标。

图 1. 本论文的叙述结构。

 摘要：近年来，深度学习在很多领域中取得了巨大成功，这使得研究者开始考虑智能系统是否能够解决人类近期才开始考虑的问题：程序合成。这项挑战与目标识别和语音翻译不同，因为其抽象本质和对严谨性的高要求对人类来说都很困难。尽管神经程序合成技术距离解决该问题还很遥远，或者与大多数现有方法相比也不具备太大竞争力，但是它发展很快，深入了解之后就会发现其具备巨大前景。本论文首先探讨程序合成的问题陈述和挑战。然后，我们回顾程序归纳模型的发展历程，以及它们的成败和再发展。最后，我们对比了程序合成的不同研究，并介绍了该领域未来可能有潜力的推荐研究方向。

 2 神经程序归纳模型

研究者提出多种模型范式和架构来解决神经程序归纳中的多种挑战。尽管模型倾向于共享使之易于分类的某些基本属性，但它们在细节方面还有更复杂的结构。这种特殊性可用于解释为什么某些模型可以成功处理一项任务，而其他模型不行。这些细节还提示哪些属性是通用的、哪些属性可以高效解决神经程序归纳任务。

2.1 简介：循环模型

循环神经网络（RNN）因其与序列数据的直观匹配而独树一帜，它们还天然匹配编程任务，因为程序归纳中的输入和输出的规模是可变的。如果任务是程序合成，则输出规模无法根据输入来推断，因此一种自然的计算方法就是一次生成一个输出 token，输出过程中不断更新内部状态。一些任务还可以建立在自然语言输入之上，这样多个 RNN 就可以一起工作。正如我们所见，一些模型使用外部存储资源得到增强，这样 RNN 就可以在不同的时间步发送请求。

2.2 卷积循环

一种非常成功的神经程序归纳模型是神经 GPU[15]，它是一种环路，但在每一个「时间步」中都涉及一个门控卷积运算。输入数据首先嵌入到被称为模型「内部状态」的 3D 张量中，它是 RNN 的隐藏状态的模拟。在时间步 t 上，模型的门控卷积运算通过卷积门控循环单元（Convolutional Gated Recurrent Unit，CGRU）运转。这种机制与 GRU 几乎相同，除了向量上的矩阵乘法被 3D 张量的卷积运算取代。

重要的是，这里有一个「更新」和「重置」门，可用于保存长期记忆信息，就像 LSTM 一样。CGRU 的输出与输入的形态总是相同的。在时间步 t+1 上，神经 GPI 使用的是与 CGRU（t）相同的 CGRU 操作，所以既有卷积也有循环。重点在于，对于某些输入规模 n，神经 GPU 只简单地应用了 n 次 CGRU 操作。在这些运算之后，模型的内部状态被解码以生成程序输出。如果模型在小 n 上能成功运行，则我们希望它在更大的问题规模上通过重复迭代运算也能有效。

卷积循环是一个聪明的想法，但神经 GPU 在实现上会有一些困难。在时间步 t 上，有关问题在所有时间步 1、2……t-1 的信息都会存储在内部状态中，并且我们无法分别观察之前的内部状态。这意味着模型的内部信息包含了处理下一时间步的所有必要信息。

2.3 注意力和指针网络

上一节讨论的问题可以用注意力机制解决。注意力机制很有用，它可以令解码器没有任何瓶颈的情况下访问每个编码器状态的信息。文献 [7] 中的神经机器翻译技术在构成输出时采用这种机制独立地处理每个输入标记。然而，更广义地说，注意力分布可以看成生成非负的归一化分布，例如标准的概率分布。在编码器-解码器范式中，这意味着解码器可以选择性地访问编码器状态，并选择其中最有用的进行处理。在程序归纳和合成中，注意力还可以用于放宽离散运算，例如选择。

图 3. 来自输入字典的关于目标指针的可视化表征。

指针网络（Pointer Networks，Ptr-Nets）[9] 可能是对注意力机制的最直接的非平凡应用，其将注意力机制的 RNN 应用到了神经程序合成中。Ptr-Nets 中涉及的运算总结如下：

• 按序馈送输入到模型中，作为编码器。编码器的隐藏状态 e_1 . . . e_k 被全部记录。

• 一旦输入完成，模型将按序对 {e_1 . . . e_k, d_t} 生成注意力分布，其中 d_t 是当前的解码器隐藏状态。这些分布在训练过程中作为软选择，并且所有分布都可以用于损失函数和梯度下降中。

重要的是，Ptr-Nets 可以求解比训练时使用的输入规模更大的问题。这是泛化能力的直接标志，但很容易推出，随着输入规模量级的增加，模型的性能将大幅降低。这归咎于神经程序归纳模型的存在症结。虽然这些模型可以归纳和训练时使用的输入规模相当的程序，但几乎不能保证其泛化到更大规模程序以及极端情况的性能。

2.4 注意力结合记忆机制

神经图灵机（Neural Turing Machine，NTM）[4] 引入了用外部记忆增强神经网络的概念。实际上，此时神经网络将作为一个控制器，执行记忆的读取和写入命令，而不是用其自身的参数作为记忆的主体。外部记忆的用矩阵 M∈ R^m×n 表示：

• 基于内容求解：对一个读取的向量 v∈ R^n，返回结果 u∈ R^m，其中 u 表示每个内存槽内容和读取向量的相似度。

• 基于定位求解：读取/写入向量 v∈ R^m 表示被读取/写入的关于记忆索引的注意力分布。

图 4. 通过基于内容求解的注意力步骤以获得读取输出 w_t。控制器（LSTM）的输出是完全可微的。

这两个机制非常简单优雅。在每个时间步上，NTM 采用输入并生成读取和写入的命令，将 RNN 控制器的输出与记忆进行交互。然而，对比 Ptr-Nets，该论文中展示的结果是非常初级的，特别是在问题规模方面。而任务本身对于算法也不复杂。尽管更加灵活，且表达力更强，但是 NTM 的训练难度要高得多。

Graves 等人采用了 NTM 的思想，进一步提出了可微神经计算机（Differentiable Neural Computer，DNC）[14]。DNC 可以用多个读写头训练，并有额外关于它的记忆的数据。它有两种特别性质：

• 时间连接（Temporal Linkages）：关于记忆写入顺序的相关信息。它能允许控制器推理数据之间的关系，因为时间连接在算法中是很常用的。

• 内存利用（Memory Usage）：关于记忆的索引是否包含有用信息的信息。理论上，它应该能通知和简化控制器对读取和写入的选择。

图 5. DNC 图示 [14]，注意 b 中有多个读向量（read vector），d 中描述了一些联结。

DNC 仍然使用 RNN 控制器作为其主核心，使用基于注意力的寻址技术。但是，和 NTM 类似，与更简单的模型如 Pointer Nets 相比，DNC 似乎更难执行高效训练。

2.5 内存和预定义基元

之前的所有模型从设计上看都是联结主义。现在，我们将尝试两个模型：神经编程器 [17] 和 Neural RAM [16]，仅使用明确定义的数据变换。具体来说，控制器不向内存发送直接可读／写的指令，而是对数据执行一种可能的一元／二元运算，如基本算术（如加、乘）、逻辑运算符（如相等比较、小于）和聚合运算符（最小、最大）。这两种模型可以能够运行的时间步可多于仅描述问题的必要时间步数。这使得模型能够组合这些基本运算，创建复杂程序。

具体来说，典型的组件有：

• RNN 控制器：使用来自（a）控制器外部和／或（b）存储单元的序列输入，自动以嵌入格式出现。

• 习得的函数可以在（a）可执行的预定义运算和（b）可执行运算的数据上生成注意力分布。

• 可读写数据的存储单元。这还可以作为指定输出位置（Neural RAM）。

两种模型存在一些有趣的差异。神经编程器设计为使用自然语言输入。当然，它们通过 RNN 控制器变成向量化的嵌入格式，但是该模型仍然需要学习英语的语义。类似地，神经编程器具备使之在存储上执行数据库类型运算的模块，该模型可从数据库中返回多个元素。从这个层面上看，神经编程器是为了成为一个自动问答系统，学习回答问题所需的潜在程序。因此，解决方案可能是综合的，但是比问题中存在表征的情况需要的步骤要少一些。

图 6：神经编程器原理图 [17]。输入是表征序列，需要多个时间步来运行。

而 Neural RAM 专门创建高度综合的程序。由于该模型的 14 个预定义模块都是原子性的，因此这些程序可以使用数百个时间步来完成。

好消息是与 NTM 和 DNC 相比，Neural RAM 可创建连贯的程序，可运行更多的时间步。这可能是因为运算并不模糊，即使使用变化比重的注意力来选择运算。当使用误差反向传播进行监督时，该模型理论上知道其中一个基元运算是正确的，无需仅依赖于写入的存储（NTM、DNC 的情况）。该模型还可以选择何时使用 sigmoid 的末尾单元终止程序，何时超出阈值，何时完全停止模型。需要注意的是，与 NTM 相比，任务本身没有那么复杂，Neural RAM 甚至无法尝试 DNC 比较擅长的图形问题。

2.6 函数层级（Function Hierarchy）

在某些情况下，监督信号会非常弱，因此训练数据很容易过拟合。神经编程解释器（Neural Programmer-Interpreter，NPI）[19] 试图通过增加模型的复杂度和监督强度解决这些问题。其中非常重要的进步是令函数在新的堆栈帧中灵活调用子函数。这可以在新的帧中通过将 RNN 控制器的隐藏状态重置为零，将给定嵌入程序、参数和环境作为输入来实现。

这些堆栈帧可以终止，并通过 一个 Sigmoid 末端控制返回调用帧（caller frame），和 Neural RAM 一样。但子函数结束时，调用子函数之前的控制器隐藏状态会被储存起来。当顶层函数结束时，整个模型将结束执行。

图 7. NPI [19] 便条签（左）和执行堆栈轨迹（右）。注意：事实上最低级别的指令是 ACT，这里为读者说明下。

核心概念是 NPI 可以抽象和更高阶地控制该程序。当新的函数和参数被调用时，它可以被表达成一个嵌入格式的向量。这个嵌入格式的向量通过联合在一起的参数嵌入、整体环境和通知子函数未来调用的语境构建而成。

3 归纳任务上的模型性能分析

这部分介绍了四个难度递增的例子。难度来自于所需的控制流级别、目标程序运行时复杂度（如果存在一个人造程序），和训练数据的可用性。

3.1 算术

我们可以比较一下 Neural GPU、NPI 与 NPL，这些模型已经用加法任务测试过了，并且在同样的问题大小环境下完美地进行小数加法。这些模型也实现了函数层级，因此它们的泛化性能更加可靠。

图 8：除了专业课程的学习，神经 GPU 也不能概括概念「运载」（左）。一个单独的问题是不同的初始参数会造成总体性能极大的改变（右）。

3.2 表逻辑

NTM 是第一个试着搞定这一问题的新型神经程序归纳模型。它能完成复制并排序长度为 20 的列表，这一成就在程序合成社区中非常引人瞩目。

Neural RAM 可以复制、融合、交换、倒置一个长度为 50 的列表。

3.3 组合优化

组合优化是一种需要用离散目标组合起来的优化函数问题，并且解决方案是有限制的。该问题首先用指针网络进行测试，测试表明指针网络中的注意力机制对于该问题设置很有用。

3.4 语义查询解析

图 9. Seq2SQL [31] 用指针网络来选择问题词和列名称，以创建 SQL 查询。

最后，该论文还展示了一些可能重塑神经编程归纳模型的策略，若读者希望了解这一部分的内容，请详细查阅原论文中的第四部分。

• 结构化注意力机制
  

• 分层记忆

• 允许递归（Enabling Recursion）

• 贪婪算法 

原文链接请点击文末“阅读原文”

来源：arXiv（机器之心编译，版权归原作者及刊载媒体所有）

荐读

点击下文标题即可阅读

编辑 /  郭梅  审核 / 徐鑫

指导：万剑华教授(微信号wjh18266613129)