×

An application of computable distributions to the semantics of probabilistic programming languages. (English) Zbl 1335.68028

Thiemann, Peter (ed.), Programming languages and systems. 25th European symposium on programming, ESOP 2016, held as part of the European joint conferences on theory and practice of software, ETAPS 2016, Eindhoven, The Netherlands, April 2–8, 2016. Proceedings. Berlin: Springer (ISBN 978-3-662-49497-4/pbk; 978-3-662-49498-1/ebook). Lecture Notes in Computer Science 9632, 337-363 (2016).
Summary: Most probabilistic programming languages for Bayesian inference give either operational semantics in terms of sampling, or denotational semantics in terms of measure-theoretic distributions. It is important that we can relate the two, given that practitioners often reason both analytically (e.g., density) as well as algorithmically (i.e., in terms of sampling) about distributions. In this paper, we give denotational semantics to a functional language extended with continuous distributions and show that by restricting attention to computable distributions, we can realize a corresponding sampling semantics.
For the entire collection see [Zbl 1333.68019].

MSC:

68N15 Theory of programming languages
68Q55 Semantics in the theory of computing
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ackerman, N.L., Freer, C.E., Roy, D.M.: Noncomputable conditional distributions. In: Proceedings of the IEEE 26th Annual Symposium on Logic in Computer Science, LICS 2011, pp. 107–116. IEEE Computer Society, Washington, DC (2011) · doi:10.1109/LICS.2011.49
[2] Bailey, D., Borwein, P., Plouffe, S.: On the Rapid Computation of Various Polylogarithmic Constants. Math. Comput. 66(218), 903–913 (1997) · Zbl 0879.11073 · doi:10.1090/S0025-5718-97-00856-9
[3] Borgström, J., Gordon, A.D., Greenberg, M., Margetson, J., Van Gael, J.: Measure transformer semantics for bayesian machine learning. In: Barthe, G. (ed.) ESOP 2011. LNCS, vol. 6602, pp. 77–96. Springer, Heidelberg (2011) · Zbl 1326.68217 · doi:10.1007/978-3-642-19718-5_5
[4] Freer, C.E., Roy, D.M.: Posterior distributions are computable from predictive distributions. In: Teh, Y.W., Titterington, D.M. (eds.) Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (AISTATS-10), vol. 9, pp. 233–240 (2010)
[5] Freer, C.E., Roy, D.M.: Computable de finetti measures. Ann. Pure. Appl. Logic 163(5), 530–546 (2012) · Zbl 1247.03098 · doi:10.1016/j.apal.2011.06.011
[6] Gács, P.: Uniform test of algorithmic randomness over a general space. Theor. Comput. Sci. 341(1), 91–137 (2005) · Zbl 1077.68038 · doi:10.1016/j.tcs.2005.03.054
[7] Galatolo, S., Hoyrup, M., Rojas, C.: Effective symbolic dynamics, random points, statistical behavior, complexity and entropy. Inf. Comput. 208(1), 23–41 (2010) · Zbl 1185.68368 · doi:10.1016/j.ic.2009.05.001
[8] Giry, M.: A categorical approach to probability theory. In: Banaschewski, B. (ed.) Categorical Aspects of Topology and Analysis, pp. 68–85. Springer, Heidelberg (1982) · Zbl 0486.60034 · doi:10.1007/BFb0092872
[9] Goodman, N.D., Mansinghka, V.K., Roy, D., Bonawitz, K., Tenenbaum, J.B.: Church: A language for generative models. In: Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, UAI , pp. 220–229 (2008)
[10] Hershey, S., Bernstein, J., Bradley, B., Schweitzer, A., Stein, N., Weber, T., Vigoda, B.: Accelerating Inference: towards a full Language, Compiler and Hardware stack. CoRR abs/1212.2991 (2012)
[11] Hoffman, M.D., Gelman, A.: The No-U-Turn sampler: adaptively setting path lengths in hamiltonian monte carlo. J. Mach. Learn. Res. 15, 1351–1381 (2013) · Zbl 1319.60150
[12] Hoyrup, M., Rojas, C.: Computability of probability measures and Martin-Löf randomness over metric spaces. Inf. Comput. 207(7), 830–847 (2009) · Zbl 1167.68023 · doi:10.1016/j.ic.2008.12.009
[13] Jones, C., Plotkin, G.: A probabilistic powerdomain of evaluations. In: Proceedings of the Fourth Annual Symposium on Logic in Computer Science, pp. 186–195. IEEE Press, Piscataway (1989) · Zbl 0716.06003 · doi:10.1109/LICS.1989.39173
[14] Koller, D., McAllester, D., Pfeffer, A.: Effective bayesian inference for stochastic programs. In: Proceedings of the 14th National Conference on Artificial Intelligence (AAAI), pp. 740–747 (1997)
[15] Kozen, D.: Semantics of probabilistic programs. J. Comput. Syst. Sci. 22(3), 328–350 (1981) · Zbl 0476.68019 · doi:10.1016/0022-0000(81)90036-2
[16] Lunn, D., Spiegelhalter, D., Thomas, A., Best, N.: The BUGS project: Evolution, critique and future directions. Statistic in Medicine (2009)
[17] McCallum, A., Schultz, K., Singh, S.: Factorie: Probabilistic programming via imperatively defined factor graphs. Adv. Neural Inf. Process. Syst. 22, 1249–1257 (2009)
[18] Minka, T., Guiver, J., Winn, J., Kannan, A.: Infer.NET 2.3, Microsoft Research Cambridge (2009)
[19] Neal, R.M.: Markov chain sampling methods for Dirichlet process mixture models. J. Comput. Graph. Stat. 9(2), 249–265 (2000)
[20] Nori, A.V., Hur, C.-K., Rajamani, S.K., Samuel, S.: R2: An efficient MCMC sampler for probabilistic programs. In: AAAI Conference on Artificial Intelligence (2014)
[21] Park, S., Pfenning, F., Thrun, S.: A probabilistic language based upon sampling functions. In: Proceedings of the 32Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2005, pp. 171–182. ACM, New York (2005) · Zbl 1369.68083 · doi:10.1145/1047659.1040320
[22] Jones, S.P., Reid, A., Henderson, F., Hoare, T., Marlow, S.: A semantics for imprecise exceptions. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 1999, pp. 25–36. ACM, New York (1999) · doi:10.1145/301618.301637
[23] Pfeffer, A.: Creating and manipulating probabilistic programs with figaro. In: 2nd International Workshop on Statistical Relational AI (2012)
[24] Pfeffer, A.: IBAL: a probabilistic rational programming language. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence - vol. 1, IJCAI 2001, pp. 733–740. Morgan Kaufmann Publishers Inc., San Francisco (2001)
[25] Ramsey, N., Pfeffer, A.: Stochastic lambda calculus and monads of probability distributions. In: Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2002, pp. 154–165. ACM, New York (2002) · Zbl 1323.68150 · doi:10.1145/565816.503288
[26] Rao, M.M., Swift, R.J.: Probability Theory with Applications. Springer-Verlag New York Inc, Secaucus (2006) · Zbl 1111.60001
[27] Saheb-Djahromi, N.: CPO’s of measures for nondeterminism. Theor. Comput. Sci. 12(1), 19–37 (1980) · Zbl 0433.68017 · doi:10.1016/0304-3975(80)90003-1
[28] Schröder, M.: Admissible representations for probability measures. Math. Logic Q. 53(4–5), 431–445 (2007) · Zbl 1124.03019 · doi:10.1002/malq.200710010
[29] Toronto, N., McCarthy, J., Van Horn, D.: Running probabilistic programs backwards. In: Vitek, J. (ed.) ESOP 2015. LNCS, vol. 9032, pp. 53–79. Springer, Heidelberg (2015) · Zbl 1335.68029 · doi:10.1007/978-3-662-46669-8_3
[30] Tristan, J.-B., Huang, D., Tassarotti, J., Pocock, A.C., Green, S., Steele, G.L.: Augur: data-parallel probabilistic modeling. In: Advances in Neural Information Processing Systems, pp. 2600–2608 (2014)
[31] Weihrauch, K.: Computability on the probability measures on the Borel sets of the unit interval. Theor. Comput. Sci. 219(1), 421–437 (1999) · Zbl 0916.68043 · doi:10.1016/S0304-3975(98)00298-9
[32] Weihrauch, K.: Computable Analysis: An Introduction. Springer-Verlag New York Inc, Secaucus (2000) · Zbl 0956.68056 · doi:10.1007/978-3-642-56999-9
[33] Wingate, D., Stuhlmller, A., Goodman, N.D.: Lightweight implementations of probabilistic programming languages via transformational compilation. In: Artificial Intelligence and Statistics, AISTATS 2011 (2011)
[34] Winskel, G.: The Formal Semantics of Programming Languages: An Introduction. MIT Press, Cambridge (1993) · Zbl 0919.68082
[35] Wood, F., van de Meent, J.W., Mansinghka, V.: A new approach to probabilistic programming inference. In: Proceedings of the 17th International Conference on Artificial Intelligence and Statistics, pp. 2–46 (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.