EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Formally Verified Samplers from Probabilistic Programs with Loops and Conditioning

Alexander Bagnall, Gordon Stewart, Anindya Banerjee

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →