神经引导演绎搜索：两全其美的程序合成方法

摘要：程序合成——自动生成满足给定规范的程序——是AI领域的一个主要挑战。它除了改变设计软件的方法外，它还具有彻底创新任务自动化的潜力。

程序合成——自动生成满足给定规范的程序——是AI领域的一个主要挑战。它除了改变设计软件的方法外，它还具有彻底创新任务自动化的潜力。没有编程技能的终端用户可以很容易地提供期望的程序行为的输入—输出实例。微软Excel中的Flash Fill功能，是一个特别成功的技术应用，证明了一个单一的例子往往足以生成正确的程序。

图1.Flash Fill仅仅从一个示例自动地完成一个字符串的转换任务

设计程序合成系统是具有挑战性的。你需要确保合成的程序满足那些所提供的实例；还需要确保它的泛化性；程序必须在不可见的输入上产生所期望的输出。许多可能的程序与一个单独的示例是一致的，挑选这个最通用的程序是一个重要的ML挑战。最后，面向用户的合成系统应该是运行快速的。

最高水平的程序合成研究遵循两个主要方向中的一个：符号或神经。符号系统使用逻辑推理和一组指定域规则来搜索满足所提供的示例的程序。它们被设计成通过构造产生一个令人满意的程序。但是，设计这样的规则要涉及巨大的工程努力，并且所得到的搜索过程可能是指数级的缓慢。

相对比来说，神经系统依赖于点对点的可微的和可训练的网络来生成程序。虽然更容易执行和训练，但是这样的网络需要大量的数据来学习程序合成。因为数据通常是随机生成的，神经系统经常不能获取现实世界的模型，并且导致产生泛化很差的非自然程序。此外，神经网络的纯统计特性不提供对合成的程序的任何正确性保证。

在第六届国际学习表征会议（ICLR）上，来自微软研究的研究人员展示了神经引导演绎搜索（NGDS）的研究结果，它结合了两种AI方法中最好的一个。它建立在由符号合成系统所采用的演绎搜索过程之上，但是是以神经引导来增强 ——一个预测每个分支决策的优先级的模型，即从该分支产生的最佳程序的泛化评分。

如图1中的任务。它最通用程序用来执行三个字符串的子表达式的级联：第一个单词的第一个字符，一个常量字符串“.”，以及最后一个单词。

在搜索的过程中，一个合成系统首先决定在正确程序中的顶级操作符是否是一个级联或是一个原始子表达式（子字符串或常量字符串）。如果它决定顶级操作符是级联的，则系统进一步减少所提供的输入——输出实例到两个级联的子表达式的必要的输入-输出示例。这些逻辑决策在搜索过程中引入了分支，其中大部分产生满足示例的程序，但不泛化到其它的输入。这样的分支可以通过使用神经引导来消除优先级。

图2.演绎搜索过程的一个片段，寻找满足给定输入输出实例的最通用的程序。

在搜索树中的每个分支点，将当前状态注入一个神经模型，该模型预测可能从每个分支产生的最佳程序的质量（如绿色分布曲线；更高的形状对应于更有希望的分支）。

重要的是，在搜索过程中的子问题是独立的；我们可以推理一个满意的子问题的程序，而不考虑它推导出的更大问题的的因素。这允许我们可以通过在搜索中记录所有中间决策来产生大量的训练数据。从385个字符串转换任务中，我们生成超过400000个实际的训练实例。

我们评估了神经引导演绎搜索（NGDS）在各种现实生活中的字符串转换任务，并将其与最先进的程序合成系统进行比较：PROSE（纯符号）、RobustFill（纯神经）和DeepCoder（神经-符号混合）。虽然NGDS和散文被给了一个单一的输入-输出实例，但是我们提供了RobustFill和DeepCoder的额外实例，因为它们没有明确地为程序泛化而设计。在我们的多个实验中，NGDS在基线PROSE系统中获得了67%的加速（一些任务的表现提高到了12倍），同时保持了任务完成的相同精度。这些基线方法不能保持相同的精度/性能平衡，或者一个不行，或者两个都不行。