[ICLR] DeepCoder: Learning to Write Programs

约 1239 个字预计阅读时间 4 分钟

Info

Author: Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, Daniel Tarlow
Conference: ICLR 2017
arXiv: 1611.01989

论文

590 KB / 21 P / 2025-03-30

核心问题与贡献

论文针对归纳式程序合成（Inductive Program Synthesis, IPS）问题，提出了一种结合深度学习与搜索技术的新型框架。传统程序合成方法面临以下挑战：

LIPS框架（Learning Inductive Program Synthesis）：
- 将程序合成转化为监督学习问题，通过神经网络预测程序属性（如使用的函数），引导搜索方向；
- 结合传统搜索算法（DFS、SMT求解器）与深度学习，实现搜索效率的显著提升。
领域特定语言设计（Domain-Specific Language, DSL）：
- 定义包含高阶函数（如Map、Filter）和受限控制流的DSL，平衡表达力与搜索效率；
- 支持对真实编程竞赛问题的建模（如数组排序、数值计算）。
数据生成与泛化能力：
- 通过程序枚举与语义剪枝生成大规模训练数据（百万级程序）；
- 验证模型在跨程序长度的泛化能力。

属性函数（Attribute Function, \(\mathcal{A}\)）：将程序映射到属性向量\(\bm{a}\)，例如函数存在性（Sort是否被调用）。属性需满足：
- 可预测性：可从输入输出样例中推断；
- 搜索空间压缩性：能显著缩小搜索范围。
程序嵌入（Program Embedding）：输入输出样例通过编码器（Encoder）映射为固定维度向量，捕捉样例中的模式（如输出为输入的排序结果）。
自适应课程学习（Adaptive Curriculum）：根据模型当前错误率动态调整训练样本分布，优先学习困难任务。

输入编码：
- 输入输出样例\(\mathcal{E}\)包含\(M\)个样例，每个样例的输入输出类型（标量/数组）通过独热编码表示；
- 整数值通过嵌入层（Embedding Layer）映射为\(E=20\)维向量，填充至固定长度\(L=20\)；
- 单样例编码：输入类型、输入值、输出类型、输出值拼接后通过3层MLP（256维，Sigmoid激活）。
池化与解码：
- 多样例编码通过均值池化聚合为全局表示；
- 解码器通过线性层预测\(C=34\)个函数的出现概率：\(p(c \mid \mathcal{E}) = \sigma(W_c \cdot h_{\text{pooled}} + b_c)\)，其中\(\sigma\)为Sigmoid函数，\(W_c \in \mathbb{R}^{256}\)为函数\(c\)的权重向量。

交叉熵损失：\(\mathcal{L} = -\sum_{c=1}^{C} \left[ y_c \log p(c \mid \mathcal{E}) + (1 - y_c) \log (1 - p(c \mid \mathcal{E})) \right]\)，其中\(y_c \in \{0,1\}\)表示函数\(c\)是否在目标程序中出现。
理论支持： Sort and Add 搜索的期望时间上界由Rank Loss（误排序标签对数）决定，最小化交叉熵等价于优化Rank Loss。

任务类型	数据生成策略	关键参数
程序合成	枚举DSL程序 → 剪枝冗余程序 → 生成输入输出样例	整数范围\([-256, 255]\)
训练/测试划分	确保测试程序与训练集语义不重叠（等价性检查）	程序长度\(T \in \{3,4,5\}\)

搜索加速比（Speedup）：\(\text{Speedup} = \frac{\text{Baseline搜索时间}}{\text{DeepCoder搜索时间}}\)
泛化能力：
- 跨程序长度泛化：训练长度\(T_{\text{train}}=4\)，测试长度\(T_{\text{test}}=5\)；
- 输入输出信息量：使用5个样例，整数范围较大（\(|x| \leq 256\)）。

搜索算法	加速比（\(T=3\)）	加速比（\(T=5\)）	关键结论
DFS	15.2×	6.8×	神经网络引导显著减少无效路径
Sort and Add	62.2×	907×	动态扩展候选函数集效率最优
\(\lambda^2\)	80.4×	9.6×	结合逻辑推理进一步压缩搜索空间

配置	搜索时间（\(T=3\)）	搜索时间（\(T=5\)）	分析
Baseline	314ms	6832s	传统枚举方法时间随\(T\)指数增长
DeepCoder	110ms	2654s	神经网络预测减少候选函数数量
RNN解码器	>1000s	-	序列生成模型难以处理长程序