research-article

Free access

Monolingual probabilistic programming using generalized coroutines

Authors:

Chung-chieh ShanAuthors Info & Claims

UAI '09: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence

Pages 285 - 292

Published: 18 June 2009 Publication History

Abstract

Probabilistic programming languages and modeling toolkits are two modular ways to build and reuse stochastic models and inference procedures. Combining strengths of both, we express models and inference as generalized coroutines in the same general-purpose language. We use existing facilities of the language, such as rich libraries, optimizing compilers, and types, to develop concise, declarative, and realistic models with competitive performance on exact and approximate inference. In particular, a wide range of models can be expressed using memoization. Because deterministic parts of models run at full speed, custom inference procedures are trivial to incorporate, and inference procedures can reason about themselves without interpretive overhead. Within this framework, we introduce a new, general algorithm for importance sampling with look-ahead.

References

[1]

Danvy, Olivier, and Andrzej Filinski. 1990. Abstracting control. In Lisp and functional programming, 151--160.

[2]

Daumé, Hal, III. 2007. Hierarchical Bayes compiler. http://www.cs.utah.edu/~hal/HBC/.

[3]

Dechter, Rina. 1999. Bucket elimination: A unifying framework for probabilistic inference. In Learning in graphical models, ed. Michael I. Jordan. MIT Press.

Digital Library

[4]

Domingos, Pedro, and Matthew Richardson. 2007. Markov logic: A unifying framework for statistical relational learning. In Getoor and Taskar (2007), 339--371.

[5]

Felleisen, Matthias, Daniel P. Friedman, Bruce F. Duba, and John Merrill. 1987. Beyond continuations. Tech. Rep. 216, Computer Science Dept., Indiana Univ.

[6]

Filinski, Andrzej. 1994. Representing monads. In Principles of programming languages, 446--457.

[7]

Fischer, Bernd, and Johann Schumann. 2003. AutoBayes: A system for generating data analysis programs from statistical models. Journal of Functional Programming 13(3):483--508.

Digital Library

[8]

Fung, Robert, and Kuo-Chu Chang. 1990. Weighing and integrating evidence for stochastic simulation in Bayesian networks. In UAI 5 (1989), 209--220.

[9]

Getoor, Lise, and Ben Taskar, eds. 2007. Introduction to statistical relational learning. MIT Press.

Digital Library

[10]

Goodman, Noah D., Vikash K. Mansinghka, Daniel Roy, Keith Bonawitz, and Joshua B. Tenenbaum. 2008. Church: A language for generative models. In UAI 24, 220--229.

[11]

Haynes, Christopher T. 1987. Logic continuations. Journal of Logic Programming 4(2):157--176.

Digital Library

[12]

Jaeger, Manfred, Petr Lidman, and Juan L. Mateo. 2007. Comparative evaluation of probabilistic logic languages and systems. In Proceedings of mining and learning with graphs. http://www.cs.aau.dk/~jaeger/plsystems/.

[13]

Kiselyov, Oleg. 2006. Native delimited continuations in (byte-code) OCaml. http://okmij.org/ftp/Computation/Continuations.html#caml-shift.

[14]

Koller, Daphne, David McAllester, and Avi Pfeffer. 1997. Effective Bayesian inference for stochastic programs. In AAAI, 740--747.

Digital Library

[15]

Leroy, Xavier, Damien Doligez, Jacques Garrigue, Didier Rémy, and Jérôme Vouillon. 2008. The Objective Caml system, release 3.11. INRIA.

[16]

McAllester, David, Michael Collins, and Fernando Pereira. 2008. Case-factor diagrams for structured probabilistic modeling. Journal of Computer and System Sciences 74(1):84--96.

Digital Library

[17]

Milch, Brian, Bhaskara Marthi, Stuart Russell, David Sontag, Daniel L. Ong, and Andrey Kolobov. 2007. BLOG: Probabilistic models with unknown objects. In Getoor and Taskar (2007), 373--398.

[18]

Minka, Tom, John M. Winn, John P. Guiver, and Anitha Kannan. 2009. Infer. NET 2.2. Microsoft Research. http://research.microsoft.com/infernet.

[19]

Murphy, Kevin. 2007a. Bayes Net Toolbox for Matlab. http://www.cs.ubc.ca/~murphyk/Software/BNT/bnt.html.

[20]

Murphy, Kevin. 2007b. Software for graphical models: A review. International Society for Bayesian Analysis Bulletin 14(4):13--15.

[21]

Pfeffer, Avi. 2007a. The design and implementation of IBAL: A general-purpose probabilistic language. In Getoor and Taskar (2007), 399--432.

[22]

Pfeffer, Avi. 2007b. A general importance sampling algorithm for probabilistic programs. Tech. Rep. TR-12-07, Harvard Univ.

[23]

Poole, David, and Alan Mackworth. 2009. Artificial intelligence: Foundations of computational agents. Cambridge Univ. Press.

[24]

Radul, Alexey. 2007. Report on the probabilistic language Scheme. In DLS '07: Proceedings of the 2007 symposium on dynamic languages, 2--10. New York: ACM Press.

Digital Library

[25]

Russell, Stuart, and Peter Norvig. 2003. Artificial intelligence: A modern approach. 2nd ed. Prentice-Hall.

Digital Library

[26]

Sato, Taisuke. 2008. A glimpse of symbolic-statistical modeling by PRISM. Journal of Intelligent Information Systems 31(2): 161--176.

Digital Library

[27]

Shachter, Ross D., and Mark A. Peot. 1990. Simulation approaches to general probabilistic inference on belief networks. In UAI 5 (1989), 221--234.

Cited By

Chistikov DDimitrova RMajumdar R(2017)Approximate counting in SMT and value estimation for probabilistic programsActa Informatica10.1007/s00236-017-0297-254:8(729-764)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s00236-017-0297-2
Chistikov DDimitrova RMajumdar R(2015)Approximate Counting in SMT and Value Estimation for Probabilistic ProgramsProceedings of the 21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems - Volume 903510.1007/978-3-662-46681-0_26(320-334)Online publication date: 11-Apr-2015
https://dl.acm.org/doi/10.1007/978-3-662-46681-0_26
Hur CNori ARajamani SSamuel S(2014)Slicing probabilistic programsACM SIGPLAN Notices10.1145/2666356.259430349:6(133-144)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2666356.2594303
Show More Cited By

Index Terms

Monolingual probabilistic programming using generalized coroutines
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Probabilistic reasoning
      2. Vagueness and fuzzy logic
  2. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Inductive inference

Recommendations

Revisiting coroutines

This article advocates the revival of coroutines as a convenient general control abstraction. After proposing a new classification of coroutines, we introduce the concept of full asymmetric coroutines and provide a precise definition for it through an ...
Coroutines in FORTRAN

A method is described for using coroutines within the strict confines of ANSI FORTRAN. A FORTRAN preprocessor that has been implemented to transform FORTRAN programs, written as if coroutines were allowed, to standard ANSI FORTRAN programs is also ...
Embedded Probabilistic Programming
DSL '09: Proceedings of the IFIP TC 2 Working Conference on Domain-Specific Languages

Two general techniques for implementing a domain-specific language (DSL) with less overhead are the <em>finally-tagless</em> embedding of object programs and the <em>direct-style</em> representation of side effects. We use these techniques to build a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

UAI '09: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence

June 2009

667 pages

ISBN:9780974903958

Conference Chair:
David McAllester
Toyota Technological Institute at Chicago

Sponsors

Google Inc.
IBMR: IBM Research
Intel: Intel
Microsoft Research: Microsoft Research

Publisher

AUAI Press

Arlington, Virginia, United States

Publication History

Published: 18 June 2009

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
116
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)8

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chistikov DDimitrova RMajumdar R(2017)Approximate counting in SMT and value estimation for probabilistic programsActa Informatica10.1007/s00236-017-0297-254:8(729-764)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s00236-017-0297-2
Chistikov DDimitrova RMajumdar R(2015)Approximate Counting in SMT and Value Estimation for Probabilistic ProgramsProceedings of the 21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems - Volume 903510.1007/978-3-662-46681-0_26(320-334)Online publication date: 11-Apr-2015
https://dl.acm.org/doi/10.1007/978-3-662-46681-0_26
Hur CNori ARajamani SSamuel S(2014)Slicing probabilistic programsACM SIGPLAN Notices10.1145/2666356.259430349:6(133-144)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2666356.2594303
Hur CNori ARajamani SSamuel SO'Boyle MPingali K(2014)Slicing probabilistic programsProceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2594291.2594303(133-144)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2594291.2594303
Gordon AAizatulin MBorgstrom JClaret GGraepel TNori ARajamani SRusso C(2013)A model-learner pattern for bayesian reasoningACM SIGPLAN Notices10.1145/2480359.242911948:1(403-416)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2480359.2429119
Gordon AAizatulin MBorgstrom JClaret GGraepel TNori ARajamani SRusso CGiacobazzi RCousot R(2013)A model-learner pattern for bayesian reasoningProceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/2429069.2429119(403-416)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2429069.2429119
Borgström JGordon AGreenberg MMargetson JVan Gael J(2011)Measure transformer semantics for Bayesian machine learningProceedings of the 20th European conference on Programming languages and systems: part of the joint European conferences on theory and practice of software10.5555/1987211.1987216(77-96)Online publication date: 26-Mar-2011
https://dl.acm.org/doi/10.5555/1987211.1987216
Toronto NMcCarthy J(2010)From Bayesian notation to pure racket via discrete measure-theoretic probability in λZFCProceedings of the 22nd international conference on Implementation and application of functional languages10.5555/2050135.2050141(89-104)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.5555/2050135.2050141
Kiselyov O(2010)Delimited control in OCaml, abstractly and concretelyProceedings of the 10th international conference on Functional and Logic Programming10.1007/978-3-642-12251-4_22(304-320)Online publication date: 19-Apr-2010
https://dl.acm.org/doi/10.1007/978-3-642-12251-4_22

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents