Exact Recursive Probabilistic Programming
Exact Recursive Probabilistic Programming
复制标题
DOI：
10.1145/3586050
复制
发表时间：
2022-10
影响因子：
--
通讯作者：
David Chiang;Colin McDonald;Chung-chieh Shan
中科院分区：
文献类型：
--
作者：
David Chiang;Colin McDonald;Chung-chieh Shan
对递归数据的递归调用对于生成概率分布是有用的，并且概率编程允许以模块化和直观的方式来表达对这些分布的计算。精确推理也很有用，但不幸的是，现有的概率编程语言不能对递归数据上的递归调用执行精确推理，迫使程序员手动编写许多应用程序。我们介绍了一种概率语言，其中各种各样的递归可以自然地表达，并进行准确的推理。例如，概率下推自动机及其推广易于表达，并且可以自动导出多项式时间解析算法。我们使用与去功能化和重新功能化相关的程序转换来消除递归数据类型。这些变换由线性类型系统保证是正确的，并且如果有一个成功的变换选择，则保证由贪婪算法找到。
Recursive calls over recursive data are useful for generating probability distributions, and probabilistic programming allows computations over these distributions to be expressed in a modular and intuitive way. Exact inference is also useful, but unfortunately, existing probabilistic programming languages do not perform exact inference on recursive calls over recursive data, forcing programmers to code many applications manually. We introduce a probabilistic language in which a wide variety of recursion can be expressed naturally, and inference carried out exactly. For instance, probabilistic pushdown automata and their generalizations are easy to express, and polynomial-time parsing algorithms for them are derived automatically. We eliminate recursive data types using program transformations related to defunctionalization and refunctionalization. These transformations are assured correct by a linear type system, and a successful choice of transformations, if there is one, is guaranteed to be found by a greedy algorithm.