【论文笔记】Program synthesis using natural language

摘要

随着计算机进入千家万户，人机交互变成了一项极其普遍的活动。一些重复性或专业性任务通常需要创建小型的、一次性的程序。为了实现这些一次性程序，终端用户(End-User)可能需要花费大量时间和精力去学习各种领域特定语言(Domain Specific Language，DSL)，这为用户带来了极大的不便。

在本文中，作者提出了一个通用框架。该框架可以构建一种能够利用自然语言(Nature Language，NL)合成目标 DSL 的程序合成器(Synthesizer)。该框架以 DSL 定义和训练数据(NL/DSL 对)为输入，通过训练使用最优权重和自然语言处理(Nature Language Processing，NLP)的若干特征的、基于关键词编程翻译的分类器，实现了目标程序合成器的构建。该框架可以应用于重复文本编辑、智能教学系统和航班信息查询三个领域。通过本文提供的框架，作者利用 1200 余个英语描述分别构建出三个针对不同领域的程序合成器。预期程序(Desired Program)在程序合成器输出的合成程序列表中排在 Top-1 和 Top-3 的概率分别为 80%和 90%。

关键词：自然语言；领域特定语言；程序合成

1 引言

程序合成(Program Synthesis)是一个根据给定的规格(Specification)、以某种基础领域特定语言(DSL)为原料自动合成程序的过程。传统的程序合成依赖完全规格(Complete Specification)。由于编写完全规格存在困难，同时结果验证(即验证合成得出的程序是否满足规格)也十分不易，因此传统程序合成并没有得到广泛的应用。

最近，相关研究尝试在程序合成过程中使用样例(Examples)作为指导合成的规格。该类研究已经得到了广泛应用，其原因在于：相比于完全规格，样例规格往往更容易获得。比较典型的例子有实例编程(Programing by Example，PBE)系统。由于样例需要与准确的程序意图相结合才能形成样例规格，因此，当样例的需求量过大时，规格的构建将变得十分困难。如 L算法——一种用于描述常规语言的 PBE 系统——它的一大缺点就是系统构建需要依赖大量的样例；再如像航空旅行查询系统(Air Travel Information System，ATIS)这类的专业领域，要求终端用户(即普通乘客)构造成充斥着专业名词输出/输出样例是一件几乎不可能的事情。但与 L算法所处的场景不同，ATIS 领域的合成问题存在改进的可能，因为“航线查询”这类领域任务通常可以利用自然语言描述。由此，作者认为自然语言的描述也许能够指导程序合成可靠地进行。

在本文中，作者解决了利用自然语言(NL)合成基础底层特定语言(DSL)的程序的问题。从本质上来说，NL 是不精确的，因此可能无法保证合成程序的正确性。为了保证结果程序的准确性，作者将程序合成器的输出定义为一组排序后的结果程序(而不是单个结果程序)，并允许用户通过检查源代码和观察程序输出的方式来检查程序、挑选程序。本文提出的合成算法能够在基准数据上提供稳定的合成结果：在 80%的序列结果序列中，预期程序排在 Top-1 的位置；在 90%的结果中，预期程序排在前三。此外，为了帮助用户更好地选择程序，作者还将代码翻译成无歧义的英语表达，以供用户预览。

本文提出的方法可以应用于多种 DSL。在使用框架时，程序合成器的设计人员需要提供两个输入：① DSL 定义，一组从 DSL 操作到对应 NL 描述/概念的映射；② 训练数据，一组样例对(Example Pair)，每个样例对包含一组英语描述和一个符合这组描述的预期程序。在训练阶段，本文的方法会：① 以半自动方式推断英语单词和 DSL 终结符之间的字典关系；② 通过一个通用合成算法，以完全自动化的方式推断英语单词的最优权重/分类符(Optimal Weight/Classifier)。综上，本文提出的方法可以看作一个能够构建 NL-to-DSL 程序合成器的通用框架。

2 研究动机

作者在研究过程中发现了三种可以应用 NL-to-DSL 合成器的场景，分别是：高阶文本编辑操作(2.1 节)、智能教学系统中的自动机构造问题(2.2 节)以及航空旅游信息系统的查询问题(2.3 节)。

2.1 文本编辑(终端用户编程)

在浏览 Office 程序(如 Microsoft Excel 和 Word)的帮助论坛时，作者发现了许多关于“如何进行重复文本编辑操作”的求助。例如：在 Word 文档中执行特定条件下的插入、删除、替换或提取操作，如表 1(b)所示。这些操作比单纯的文本搜索或字符串替换要复杂的多，属于高阶文本编辑操作。高阶操作通常具有两类特征：① 字符串的搜寻条件不是常量，而是正则表达式；② 文本的编辑和目标文本的上下文有关。高阶文本编辑往往需要用户了解正则表达式、条件语句和循环语句的语法和语义，而这大大超出了绝大部分终端用户的能力。

表 1 文本编辑领域相关的语法和基准样本

