Formally Verified Samplers from Probabilistic Programs with Loops and Conditioning
Proceedings of the ACM on Programming Languages · 06.06.2023 · 7 (PLDI) · 1-24
DOI: 10.1145/3591220 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 06.06.2023. Verfasst von Alexander Bagnall und 2 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 63 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We present Zar: a formally verified compiler pipeline from discrete probabilistic programs with unbounded loops in the conditional probabilistic guarded command language (cpGCL) to proved-correct executable samplers in the random bit model. We exploit the key idea that all discrete probability distributions can be reduced to unbiased coin-flipping schemes. The compiler pipeline first translates cpGCL programs into choice-fix trees, an intermediate representation suitable for reduction of biased probabilistic choices. Choice-fix trees are then translated to coinductive interaction trees for execution within the random bit model. The correctness of the composed translations establishes the sampling equidistribution theorem: compiled samplers are correct wrt. the conditional weakest pre-expectation semantics of cpGCL source programs. Zar is implemented and fully verified in the Coq proof assistant. We extract verified samplers to OCaml and Python and empirically validate them on a number of illustrative examples.
Zitieren
APA
Bagnall, A., Stewart, G., & Banerjee, A. (2023). Formally Verified Samplers from Probabilistic Programs with Loops and Conditioning. Proceedings of the ACM on Programming Languages, 7(PLDI), 1-24. https://doi.org/10.1145/3591220
Vancouver
Bagnall A, Stewart G, Banerjee A. Formally Verified Samplers from Probabilistic Programs with Loops and Conditioning. Proceedings of the ACM on Programming Languages. 2023;7(PLDI):1-24. doi:10.1145/3591220
BibTeX
@article{Bagnall2023,
author = {Bagnall, Alexander and Stewart, Gordon and Banerjee, Anindya},
title = {Formally Verified Samplers from Probabilistic Programs with Loops and Conditioning},
journal = {Proceedings of the ACM on Programming Languages},
year = {2023},
volume = {7},
number = {PLDI},
pages = {1--24},
doi = {10.1145/3591220}
}
EUVIMED