（Under review as a conference paper at ICLR 2017）
ICLR 2017已提交的关于自动编程有 12 篇论文，以下为其中一篇。
主要工作是提出一种利用神经网络生成算法代码的方法，相比于不用神经网络的搜索过程，速度有极大的提升。
学习编程（DeepCoder: Learning to Write Programs）
链接
https://openreview.net/pdf?id=ByldLrqlx
作者
Matej Balog∗ Department of Engineering University of Cambridge Alexander
L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, Daniel Tarlow Microsoft Research
摘要
目标
构建可以编写计算机程序的系统，生成人类可读的源代码。
这项工作的两个主要想法：
（1）学习诱导计划——使用一个语料库程序导入问题来学习概括问题的策略。
（2）整合神经网络架构与基于搜索的技术。
归纳程序综合（IPS）
IPS问题的研究目标是：给定输入输出示例，产生具有与示例一致的行为的程序。
构建IPS系统需要解决两个问题。
1. 搜索问题：找到一致程序，我们需要搜索一组合适的可能程序。 我们需要定义集合（即，程序空间）和搜索过程。
2. 排名问题：如果有多个程序与输入输出示例一致，我们返回哪一个？
这两个问题取决于问题制定的具体细节。 因此，第一个重要决定制定程序合成的方法是领域特定语言的选择。
域特定语言（DSLs）
DSLs是适合于的编程语言专业领域，但比全特征编程语言更受限制。例如，可能不允许循环或其他控制流，并且只允许字符串数据类型和少量原始操作，如连接。大多数程序合成研究侧重于合成因为像C ++这样的全功能语言会扩大搜索空间和复杂性合成。
DSLs的选择可以实现更高效的专用搜索算法。如果DSLs只允许输入字符串的子串的连接，动态规划算法可以有效地搜索所有可能的程序（Polozov＆Gulwani，2015）。
DSLs的选择也会影响排名难度。例如，在没有if的DSLs中语句，相同的算法应用于所有输入，减少程序数量一致与任何输入输出示例集合，因此排名变得更容易。
DSLs的选择也取决于系统需要解决哪些问题。
搜索技术 (Search Techniques)
用于搜索与输入输出一致的程序。
1. 定义语法，然后搜索所有语法的导出，检查每一个与示例的一致性。
2. SMT组合SAT风格的搜索与算术和不等式的理论，有益于理论依赖子问题可以由专用求解器处理。
3. 可以采用随机局部搜索来搜索程序空间，并且有很长的时间将遗传算法应用于这个问题的历史。
排行（Rank）
流行的排名选择是选择与输入输出一致的最短的程序（Gulwani，2016）。
FlashFill采用了更复杂的方法（Singh＆Gulwani，2015）。 它以类似于最大余量结构化预测的方式工作，其中已知给出了真实数据程序，并且学习任务是将得分分配给程序，使得真实数据程序得分高于满足输入输出规范的其他程序。
学习感应程序合成（LIPS）
（1）DSL规范
将DSL的程序P映射到有限属性向量 a = A(P)的属性函数A。
属性向量作为机器学习和LIPS的搜索组件之间的链接：机器学习模型预测分布q（a | ε），其中E是输入输出示例的集合，以及搜索过程旨在按照q（A（P）| ε）的顺序搜索程序P。
（2）数据生成过程
生成数据集D。
程序P（n）在所选择的DSL中，它们相应的属性a（n），以及伴随的输入输出示例ε（n）。
（3）机器学习模型
机器学习问题是学习给定输入输出示例下属性的分布q（a| ε），可以使用最大似然法。
（4）搜索过程
搜索组件的目的是与现有的解算器连接，使用预测q（a| ε）指导搜索。
DeepCoder
（1）DSL规范
我们的DSL包含一阶函数HEAD，LAST，TAKE，DROP，ACCESS，MINIMUM，MAXIMUM，REVERSE，SORT，SUM和高阶函数MAP，FILTER，COUNT，ZIPWITH，SCANL1。 高阶函数需要适当的lambda函数来实现它们的行为完全指定：对于MAP，我们的DSL提供lambdas（+1），（-1），（* 2），（/ 2），（*（ - 1）），（** 2）（* 3），（/ 3），（* 4），（/ 4） 对于FILTER和COUNT，有谓词（> 0），（<0），（％2 == 0）（％2 == 1），对于ZIPWITH和SCANL1，DSL提供lambda（+），（ - ），（*），MIN，MAX。
（2）数据生成过程
为了生成数据集，我们在DSL中枚举程序，启发性地删除它们易于检测的问题，例如其值不影响程序输出的冗余变量，或者更一般地，存在较短的等效程序（等同性可以被过度近似通过在随机或仔细选择的输入上的相同行为）。 为了生成程序的有效输入，我们对输出值强制限制整数到某个预定范围的约束，然后通过程序向后传播这些约束，以获得每个的有效值范围输入。 如果这些范围之一为空，我们就丢弃该程序。 否则，输入输出对可以通过从预先计算的有效范围拣选输入并执行程序来获得输出值。 二进制属性向量容易从程序源代码计算。
（3）机器学习模型
我们使用神经网络来建模和学习从输入输出的映射属性的示例。我们可以认为这些网络由两部分组成：
1。编码器：来自由a生成的一组N个输入输出示例的可微分映射单程序到潜在实值向量，以及
2。解码器：来自表示一组N个输入输出的潜在向量的可微分映射预测地面真理程序属性的例子。
（4）搜索过程
这项工作的中心思想之一是使用神经网络来指导搜索程序与一组输入输出示例一致，而不是直接预测整个源代码。
网络结构如下。
使用负交叉熵损失训练神经网络。文中使用了多种搜索方法进行比较，效率比较高的是“排序和添加”枚举(“Sort and add” enumeration)。
这种方法是利用预测函数概率的枚举搜索过程，它保持一组活动函数并仅使用活动函数集执行DFS。 每当搜索失败，下一个最可能的函数（或几个）被添加到活动集，并以这个较大的活动集重新开始搜索。
实验结果
0.神经网络使用的条件矩阵。
1.使用DeepCoder的LIPS框架在解决IPS方面带来显着的性能提升。
2.不同长度的程序之间具有强大的泛化能力。
上图右侧展示能基于训练的神经网络进行预测的层的相对加速度。
为了研究编码器在不同长度的程序中的泛化能力，我们进行了训练一个网络，用于从程序生成的输入输出示例中预测。使用的函数长度Ttrain∈{1，... ，4}。使用每个网络来预测5个测试集上的函数包含长度为Ttest∈{1，... ，N}的程序生成的输入输出示。给定长度T的测试程序与所有训练程序语义上不相交相同长度T，以及来自较短长度T的所有训练和测试程序T' <T。对于Ttrain和Ttest的每个组合，排序和添加枚举搜索都运行并且不使用神经网络的预测（在后一种情况下使用先验概率）直到它解决了20％的测试集任务。这些结果表明神经网络具有泛化超出训练长度的能力。
讨论
我们提出了一个框架，通过使用神经网络来翻译输入输出示例中的线索改进IPS系统在程序空间中的搜索。
实证结果显示对于许多程序，这种技术提高了大范围的IPS基线的运行时间。
不足之处：
首先，我们可以综合的程序只是最简单的编程竞争网站的问题，比大多数竞争问题更简单。
第二，我们目前使用五个输入输出具有相对大的整数值（高达256个数量级）的示例，这可能比典型（较小）的例子提供了更多信息。
我们最感兴趣的是更好的数据生成过程通过使用源代码的生成模型，并纳入自然语言问题描述以减少输入输出示例所需的信息负担。
DeepCoder代表着一个有希望的前进方向，我们对未来使用机器学习来合成程序的前景保持乐观。