上述需求启发作者设计一种用于实现高阶文本边界操作的命令语言，该语言的部分语法如表 1(a)所示。语法中包含了一些文本编辑的关键命令，如插入 Insert、删除 Remove、打印 Print 和替换 Replace，这些命令都依赖于一个指明了编辑操作作用范围(比如一组行、一组单词或整个 Word 文档)的 IterScope 表达式。SelectStr 产生式(Production)内含一个允许有限通配符匹配的令牌 Token、一个用于过滤匹配值的布尔条件 BCond 以及一个基于下标的结果选择记号——出现值 Occurrence。例如：我们可以使用 AtomicOccurrence 中的 FirstFew(N)项来删除符合匹配条件的前 N 的结果；特别地，当 Occurrence 的值为 ALL 时，所有满足匹配条件的结果都将被删除。布尔条件 BCond 囊括了一些标准的字符串匹配谓词(如 Contains、StartsWith 等)，由原子条件 AtomicCond 组成，支持 And、Not 在内的条件组合。CommonCond 产生式标定了相对于某个字符组合的位置，如在某个字符组合之后 After(Token)、在某个组合之前 Before(Token)和某两个组合之间等 Between(Token, Token)。样例 1 和样例 2 分别给出了针对表 1(b)中所示的编辑任务 1 和 2 的命令语言描述。

此外，表 1(c)描述了该语言系统可以处理的其他变式。这些自然语言任务都可以用表 1(a)所示 DSL 语法来描述。作者认为表 1(a)给出的语法足够支持高阶文本编辑操作：一旦用户习惯使用 DSL 语言完成简单的条件性文本操作，那么通过将复杂问题分解为简单问题，更加复杂的文本操作也不成问题。

2.2 自动机理论(智能教学)

形式化方法的研究成果已经在智能教学系统的多个部分中得到了应用，包括问题生成(Problem Generation)、题解生成(Solution Generation)和一些关于几何、自动机理论在内的各种学科领域的反馈生成(Feedback Generation)等多个领域。这些领域中的每一个都涉及一种专用的 DSL，用于生成题目、产生题解以及生成针对学生提交题解的反馈意见。

以自动机的构造为例：假设学生需要构造这样一个自动机，该自动机需要能够接受一段描述了某种语言的英文段落(有关示例见表 2)。根据 Alur 等人提供的、关于构造此类语言的一些要素，作者设计了一种 DSL，可以通过两种方式为学生提供指导：① 作为题解生成工具的输入以生成一个正确的题解，并以这个正确题解为基准为学生提交的题解打分；② 用于提供反馈并根据学生的提交生成问题变式。该反馈生成工具已经部署在部分教室中。实践证明，该工具能够以比人类更快、更合理方式分配成绩和生成反馈。

表 2 有关自动机领域的基准样本

 样例 3 和样例 4 分别展示了表 2 中规格 1 和规格 2 的 DSL 翻译结果。

2.3 航空旅游信息系统(ATIS)

ATIS 是用于查询航空旅行信息的标准基准，包括英语查询和包含航班信息的数据库。长期以来，ATIS 一直被自然语言处理和语音处理社区广泛用作通用基准。表 3 展示了一些来自 ATIS 的查询样本。

 表 3 ATIS 领域的基准样本

针对 ATIS，作者设计了一种基于 SQL 行列操作的 DSL，能支持谓词和表达式运算。这些谓词和表达式与航空旅行查询领域的出发地/目的地、日期、价格等重要概念相对应。表 3 中的第一个查询语句可以翻译成如样例 5 所示的形式。

 样例 5 表 3 中第一个查询语句的 DSL 表示

3 问题定义

本文主要研究如何使用给定的 DSL 定义和训练数据合成目标 NL-to-DSL 合成器。现给出如下定义：

(1)领域特定语言：一个领域特定语言 L = (G, TC)由一组上下文无关文法 G(其中 GT 表示终结符集、GR 表示产生式规则集)和一个可以检查给定程序类型正确性的类型/语义检查器 TC 构成；

(2)训练数据：训练数据由一组形如(S, P)的对组成，其中：S 是一个英语句子，P 是用领域特定语言 L 写成的预期程序。一个英语句子 S 可以简单表示为一个单词序列[w1, w2, … , wn]；

(3)NL-to-DSL的功能目标：生成的 NL-to-DSL 生成器应该能够将一个英语句子翻译成一个由排序后程序组成集合[P1, P2, …, Pk]。其中所有的程序都由 L 编写。

4 语言转换算法

本文提出的合成算法(算法 1)从用户处获取自然语言命令作为输入，并创建候选 DSL 排名列表作为输出。算法的第一步(第 2 行的循环)是利用定义了 NL 到终结符映射的字典结构 NLDict 将用户输入中的而每个单词转换为一个或多个终结符。该循环遍历输入语句的每个字符。针对每一个索引，算法将利用 NLDict 挑选出相关单词，并查找 DSL 中与这些单词相关终结符集。从本质上来说，NLDict 为每个终结符进行了编码，并根据输入的英语单词决定在最终生成的预期程序中选用哪些终结符。

字典 NLDict 会分别将每个自然语言单词与一组终结符关联起来。终结符可能是常量值，也有可能是参数空缺的的函数(留白参数用“□”表示)。因此，当在算法 1 的第三行上应用 NLDict 时，生成程序中某些函数的参数可能会发生缺失，进而输出不完整的程序。以语句“Print all lines that do not contain 834(打印除 834 以外的所有行)”为例：由于语法中包含产生式规则 PrintCmd := Print(SelectStr，IterScope)，且字典将单词“print”与函数 Print 关联在了一起，那么这样就会生成不完整的程序 Print(□, □)。这些空缺将在后续被一些能够匹配参数 SelectStr 和 IterScope 的程序所替换。

 算法 1 NL-to-DSL 合成算法

