Probabilistic Program Abstractions

Steven Holtzen, Todd Millstein, Guy Van den Broeck
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:621-630, 2017.

Abstract

Abstraction is a fundamental tool for reasoning about complex systems. Program abstraction has been utilized to great effect for analyzing deterministic programs. At the heart of program abstraction is the relationship between a concrete program, which is difficult to analyze, and an abstract program, which is more tractable. Program abstractions, however, are typically not probabilistic. We generalize non-deterministic program abstractions to probabilistic program abstractions by explicitly quantifying the non-deterministic choices. Our framework upgrades key definitions and properties of abstractions to the probabilistic context. We also discuss preliminary ideas for performing inference on probabilistic abstractions and general probabilistic programs.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-holtzen17a, title = {Probabilistic Program Abstractions}, author = {Holtzen, Steven and Millstein, Todd and Broeck, Guy Van den}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {621--630}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/holtzen17a/holtzen17a.pdf}, url = {https://proceedings.mlr.press/r15/holtzen17a.html}, abstract = {Abstraction is a fundamental tool for reasoning about complex systems. Program abstraction has been utilized to great effect for analyzing deterministic programs. At the heart of program abstraction is the relationship between a concrete program, which is difficult to analyze, and an abstract program, which is more tractable. Program abstractions, however, are typically not probabilistic. We generalize non-deterministic program abstractions to probabilistic program abstractions by explicitly quantifying the non-deterministic choices. Our framework upgrades key definitions and properties of abstractions to the probabilistic context. We also discuss preliminary ideas for performing inference on probabilistic abstractions and general probabilistic programs.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Probabilistic Program Abstractions %A Steven Holtzen %A Todd Millstein %A Guy Van den Broeck %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-holtzen17a %I PMLR %P 621--630 %U https://proceedings.mlr.press/r15/holtzen17a.html %V R15 %X Abstraction is a fundamental tool for reasoning about complex systems. Program abstraction has been utilized to great effect for analyzing deterministic programs. At the heart of program abstraction is the relationship between a concrete program, which is difficult to analyze, and an abstract program, which is more tractable. Program abstractions, however, are typically not probabilistic. We generalize non-deterministic program abstractions to probabilistic program abstractions by explicitly quantifying the non-deterministic choices. Our framework upgrades key definitions and properties of abstractions to the probabilistic context. We also discuss preliminary ideas for performing inference on probabilistic abstractions and general probabilistic programs. %Z Reissued by PMLR on 04 October 2026.
APA
Holtzen, S., Millstein, T. & Broeck, G.V.d.. (2017). Probabilistic Program Abstractions. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:621-630 Available from https://proceedings.mlr.press/r15/holtzen17a.html. Reissued by PMLR on 04 October 2026.

Related Material