journal article
Open Access
Nov 13, 2020
Scaling exact inference for discrete probabilistic programs
Proceedings of the ACM on Programming Languages
Vol. 4
No. OOPSLA
pp. 1-31
·
Association for Computing Machinery (ACM)
Abstract
Probabilistic programming languages (PPLs) are an expressive means of representing and reasoning about probabilistic models. The computational challenge ofprobabilistic inferenceremains the primary roadblock for applying PPLs in practice. Inference is fundamentally hard, so there is no one-size-fits all solution. In this work, we target scalable inference for an important class of probabilistic programs: those whose probability distributions arediscrete. Discrete distributions are common in many fields, including text analysis, network verification, artificial intelligence, and graph analysis, but they prove to be challenging for existing PPLs.We develop a domain-specific probabilistic programming language called Dice that features a new approach to exact discrete probabilistic program inference. Dice exploits program structure in order to factorize inference, enabling us to perform exact inference on probabilistic programs with hundreds of thousands of random variables. Our key technical contribution is a new reduction from discrete probabilistic programs to weighted model counting (WMC). This reduction separates the structure of the distribution from its parameters, enabling logical reasoning tools to exploit that structure for probabilistic inference. We (1) show how to compositionally reduce Dice inference to WMC, (2) prove this compilation correct with respect to a denotational semantics, (3) empirically demonstrate the performance benefits over prior approaches, and (4) analyze the types of structure that allow Dice to scale to large probabilistic programs.
Topics
No keywords indexed for this article. Browse by subject →
References
85
[2]
[4]
Algebraic Decision Diagrams and Their Applications
R.I. Bahar, E.A. Frohm, C.M. Gaona et al.
Formal Methods in System Design
10.1023/a:1008699807402
[6]
Vaishak Belle , Andrea Passerini , and Guy Van den Broeck . 2015 . Probabilistic Inference in Hybrid Domains by Weighted Model Integration . In Proc. of IJCAI. 2770 - 2776 . Vaishak Belle, Andrea Passerini, and Guy Van den Broeck. 2015. Probabilistic Inference in Hybrid Domains by Weighted Model Integration. In Proc. of IJCAI. 2770-2776.
[7]
Armin Biere . 2009. Bounded Model Checking . In Handbook of Satisfiability, Armin Biere, Marijn J . H. Heule, Hans van Maaren, and Toby Walsh (Eds.). Frontiers in Artificial Intelligence and Applications, Vol. 185 . IOS Press , Chapter 14. Armin Biere. 2009. Bounded Model Checking. In Handbook of Satisfiability, Armin Biere, Marijn J. H. Heule, Hans van Maaren, and Toby Walsh (Eds.). Frontiers in Artificial Intelligence and Applications, Vol. 185. IOS Press, Chapter 14.
[9]
Eli Bingham , Jonathan P Chen , Martin Jankowiak , Fritz Obermeyer , Neeraj Pradhan , Theofanis Karaletsos , Rohit Singh , Paul Szerlip , Paul Horsfall , and Noah D Goodman . 2019 . Pyro: Deep universal probabilistic programming . The Journal of Machine Learning Research 20 , 1 ( 2019 ), 973-978. Eli Bingham, Jonathan P Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D Goodman. 2019. Pyro: Deep universal probabilistic programming. The Journal of Machine Learning Research 20, 1 ( 2019 ), 973-978.
[12]
Craig Boutilier , Nir Friedman , Moises Goldszmidt , and Daphne Koller . 1996 . Context-specific independence in Bayesian networks . In Proceedings of the Twelfth international conference on Uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc., 115-123 . Craig Boutilier, Nir Friedman, Moises Goldszmidt, and Daphne Koller. 1996. Context-specific independence in Bayesian networks. In Proceedings of the Twelfth international conference on Uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc., 115-123.
[14]
Bob Carpenter , Andrew Gelman , Matt Hofman , Daniel Lee , Ben Goodrich , Michael Betancourt , Michael A Brubaker , Jiqiang Guo , Peter Li , and Allen Riddell . 2016 . Stan: A probabilistic programming language. Journal of Statistical Software ( 2016 ). Bob Carpenter, Andrew Gelman, Matt Hofman, Daniel Lee, Ben Goodrich, Michael Betancourt, Michael A Brubaker, Jiqiang Guo, Peter Li, and Allen Riddell. 2016. Stan: A probabilistic programming language. Journal of Statistical Software ( 2016 ).
[15]
Arun Chaganty , Aditya Nori , and Sriram Rajamani . 2013 . Eficiently sampling probabilistic programs via program analysis . In Artificial Intelligence and Statistics. 153 - 160 . Arun Chaganty, Aditya Nori, and Sriram Rajamani. 2013. Eficiently sampling probabilistic programs via program analysis. In Artificial Intelligence and Statistics. 153-160.
[16]
Mark Chavira and Adnan Darwiche . 2005 . Compiling Bayesian networks with local structure . In IJCAI. 1306 - 1312 . Mark Chavira and Adnan Darwiche. 2005. Compiling Bayesian networks with local structure. In IJCAI. 1306-1312.
[21]
Edmund M. Clarke , Jr., Orna Grumberg , and Doron A . Peled . 1999 . Model Checking. MIT Press , Cambridge, MA, USA. Edmund M. Clarke, Jr., Orna Grumberg, and Doron A. Peled. 1999. Model Checking. MIT Press, Cambridge, MA, USA.
[25]
Adnan Darwiche . 2011 . SDD: A new canonical representation of propositional knowledge bases . In IJCAI ProceedingsInternational Joint Conference on Artificial Intelligence. 819 . Adnan Darwiche. 2011. SDD: A new canonical representation of propositional knowledge bases. In IJCAI ProceedingsInternational Joint Conference on Artificial Intelligence. 819.
[26]
A. Darwiche and P. Marquis. 2002. A Knowledge Compilation Map. Journal of Artificial Intelligence Research 17 ( 2002 ) 229-264. A. Darwiche and P. Marquis. 2002. A Knowledge Compilation Map. Journal of Artificial Intelligence Research 17 ( 2002 ) 229-264.
10.1613/jair.989
[27]
Luc De Raedt , Angelika Kimmig , and Hannu Toivonen . 2007 . ProbLog: A Probabilistic Prolog and Its Application in Link Discovery . In Proceedings of IJCAI , Vol. 7 . 2462 - 2467 . Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. 2007. ProbLog: A Probabilistic Prolog and Its Application in Link Discovery. In Proceedings of IJCAI, Vol. 7. 2462-2467.
[29]
Joshua V Dillon Ian Langmore Dustin Tran Eugene Brevdo Srinivas Vasudevan Dave Moore Brian Patton Alex Alemi Matt Hofman and Rif A Saurous. 2017. TensorFlow Distributions. arXiv preprint arXiv:1711.10604 ( 2017 ). Joshua V Dillon Ian Langmore Dustin Tran Eugene Brevdo Srinivas Vasudevan Dave Moore Brian Patton Alex Alemi Matt Hofman and Rif A Saurous. 2017. TensorFlow Distributions. arXiv preprint arXiv:1711.10604 ( 2017 ).
[37]
V. Gogate and R. Dechter. 2011. SampleSearch: Importance sampling in presence of determinism. Artificial Intelligence 175 2 ( 2011 ) 694-729. V. Gogate and R. Dechter. 2011. SampleSearch: Importance sampling in presence of determinism. Artificial Intelligence 175 2 ( 2011 ) 694-729.
10.1016/j.artint.2010.10.009
[38]
Noah D. Goodman , Vikash K. Mansinghka , Daniel M. Roy , Keith Bonawitz , and Joshua B. Tenenbaum . 2008. Church: a language for generative models . In Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence (UAI). Noah D. Goodman, Vikash K. Mansinghka, Daniel M. Roy, Keith Bonawitz, and Joshua B. Tenenbaum. 2008. Church: a language for generative models. In Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence (UAI).
[39]
Noah D Goodman and Andreas Stuhlmüller. 2014. The design and implementation of probabilistic programming languages. Noah D Goodman and Andreas Stuhlmüller. 2014. The design and implementation of probabilistic programming languages.
[40]
Maria I Gorinova , Dave Moore , and Matthew D Hofman . 2020 . Automatic Reparameterisation of Probabilistic Programs. International Conference on Machine Learning (ICML) ( 2020 ). Maria I Gorinova, Dave Moore, and Matthew D Hofman. 2020. Automatic Reparameterisation of Probabilistic Programs. International Conference on Machine Learning (ICML) ( 2020 ).
[41]
Bradley Gram-Hansen , Yuan Zhou , Tobias Kohn , Tom Rainforth , Hongseok Yang , and Frank Wood . 2018. Hamiltonian Monte Carlo for Probabilistic Programs with Discontinuities. arXiv preprint arXiv : 1804 . 03523 ( 2018 ). Bradley Gram-Hansen, Yuan Zhou, Tobias Kohn, Tom Rainforth, Hongseok Yang, and Frank Wood. 2018. Hamiltonian Monte Carlo for Probabilistic Programs with Discontinuities. arXiv preprint arXiv: 1804. 03523 ( 2018 ).
[42]
Matthew D Hofman and Andrew Gelman . 2014 . The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo . Journal of Machine Learning Research 15 , 1 ( 2014 ), 1593-1623. Matthew D Hofman and Andrew Gelman. 2014. The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. Journal of Machine Learning Research 15, 1 ( 2014 ), 1593-1623.
[43]
Steven Holtzen , Guy Van den Broeck , and Todd Millstein . 2018 . Sound abstraction and decomposition of probabilistic programs . In Proceedings of the 35th International Conference on Machine Learning (ICML). Steven Holtzen, Guy Van den Broeck, and Todd Millstein. 2018. Sound abstraction and decomposition of probabilistic programs. In Proceedings of the 35th International Conference on Machine Learning (ICML).
[44]
Steven Holtzen , Guy Van den Broeck, and Todd Millstein . 2020 . Scaling Exact Inference for Discrete Probabilistic Programs . arXiv:arXiv: 2005.09089 Steven Holtzen, Guy Van den Broeck, and Todd Millstein. 2020. Scaling Exact Inference for Discrete Probabilistic Programs. arXiv:arXiv: 2005.09089
[48]
An Introduction to Variational Methods for Graphical Models
Michael I. Jordan, Zoubin Ghahramani, Tommi S. Jaakkola et al.
Machine Learning
10.1023/a:1007665907178
[49]
Jonathan Katz , Alfred J Menezes , Paul C Van Oorschot, and Scott A Vanstone . 1996 . Handbook of applied cryptography. CRC press . Jonathan Katz, Alfred J Menezes, Paul C Van Oorschot, and Scott A Vanstone. 1996. Handbook of applied cryptography. CRC press.
[50]
D. Koller and N. Friedman. 2009. Probabilistic graphical models: principles and techniques. MIT press. D. Koller and N. Friedman. 2009. Probabilistic graphical models: principles and techniques. MIT press.
Showing 50 of 85 references
Cited By
61
Inference of Probabilistic Programs with Moment-Matching Gaussian Mixtures
Proceedings of the ACM on Programmi...
Francesca Randone, Luca Bortolussi · 2024
Metrics
61
Citations
85
References
Details
- Published
- Nov 13, 2020
- Vol/Issue
- 4(OOPSLA)
- Pages
- 1-31
- License
- View
Authors
Funding
National Science Foundation
Award: IIS-1943641
Cite This Article
Steven Holtzen, Guy Van den Broeck, Todd Millstein (2020). Scaling exact inference for discrete probabilistic programs. Proceedings of the ACM on Programming Languages, 4(OOPSLA), 1-31. https://doi.org/10.1145/3428208
Related
You May Also Like
code2vec: learning distributed representations of code
Uri Alon, Meital Zilberstein · 2019
880 citations
Grounded Copilot: How Programmers Interact with Code-Generating Models
Shraddha Barke, Michael B. James · 2023
275 citations