在完成了基本终结符集合的构建之后，算法 1 将采用 Bag 算法(算法 2)来生成一个包含所有候选程序的集合 ResT，对应算法 1 的第 5 行。算法 1 的最后一步是结合得分和权重，对集合中所有的候选程序进行排序，对应算法 1 第 8 行。

4.1 一致程序的综合

DSL 中的程序 P 要么是原子值（即 G 中的终结符），要么是应用于参数列表的函数/运算符。 按照惯例，我们将函数应用表示为 s-表达式，其中应用到 k 个参数的函数 F 被写成 (F,P1,...,Pk)。

Consistent Programs and Witness Maps.

给定一种DSL：L = (G,TC)，如果存在映射 M 将句子S 中的（一些）单词出现映射到 GT 中的终结符，使得 M 的范围 等于程序 P 中的终结符集，（由于同一个英文单词可能出现在S中的不同位置，具有不同的含义，因此任何映射M也必须以位置信息作为参数。 此论文中忽略了这一点。），我们将这样的映射M 称为目击者映射，并使用符号 WitnessMaps(P,S) 来表示所有此类映射的集合。

Usable and Used Words.

设 S 是一个英文句子，P 是一个与 S 一致的程序，M 是任何见证映射。 UsableWords(S) 是 S 中那些映射到某个语法终结符的单词出现，因此可能对翻译有用。 UsedWords(S,M) 是 S 中可用词出现的集合，用作映射 M 的一部分。

Partial Programs.

一个部分程序延申了程序的概念，还允许将一个hole 作为参数。一个hole是一个象征性的占位符，可以在其中放置另一个完整的程序（没有任何hole的程序）以形成更大的程序。 为了避免冗长，将部分程序简称为程序。给定一个部分程序 P = (F,...,✷,...) 有一个hole ✷，我们可以用一个完整的程序 P’ 来填补这个hole：

有效性检查，TC，确保所有合成程序在 DSL 语法和类型系统方面都得到了很好的定义（否则我们将返回无效程序 ⊥）

 Combination.

组合运算符 SubAll 生成所有有效程序的集合，这些程序可以通过将完整程序 P‘ 替换到部分程序 P 的某个hole 中来获得。这是通过遍历 P 的所有参数并为有hole 的参数位置生成替换来完成的 . 给定部分程序 P = (F,P1,...,Pk) 和完整程序 P’ ，我们有：

 Bag Algorithm.

 

 算法 2 Bag 子合成算法

Bag 算法（Alg. 2）基于通过枚举程序集中所有可能的类型良好的组合来计算程序集的闭包。 主循环（第 2 行）是对已构建程序的结果集的固定点迭代。
在应用 SubAll 函数时，要求 P2 是一个完整的程序（第 5 行）确保结果程序中唯一的hole是最初在 P1 中的hole。 我们将 B0 的初始化限制为仅包括完整程序和仅在顶层有hole的部分程序。 使用这个限制，我们可以归纳地表明，在每一步，所有部分程序都只在顶层有hole。 因此，我们可以以自底向上的方式有效地计算所有可能程序的固定点。 条件 UsedWords(S,M1)∩UsedWords(S,M2) = 0/（第 6 行）确保两个程序不使用来自用户输入的重叠词集。 这保证了最终的程序不能从用户输入的同一部分创建多个不同含义的子程序。 这也确保了可能组合的集合具有基于输入中单词数量的有限界限。 第 8 行构造了 P2 的所有可能替换到 P1 中的hole的集合（忽略任何无效结果）。 对于每个可能的替换，我们将结果（和 M 个映射的并集）添加到新程序集（第 9 行）。 由于映射的域是不相交的，联合操作是明确定义的。
Bag 算法具有很高的召回率，但在实践中，它可能会生成由于对英语句子中的单词进行任意重新排列而产生的虚假程序。 为了解决这个问题，通过根据程序的特征和句子的解析树选择排名最高的程序来报告正确的翻译。

4.2 一致程序的排序

我们认为合成程序的抽象语法树由两个重要组成部分组成：程序中的终结符集，以及这些终结符之间的树结构。 我们使用这些成分来计算以下三个分数来确定一致程序的排名：（i）覆盖率分数，反映了英语句子中有多少单词被映射到程序中的某个操作或值，（ii） 映射分数，反映单词到终结符映射捕获用户意图的可能性 (iii) 结构分数，捕获树程序结构的自然性以及程序部分与句子部分之间的联系 产生了它们。

4.2.1 覆盖率分数

对于给定的句子 S、候选翻译 P 和见证映射 M，覆盖率分数定义为，

 CoverageScore(P,S,M) 表示 S 中实际用于生成 P 的可用信息的比例。直观地说，我们希望更多地使用输入信息的程序。

 第一个程序 P1 使用用户输入的所有部分，包括所需的最便宜的票价，而第二个程序 P2 忽略此信息。 Coverage 分数将 P1 排在高于 P2 的位置。

4.2.1 映射分数

