[NIPS2018]Library Learning for Neurally-Guided Bayesian Program Induction
-
- 1. 摘要
- 2. 问题定义
- 3. 方法介绍
-
- 3.1. 分层贝叶斯框架
- 3.2. Explore阶段：寻找程序集合Fx
- 3.3. Compile阶段: 学习识别模型q
- 3.4. Compress阶段: 学习生成模型 (DSL)
- 4. 实验结果
作者：Kevin Ellis，Lucas Morales，Mathias Sablé-Meyer，Armando Solar-Lezama，Joshua B. Tenenbaum。（MIT）
1. 摘要
一般的程序归纳方法需要手工定义一个DSL（domain-specific language），用来限制程序的搜索空间并预定义一些程序的先验知识。而该文则提出了一种称之为EC2的方法，可以在训练用来搜索程序的神经网络时，进一步的学习新的函数并添加到DSL中（library of program components），然后在更新后的DSL中重新搜索程序。
2. 问题定义
该文提出的方法是在训练用以搜寻程序的神经网络时，不断更新并丰富DSL。上面是文章中举出的可以使用该方法的三个场景。三个例子分别为列表处理List Processing，文本编辑和符号回归，前两个输入为一些输入输出对，通过输入输出对有监督的学习出一个正确的程序，最后一个为输入图像，在提前限制的有理函数中利用神经网络搜索程序。
3. 方法介绍
EC2（ECC, Explore/Compress/Compile）。
Explore阶段，给定任务（如几百个例子），按照当前的DSL和神经网络搜索符合条件的程序。
Compress阶段，通过对上一步得到的程序分析得到一些规则，并将其变为可调用的代码段，增加到DSL中。
Compile阶段，通过新的DSL和代码训练神经网络，提高网络搜索的结果。
3.1. 分层贝叶斯框架
分层贝叶斯框架Hierarchical Bayesian Framing。
考虑一个输入任务的集合X，定义似然模型P[x|p]，其中p是一个程序，该模型可以理解为程序p在任务x的评分（x∈X）。同时从程序p中推理DSL，记为D。D和实值权重矢量θ共同定义(D, θ)为程序的生成模型。此时，任务的目标变成了求给定X下的(D, θ)的最大后验概率。公式如下：
但是，由于程序p属于一个无穷集合，因此上式实际不可计算。实际中，可以定义一个有限的程序p集合frontier（Fx），只在Fx上求解。通过最大化下面的式子来近似得到最大后验概率。
Explore: 最大化Fx，即，固定(D, θ)，寻找新的程序p加入Fx集合使得上式最大。
Compress:最大化DSL，固定Fx，对上式的 θ 求积分得到D，然后再更新 θ。
搜索新的程序时，由于程序的搜索空间太大，采用训练一个神经识别模型q来搜索程序p，q(p|x) ≈ P[p|x, D, θ] ∝ P[x|p]P[p|D, θ]。
Compile: 训练q使得P[x|p]P[p|D, θ]最大。样本p可以取自Explore阶段找到程序和从DSL中采样得到。
三个步骤之间的相互关系如上图所示。1）两个虚线为Explore阶段，根据当前的DSL和识别模型q寻找新的程序p。2）得到程序p后进行Compress阶段，求解DSL。3）根据程序p和新的DSL采样可以再次训练识别模型q。
3.2. Explore阶段：寻找程序集合Fx
从DSL中直接通过枚举的方式寻找程序p，如果p满足P[x|p] > 0，则加入Fx。具体DSL形式可以用λ演算表达式来表示。定义DSL如下：
(D, θ)：D是λ演算表达式的集合，θ是长度为|D|+1的向量，分别对应D中每个表达式和一个常量的出现概率。这样定义DSL后，就得到了一个程序的分布，P[p|D, θ]，然后就可以从中枚举程序了。
3.3. Compile阶段: 学习识别模型q
训练一个识别模型q的目的是分摊（amortize）搜索程序时的代价。在先验(D, θ)下，对每个任务预测一个使得P[x|p]概率最大的程序p。具体网络可以参考DeepCoder。
3.4. Compress阶段: 学习生成模型 (DSL)
通过加入新的λ表达式产生新的DSL，直到下式不再增加。新的λ表达式来自Fx中的程序的片段。
总的算法流程如下图：
4. 实验结果
略
论文链接：https://papers.nips.cc/paper/8006-learning-libraries-of-subroutines-for-neurallyguided-bayesian-program-induction