Sound Abstraction and Decomposition of Probabilistic Programs

35th International Conference on Machine Learning (ICML 2018), Stockholm, Sweden, July 10-15, 2018.
Steven Holtzen, Guy Van den Broeck, Todd Millstein
Probabilistic programming languages are a flexible tool for specifying statistical models, but this flexibility comes at the expense of efficient analysis. It is currently difficult to compactly represent the subtle independence properties of a probabilistic program and to exploit independence properties to decompose inference. Classical graphical model abstractions do capture some properties of the underlying distribution, enabling inference algorithms to operate at the level of the graph topology. However, we observe that graph-based abstractions are often too coarse to capture interesting properties of programs. We propose a form of sound abstraction for probabilistic programs wherein the abstractions are themselves simplified programs. We provide a theoretical foundation for these abstractions, as well as an algorithm to generate them. Experimentally, we also illustrate the practical benefits of our framework as a tool to decompose probabilistic program inference.