对于任何词 w，在集合 NLDict(w) 中可能有多个终结符（函数或值），每个终结符对应于对 w 的不同解释。 我们使用机器学习技术获得基于斯坦福 NLP 引擎 [26] 为单词提供的词性 (POS) 标签的分类器 Cmap。 分类器的 Cmap.Predict 函数预测每个词到终结符映射正确的概率。 我们使用来自 Cmap 的预测来计算 MappingScore，即 P 中的终结符正确解释 S 中相应单词的可能性。

MappingScore 分数的一个限制是它只查看一个词的映射，而不是它与其他词的关系以及它们是如何被翻译映射的。 因此，在正确的翻译中交换一对终结符会给我们一个具有相同分数的错误翻译。

 这两个程序使用相同的词集，因此它们具有相同的覆盖率分数。 唯一的区别是单词“beginning”在 P1 中映射到 StartsWith（POS：动词短语），在 P2 中映射到 Before（POS：介词短语）。 映射分数有助于确定 P1 是正确的选择。

4.2.3 结构分数

结构得分体现了子程序放置中的自然性概念。 我们使用从句子 S 获得的连接特征、句子的自然语言解析树 NLParse(S) 和相应的程序 P 来定义整体结构分数。 这些特征用于生成分类器 Cstr，该分类器计算 P 中每个组合正确的概率。

定义 1（连接）。 对于形式为 N → N1 ...Ni ...Nj ...Nk 的产生式 R ∈ GR，元组 (R,i, j) 其中 1 ≤ i, j ≤ k, and i不等于j 被称为 一种连接。

定义 2（组合）。 考虑使用产生式 R :N → N1N2 ...Nk 生成的程序 P = (P1,P2, ..., Pk)，这样 Ni 在 1 ≤ i ≤ k 时生成 Pi。 我们说这对子程序 (Pi ,Pj) 是通过连接 (R,i, j) 组合的，这种组合表示为 Conn(Pi ,Pj)。

整体的结构得分是通过对程序 P 的分数的各种连接概率取几何平均值获得的——这一步将分数标准化以解释具有不同连接数的程序。

我们为每个连接 Conn 获得单独的分类器 Cstr[Conn]。函数 Cstr[Conn].Predict 要求分类器预测 f-vec 属于类 1 的概率（即，出现在正确翻译中）。 另一类是0。给定一个程序 P 和输入句子 S，它们通过见证映射 M 和解析树 NLParse(S) 相关联，以下函数定义了几个有用的关系：

 在本节的其余部分，我们假设 P1 和 P2 表示 P 的两个子程序。 以下特征决定了 P、P1、P2 和 S 之间连接的自然性：

定义 3（根 POS 标签）。 词性特征是 NL Parser 分配给分别与 P1 和 P2 关联的子树的根节点的词性标签：

 

特征 fpos1 和 fpos2 有助于学习通常使用特定连接组合的短语。

定义 4（LCA 距离）。 令 LCA 是 Root(P1,S,M) 和 Root(P2,S,M) 的最小共同祖先。 LCA 距离特征是从 LCA 到分别与 P1 和 P2 关联的子树的根节点的树距离：

定义 5（顺序）。 顺序特征由与 P1 和 P2 关联的子树根在 NLParse(S) 的中序遍历中的位置决定。

特征flca1、flca2和forder用于学习解析树结构和程序结构的对应关系。我们使用这些来保持翻译结构接近解析树的结构。

定义 6（重叠）。 重叠特征捕获了两个程序由 NL 解析树中的两个子树的混合构造的可能性：

定义 7（距离）。 给定两个程序 P1 和 P2，我们通过查看程序中使用的单词跨度之间的距离来定义程序的距离特征：

 fover 和 fdist 特征捕获单词的邻近信息并且很有用，因为相关的单词经常一起出现在输入句子中。

 在解析树 NLParse(S) 中，“print”将有两个参数，打印什么（“lines”）和何时打印（“not contain 834”）。 我们观察到候选程序的以下内容：

(a) 单词“lines”更接近“print”，而单词“834”在 NLParse(S) 中更远。 对 P1 来说我们能观察到相同的结构，但对 P2 来说观察不到。这是由 LCA 距离捕获的。  

(b) NLParse(S) 中单词的顺序与 P1 中的顺序匹配比在 P2 中更好。 这是由顺序特征捕获的。

(c) 短语 “not contain 834” 在 P1 中保持不变，但在 P2 中分开。 重叠和距离特征将捕获这种拆分和重新排序。
这两个程序使用相同的词集，以及相同的词到终结符的映射，导致相同的覆盖分数和相同的映射分数。 然而，程序 P1 是正确的，我们选择的特征将其排名更高。

 4.3 综合分数示例

为了直观地了解各种分数的互补优势和劣势，我们检查了它们在由 Bag 算法为以下文本编辑任务生成的程序子集上的表现：

Add a “*” at the beginning of the line in which the string “P.O. BOX” occurs.

 表 4 显示了由 Bag 算法生成的一些一致程序。 第一个程序 (P1) 是预期的翻译。 让我们看看每个组件得分的表现：

