[ICLR2017] Deepcoder: Learning to write programs

[ICLR2017] Deepcoder: Learning to write programs

Author: Matej Balog, Alexander L.Gaunt, Marc Brockschmidt, Sebastian Nowozin, Daniel Tarlow

任务描述

IPS 的归纳综合系统通过分析包含多对输入输出的数据集，在线生成满足所有条件的最优解。

主要思想

• 用神经网络预测程序中可能使用到的函数
• 用这些函数穷举搜索程序

方法流程

1. 定义特定领域语言（DSL）

相当于定义一个语法规则

在上述示例中，该系统共有五个指令条目：其中k代表一个整数值输入；b则表示接受一个数组形式的数据；c是经过对b进行排序处理后的结果；d是根据k从c中选取前k个元素；e则是对d进行求和运算的结果。 DSL所包含的基本函数包括：初始化、数据加载、排序操作、子集提取以及求和计算等基本功能模块。

In summary, our DSL incorporates a comprehensive set of first-class functions including HEAD, LAST, TAKE, DROP, ACCESS, MINIMUM, MAXIMUM, REVERSE, SORT, SUM. Additionally, it encompasses higher-level operations such as MAP, FILTER, COUNT, ZIPWITH, and SCANL1. These higher-order operations are dependent on suitable lambda expressions to define their behavior accurately. Specifically:

• For the MAP operation, our DSL offers lambda expressions with increments (+1) or decrements (-1) and scaling factors such as (2) or (/2). More complex adjustments include ((-1)), (**2), (*3), (/3), (_4), and (/4).
• The FILTER and COUNT operations utilize predicates like (>0) or (<0).
• For ZIPWITH and SCANL1 operations, suitable lambda expressions incorporating basic arithmetic operations (+,-,), along with MIN and MAX functionalities.

2. 生成训练程序和对应的输入输出对

列出属于DSL程序的所有代码块，并删减那些包含冗余语句的代码块（例如无用变量部分）。接着创建一组输入输出样本集，并将输出结果限定在区间[-256, 256]内。最后通过二进制向量的形式记录程序中调用的所有函数名称。

3. 通过生成的数据训练神经网络预测可能用到的函数

输入输出 ：输入输出的类型采用one-hot表示。

整数映射到一个嵌入向量（embedding vector）。

为整数输入与输出设定特定的NULL值以填满固定长度（L=6）。例如下述输入-17 -3 4对应输出7：

拼接顺序：输入类型，输入数据，输出类型，输出数据。

输入结构：数据经过前馈网络的三层隐含层处理，每层均采用sigmoid激活函数，并包含256个神经元单元。

每一个输入输出对最后输出256维向量；一个程序的所有输入输出对取平均值后得到最终256维向量

输出 ：将该向量左乘一个34*256的矩阵（共34个函数），得到每个函数的概率。

整个网络结构如下：

loss函数使用负的交叉熵：

4. 采用传统方法搜索程序

• 按照概率大小对神经网络预测得到的函数进行排序
• 每次从当前已识别的几个候选函数中进行搜索；如果未能找到所需结果，则依次增加候选函数数量
• Sketch（基于SMT程序合成工具）