学界 | MIT与微软联合论文提出深度API编程器: 可通过API调用合成新程序

机器之心编译

参与：吴攀

让机器学会自动编程一直以来都是人工智能研究界所追求的一个重要目标，甚至被一些人认为是实现真正通用的人工智能的关键。在这方面的研究也一直是层出不穷，比如《深度 | 机器的自我进化：走向自主编程的人工智能（附提交 ICLR 2017 的自动编程论文）》和《学界 | 剑桥与微软提交 ICLR 2017 论文提出 DeepCoder：组合其它程序代码生成新程序》。近日，麻省理工学院和微软研究院的研究者又发布了一篇相关论文，提出了一种可以学习使用 API 编程的方法——深度 API 编程器。机器之心对该论文的部分内容进行了编译介绍，其中重点介绍了该方法的概述部分，更多详情请点击文末「阅读原文」查阅原论文。

我们提出了 DAPIP（Deep API Programmer/深度 API 编程器），这是一个可以根据示例编程（Programming-By-Example）的系统，其可以学习使用 API 来编写执行数据转换任务的程序。我们设计了一种领域特定语言（DSL：domain-specific language），允许 API 输出和常量字符串的任意拼接（concatenation）。该 DSL 由三个 API 系列组成：基于正则表达式的 API、查找 API 和转换 API。然后我们提出了一种全新的神经合成算法（neural synthesis algorithm）来在该 DSL 中搜索与一个给定的示例集一致的程序。该搜索算法使用了最近引入的神经架构来编码「输入-输出示例（input-output examples）」和建模在该 DSL 中的程序搜索。我们的研究表明：在合成基准和真实世界基准上，该合成算法在程序合成上的表现都优于基线方法。

1 引言

总体而言，这篇论文的主要贡献有：

我们设计了一个表达式 DSL，其带有可以编码句法和语义数据转换任务的 API。

我们使用神经架构在该 DSL 中自动学习了一个用于合成程序的的合成算法。

我们在 238 个真实世界 FlashFill 基准和数千个合成基准上评估了我们的系统 DAPIP。

2 目标示例

示例 1：一个 Excel 用户想要将一些名字转换成如图 1 所示的形式。因为一些输入样本有可选的中间名，所以该用户难以找到一个可以用于执行该任务的宏。

图 1：缩写名字的 FlashFill 任务示例。该用户提供了前两个输出，然后学习到的程序自动生成了下面加粗的两项

DAPIP 为这个任务学习到了以下程序：

Concat(GetFirstChar(v), ConstStr(「. 00), GetLastWord(v))

这个学习到的程序使用了属于正则表达式 API 的 GetFirstChar 和 GetLastWord API，其可以基于正则表达式来提取输入字符串中的子字符串。

3 方法概述

现在，我们给出我们的学习在一个 DSL 中合成与示例集一致的程序的端到端系统的概述。我们的系统的训练阶段如图 4 所示，测试阶段如图 3 所示。我们首先设计了一个允许使用常量字符串组成嵌套 API 调用的 DSL。在设计这个 DSL 之前，我们研究了大量真实的字符串转换任务，以使得其有足够的能力编码这些任务。在训练阶段，我们使用了一个程序采样器（program sampler）来统一从该 DSL 中采样大量程序。对于其中每一个程序，我们都使用了一种基于规则的方法来为其构建了 5 个输入字符串，以满足该程序的先决条件。我们通过在这些输入字符串上执行程序来获取输出字符串。

图 3：给定一组输入-输出示例，使用训练好的 R3NN 模型来从该 DSL 中采样程序；即使是在推理的用例中，节点也会以一种独特的离散方式扩展

图 4：基于输入-输出示例，训练该 R3NN 网络来学习 DSL 扩展之上的分布；扩展（expansion）按一种由条件分布确定的特定顺序执行。

在训练阶段，每个被采样的程序与其对应的输入-输出样本被用于训练该 R3NN 模型，这是一个可以根据示例学习该 DSL 中的扩展之上的分布的神经架构。这些示例的编码使用了另一种被称为交叉相关编码器（cross-correlational encoder）的神经架构，其可以产生一个固定维度的向量。该 R3NN 系统将这个输入-输出调节向量（input-output conditioning vector）、该 DSL 和其训练程序作为输入，并被训练用于预测在该 DSL 扩展的集合上的一个条件分布。接下来的扩展是从这个条件分布上采样的，这会导致形成部分树（partial tree），然后重复该流程；你可以在对应的图中看到潜在的指数级节点增长。

然后这个训练好的 R3NN 模型可以在给定一组示例的情况下在该 DSL 中合成程序。这个训练好的模型的输入是那个输入-输出调节向量，然后在该 DSL 扩展的集合上生成一个分布，该扩展很有可能是构建想要的程序所需的扩展。然后该分布会被采样，以在该 DSL 中导出程序，其中扩展的阶数是由该分布确定的，如对应的图中所示，而且该系统会返回首个与该输入-输出示例一致的程序。

4 领域特定语言（DSL）

这个用于基于 API 的字符串转换的领域特定语言的句法如图 5 所示。该语言的顶级结构是 Concat 函数，其返回其参数子字符串 fi 的拼接（concatenation）。子字符串表达式 f 可以是一个常量字符串 s、输入字符串 v 或一个以 f 作为参数的 API 函数的结果。该 Concat 算子允许使用常量字符串来组成 API 调用。该 DSL 由 3 种 API 组成：正则表达式 API R、查找 API L 和转换 API T。

图 5：用于 API 组成的 DSL 的句法

5 用于搜索的神经架构

这种在 DSL 中程序上基于输入-输出示例的神经搜索使用了 [Parisotto et al., 2016] 中介绍的模型。首先，其输入-输出示例被编码成了一个固定长度的特征向量，其目标是在输入和输出字符串之间获取共享的模式。然后这种示例表征会被传递给程序树（program tree）上的一个基于神经树（neural tree）的生成模型，该模型被称为 R3NN，可以用来生成所需的隐藏程序。我们提供了对这两种架构的高层面的概述。