More Web Proxy on the site http://driver.im/

research-article

Open access

Sound probabilistic inference via guide types

Authors:

Thomas RepsAuthors Info & Claims

PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

Pages 788 - 803

https://doi.org/10.1145/3453483.3454077

Published: 18 June 2021 Publication History

Abstract

Probabilistic programming languages aim to describe and automate Bayesian modeling and inference. Modern languages support programmable inference, which allows users to customize inference algorithms by incorporating guide programs to improve inference performance. For Bayesian inference to be sound, guide programs must be compatible with model programs. One pervasive but challenging condition for model-guide compatibility is absolute continuity, which requires that the model and guide programs define probability distributions with the same support.

This paper presents a new probabilistic programming language that guarantees absolute continuity, and features general programming constructs, such as branching and recursion. Model and guide programs are implemented as coroutines that communicate with each other to synchronize the set of random variables they sample during their execution. Novel guide types describe and enforce communication protocols between coroutines. If the model and guide are well-typed using the same protocol, then they are guaranteed to enjoy absolute continuity. An efficient algorithm infers guide types from code so that users do not have to specify the types. The new programming language is evaluated with an implementation that includes the type-inference algorithm and a prototype compiler that targets Pyro. Experiments show that our language is capable of expressing a variety of probabilistic models with nontrivial control flow and recursion, and that the coroutine-based computation does not introduce significant overhead in actual Bayesian inference.

References

[1]

Jessica Ai, Nimar S. Arora, Ning Dong, Beliz Gokkaya, Thomas Jiang, Anitha Kubendran, Arun Kumar, Michael Tingley, and Narjes Torabi. 2019. HackPPL: A Universal Probabilistic Programming Language. In Int. Workshop on Machine Learning and Prog. Lang. (MAPL’19). https://doi.org/10.1145/3315508.3329974

Digital Library

[2]

Konrad Anton and Peter Thiemann. 2010. Towards Deriving Type Systems and Implementations for Coroutines. In Asian Symp. on Prog. Lang. and Systems (APLAS’10). https://doi.org/10.1007/978-3-642-17164-2_6

[3]

Konrad Anton and Peter Thiemann. 2010. Typing Coroutines. In Trends in Functional Programming (TFP’10). https://doi.org/10.1007/978-3-642-22941-1_2

[4]

Eric Atkinson, Cambridge Yang, and Michael Carbin. 2018. Verifying Handcoded Probabilistic Inference Procedures. arxiv:1805.01863

[5]

Sooraj Bhat, Ashish Agarwal, Richard Vuduc, and Alexander Gray. 2012. A Type Theory for Probability Density Functions. In Princ. of Prog. Lang. (POPL’12). https://doi.org/10.1145/2103656.2103721

Digital Library

[6]

Sooraj Bhat, Johannes Borgström, Andrew D. Gordon, and Claudio Russo. 2013. Deriving Probability Density Functions from Probabilistic Functional Programs. In Tools and Algs. for the Construct. and Anal. of Syst. (TACAS’13). https://doi.org/10.1007/978-3-642-36742-7_35

Digital Library

[7]

Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rishabh Singh, Paul Szerlip, Paul Horsfall, and Noah D. Goodman. 2018. Pyro: Deep Universal Probabilistic Programming. J. Machine Learning Research, 20, 1 (2018), January, https://dl.acm.org/doi/10.5555/3322706.3322734

[8]

Keith A. Bonawitz. 2008. Composable Probabilistic Inference with Blaise. Ph.D. Dissertation. Massachusetts Institute of Technology.

[9]

Johannes Borgström, Ugo Dal Lago, Andrew D. Gordon, and Marcin Szymczak. 2016. A Lambda-Calculus Foundation for Universal Probabilistic Programming. In Int. Conf. on Functional Programming (ICFP’16). https://doi.org/10.1145/2951913.2951942

Digital Library

[10]

Luís Caires and Frank Pfenning. 2010. Session Types as Intuitionistic Linear Propositions. In Int. Conf. on Concurrency Theory (CONCUR’10). https://doi.org/10.1007/978-3-642-15375-4_16

