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.

@inproceedings{HoltzenUAI17,
  author    = {Holtzen, Steven and Millstein, Todd and Van den Broeck, Guy},
  title     = {Probabilistic Program Abstractions},
  booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI)},
  url = "http://starai.cs.ucla.edu/papers/HoltzenUAI17.pdf",
  month = Aug,
  year={2017},
  keywords={conference,selective}
}