iffsid / stochastic-discrete Goto Github PK

This implements a stochastic programming language for discrete distributions along with a stochastic constraint satisfaction problem solver.

Distributions are lists of dotted pairs, an arbitrary object followed by a probability (e.g. ((a . 0.2) (b . 0.5) (c . 0.3))). They must be non-negative, but may sum to less than one. The output of distribution of a stochastic program is not normalized to sum to 1; you'll have to do that yourself if that's what you're after.

This egg is an extension to the nondeterminism and csp eggs and works very similarly. Domains are distributions, a csp (constraint satisfaction problem) is a gm (graphical model), fail is bottom, unwedge-trail is forget-trail.

We can implement the above with a stochastic program, I've kept this simple using only flip but it could be more succinctly written with draw.

   (define (example1)
    (let* ((rain (flip 0.2))
           (sprinkler (if rain (flip 0.01) (flip 0.4)))
           (grass-wet (cond ((and (not sprinkler) (not rain)) (flip 0))
                            ((and (not sprinkler) rain)       (flip 0.8))
                            ((and sprinkler (not rain))       (flip 0.9))
                            ((and sprinkler rain)             (flip 0.99)))))
     (list rain sprinkler grass-wet)))

We can then query the program, say we want to answer the same question as the Wikipedia page for Bayesian networks ("What is the probability that it is raining, given the grass is wet?")

   (normalize-distribution
    (distribution
     (let ((r (example1)))
      (when (not (last r)) (bottom))
      (first r))))

This will return

    ((#f . 0.642312324367724) (#t . 0.357687675632276))

Which agrees with Wikipedia's computation of 35.77%.

(flip alpha)

(bottom)

(forget-trail)

(draw distribution)

(current-probability)

(create-distribution-variable distribution)

(gm-solution ds)

(gm-bb-solution ds)

(gm-bb-predict-solution ds)

(gm-bb-predict-solution-with-start ds start)

(gm-assert-constraint! constraint . distribution-variables)

(gm-assert-constraint-efd! constraint ds)

(gm-assert-constraint-fc! constraint ds)

(gm-assert-constraint-vp! constraint ds)

(gm-assert-constraint-gfc! constraint ds)

(gm-assert-constraint-ac! constraint ds)

(support ...)

(probability ...)

(expected-value ...)

(entropy ...)

(most-likely-value distribution)

(most-likely-pair distribution)

(draw-pair distribution)

(fold-distribution-thunk f i thunk)

(top-level-flip alpha)

(top-level-bottom)

(top-level-current-probability)

(supportq ...)

(supportv ...)

(supportp ...)

(distributionq ...)

(distributionv ...)

(distributionp ...)

(fold-distribution ...)

(support-thunk thunk)

(supportq-thunk thunk)

(supportv-thunk thunk)

(supportp-thunk p? thunk)

(probability-thunk thunk)

(expected-value-thunk plus times zero thunk)

(entropy-thunk thunk)

(distribution-thunk thunk)

(distributionq-thunk thunk)

(distributionv-thunk thunk)

(distributionp-thunk p? thunk)

(upon-bottom-thunk thunk)

(restrict-distribution! x distribution)

(gm-bound? x)

(gm-binding x)

(some-element p x)

(one-element p x)

(the-element p x)

(the-elements p x)

(attach-demon! demon x)

Copyright 2010-2012 Purdue University. All rights reserved. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Lesser Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Lesser Public License for more details. You should have received a copy of the GNU General Lesser Public License along with this program. If not, see http://www.gnu.org/licenses.