Stochastic lambda calculus and monads of probability distributions

ABSTRACT

Probability distributions are useful for expressing the meanings of probabilistic languages, which support formal modeling of and reasoning about uncertainty. Probability distributions form a monad, and the monadic definition leads to a simple, natural semantics for a stochastic lambda calculus, as well as simple, clean implementations of common queries. But the monadic implementation of the expectation query can be much less efficient than current best practices in probabilistic modeling. We therefore present a language of measure terms, which can not only denote discrete probability distributions but can also support the best known modeling techniques. We give a translation of stochastic lambda calculus into measure terms. Whether one translates into the probability monad or into measure terms, the results of the translations denote the same probability distribution.

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: Stefan Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded, decomposability—a survey, BIT, v.25 n.1, p.2-23, 1985
• 3: Albert Benveniste , Bernard C. Levy , Eric Fabre , Paul Le Guernic, A calculus of stochastic systems for the specification, simulation, and hidden state estimation of mixed stochastic/nonstochastic systems, Theoretical Computer Science, v.152 n.2, p.171-217, Dec. 25, 1995 [doi>10.1016/0304-3975(94)00295-1]
• 4: Eugene Charniak, Statistical Language Learning, MIT Press, Cambridge, MA, 1994
• 5: Koen Claessen , John Hughes, QuickCheck: a lightweight tool for random testing of Haskell programs, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.268-279, September 2000
• 6: Olivier Danvy, Type-directed partial evaluation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.242-257, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237784]
• 7: Dechter,Ria.1996 (August).Bucket elimination:Auifying framework for probabilistic i ference.I Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence (UAI-96),pages 211 -219,Sa Francisco.
• 8: Giry,Michele.1981.A categorical approach to probability theory.I Banaschewski,Bernhard,editor,Categorical Aspects of Topology and Analysis Vol.915 of Lecture Notes In Mathematics pages 68-85.Springer Verlag.
• 9: Vineet Gupta , Radha Jagadeesan , Prakash Panangaden, Stochastic processes as concurrent constraint programs, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.189-202, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292558]
• 10: J. Hughes, Why functional programming matters, The Computer Journal, v.32 n.2, p.98-107, April 1989 [doi>10.1093/comjnl/32.2.98]
• 11: ____1995.The design of a pretty-printing library.I Jeurig, Johan and Erik Meijer,editors,Advanced Functional Programming Vol.925 of Lecture Notes in Computer Science Springer Verlag.
• 12: Jaakkola,Tommi S.and Michael I.Jordan.1999.Variational probabilistic i ference and the QMR-DT etwork.Journal of Artificial Intelligence Research 10:291 -322.
• 13: Finn V. Jensen , F.V. V. Jensen , F. V. Jensen, Introduction to Bayesian Networks, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 14: Claire Jones, Probabilistic non-determinism, University of Edinburgh, Edinburgh, Scotland, 1992
• 15: C. Jones , G. Plotkin, A probabilistic powerdomain of evaluations, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.186-195, June 1989, Pacific Grove, California, United States
• 16: Michael I. Jordan, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 17: Koller,Daphne,David McAllester,and Avi Pfeffer.1997. Effective Bayesian inference for stochastic programs. In Fourteenth National Conference on Artificial Intelligence (AAAI),pages 740 -747.
• 18: Lauritzen,Ste .en L.and David J.Spiegelhalter.1988.Local computations with probabilities of graphical structures and their applicatio to expert systems.Journal of the Royal Statistical Society pages 157 -224.
• 19: Lawvere,F.William.1962.The category of probabilistic mappings.Unpublished.
• 20: Li,Zhaoyu and Bruce d 'Ambrosio.1994.Efficient inference in Bayes nets as a combinatorial optimization problem.International Journal of Approximate Reasoning 11(1):55 -81.
• 21: Luger,George and Dan Pless.2001.A stochastic -calculus.Technical Report TR-CS-2001-04,Department of Computer Science,University of New Mexico.
• 22: Mahoney,Suzanne M.a d Kathryn Blackmo d Laskey. 1998 (July).Constructing situation specific belief etworks.I Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI-98),pages 370 - 378.Morgan Kaufma .
• 23: Muggleton,Stephe .2001.Stochastic logic programs.Journal of Logic Programming Accepted subject to revision.
• 24: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 25: Pfeffer ,Avi.2001 (August).IBAL:A probabilistic rational programming language.I Seventeenth Interna-tional Joint Conference on Artificial Intelligence (IJ- CAI) ,pages 733-740,Seattle.
• 26: Avi Pfeffer , Daphne Koller, Semantics and Inference for Recursive Probability Models, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.538-544, July 30-August 03, 2000
• 27: Norman Ramsey, Literate Programming Simplified, IEEE Software, v.11 n.5, p.97-105, September 1994 [doi>10.1109/52.311070]
• 28: Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill, Inc., New York, NY, 1987
• 29: Saheb-Djahromi,N.1978 (September).Probabilistic LCF. In Winkowski, Jozef,editor,Proceedings of the 7th Symposium on Mathematical Foundations of Computer Science Vol.64of Lecture Notes in Computer Science pages 442 -451.Springer.
• 30: ____.1980 (September).CPO 's of measures for o determinism.Theoretical Computer Science 12(1):19 -37.
• 31: Michael B. Smyth, Power Domains and Predicate Transformers: A Topological View, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.662-675, July 18-22, 1983
• 32: Philip Wadler, The essence of functional programming, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143169]
• 33: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]
• 34: Zhang,Nevin L.and David Poole.1994.A simple approach to Bayesian etwork computations.I Tenth Biennial Canadian Artificial Intelligence Conference