Just-in-time learning for bottom-up enumerative synthesis
Just-in-time learning for bottom-up enumerative synthesis
复制标题
自下而上的枚举综合的即时学习
DOI：
10.1145/3428295
复制
发表时间：
2020
影响因子：
--
通讯作者：
Polikarpova, Nadia
中科院分区：
文献类型：
--
作者：
Barke, Shraddha;Peleg, Hila;Polikarpova, Nadia
程序合成的一个关键挑战是合成器必须探索的搜索空间的天文数字大小。为了应对这一挑战，最近的工作提出使用学习概率模型来指导合成。然而，对于没有高质量训练数据可用的问题域，获得这样的模型可能是不可行的。在这项工作中，我们介绍了一种替代方法来指导程序合成：而不是提前训练模型，我们展示了如何在合成过程中通过学习沿途遇到的部分解来及时引导一个模型。为了充分利用该模型，我们还提出了一种新的程序枚举算法，我们称之为引导自底向上搜索，它扩展了基于概率模型的高效自底向上搜索。我们在一个名为Probe的工具中实现了这种方法，该工具针对流行的语法引导合成（SyGuS）格式中的问题。我们根据文献中的基准对Probe进行了评估，并表明它比无引导的自下而上搜索和最先进的概率引导合成器都取得了显著的性能提升，后者已经在现有解决方案的语料库上进行了训练。此外，我们还展示了这些性能提升并不是以牺牲解决方案质量为代价的：Probe生成的程序只比最短的解决方案稍微冗长一点，并且没有执行不必要的分例。
A key challenge in program synthesis is the astronomical size of the search space the synthesizer has to explore. In response to this challenge, recent work proposed to guide synthesis using learned probabilistic models. Obtaining such a model, however, might be infeasible for a problem domain where no high-quality training data is available. In this work we introduce an alternative approach to guided program synthesis: instead of training a model ahead of time we show how to bootstrap one just in time, during synthesis, by learning from partial solutions encountered along the way. To make the best use of the model, we also propose a new program enumeration algorithm we dub guided bottom-up search, which extends the efficient bottom-up search with guidance from probabilistic models.We implement this approach in a tool called Probe, which targets problems in the popular syntax-guided synthesis (SyGuS) format. We evaluate Probe on benchmarks from the literature and show that it achieves significant performance gains both over unguided bottom-up search and over a state-of-the-art probability-guided synthesizer, which had been trained on a corpus of existing solutions. Moreover, we show that these performance gains do not come at the cost of solution quality: programs generated by Probe are only slightly more verbose than the shortest solutions and perform no unnecessary case-splitting.
登录
查看更多内容
DOI：
--
发表时间：
2018-09
期刊：
--
影响因子：
--
作者：
X. Si;Yuan Yang;H. Dai;M. Naik;Le Song
通讯作者：
X. Si;Yuan Yang;H. Dai;M. Naik;Le Song
完美是优秀的敌人：尽力而为的程序综合（神器）
DOI：
10.4230/darts.6.2.16
发表时间：
2020
期刊：
2016 IEEE 32nd International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
Hila Peleg;N. Polikarpova
通讯作者：
N. Polikarpova
影响因子：
--
作者：
Xinyu Wang;Işıl Dillig;Rishabh Singh
通讯作者：
Xinyu Wang;Işıl Dillig;Rishabh Singh
使用有限树自动机合成数据完成脚本
影响因子：
--
作者：
Xinyu Wang;Işıl Dillig;Rishabh Singh
通讯作者：
Rishabh Singh
Leon 工具中演绎合成和修复的更新
DOI：
--
发表时间：
2016
期刊：
SYNT@CAV
影响因子：
--
作者：
Manos Koukoutos;Etienne Kneuss;Viktor Kunčak
通讯作者：
Viktor Kunčak