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.
- 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.Google Scholar
- 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. Google ScholarDigital Library
- . URL http://doi.acm.org/10.1145/2535838.2535872.Google Scholar
- 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.Google Scholar
- A. Doucet and A. M. Johansen. A tutorial on particle filtering and smoothing: fifteen years later, 2011.Google Scholar
- A. Doucet, S. Godsill, and C. Andrieu. On sequential monte carlo sampling methods for bayesian filtering. STATISTICS AND COMPUTING, 10(3): 197–208, 2000. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- L. Getoor and B. Taskar. Introduction to Statistical Relational Learning. The MIT Press, 2007. Google ScholarDigital Library
- W. R. Gilks, A. Thomas, and D. J. Spiegelhalter. A language and program for complex Bayesian modelling. The Statistician, 43:169–178, 1994.Google ScholarCross Ref
- 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.Google Scholar
- N. D. Goodman. The principles and practice of probabilistic programming. In Principles of Programming Languages (POPL’13), pages 399–402, 2013. Google ScholarDigital Library
- N. D. Goodman and A. Stuhlmüller. The Design and Implementation of Probabilistic Programming Languages. http://dippl.org, 2014.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- C.-K. Hur, A. Nori, S. Rajamani, S. Samuel, and D. Vijaykeerthy. Implementing a correct sampler for imperative probabilistic programs. 2015.Google Scholar
- 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. Google ScholarDigital Library
- O. Kiselyov and C. Shan. Embedded probabilistic programming. In Conference on Domain-Specific Languages, pages 360–384, 2009. 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
- K. F. Larsen. Memory efficient implementation of probability monads. unpublished, 2011.Google Scholar
- D. Lunn, C. Jackson, N. Best, A. Thomas, and D. Spiegelhalter. The BUGS Book. CRC Press, 2013.Google Scholar
- V. Mansinghka, D. Selsam, and Y. Perov. Venture: a higher-order probabilistic programming platform with programmable inference. arXiv preprint arXiv:1404.0099, 2014.Google Scholar
- 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. 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.Google Scholar
- R. M. Neal. Mcmc using hamiltonian dynamics. Handbook of Markov Chain Monte Carlo, 2, 2011.Google Scholar
- B. Paige and F. Wood. A compilation target for probabilistic programming languages. In ICML, 2014.Google Scholar
- 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. Google ScholarDigital Library
- A. Pfeffer. Figaro: An object-oriented probabilistic programming language. Technical report, Charles River Analytics, 2009.Google Scholar
- N. Ramsey and A. Pfeffer. Stochastic lambda calculus and monads of probability distributions. In POPL, pages 154–165, 2002. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- J. S. Rosenthal. A First Look at Rigorous Probability Theory. World Scientific, 2nd edition, 2006.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
Index Terms
- Practical probabilistic programming with monads
Recommendations
Functional programming for modular Bayesian inference
We present an architectural design of a library for Bayesian modelling and inference in modern functional programming languages. The novel aspect of our approach are modular implementations of existing state-of-the-art inference algorithms. Our design ...
Practical probabilistic programming with monads
Haskell '15: Proceedings of the 2015 ACM SIGPLAN Symposium on HaskellThe 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 ...
Making monads first-class with template haskell
HASKELL '08Monads as an organizing principle for programming and semantics are notoriously difficult to grasp, yet they are a central and powerful abstraction in Haskell. This paper introduces a domain-specific language, MonadLab, that simplifies the construction ...
Comments