Report on the probabilistic language scheme

ABSTRACT

Reasoning with probabilistic models is a widespread and successful technique in areas ranging from computer vision, to natural language processing, to bioinformatics. Currently, these reasoning systems are either coded from scratch in general-purpose languages or use formalisms such as Bayesian networks that have limited expressive power. In both cases, the resulting systems are difficult to modify, maintain, compose, and interoperate with. This work presents Probabilistic Scheme, an embedding of probabilistic computation into Scheme. This gives programmers an expressive language for implementing modular probabilistic models that integrate naturally with the rest of Scheme.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 2: F. Bacchus, S. Dalmao, and T. Pitassi. Value elimination: Bayesian inference via backtracking search, 2003.
• 3: Nir Friedman , Lise Getoor , Daphne Koller , Avi Pfeffer, Learning Probabilistic Relational Models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1300-1309, July 31-August 06, 1999
• 4: N. I. Adams, IV , D. H. Bartley , G. Brooks , R. K. Dybvig , D. P. Friedman , R. Halstead , C. Hanson , C. T. Haynes , E. Kohlbecker , D. Oxley , K. M. Pitman , G. J. Rozas , G. L. Steele, Jr. , G. J. Sussman , M. Wand , H. Abelson, Revised5 report on the algorithmic language scheme, ACM SIGPLAN Notices, v.33 n.9, p.26-76, Sept. 1, 1998 [doi>10.1145/290229.290234]
• 5: Daphne Koller , Avi Pfeffer, Probabilistic frame-based systems, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.580-587, July 1998, Madison, Wisconsin, United States
• 6: J. McCarthy. A Basis for a Mathematical Theory of Computation. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Systems. North-Holland, Amsterdam, 1963.
• 7: B. Milch, B. Marthi, S. Russell, D. Sontag, D. Ong, and A. Kolobov. BLOG: Probabilistic models with unknown objects. Proceedings of the Nineteenth Joint Conference on Artificial Intelligence, 2005.
• 8: A. Pfeffer. IBAL: A probabilistic rational programming language. In IJCAI, pages 733--740, 2001.
• 9: Norman Ramsey , Avi Pfeffer, Stochastic lambda calculus and monads of probability distributions, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.154-165, January 16-18, 2002, Portland, Oregon
• 10: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 11: M. Sahami, S. Dumais, D. Heckerman, and E. Horvitz. A Bayesian approach to filtering junk e-mail. Learning for Text Categorization: Papers from the 1998 Workshop, 62, 1998.
• 12: E. Segal, B. Taskar, A. Gasch, N. Friedman, and D. Koller. Rich probabilistic models for gene expression. Bioinformatics, 17(Suppl 1):S243--52, 2001.
• 13: D. Spiegelhalter, A. Thomas, N. Best, and W. Gilks. BUGS: Bayesian inference using Gibbs sampling. MRC Biostatistics Unit, Cambridge, England. www. mrc-bsu. cam. ac. uk/bugs, 1994.
• 14: R. M. Stallman and G. J. Sussman. Forward reasoning and dependency directed backtracking in a system for computer-aided circuit analysis. AI Memo 380, MIT Artificial Intelligence Laboratory, September 1976.
• 15: S. Thrun, M. Montemerlo, and A. Aron. Probabilistic Terrain Analysis For High-Speed Desert Driving. Proc. Robotics Science and Systems, Philadelphia, PA, USA, August, pages 16--19, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Algorithms, Design, Languages

Keywords:
embedding, probability, scheme