Loopy Belief Propagation code example

Question

Does anybody know of a working code example of the sum-product algorithm for (loopy) belief for Bayesian Networks? I have scoured the earth for a couple days but haven't had much luck. I'm indifferent to which language it is in.

All the documents I have found on the topic are full of arcane and absurdly ambiguous mathspeak. It doesn't seem like a difficult algorithm, but I can't be sure because some of the tricky bits are glossed over so much.

Alternately, an example that uses real numbers (rather than variable names) would probably do the trick as well.

Answer 1

I've implemented Pearl's belief propagation algorithm for Bayesian Networks. It supports loopy propagation as well, as it will terminate when the informed belief values converge to within 0.001.

All the code is in Java, and it may be found in my Google code pen-ui svn repo.

This doesn't explicitly make a factor graph.

The class "Support" has a main function, and a couple static methods that create small networks that you can play with. In particular I implemented the three-node Burlar-FreightTruck-Alarm network found in Neapolitan's book, and my numbers check out. (No promises beyond that!)

Answer 2

I'm in a similar situation. I'm using the book "Pattern Recognition and Machine Learning" by Christopher M. Bishop for a theoretical introduction, even though I do want to use the algorithm in some other context. The chapter on "max-product" and "sum-product" describes belief propagation, although it is very mathematical.

I'm still looking for a small numerical example so if you find one I'd be very interested.

Meanwhile you can take a look at libDAI, an open source library that implements BP.

Answer 3

I am implementing a factor graph / belief propagation algorithm in Clojure, but the code is not yet ready. (My code also lifts Bayesian networks from propositional logic to first-order / higher-order logic.)

Anyway, I'd like to share some tips:

1. First, note that even though marginalization is denoted as summation, its properties are different from summation. In particular, it commutes with products of probability tables (known as potentials). That's why in the mathematical derivation, sums and products can be exchanged, whereas in ordinary arithmetic they cannot.

2. Note that in Pearl's algorithm, the messages that go upstream and downstream are different -- likelihoods go upstream and probabilities go downstream. (This is the reason why Bayes's rule works in the derivation of belief propagation).

3. In the factor graph algorithm, messages are CPTs (conditional probability tables) such as P(A|K). The CPTs of P(A|K) and P(K|A) and P(A,K) contain essentially the same information. At a terminal node, we have to marginalize as well as condition the CPT over the appropriate variables. This seems to be obscured in the math notations.