From high-level inference algorithms to efficient code
From high-level inference algorithms to efficient code
复制标题
DOI：
10.1145/3341702
复制
发表时间：
2018-05
影响因子：
--
通讯作者：
R. Walia;P. Narayanan;J. Carette;Sam Tobin-Hochstadt;Chung-chieh Shan
中科院分区：
文献类型：
--
作者：
R. Walia;P. Narayanan;J. Carette;Sam Tobin-Hochstadt;Chung-chieh Shan
概率编程语言很有价值，因为它们允许领域专家表达概率模型和推理算法，而不必担心不相关的细节。然而，几十年来，仍然存在一类重要的和流行的概率推理算法，其有效实施需要繁琐且容易出错的人工低级编码。它们是算法，其惯用表达式要求随机数组变量是潜在的或其可能性是共轭的。尽管这是实践者在纸上交流和组成这些算法的方式，但执行这样的表达式需要消除潜在变量，并通过符号数学识别共轭。此外，匹配手写代码的性能需要将循环的速度提高一倍以上。我们展示了如何编译直接和简洁地表达这些所需推理算法的概率程序，同时保持效率。我们引入了新的转换，将带有数组的高级概率程序转换为纯循环代码。然后，我们大量使用特定于域的不变量和规范来优化代码，并在每次执行时专门化和JIT编译代码。由此产生的性能与手动实现相比具有竞争力。
Probabilistic programming languages are valuable because they allow domain experts to express probabilistic models and inference algorithms without worrying about irrelevant details. However, for decades there remained an important and popular class of probabilistic inference algorithms whose efficient implementation required manual low-level coding that is tedious and error-prone. They are algorithms whose idiomatic expression requires random array variables that are latent or whose likelihood is conjugate. Although that is how practitioners communicate and compose these algorithms on paper, executing such expressions requires eliminating the latent variables and recognizing the conjugacy by symbolic mathematics. Moreover, matching the performance of handwritten code requires speeding up loops by more than a constant factor. We show how probabilistic programs that directly and concisely express these desired inference algorithms can be compiled while maintaining efficiency. We introduce new transformations that turn high-level probabilistic programs with arrays into pure loop code. We then make great use of domain-specific invariants and norms to optimize the code, and to specialize and JIT-compile the code per execution. The resulting performance is competitive with manual implementations.