Efficient synthesis of probabilistic programs
Efficient synthesis of probabilistic programs
复制标题
概率程序的高效综合
DOI：
10.1145/2737924.2737982
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Deepak Vijaykeerthy
中科院分区：
文献类型：
--
作者：
A. Nori;Sherjil Ozair;S. Rajamani;Deepak Vijaykeerthy
我们展示了如何从真实世界的数据集中自动合成概率程序。这样的综合是可行的，因为结合了两种技术：(1)我们借用了确定性程序综合中的“草图”思想，允许程序员编写带有“洞”的骨架程序。草图使程序员能够传达对所需程序结构的特定领域的直觉，并修剪搜索空间。(2)设计了一种高效的基于马尔可夫链蒙特卡罗(MCMC)的合成算法，用程序片段实例化草图中的漏洞。我们的算法有效地合成了一个与数据最一致的概率程序。概率规划综合的一个核心困难是计算候选规划P生成数据D的似然L(P|D)。本文提出了一种利用混合高斯分布来计算似然的近似方法，从而避免了昂贵的积分计算。这种近似的使用使我们能够将候选方案的可能性评估速度提高1000倍，并使基于马尔可夫链蒙特卡罗的搜索变得可行。我们已经在一个名为PSKETCH的工具中实现了我们的算法，我们的结果是PSKETCH能够自动综合16个非平凡的真实世界概率程序。
We show how to automatically synthesize probabilistic programs from real-world datasets. Such a synthesis is feasible due to a combination of two techniques: (1) We borrow the idea of ``sketching'' from synthesis of deterministic programs, and allow the programmer to write a skeleton program with ``holes''. Sketches enable the programmer to communicate domain-specific intuition about the structure of the desired program and prune the search space, and (2) we design an efficient Markov Chain Monte Carlo (MCMC) based synthesis algorithm to instantiate the holes in the sketch with program fragments. Our algorithm efficiently synthesizes a probabilistic program that is most consistent with the data. A core difficulty in synthesizing probabilistic programs is computing the likelihood L(P | D) of a candidate program P generating data D. We propose an approximate method to compute likelihoods using mixtures of Gaussian distributions, thereby avoiding expensive computation of integrals. The use of such approximations enables us to speed up evaluation of the likelihood of candidate programs by a factor of 1000, and makes Markov Chain Monte Carlo based search feasible. We have implemented our algorithm in a tool called PSKETCH, and our results are encouraging PSKETCH is able to automatically synthesize 16 non-trivial real-world probabilistic programs.