A probabilistic language

    Probabilistic programming languages are an attempt to unify a variety of probabilistic models.  For instance, Koller et al's stochastic lambda calculus [2], and Pfeffer's IBAL language [3], both can express tree- and table- structured distributions, Bayes nets, and probabilistic grammars.  Ideally, the language user should just have to worry about specifying the model, while the implementation takes care of the probability "bookkeeping" for inference and learning.
    I implemented inference for a similar language using the probability monad.

The probability monad

    Monads are an idea from category theory, which are used in the functional language Haskell to encapsulate IO and state-changing effects.  Probability distributions form a monad. [4]
    The probability monad provides four building blocks with which to build probabilistic programs:

• choose p A B - returns A's result with probability p, B's result with probability 1-p
• then A B - samples A, then returns B (which can depend on A's result)
• return x - always results in x (i.e., with probability 1)
• observe p A - returns the result of A, only in cases when p is true
  

(observe isn't in the basic probability monad, but it is a fundamental operation in Pfeffer's IBAL language.)  The naive implementations of sampling and support are efficient, but the naive implementation of inference (and therefore learning) can take exponentially longer, because it ignores conditional independence.

Implementation

    I implemented the probability monad in R4RS Scheme.  (It also requires the SLIB library.)  The source, distributed under the GNU Lesser General Public License, was developed using UMB Scheme.
    I used call-with-current-continuation (also known as call/cc) to make inference take advantage of conditional independence.  The implementation of then A B starts out by assuming that the distribution of A isn't needed.  But, if it is needed, then call/cc calls a function which computes A's distribution, and uses that to compute B's distribution.

Strengths

    The resulting implementation is concise - less than 200 lines of Scheme code.  It is well-integrated with the host language; probabilistic programs can use Scheme programs and built-in functions, and Scheme programs can call inference routines.

Weaknesses

    The implementation requires call/cc, which is in the R4RS standard, but tricky to implement efficiently.  Also, it still wastes some effort (because call/cc throws out some work)

    I haven't implemented EM so far.

    The syntax for probabilistic programs is awkward.  Haskell's do-notation would help, but Haskell doesn't have call/cc.
    There also need to be more test programs.

To do

    choose should be generalized to return one of several results.
    EM should be implemented.
    I'd like to avoid using call/cc, possibly using arrows [1], which are a generalisation of monads.

References

[1] Hughes, John.  2000.  Generalising Monads to Arrows.  In Science of Computer Programming 37, pp67-111, May 2000.

[2] 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.

[3] Pfeffer, Avi.  2001.  IBAL: An Integrated Bayesian Agent Language.  In IJCAI 2001.

[4] Ramsey, Norman and Avi Pfeffer.  2002.  Stochastic Lambda Calculus and Monads of Probability Distributions.  In Principles of Programming Languages (POPL) '02.

---

Josh Burdick / jburdick@gradient.cis.upenn.edu / last modified June 17, 2003