覆盖率分数：P1 和 P4 都使用句子中的最大单词数，并列在最高分上。  P4 是错误的，因为它添加了“P.  O. BOX”在包含“*”的行的开头。
映射分数：我们系统学习的分类器将单词“beginning”映射到终结符 StartsWith 的概率很高，但映射到终结符 START 的概率较低。 此外，它以更低的概率将“发生”映射到终结符包含。  P2 不使用“occur”这个词，否则它与 P1 具有相同的映射。 因此，它比 P1 具有更高的映射分数，但在覆盖率方面受到影响。  P3 将“beginning”映射到 StartsWith，并且不使用“occurs”这个词。 因此，它的映射分数低于 P2 但高于 P1。 如果我们单独使用映射分数，我们将无法将所需程序 P1 排在错误程序 P3 和 P4 之上。

结构分数：覆盖率分数和映射分数只看一个词的映射，而不是它与其他映射的关系以及它们相对于原始句子的位置。 结构分数通过考虑句子中的结构信息（解析树、词的排序和词之间的距离）来解决这个问题。
P4 的结构得分很差，因为它交换了字符串“*” 和 “P.O. BOX”的句子顺序。  当 P3 将“beginning”（映射到 StartsWith）从“Add”（映射到 Insert）移开时，它也会受到影响。
P1 获得了很高的结构分数，因为它维护了输入文本的解析树结构。 请注意，P2 和 P5 的结构得分也很高。 这是因为结构分数没有考虑使用单词的比例或单词到终结符的映射。 因此，使用很少的单词但将它们映射到正确的终结符并正确放置它们的不完整翻译可能具有很高的价值。
所需的程序 P1 仅在其中一个分数上排名第一，即使在这种情况下，该分数也会与另一个不正确的结果并列。
但是，将分数与适当的权重（第 5 节）相结合，将 P1 列为明显的赢家！

5 训练阶段

本节描述第 4 节中描述的合成算法使用的分类器、权重和单词到终结符映射的学习过程。 此过程中的关键方面是 (i) 决定使用哪种机器学习算法，以及 (ii) 从 DSL 设计者提供的高阶训练数据中为该机器学习算法生成低阶训练数据。

5.1映射分数分类器Cmap

Cmap 分类器的目标是使用单词 w 的 POS 标签预测 映射到终结符 t ∈ GT 的可能性。 该分类器的学习是使用朴素贝叶斯分类器 [6] 的现成实现来执行的。 该分类器的训练数据如算法3所示。

关键思想是首先构建可以从自然语言输入 S 中产生程序 P 的所有见证映射的集合 M 。 然后我们根据相似性得分元组（likeability score tuples）提供的字典偏序（partial lexicographic order），从M中挑选出可能性最高的见证映射M，文中给出以下推导：

 相似性元组主要为两个目标服务：第一，通过 UsedWords，引导系统侧重那些“使用了输入语句中所有部分”的映射；第二，通过 Disjointness，引导系统侧重那些惩罚了“使用输入语句中单个部分来构建多个不同子程序”的映射。

5.2 结构分数分类器Cstr

 本部分将介绍为结构得分服务的分类器 Cstr 的训练过程。对于每一个连接 Conn，都有一个分类器 Cstr [Conn]与之对应。分类器 Cstr [Conn]的主要功能是预测一个组合 c 是连接 Conn 的一个实例的概率。本文使用了朴素贝叶斯分类器的现有实现来生成训练数据，训练过程如算法 4 所示。

算法 4 的关键思路是在不记录单个步骤得分的情况下(SynthNoScore)运行合成算法，目的是利用一个英语句子 S 构造包含所有可能程序结果的集合 AllOpts。P’是 AllOpts 中的一个程序。任何出现在 P’但没有出现在 P 中的组合都将被用作负样例(Negative Example)；相反的，如果该组合同时出现在 P’和 P 中，那么它将被用作正样例(Positive Example)。

5.3 字典构建

利用 DSL 中终结符的名字(表示函数和参数)，本文提出的方法将通过一种半自动化的方式构建字典 NLDict。对于名字恰好对应英文单词(例如 Insert)的操作，作者直接利用 WordNet 同义词列表来收集所有和该操作(插入操作)相关的所有常用同义词；对于终结符的名字不是一个英文单词、而是采用某种命名方式产生的单词的链接(例如 StartsWith)的操作，作者首先利用命名规则分解操作名称，紧接着再解析出每个子名称对应的同义词。

值得注意的是：WordNet 提供的同义词集合中可能会包含一些对目标特定领域没有意义的英文单词。这个问题由 5.1 节介绍的算法 3 解决：根据映射得分训练算法，这类单词的得分将会比较低。并且，本文的方法还会在得分分配完成后，舍弃掉得分低于某个阈值的所有映射；同理，WordNet 也有可能无法提供对于某个特定领域极其重要的英语单词、或者 DSL 中终结符的名称不能有效地匹配到英语单词。由于在这种情况下，算法 4 将无法生成见证者映射，因此系统将能够自动检测到这种情况，并告知用户他/她的输入中有哪些无法和终结符正确对应的单词。这些不能正确对应到终结符的单词将被用作种子单词(Seed Word)输入到 WordNet，以进一步生成更加全面的同义词集。

5.4 学习组合权重

在上一节中，我们为翻译定义了 3 个组成部分。 将多个分数组合成单个最终分数的标准机制是使用组成分数的加权总和。 在本节中，我们描述了一种新方法，用于学习用于最大化以下函数的所需权重。

优化函数：训练集中的基准数量，正确翻译的等级为 1。

