Practical probabilistic programming with monads

Abstract

The machine learning community has recently shown a lot of interest in practical probabilistic programming systems that target the problem of Bayesian inference. Such systems come in different forms, but they all express probabilistic models as computational processes using syntax resembling programming languages. In the functional programming community monads are known to offer a convenient and elegant abstraction for programming with probability distributions, but their use is often limited to very simple inference problems. We show that it is possible to use the monad abstraction to construct probabilistic models for machine learning, while still offering good performance of inference in challenging models. We use a GADT as an underlying representation of a probability distribution and apply Sequential Monte Carlo-based methods to achieve efficient inference. We define a formal semantics via measure theory. We demonstrate a clean and elegant implementation that achieves performance comparable with Anglican, a state-of-the-art probabilistic programming system.

References

1. C. Andrieu, A. Doucet, and R. Holenstein. Particle markov chain monte carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(3):269–342, 2010. ISSN 1467-9868.. URL http://dx.doi.org/10.1111/j.1467-9868.2009.00736.x. D. Barber. Bayesian Reasoning and Machine Learning. CUP, 2012.
2. S. Bhat, J. Borgström, A. D. Gordon, and C. V. Russo. Deriving probability density functions from probabilistic functional programs. In TACAS, pages 508–522, 2013.
3. . URL http://doi.acm.org/10.1145/2535838.2535872.
4. P. Domingos and M. Richardson. Markov logic: A unifying framework for statistical relational learning. In Proceedings of the ICML-2004 Workshop on Statistical Relational Learning and its Connections to other Fields, pages 49–54, 2004.
5. A. Doucet and A. M. Johansen. A tutorial on particle filtering and smoothing: fifteen years later, 2011.
6. A. Doucet, S. Godsill, and C. Andrieu. On sequential monte carlo sampling methods for bayesian filtering. STATISTICS AND COMPUTING, 10(3): 197–208, 2000.
7. M. Eberl, J. Hölzl, and T. Nipkow. A verified compiler for probability density functions. In J. Vitek, editor, Programming Languages and Systems - 24th European Symposium on Programming, ESOP 2015, volume 9032 of Lecture Notes in Computer Science, pages 80–104. Springer, 2015.. URL http://dx.doi.org/10.1007/978-3-662-46669-8_4. M. Erwig and S. Kollmansberger. Functional pearls: Probabilistic functional programming in Haskell. J. Funct. Program., 16(1):21–34, 2006.
8. L. Getoor and B. Taskar. Introduction to Statistical Relational Learning. The MIT Press, 2007.
9. W. R. Gilks, A. Thomas, and D. J. Spiegelhalter. A language and program for complex Bayesian modelling. The Statistician, 43:169–178, 1994.
10. N. 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’08), pages 220–229. AUAI Press, 2008.
11. N. D. Goodman. The principles and practice of probabilistic programming. In Principles of Programming Languages (POPL’13), pages 399–402, 2013.
12. N. D. Goodman and A. Stuhlmüller. The Design and Implementation of Probabilistic Programming Languages. http://dippl.org, 2014.
13. Accessed: 2015-5-22. A. D. Gordon, M. Aizatulin, J. Borgström, G. Claret, T. Graepel, A. Nori, S. Rajamani, and C. Russo. A model-learner pattern for Bayesian reasoning. In POPL, 2013.
14. A. D. Gordon, T. A. Henzinger, A. V. Nori, and S. K. Rajamani. Probabilistic programming. In Future of Software Engineering (FOSE 2014), pages 167–181, 2014.
15. F. Gretz, N. Jansen, B. L. Kaminski, J. Katoen, A. McIver, and F. Olmedo. Conditioning in probabilistic programming. CoRR, abs/1504.00198, 2015. URL http://arxiv.org/abs/1504.00198.
16. C.-K. Hur, A. Nori, S. Rajamani, S. Samuel, and D. Vijaykeerthy. Implementing a correct sampler for imperative probabilistic programs. 2015.
17. Unpublished draft. A. Kimmig, B. Demoen, L. D. Raedt, V. S. Costa, and R. Rocha. On the implementation of the probabilistic logic programming language problog. TPLP, 11(2-3):235–262, 2011.. URL http://dx.doi.org/ 10.1017/S1471068410000566.
18. O. Kiselyov and C. Shan. Embedded probabilistic programming. In Conference on Domain-Specific Languages, pages 360–384, 2009.
19. D. Kozen. Semantics of probabilistic programs. Journal of Computer and System Sciences, 22(3):328–350, 1981.
20. D. Kozen. A probabilistic PDL. J. Comput. Syst. Sci., 30(2):162–178, 1985.
21. K. F. Larsen. Memory efficient implementation of probability monads. unpublished, 2011.
22. D. Lunn, C. Jackson, N. Best, A. Thomas, and D. Spiegelhalter. The BUGS Book. CRC Press, 2013.
23. V. Mansinghka, D. Selsam, and Y. Perov. Venture: a higher-order probabilistic programming platform with programmable inference. arXiv preprint arXiv:1404.0099, 2014.
24. 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.
25. T. Minka, J. Winn, J. Guiver, and A. Kannan. Infer.NET 2.3, Nov. 2009. Software available from http://research.microsoft.com/ infernet. R. M. Neal. Probabilistic inference using Markov chain Monte Carlo methods. Technical Report CRG-TR-93-1, Dept. of Computer Science, University of Toronto, September 1993.
26. R. M. Neal. Mcmc using hamiltonian dynamics. Handbook of Markov Chain Monte Carlo, 2, 2011.
27. B. Paige and F. Wood. A compilation target for probabilistic programming languages. In ICML, 2014.
28. B. Paige, F. Wood, A. Doucet, and Y. W. Teh. Asynchronous anytime sequential monte carlo. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 3410–3418. Curran Associates, Inc., 2014. URL http://papers.nips.cc/paper/ 5450-asynchronous-anytime-sequential-monte-carlo.pdf. A. Pfeffer. IBAL: A probabilistic rational programming language. In B. Nebel, editor, International Joint Conference on Artificial Intelligence (IJCAI’01), pages 733–740. Morgan Kaufmann, 2001.
29. A. Pfeffer. Figaro: An object-oriented probabilistic programming language. Technical report, Charles River Analytics, 2009.
30. N. Ramsey and A. Pfeffer. Stochastic lambda calculus and monads of probability distributions. In POPL, pages 154–165, 2002.
31. S. R. Riedel, S. Singh, V. Srikumar, T. Rocktäschel, L. Visengeriyeva, and J. Noessner. WOLFE: strength reduction and approximate programming for probabilistic programming. In Statistical Relational Artificial Intelligence, 2014.
32. J. S. Rosenthal. A First Look at Rigorous Probability Theory. World Scientific, 2nd edition, 2006.
33. Stan Development Team. Stan: A C++ library for probability and sampling, version 2.2, 2014. URL http://mc-stan.org/. Y. W. Teh. Dirichlet processes. In Encyclopedia of Machine Learning. Springer, 2010.
34. J. van de Meent, H. Yang, V. Mansinghka, and F. Wood. Particle gibbs with ancestor sampling for probabilistic programs. In G. Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2015, San Diego, California, USA, May 9-12, 2015, volume 38 of JMLR Proceedings. JMLR.org, 2015. URL http://jmlr.org/ proceedings/papers/v38/vandemeent15.html. D. Wingate, A. Stuhlmueller, and N. Goodman. Lightweight implementations of probabilistic programming languages via transformational compilation. In Proceedings of the 14th Intl. Conf. on Artificial Intelligence and Statistics, page 131, 2011.
35. F. Wood, J.-W. van de Meent, and V. Mansinghka. A new approach to probabilistic programming inference. In Proceedings of the 17th International conference on Artificial Intelligence and Statistics, 2014.

Index Terms

• Mathematics of computing

  • Probability and statistics