[11]

Luís Caires, Frank Pfenning, and Bernardo Toninho. 2016. Linear Logic Propositions as Session Types. Math. Struct. Comp. Sci., 26, 3 (2016), March, https://doi.org/10.1017/S0960129514000218

[12]

Bob Carpenter, Andrew Gelman, Matthew D. Hoffman, Daniel Lee, Ben Goodrich, Michael Betancourt, Marcus Brubaker, Jiqiang Guo, Peter Li, and Allen Riddell. 2017. Stan: A Probabilistic Programming Language. J. Statistical Softw., 76, 1 (2017), https://doi.org/10.18637/jss.v076.i01

[13]

Simon Castellan and Hugo Paquet. 2019. Probabilistic Programming Inference via Intensional Semantics. In European Symp. on Programming (ESOP’19). https://doi.org/10.1007/978-3-030-17184-1_12

[14]

J. T. Chang and D. Pollard. 1997. Conditioning as disintegration. Netherlands Society for Statistics and Operations Research, 51, 3 (1997), November, https://doi.org/10.1111/1467-9574.00056

[15]

Mario Coppo, Mariangiola Dezani-Ciancaglini, Luca Padovani, and Nobuko Yoshida. 2015. A Gentle Introduction to Multiparty Asynchronous Session Types. In Formal Methods for Eternal Networked Software Systems (SFM’15). https://doi.org/10.1007/978-3-319-18941-3_4

[16]

Marco F. Cusumano-Towner, Feras A. Saad, Alexander K. Lew, and Vikash K. Mansinghka. 2019. Gen: A General-Purpose Probabilistic Programming System with Programmable Inference. In Prog. Lang. Design and Impl. (PLDI’19). https://doi.org/10.1145/3314221.3314642

Digital Library

[17]

Ankush Das, Henry DeYoung, Andreia Mordido, and Frank Pfenning. 2020. Nested Session Types. arxiv:2010.06482

[18]

Adam Foster, Martin Jankowiak, Eli Bingham, Paul Horsfall, Yee Whye Teh, Tom Rainforth, and Noah D. Goodman. 2019. Variational Bayesian Optimal Experimental Design: Efficient Automation of Adaptive Experiments. In Neural Info. Processing Syst. (NIPS’19). arxiv:1903.05480

[19]

Rong Ge, Kai Xu, and Zoubin Ghahramani. 2018. Turing: A Language for Flexible Probabilistic Inference. In Artificial Intelligence and Statistics (AISTATS’18).

[20]

Andrew Gelman, John B. Carlin, Hal S. Stern, David B. Dunson, Aki Vehtari, and Donald B. Rubin. 2013. Bayesian Data Analysis. Chapman and Hall/CRC. https://doi.org/10.1201/b16018

[21]

Zoubin Ghahramani. 2015. Probabilistic machine learning and artificial intelligence. Nature, 521 (2015), May, https://doi.org/10.1038/nature14541

[22]

W. R. Gilks, A. Thomas, and D. J. Spiegelhalter. 1994. A Language and Program for Complex Bayesian Modelling. J. Royal Statistical Society, 43, 1 (1994), January, https://doi.org/10.2307/2348941

[23]

Noah D. Goodman, Vikash K. Mansinghka, Daniel Roy, Keith A. Bonawitz, and Joshua B. Tenenbaum. 2008. Church: A language for generative models. In Uncertainty in Artificial Intelligence (UAI’08). https://dl.acm.org/doi/10.5555/3023476.3023503

Digital Library

[24]

Noah D. Goodman and Andreas Stuhlmüller. 2014. The Design and Implementation of Probabilistic Programming Languages. Available on. http://dippl.org

[25]

Thomas L. Griffiths, Charles Kemp, and Joshua B. Tenenbaum. 2008. Bayesian Models of Cognition. In The Cambridge Handbook of Computational Psychology. Cambridge University Press. https://doi.org/10.1017/CBO9780511816772.006

[26]

Robert Harper. 2016. Practical Foundations for Programming Languages. Cambridge University Press. https://dl.acm.org/doi/book/10.5555/3002812

Digital Library

[27]

C. A. R. Hoare. 1978. Communicating Sequential Processes. Commun. ACM, 21, 8 (1978), August, https://doi.org/10.1145/359576.359585

Digital Library

[28]

Kohei Honda. 1993. Types for Dyadic Interaction. In Int. Conf. on Concurrency Theory (CONCUR’93). https://doi.org/10.1007/3-540-57208-2_35

[29]

Kohei Honda, Vasco T. Vasconcelos, and Makoto Kubo. 1998. Language Primitives and Type Discipline for Structured Communication-Based Programming. In European Symp. on Programming (ESOP’98). https://doi.org/10.1007/BFb0053567

[30]

Kohei Honda, Nobuko Yoshida, and Marco Carbone. 2008. Multiparty Asynchronous Session Types. In Princ. of Prog. Lang. (POPL’08). https://doi.org/10.1145/1328438.1328472

Digital Library

[31]

Daniel Huang, Jean-Baptiste Tristan, and Greg Morrisett. 2017. Compiling Markov Chain Monte Carlo Algorithms for Probabilistic Modeling. In Prog. Lang. Design and Impl. (PLDI’17). https://doi.org/10.1145/3062341.3062375

Digital Library

[32]

Chung-Kil Hur, Aditya V. Nori, Sriram K. Rajamani, and Selva Samuel. 2015. A Provably Correct Sampler for Probabilistic Programs. In Leibniz International Proceedings in Informatics (LIPIcs’15). https://doi.org/10.4230/LIPIcs.FSTTCS.2015.475

[33]

F. Jelinek, J. D. Lafferty, and R. L. Mercer. 1992. Basic Methods of Probabilistic Context Free Grammars. In Speech Recognition and Understanding. https://doi.org/10.1007/978-3-642-76626-8_35

[34]

Donald E. Knuth. 1997. The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. Addison-Wesley. https://dl.acm.org/doi/book/10.5555/270146

Digital Library

[35]

Dexter Kozen. 1981. Semantics of Probabilistic Programs. J. Comput. Syst. Sci., 22, 3 (1981), June, https://doi.org/10.1016/0022-0000(81)90036-2

[36]

Wonyeol Lee, Hangyeol Yu, Xavier Rival, and Hongseok Yang. 2019. Towards Verified Stochastic Variational Inference for Probabilistic Programs. Proc. ACM Program. Lang., 4, POPL (2019), December, https://doi.org/10.1145/3371084

Digital Library

[37]

Alexander K. Lew, Marco F. Cusumano-Towner, Benjamin Sherman, Michael Carbin, and Vikash K. Mansinghka. 2019. Trace Types and Denotational Semantics for Sound Programmable Inference in Probabilistic Languages. Proc. ACM Program. Lang., 4, POPL (2019), December, https://doi.org/10.1145/3371087

Digital Library

[38]

Vikash K. Mansinghka, Ulrich Schaechtle, Shivam Handa, Alexey Radul, Yutian Chen, and Martin C. Rinard. 2018. Probabilistic Programming with Programmable Inference. In Prog. Lang. Design and Impl. (PLDI’18). https://doi.org/10.1145/3296979.3192409

Digital Library

[39]

Robin Milner. 1989. Communication and Concurrency. Prentice-Hall, Inc. https://dl.acm.org/doi/book/10.5555/534666

Digital Library

[40]

Robin Milner, Joachim Parrow, and David Walker. 1992. A Calculus of Mobile Processes, I. Information and Computation, 100, 1 (1992), September, https://doi.org/10.1016/0890-5401(92)90008-4

Digital Library

[41]

Robin Milner, Joachim Parrow, and David Walker. 1992. A Calculus of Mobile Processes, II. Information and Computation, 100, 1 (1992), September, https://doi.org/10.1016/0890-5401(92)90009-5

Digital Library

[42]

Eugenio Moggi. 1989. Computational lambda-calculus and monads. In Logic in Computer Science (LICS’89). https://doi.org/10.1109/LICS.1989.39155

[43]

Lawrence M. Murray. 2015. Bayesian State-Space Modelling on High-Performance Hardware Using LibBi. J. Statistical Softw., 67, 10 (2015), https://doi.org/10.18637/jss.v067.i10

[44]

Praveen Narayanan, Jacques Carette, Wren Romano, Chung-chieh Shan, and Robert Zinkov. 2016. Probabilistic Inference by Program Transformation in Hakaru (System Description). In Int. Symp. on Functional and Logic Programming (FLOPS’16). https://doi.org/10.1007/978-3-319-29604-3_5

[45]

Martyn Plummer. 2003. JAGS: A Program for Analysis of Bayesian Graphical Models using Gibbs Sampling. In Int. Workshop on Distributed Statistical Comp. (DSC’03).

[46]

Feras A. Saad, Marco F. Cusumano-Towner, Ulrich Schaechtle, Martin C. Rinard, and Vikash K. Mansinghka. 2019. Bayesian Synthesis of Probabilistic Programs for Automatic Data Modeling. Proc. ACM Program. Lang., 3, POPL (2019), January, https://doi.org/10.1145/3290350

Digital Library

[47]

Alceste Scalas and Nobuko Yoshida. 2019. Less Is More: Multiparty Session Types Revisited. Proc. ACM Program. Lang., 3, POPL (2019), January, https://doi.org/10.1145/3290343

Digital Library

[48]

Adam Ścibior, Zoubin Ghahramani, and Andrew D. Gordon. 2015. Practical Probabilistic Programming with Monads. In Symp. on Haskell (Haskell’15). https://doi.org/10.1145/2887747.2804317

Digital Library

[49]

Adam Ścibior, Ohad Kammar, Matthijs Vákár, Sam Staton, Hongseok Yang, Yufei Cai, Klaus Ostermann, Sean K. Moss, Chris Heunen, and Zoubin Ghahramani. 2017. Denotational Validation of Higher-Order Bayesian Inference. Proc. ACM Program. Lang., 2, POPL (2017), December, https://doi.org/10.1145/3158148

Digital Library

[50]

Chung-chieh Shan and Norman Ramsey. 2017. Exact Bayesian Inference by Symbolic Disintegration. In Princ. of Prog. Lang. (POPL’17). https://doi.org/10.1145/3009837.3009852

Digital Library

[51]

Peter Thiemann and Vasco T. Vasconcelos. 2016. Context-Free Session Types. In Int. Conf. on Functional Programming (ICFP’16). https://doi.org/10.1145/2951913.2951926

Digital Library

[52]

Peter Thiemann and Vasco T. Vasconcelos. 2019. Label-Dependent Session Types. Proc. ACM Program. Lang., 4, POPL (2019), December, https://doi.org/10.1145/3371135

Digital Library

[53]

Dustin Tran, Matthew D. Hoffman, Rif A. Saurous, Eugene Brevdo, Kevin Murphy, and David M. Blei. 2017. Deep Probabilistic Programming. In Int. Conf. on Learning Representations (ICLR’17).

[54]

Philip Wadler. 2012. Propositions as Sessions. In Int. Conf. on Functional Programming (ICFP’12). https://doi.org/10.1145/2364527.2364568

Digital Library

[55]

Di Wang, Jan Hoffmann, and Thomas Reps. 2021. Sound Probabilistic Inference via Guide Types. arxiv:2104.03598

[56]

Stefan Webb, Adam Golinski, Robert Zinkov, N. Siddharth, Tom Rainforth, Yee Whye Teh, and Frank Wood. 2018. Faithful Inversion of Generative Models for Effective Amortized Inference. In Neural Info. Processing Syst. (NIPS’18). https://dl.acm.org/doi/10.5555/3327144.3327229

[57]

Website. 2020. greenlet: Lightweight concurrent programming. Available on. https://greenlet.readthedocs.io

[58]

Frank Wood, Jan Willem van de Meent, and Vikash K. Mansinghka. 2014. A New Approach to Probabilistic Programming Inference. In Artificial Intelligence and Statistics (AISTATS’14).

[59]