在数值优化中，优化函数的最大化是一个标准问题，可以使用随机梯度下降 [5] 来解决。 为了使用梯度下降找到最大化我们的优化函数的权重值，我们需要定义一个连续且可微的损失函数 Floss。 该损失函数用于指导迭代搜索一组使优化函数值最大化的权重，如下所示：

 其中倒三角表示梯度，γ 是一个正常数。 在每一步，w 向 Floss 值减小的方向移动，当连续步骤中函数值的变化低于指定的阈值 ε 时，过程停止。

损失函数的常见形式是 sigmoid。 我们可以将我们的不良优化函数转换为更接近执行梯度下降所需的损失函数，方法是将 sigmoid 建立在给出最佳错误结果的比率分数和通过以下构造给出的期望速率分数的基础上 ：

虽然上述转换导致损失函数大部分表现良好，但它适当地饱和并且是分段连续和可微的，但仍然存在函数不连续的点。 特别是在 Vwrong 的定义中 max 函数的存在会在 Floss 中产生不连续的点。 但是，以下见解使我们能够用连续近似替换不连续最大操作：

因此，我们可以用这个函数替换 max 运算符，以自然的方式扩展到 k 个参数，在 Vwrong 的计算中产生一个全局连续和可微的损失函数。 通过为 c 选择一个较大的值来最小化有几个不正确的结果并给出非常相似的分数的情况，这会放大小的差异。 此外，在两个分数非常接近的最坏情况下，近似的影响是驱动梯度下降以增加 Vwrong 和 Score(Pdesired) 之间的比率。 因此，不影响梯度下降算法的正确性。

除了满足执行梯度下降的基本要求之外，我们的损失函数 Floss 会在 λ 的大值下饱和。 这意味着如果一个输入 S， 有Vwrong/Score(Pdesired) >>1 ，它将不会主导梯度下降，从而导致它以牺牲大量其他基准的排名质量为代价来提高单个基准的排名结果。 饱和度还意味着下降不会陷入试图为输入寻找权重的过程中，其中没有分配可以提高排名的权重，即存在不正确的结果程序 Pi，其中每个组成部分的分数都高于 所需的程序 Pd。

6 实验评估

由 Bag 算法和特征提取（用于排名）组成的（在线）合成算法是用 C# 实现的，并使用斯坦福 NLP 引擎（2.0.2 版）[53] 进行 POS 标记和提取其他 NL 特征。 离线梯度下降是用 C# 实现的，而用于训练组件特征的分类器是用 MATLAB 构建的。

这项研究的一个主要目标是生成一个通用框架，用于从英语句子合成给定 DSL 中的程序。 因此，我们选择了 3 个不同类别的任务，问答（ATIS）、基于约束的模型构建（自动机理论辅导）和非结构化数据的命令执行（重复文本编辑）。 这些域（在 §2 中详细描述）呈现了底层 DSL 中的各种结构、所使用的语言习语以及所见英语句子的复杂性。 对于基准测试，自动机描述是从教科书和在线作业中逐字提取的；文本编辑描述逐字来自帮助论坛和用户研究； ATIS 描述是标准套件的一部分。 表 1(b)、1(c)、2 和 3 描述了一个基准样本。 基准的详细信息及其来源可以从配套网站获得：https://sites.google.com/site/nl2pgm/[9]。

航空旅行信息系统 (ATIS)

我们从完整的 ATIS 套件（由几千个查询组成）中随机选择了 535 个查询，并在我们的 DSL 中手工构建了相应的程序来实现查询。 ATIS 域中的每个任务都是对飞行相关信息的查询。

自动机理论辅导

我们从有关自动机理论的书籍和在线课程中收集了 245 个有限状态自动机的自然语言规范（接受条件）。

重复文本编辑

我们从 Excel 书籍和帮助论坛中收集了 21 个文本编辑任务的描述。 我们通过用户研究收集了这 21 个任务的 265 个英文描述，该研究涉及 25 名参与者（他们是本科一年级和二年级学生）。 大量的参与者确保了英语描述的多样性（例如，见表 1（c））。 为了消除任何描述偏差，这些任务中的每一个都不是使用英语而是使用具有代表性的输入和输出示例对来描述的。 此外，我们从一个独立的语料库中获得了 227 个文本编辑任务的 227 个英文描述（每个任务一个）[36]。

6.1 准确率、召回率和计算成本

在这项研究中，我们使用标准的 10 折交叉验证来评估翻译人员在每个领域的准确率和召回率。 因此，我们随机选择 90% 的数据用于学习分类器/权重，然后根据剩余的 10% 数据（在训练期间未看到）来评估系统。 在排名中，我们使用 1334 排名方案 [46] 处理分配给元素的分数之间的关系。在1334 排名方案中，在分数相同的情况下，为相同组中的每个元素分配一个排名，对应于排序结果列表中的最低位置（与最高位置相反）。 这确保报告的结果代表在找到所需程序之前可能出现在排名列表中的最坏情况项目数。

准确率

图 1 显示了 DSL 中所需程序是排名最高的结果的输入百分比，以及所需结果在前三个结果中的输入百分比。 如图所示，对于每个领域，在超过 80% 的输入中，所需程序被明确标识为排名第一的结果。此外，对于 ATIS 领域，所需的结果是 88.4% 的自然语言输入的排名最高的结果。 鉴于我们来自完整 ATIS 套件的样本大小，我们可以推断出所需的程序将是 88.4 ± 4.2% 的自然语言输入的最高排名结果，置信区间为 95%。 这些结果表明，我们新颖的基于程序综合的翻译方法与最先进的自然语言处理系统具有竞争力：[57] 中的 85%、[42] 中的 84% 和 [27] 中的 83% .

召回率

除了始终如一地生成所需程序作为大多数输入的最高排名结果之外，排名算法将所需程序置于前 3 个结果中的几率还有 5%-12%。 因此，在所有三个领域中，对于超过 90% 的自然语言输入，所需的程序是排名前三的结果之一。 这为任何域留下了不到 10% 的输入，而在文本编辑域的情况下只有 5%，在该领域中，合成器无法生成所需的程序并将其置于前三名。

计算成本

图 2 显示了在具有 8 GB RAM 的 2.80 GHz Intel(R) Core(TM) i7 CPU 上运行合成算法和执行排名所需的时间分布。 文本编辑的平均翻译需要 0.68 秒，自动机需要 1.72 秒，ATIS 输入需要 1.38 秒。 此外，时间分布严重倾斜，超过 85% 的输入花费不到 1 秒，很少有超过 3 秒的输入。 异常值往往是用户以异常冗余的方式指定操作的输入。

与从根本上涉及指数空间搜索的任何程序综合技术一样，我们技术的成本也是最坏情况下 DSL 大小的指数。 然而，关键问题是在实际案例中有效地做到这一点。 我们的合成对一系列有用的 DSL 有效（通常不到 1 秒）。 字典的大小对运行时的影响最小，因为翻译仅依赖于与输入句子中的单词对应的字典子集。

6.2 单个组件评估

在第 4 节中，我们定义了用于排名的各种组件，并提供了对其有用性的直觉。 为了验证这些组件分数对于取得良好结果的重要性，我们通过使用组件分数的各个子集、学习子集的最佳权重并对程序重新排序来评估我们的选择。

单个分数的表现

单独使用每个组件的结果如表 5 所示。该表显示，在确定排名靠前的程序时，仅使用 CoverageScore 的最佳性能为 17.9%，使用 MappingScore 为 31.0%，使用 StructureScore 为 51.4%。这比使用组合排名获得的结果要差得多，后者将所需程序作为 84.9% 输入的最高结果。 因此，我们得出结论，单独的组件是不够的。

得分的独立性

尽管这些结果表明独立的任何组件都不足以进行程序排名，但可能存在这样的情况，即其中一个组件实际上是其他两个组件的组合。 表 6 显示了在删除组件之一时对程序进行排名的结果。 丢弃StructureScore导致的下降幅度最大，最坏情况高达81.86%，即使是最好的情况也有47.75%的下降。 降低 CoverageScore 也会导致显着的退化，尽管不如 StructureScore 高。 丢弃 MappingScore 的影响要小得多，在 2.04% 到 4.67% 之间。 然而，MappingScore 一贯的积极贡献表明它仍然为排名提供了有用的信息。 因此，所有组件都提供了独特且有用的信息。

字典构建

实际上，半自动方法使字典构建成为一项任务，虽然通常需要人工协助，但不需要自然语言处理或程序综合方面的专业知识。 每个领域的词典平均包含 144 个英语单词，平均 4.51 个词/终结符和 1.48 个终结符/词。 提示用户在三个 DSL 中平均提供 20.7% 的映射。 虽然超出了这项工作的范围，即它需要更大的训练数据语料库，但可以通过使用统计对齐从训练数据中自动提取领域特定的同义词来进一步减少用户干预的数量。

分数组合权重

我们使用梯度下降来学习计算程序最终排名时每个分数的权重。 为了评估通过梯度下降识别的权重的质量，我们将它们与所有组件分数的相等权重的天真选择以及提升的结果进行了比较。 Boosting [10] 是一种常用的技术，它结合了一组较弱的排名，例如单个组件的分数，以产生一个单一的强排名。 表 7 显示了使用三种方法获得的排名结果。

 与朴素的权重选择相比，使用梯度下降显着提高了排名靠前的基准的数量（高达 15%）。 但是，排名前三的基准点的改进要小得多。 同样，梯度下降方法产生的结果明显优于 RankBoost，在排名靠前的基准中平均年龄差异为 9%。 因此，我们可以得出结论，使用梯度下降来学习组合权重对于结果的整体质量很重要。

我们对排名函数的选择对结果的质量至关重要。 如表 6 所示，删除任何组件函数都会导致精度的显着损失。 此外，与使用梯度下降法相比，使用更简单的方法（例如等权重或提升 [10]）来计算组合权重会导致精度损失 9-15%（表 7）。
在我们的系统中，大多数失败（即正确的解决方案未能排在前三个解决方案中）的出现是因为英语描述中隐含了一些关键信息，例如 “I want to fly to Chicago on August 15”。 在这种情况下，出发城市应默认为“CURRENT_CITY”，时间应默认为“ANY”。 此类问题可以通过拥有数量级更大的训练数据或通过构建一些专门的支持来处理各个领域中的隐式上下文信息来解决。

作为学习分量分数权重的一部分，我们使用逻辑函数的一个移位变体作为我们的损失函数（§5）。 图 3 显示了损失值如何随着迭代索引和排名靠前的基准的相应数量而变化。 可以看出，随着损失值的减小，排名靠前的基准的数量增加，反之亦然。 因此，由于这些值是梯度下降算法最佳性能所需的负相关，即使我们的损失函数包含最大操作的对数指数近似，它对于梯度下降算法也表现良好。

由于 §4.2 中学习的权重是通用的，我们希望从一个域中学到的权重适用于其他领域，从而消除在每个新域上重新学习这些值所需的时间和精力。 表 8 中的结果表明，为一个域学习的权重向量在用于对新域的结果进行排序时表现良好。 排名靠前的节目数量平均下降仅1.9%（最大下降5.0%）。 排名前三的项目数量变化不大，最大降幅小于 0.5%，因此我们不包括在内。 该结果表明，分量权重的学习是高度独立于领域的，并且泛化性很好，允许将其重用（或用作起点）用于新领域。

7 相关工作 

演示编程 (PBD) 系统使用用户执行的任务跟踪，示例编程 (PBE) 系统从一组输入输出示例中学习，已被用于支持各种领域的终端用户编程。 对于 PBD，这些领域包括文本操作 [28] 和表格转换 [23] 等 [7]。 Gulwani 等人最近在 PBE 上的工作已经包括用于操作字符串 [13, 48]、数字 [49] 和表格 [21] 的领域。 如前所述，当所需的转换涉及条件操作时，基于 PBD 和 PBE 的技术都会遇到困难。 相比之下，这项工作中基于自然语言的方法对于简单和条件操作都表现良好。

关键字编程是指通过某些 API 将一组或一序列关键字转换为函数调用的过程。 该 API 可能包含现有编程语言中的操作 [34, 41, 54] 或为特定任务类别构建的 DSL [32, 33]。 这些技术使用各种程序合成方法从底层 API 的元素构建表达式树，类似于第 4 节中的 Bag 算法，然后使用简单的启发式方法，例如使用的单词和关键字到终端的权重， 对生成的表达式树进行排名。 这些系统在用于具有复杂意图的输入时精度较低，[34] 中的准确度为 50%-60%，并且经常会建议不正确的程序。 相反，由于排名方法，本文中的合成器即使在 ATIS 等复杂领域（我们达到 88% 的准确率）也能保持高精度。

语义解析 [39] 是一种使用专门的语言解析器从自然语言构建程序的复杂方法。已经提出了几种方法，包括语法定向 [25]、NLP 解析树 [11]、SVM 驱动 [24]、组合分类语法 [27、56、57] 和基于依赖的语义 [30、42]。 这些系统具有很高的精度，通常会提示正确的程序，但在 ATIS 中召回率低于 85% [57]。 相比之下，本文中的技术在提供接近 92% 的召回率的同时实现了类似或更高水平的精度。

许多自然语言编程系统都是围绕语法、NLC [4] 或模板、NaturalJava [45] 构建的，它们对输入表达式施加了各种约束。 这样的系统对语法错误或无关的词很敏感。 对开发数据库的自然语言接口 (NLIDB) [2, 40] 进行了广泛的研究。 虽然早期系统基于将用户输入与已知模式之一进行模式匹配，但 PRECISE [43, 44] 将语义上易于处理的 NL 问题转换为相应的 SQL 查询。 这些系统严重依赖于具有已知模式的底层数据，这使得它们在底层数据结构未知（或不存在）时（如本工作中使用的文本编辑域）不切实际。

SmartSynth [29] 是一个从 NL 自动生成智能手机脚本的系统。 SmartSynth 中的综合技术高度专业化于底层智能手机领域，并对其生成的程序使用简单的排名策略。 类似地，NLyze [20] 系统从 NL 合成电子表格公式。同样，NLyze 是为特定领域（mula 的电子表格）设计的，并使用相对简单的排名系统，仅由我们论文中介绍的覆盖率、映射和重叠特征等价物组成。 相比之下，我们的技术与目标 DSL 的细节无关，排名特征独立于底层 DSL，我们会自动学习这些特征的适当权重。 此外，如表 6 中的实验结果所示，使用 SmartSynth 或 NLyze 中描述的排序方法会导致召回率/精度大幅降低。 因此，本文中的排名方法对 NLyze/SmartSynth 中的使用进行了改进，并提供了通过整合这些进步进一步提高其性能的机会。

[47] 中的工作利用自然语言来实现组合 PBE（通过示例编程）。 它不应用 PBNL 方法中使用的任何自然语言学习技术，而仅利用自然语言分解成短语，然后要求用户提供这些短语的基于示例的解释。

8 结论

本文开发了一种元方法，用于从自然语言描述中合成程序，可以为一系列有趣的 DSL 实例化，包括文本处理、自动机构建和信息检索查询。 我们的方法从合成设计者那里获得三个输入、一个合适的 DSL 定义、一个基本训练数据集和帮助构建一个词到标记字典，并从这些输入构建一个相应的高精度和高召回率 NL 到 DSL 合成器。

我们的目标是进一步推广该框架，以允许为更广泛的领域构建合成器。 另一个研究领域是在翻译单行意图（如我们的）时添加上下文感知，以便为更大的 DSL 中的编程和完成更复杂的任务提供交互式编程环境。