Andrew D. Gordon
ABSTRACT
Probabilistic programs are usual functional or imperative programs with two added constructs: (1) the ability to draw values at random from distributions, and (2) the ability to condition values of variables in a program via observations. Models from diverse application areas such as computer vision, coding theory, cryptographic protocols, biology and reliability analysis can be written as probabilistic programs.
Probabilistic inference is the problem of computing an explicit representation of the probability distribution implicitly specified by a probabilistic program. Depending on the application, the desired output from inference may vary---we may want to estimate the expected value of some function f with respect to the distribution, or the mode of the distribution, or simply a set of samples drawn from the distribution.
In this paper, we describe connections this research area called ``Probabilistic Programming" has with programming languages and software engineering, and this includes language design, and the static and dynamic analysis of programs. We survey current state of the art and speculate on promising directions for future research.
- R. I. Bahar, E. A. Frohm, C. M. Gaona, G. D. Hachtel, E. Macii, A. Pardo, and F. Somenzi. Algebraic decision diagrams and their applications. Formal Methods in System Design, 10(2/3):171–206, 1997. Google Scholar
Digital Library
- T. Ball, R. Majumdar, T. Millstein, and S. K. Rajamani. Automatic predicate abstraction of C programs. In Programming Language Design and Implementation (PLDI), pages 203–213, 2001. Google ScholarDigital Library
- G. Barthe, B. Grégoire, and S. Zanella Béguelin. Formal certification of code-based cryptographic proofs. In Principles of Programming Languages (POPL), pages 90–101, 2009. Google ScholarDigital Library
- G. Barthe, B. Gr ˜ Al’goire, S. Heraud, and S. Zanella Béguelin. Computer-aided security proofs for the working cryptographer. In Advances in Cryptology (CRYPTO), pages 71–90. 2011. Google ScholarDigital Library
- J. Borgström, A. D. Gordon, M. Greenberg, J. Margetson, and J. Van Gael. Measure transformer semantics for Bayesian machine learning. In European Symposium on Programming (ESOP), pages 77–96, 2011. Google ScholarDigital Library
- C. G. Cassandras and S. Lafortune. Introduction to Discrete Event Systems. Springer Science+Business Media, LLC, 2008.Google ScholarCross Ref
- A. T. Chaganty, A. V. Nori, and S. K. Rajamani. Efficiently sampling probabilistic programs via program analysis. In Artificial Intelligence and Statistics (AISTATS), pages 153–160, 2013.Google Scholar
- S. Chaudhuri and A. Solar-Lezama. Smooth interpretation. In Programming Language Design and Implementation, pages 279–291, 2010. Google ScholarDigital Library
- M. Chavira and A. Darwiche. Compiling bayesian networks using variable elimination. In International Joint Conference on on Artificial Intelligence (IJCAI), pages 2443–2449, 2007. Google ScholarDigital Library
- S. Chib and E. Greenberg. Understanding the Metropolis-Hastings algorithm. American Statistician, 49(4):327–335, 1995.Google Scholar
- G. Claret, S. K. Rajamani, A. V. Nori, A. D. Gordon, and J. Borgström. Bayesian inference using data flow analysis. In Foundations of Software Engineering (FSE), pages 92–102, 2013. Google ScholarDigital Library
- M. R. Clarkson, A. C. Myers, and F. B. Schneider. Quantifying information flow with beliefs. Journal of Computer Security, 17(5):655–701, 2009. Google ScholarDigital Library
- P. Cousot and R. Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Principles of Programming Languages (POPL), pages 238–252, 1977. Google ScholarDigital Library
- L. de Alfaro, M. Z. Kwiatkowska, G. Norman, D. Parker, and R. Segala. Symbolic model checking of probabilistic processes using mtbdds and the kronecker representation. In Tools and Algorithms for Construction and Analysis of Systems (TACAS), pages 395–410, 2000. Google ScholarDigital Library
- D. L. Detlefs, K. R. M. Leino, G. Nelson, and J. B. Saxe. Extended static checking. Technical Report Research Report 159, Compaq Systems Research Center, December 1998.Google Scholar
- E. W. Dijkstra. Guarded commands, nondeterminacy and formal derivation of programs. Communications of the ACM (CACM), 18(8):453–457, 1975. Google ScholarDigital Library
- P. Domingos. Markov logic: a unifying language for knowledge and information management. In CIKM: ACM Conference on Information and Knowledge Management, page 519, 2008. Google ScholarDigital Library
- J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. Transactions on Programming Languages and Systems (TOPLAS)., 9(3):319–349, 1987. Google ScholarDigital Library
- W. R. Gilks, A. Thomas, and D. J. Spiegelhalter. A language and program for complex Bayesian modelling. The Statistician, 43(1):169–177, 1994.Google ScholarCross Ref
- V. Gogate, W. A. Webb, and P. Domingos. Learning efficient markov networks. In Neural Information Processing Systems (NIPS), pages 748–756, 2010.Google Scholar
- N. D. Goodman, V. K. Mansinghka, D. M. Roy, K. Bonawitz, and J. B. Tenenbaum. Church: a language for generative models. In Uncertainty in Artificial Intelligence (UAI), pages 220–229, 2008.Google Scholar
- A. D. Gordon, M. Aizatulin, J. Borgström, G. Claret, T. Graepel, A. V. Nori, S. K. Rajamani, and C. Russo. A model-learner pattern for Bayesian reasoning. In Principles of Programming Languages (POPL), pages 403–416, 2013. Google ScholarDigital Library
- A. D. Gordon, T. Graepel, N. Rolland, C. Russo, J. Borgström, and J. Guiver. Tabular: A schema-driven probabilistic programming language. In Principles of Programming Languages (POPL), 2014. To appear. Google ScholarDigital Library
- H. Hansson and B. Jonsson. A logic for reasoning about time and reliability. Formal Aspects of Computing, 6(5):512–535, 1994.Google ScholarDigital Library
- D. Heckerman, D. Geiger, and D. M. Chickering. Learning bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20(3):197–243, 1995. Google ScholarDigital Library
- R. Herbrich, T. Minka, and T. Graepel. TrueSkill: A Bayesian skill rating system. In Neural Information Processing Systems (NIPS), pages 569–576, 2006.Google Scholar
- M. D. Hoffman and A. Gelman. The no-U-turn sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo. Journal of Machine Learning Research, in press, 2013.Google Scholar
- John Langford. Vowpal Wabbit.Google Scholar
- J.-P. Katoen, I. S. Zapreev, E. M. Hahn, H. Hermanns, and D. N. Jansen. The ins and outs of the probabilistic model checker MRMC. In Quantitative Evaluation of Systems (QEST), pages 167–176, 2009. Google ScholarDigital Library
- D. Knuth and A. Yao. Algorithms and Complexity: New Directions and Recent Results, chapter The complexity of nonuniform random number generation. Academic Press, 1976. Google ScholarDigital Library
- S. Kok, M. Sumner, M. Richardson, P. Singla, H. Poon, D. Lowd, and P. Domingos. The Alchemy system for statistical relational AI. Technical report, University of Washington, 2007. http://alchemy.cs.washington.edu.Google Scholar
- D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009. Google ScholarDigital Library
- D. Koller, D. A. McAllester, and A. Pfeffer. Effective Bayesian inference for stochastic programs. In National Conference on Artificial Intelligence (AAAI), pages 740–747, 1997. Google ScholarDigital Library
- D. Kozen. Semantics of probabilistic programs. Journal of Computer and System Sciences, 22(3):328–350, 1981.Google ScholarCross Ref
- D. Kozen. A probabilistic PDL. J. Comput. Syst. Sci., 30(2):162–178, 1985.Google ScholarCross Ref
- M. Z. Kwiatkowska, G. Norman, and D. Parker. PRISM 4.0: Verification of probabilistic real-time systems. In Computer Aided Verification (CAV), pages 585–591, 2011. Google ScholarDigital Library
- A. Lotka. Elements of physical biology. Williams & Wilkins company, Baltimore, 1925.Google Scholar
- D. J. C. MacKay. Information Theory, Inference & Learning Algorithms. Cambridge University Press, New York, NY, USA, 2002. Google ScholarDigital Library
- P. Mardziel, S. Magill, M. Hicks, and M. Srivatsa. Dynamic enforcement of knowledge-based security policies using probabilistic abstract interpretation. Journal of Computer Security, January 2013. Google ScholarDigital Library
- B. Milch, B. Marthi, S. J. Russell, D. Sontag, D. L. Ong, and A. Kolobov. BLOG: Probabilistic models with unknown objects. In Probabilistic, Logical and Relational Learning — A Further Synthesis, 2005.Google Scholar
- T. Minka, J. Winn, J. Guiver, and A. Kannan. Infer.NET 2.3, Nov. 2009. Software available from http://research.microsoft.com/infernet.Google Scholar
- G. Nelson. A generalization of Dijkstra’s calculus. Transactions on Programming Languages and Systems (TOPLAS)., 11(4):517–561, 1989. Google ScholarDigital Library
- F. Niu, C. Ré, A. Doan, and J. W. Shavlik. Tuffy: Scaling up statistical inference in Markov Logic Networks using an RDBMS. Very Large Databases (PVLDB), 4(6):373–384, 2011. Google ScholarDigital Library
- A. V. Nori, C. Hur, S. K. Rajamani, and S. Samuel. The R2 probabilistic programming system. 2013. http://research.microsoft.com/r2.Google Scholar
- A. V. Nori, C. Hur, S. K. Rajamani, and S. Samuel. Slicing probabilistic programs. 2013. Working draft.Google Scholar
- J. R. Norris. Markov chains. Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, 1998.Google Scholar
- J. Pearl. Probabilistic Reasoning in Intelligence Systems. Morgan Kaufmann, 1996. Google ScholarDigital Library
- A. Pfeffer. The design and implementation of IBAL: A general-purpose probabilistic language. In Statistical Relational Learning. MIT Press, 2007.Google Scholar
- A. Pfeffer. A general importance sampling algorithm for probabilistic programs. Technical report, Harvard University TR-12-07, 2007.Google Scholar
- M. L. Puterman. Markov Decision Processes. Wiley, 1994.Google ScholarCross Ref
- D. Roth. On the hardness of approximate reasoning. Artificial Intelligence, 82(1–2):273–302, 1996. Google ScholarDigital Library
- S. Sankaranarayanan, A. Chakarov, and S. Gulwani. Static analysis of probabilistic programs: Inferring whole program properties from finitely many executions. In Programming Languages Design and Implementation (PLDI), 2013. Google ScholarDigital Library
- A. Solar-Lezama. The sketching approach to program synthesis. In Asian Symposium on Programming Languages and Systems (APLAS), pages 4–13, 2009. Google ScholarDigital Library
- Stan Development Team. Stan: A C++ library for probability and sampling, version 2.0, 2013.Google Scholar
- D. Suciu, D. Olteanu, C. Ré, and C. Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. Google ScholarDigital Library
- M. Y. Vardi. Automatic verification of probabilistic concurrent finite-state programs. In Foundations of Computer Science (FOCS), pages 327–338, 1985. Google ScholarDigital Library
- V. Volterra. Fluctuations in the abundance of a species considered mathematically. Nature, 118:558–560, 1926.Google ScholarCross Ref
- D. Wingate, N. D. Goodman, A. Stuhlmüller, and J. M. Siskind. Nonstandard interpretations of probabilistic programs for efficient inference. In Neural Information Processing Systems (NIPS), pages 1152–1160, 2011.Google Scholar
- D. Wingate, A. Stuhlmüller, and N. D. Goodman. Lightweight implementations of probabilistic programming languages via transformational compilation. International Conference on Artificial Intelligence and Statistics (AISTATS), 15:770–778, 2011.Google Scholar
Index Terms
- Probabilistic programming
Index terms have been assigned to the content through auto-classification.
Recommendations
Gen: a general-purpose probabilistic programming system with programmable inference
PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and ImplementationAlthough probabilistic programming is widely used for some restricted classes of statistical models, existing systems lack the flexibility and efficiency needed for practical use with more challenging models arising in fields like computer vision and ...
Deployable probabilistic programming
Onward! 2019: Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and SoftwareWe propose design guidelines for a probabilistic programming facility suitable for deployment as a part of a production software system. As a reference implementation, we introduce Infergo, a probabilistic programming facility for Go, a modern ...
Probabilistic programming: A review for environmental modellers
AbstractThe development process for an environmental model involves multiple iterations of a planning-implementation-assessment cycle. Probabilistic programming languages (PPLs) are designed to expedite this process with general-purpose ...
Highlights- Probabilistic programming languages offer modellers generic components for specifying stochastic and deterministic models.
Comments