Robert Zinkov and Chung-chieh Shan. 2017. Composing Inference Algorithms as Program Transformations. In Uncertainty in Artificial Intelligence (UAI’17). arxiv:1603.01882

Cited By

Böck MSchröder MCito JFilkov VRay BZhou M(2024)Language-Agnostic Static Analysis of Probabilistic ProgramsProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695031(78-90)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695031
Pham LWang DSaad FHoffmann J(2024)Programmable MCMC with Soundly Composed Guide ProgramsProceedings of the ACM on Programming Languages10.1145/36897488:OOPSLA2(1051-1080)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689748
Becker MLew AWang XGhavami MHuot MRinard MMansinghka V(2024)Probabilistic Programming with Programmable Variational InferenceProceedings of the ACM on Programming Languages10.1145/36564638:PLDI(2123-2147)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656463
Show More Cited By

Index Terms

Sound probabilistic inference via guide types
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic inference problems
2. Theory of computation
  1. Models of computation
    1. Probabilistic computation
  2. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Trace types and denotational semantics for sound programmable inference in probabilistic languages

Modern probabilistic programming languages aim to formalize and automate key aspects of probabilistic modeling and inference. Many languages provide constructs for programmable inference that enable developers to improve inference speed and accuracy by ...
Programmable MCMC with Soundly Composed Guide Programs

Probabilistic programming languages (PPLs) provide language support for expressing flexible probabilistic models and solving Bayesian inference problems. PPLs with programmable inference make it possible for users to obtain improved results by ...
HackPPL: a universal probabilistic programming language
MAPL 2019: Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages

HackPPL is a probabilistic programming language (PPL) built within the Hack programming language. Its universal inference engine allows developers to perform inference across a diverse set of models expressible in arbitrary Hack code. Through language-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 2021

1341 pages

ISBN:9781450383912

DOI:10.1145/3453483

General Chair:
Stephen N. Freund
Williams College, USA
,
Program Chair:
Eran Yahav
Technion, Israel

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

a gift from Rajiv and Ritu Batra
DARPA under AA contract
NSF under SaTC
NSF under CAREER
ONR
NSF under SHF

Conference

PLDI '21

Sponsor:

SIGPLAN

PLDI '21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 20 - 25, 2021

Virtual, Canada

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
562
Total Downloads

Downloads (Last 12 months)132
Downloads (Last 6 weeks)15

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Böck MSchröder MCito JFilkov VRay BZhou M(2024)Language-Agnostic Static Analysis of Probabilistic ProgramsProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695031(78-90)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695031
Pham LWang DSaad FHoffmann J(2024)Programmable MCMC with Soundly Composed Guide ProgramsProceedings of the ACM on Programming Languages10.1145/36897488:OOPSLA2(1051-1080)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689748
Becker MLew AWang XGhavami MHuot MRinard MMansinghka V(2024)Probabilistic Programming with Programmable Variational InferenceProceedings of the ACM on Programming Languages10.1145/36564638:PLDI(2123-2147)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656463
Li JWang EZhang Y(2024)Compiling Probabilistic Programs for Variable Elimination with Information FlowProceedings of the ACM on Programming Languages10.1145/36564488:PLDI(1755-1780)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656448
Lew AGhavamizadeh MRinard MMansinghka V(2023)Probabilistic Programming with Stochastic ProbabilitiesProceedings of the ACM on Programming Languages10.1145/35912907:PLDI(1708-1732)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591290
Bagnall AStewart GBanerjee A(2023)Formally Verified Samplers from Probabilistic Programs with Loops and ConditioningProceedings of the ACM on Programming Languages10.1145/35912207:PLDI(1-24)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591220
Li JVen LShi PZhang Y(2023)Type-Preserving, Dependence-Aware Guide Generation for Sound, Effective Amortized Probabilistic InferenceProceedings of the ACM on Programming Languages10.1145/35712437:POPL(1454-1482)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571243
Lee WRival XYang H(2023)Smoothness Analysis for Probabilistic Programs with Application to Optimised Variational InferenceProceedings of the ACM on Programming Languages10.1145/35712057:POPL(335-366)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571205

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents