Author or contributor
PROBABILITY & STATISTICS

Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints

Resource type
Authors/contributors
Title
Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints
Abstract
We study the semantic foundation of expressive probabilistic programming languages, that support higher-order functions, continuous distributions, and soft constraints (such as Anglican, Church, and Venture). We define a metalanguage (an idealised version of Anglican) for probabilistic computation with the above features, develop both operational and denotational semantics, and prove soundness, adequacy, and termination. They involve measure theory, stochastic labelled transition systems, and functor categories, but admit intuitive computational readings, one of which views sampled random variables as dynamically allocated read-only variables. We apply our semantics to validate nontrivial equations underlying the correctness of certain compiler optimisations and inference algorithms such as sequential Monte Carlo simulation. The language enables defining probability distributions on higher-order functions, and we study their properties.
Publication
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '16
Pages
525-534
Date
2016
DOI
10/ggdf97
Short Title
Semantics for probabilistic programming
Accessed
2019-11-23T16:36:30Z
Library Catalog
Extra
ZSCC: 0000071 arXiv: 1601.04943
Citation
Staton, S., Yang, H., Heunen, C., Kammar, O., & Wood, F. (2016). Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints. Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science - LICS ’16, 525–534. https://doi.org/10/ggdf97
PROBABILITY & STATISTICS
Attachment
Processing time: 0.02 seconds

Graph of references

(from Zotero to Gephi via Zotnet with this script)
Graph of references