Program synthesis is challenging largely because of the difficulty of search in a large space of programs. Human programmers routinely tackle the task of writing complex programs by writing sub-programs and then analyzing their intermediate results to compose them in appropriate ways. Motivated by this intuition, we present a new synthesis approach that leverages learning to guide a bottom-up search over programs. In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a given set of input-output examples. This is a powerful combination because of several emergent properties. First, in bottom-up search, intermediate programs can be executed, providing semantic information to the neural network. Second, given the concrete values from those executions, we can exploit rich features based on recent work on property signatures. Finally, bottom-up search allows the system substantial flexibility in what order to generate the solution, allowing the synthesizer to build up a program from multiple smaller sub-programs. Overall, our empirical evaluation finds that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches. We demonstrate the effectiveness of our technique on two datasets, one from the SyGuS competition and one of our own creation.


翻译:程序合成之所以具有挑战性,主要是因为在很大的程序空间中搜索难度很大。 人类程序设计员通常通过撰写子程序,处理撰写复杂程序的任务,然后分析其中间结果,以适当的方式形成它们。 受这种直觉的启发,我们提出了一个新的综合方法,利用学习来引导自下而上搜索程序。 特别是,我们训练了一个模型,在根据一套特定的输入-产出实例进行搜索时,确定中间值构成的优先次序。 这是一个强大的组合,因为有几个突发特性。 首先,在自下而上的搜索中,可以执行中间程序,向神经网络提供语义信息。 其次,鉴于这些处决的具体价值,我们可以利用基于最近关于属性签名的工作的丰富特征。 最后,自下而上的搜索使系统在产生解决方案时具有相当大的灵活性,使合成器能够从多个较小的子程序中建立程序。 总体而言,我们的经验评估发现,学习和自下而上搜索的组合非常有效,甚至可以用简单的监督学习方法。 我们展示了我们在两个数据集上的方法的有效性, 一个来自SYGu的创建和我们自己的竞争。

0
下载
关闭预览

相关内容

【干货书】用Python构建概率图模型,173页pdf
专知会员服务
111+阅读 · 2020年8月23日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
106+阅读 · 2020年6月10日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Andrew NG的新书《Machine Learning Yearning》
我爱机器学习
11+阅读 · 2016年12月7日
Arxiv
0+阅读 · 2021年11月22日
Video-to-Video Synthesis
Arxiv
9+阅读 · 2018年8月20日
Learning to Focus when Ranking Answers
Arxiv
5+阅读 · 2018年8月8日
Arxiv
7+阅读 · 2018年1月30日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Andrew NG的新书《Machine Learning Yearning》
我爱机器学习
11+阅读 · 2016年12月7日
Top
微信扫码咨询专知VIP会员