Using Belief Propagation and Factor Graphs

User 823 | 12/24/2014, 12:51:00 PM

Hi, I wanted to infer using belief propagation algorithm. I saw your example "testdensetable.cpp" and understood what's going on in it. But when I calculate the LBP algorithm by hand, I get different results, I want to know what my mistakes are. Here I will explain the problem and then the solution that I got from algorithm As far as I understood, we have a factor graph that is in the following form:

factor(foo :1)---foo---factor(foo,boolvarb:2)---boolvarb---factor(boolvarb :3)

So we have 2 variables (foo,boolvarb) and three factors. you can also see our factors in the following tables: ===================================== boolvarb | foo | potential 0 | 0 | 0.1 0 | 1 | 0.8 1 | 0 | 0.9 1 | 1 | 0.2 ======================= foo | potential 0 | exp(-1) 1 | 1-exp(-1) ========================= boolvarb | potential 0 | 0.1 1 | 0.9

So belief of variable boolvarb can be obtained in one step inference: M12(foo) = phi(foo) phi(foo=0) = exp(-1) phi(foo=1) = 1-exp(-1) Here M stands for message and M12 is a message that is passed from factor 1 to factor 2.

M23(boolvarb=0) = psi(foo=0,boolvarb=0)*phi(foo=0)+psi(foo=1,boolvarb=0)*phi(foo=1) psi(foo=0,boolvarb=0) = 0.1 psi(foo=1,boolvar_b=0) = 0.8

M23(boolvarb=1) = psi(foo=0,boolvarb=1)*phi(foo=0)+psi(foo=1,boolvarb=1)*phi(foo=1) psi(foo=0,boolvarb=1) = 0.9 psi(foo=1,boolvar_b=1) = 0.2

belief(boolvarb=0) = M23(boolvarb=0)*phi(boolvarb=0) phi(boolvar_b=0) = 0.1

belief(boolvarb=1) = M23(boolvarb=1)*phi(boolvarb=1) phi(boolvar_b=0) = 0.9

And finally we get the following probabilities for variable boolvarb: ptrue = 0.88359 pfalse = 0.11641

but the program "testdensetable.cpp" shows the following results: ptrue = 0.78835 pfalse = 0.21165

I want to know what my mistake is. thanks

Comments

User 140 | 1/5/2015, 10:06:45 PM

Hi Arzani, Sorry for the delayed response.

I am confused by your post. I assume the executable you are referring to is actually testcatbooljoint, and not testdensetable. If so, your foo and boolvar_b potential are not correct. The factor graph looks like this:

<code class="CodeInline">boolobs (factor) -- boolvar_b (variable) -- cbj (factor) -- foo (variable)</code>

However, the graph can be simplified into an equivalent graph by transforming boolobs into a prior on boolvar_b, so the graph would look like this:

<code class="CodeInline">boolvarb (variable:1) -- cbj (factor:2) -- foo (variable:3)</code>

Also, the priors on the factors should be: <blockquote class="Quote">foo | potential 0 | exp(-1) = 0.269 1 | exp(0) = 0.731; not 1-exp(-1) as you have, although a round number would be nicer </blockquote> <blockquote class="Quote">boolvarb | potential 0 | 0.1 1 | 0.9 </blockquote> <blockquote class="Quote">boolvarb x foo | potential 0 | 0 | 0.1 0 | 1 | 0.8 1 | 0 | 0.9 1 | 1 | 0.2 </blockquote>

It is mentioned in the documentation, but it should be clearer: we are preforming the max-product (max-sum in log-space) version of belief propagation (although support for the sum-product variant exists).

So the first message to boolvarb would be (all operations are preformed in log space, although that will be omitted for clarity) [max( [0.269, 0.731] [0.1, 0.8] ), max( [0.269, 0.731] [0.9, 0.2] )] = [max( [0.0269, 0.5848] ), max( [0.2421, 0.1462] )] = [0.5848, 0.2421] = [0.5848, 0.2421] / sum([0.5848, 0.2421]) = [0.7072, 0.29278]

Then, applying the boolvarb prior gives the current belief of ptrue & pfalse [0.7072, 0.29278] * [0.1, 0.9] = [pfalse, ptrue] = [0.21165, 0.78835]

Let me know if that is any clearer.


User 823 | 1/15/2015, 4:41:18 PM

Thank you sgrichar for your informative explanation, I found my mistakes and it is clear to me now.


User 823 | 6/23/2015, 10:32:07 AM

Thanks again for your response, recently we encountered a new problem regarding calculating the believes for the variables. we changed the belief propagation calculation method from max-product to sum product and now we need to calculate believes for our work but we could not find out how your code calculates them. In above mentioned example we calculated the believes as stated below:

If we normalize the factors we achieve the following results: <blockquote class="Quote"> <div>foo | potential</div> <div>0 | 0.269</div> <div>1 | 0.731</div> </blockquote>

<blockquote class="Quote"> <div>boolvarb | potential</div> <div>0 | 0.1</div> <div>1 | 0.9</div> </blockquote>

<blockquote class="Quote"> <div>boolvarb x foo | potential</div> <div>0 | 0 | 0.05</div> <div>0 | 1 | 0.4</div> <div>1 | 0 | 0.45</div> <div>1 | 1 | 0.1</div> </blockquote>

then our believes will be: m1 = foo * [boolvarb x foo] = 0.2689 [ 0.0500 0.4500] ; 0.7311 [ 0.4000 0.1000] =

m1 = 0.0134 0.1210 0.2924 0.0731

m2 = sum(m1)

=> m2 = [0.3059 0.1941]

beliefforvariable = [0.3059 0.1941] * [0.1 0.9] = [0.0306 0.1747]

but the code result is 0.1111 0.6347

I was wondering how the code calculates believes.

Also, I would be grateful if you could mention the papers which you have implemented graphical models based on them (especially belief propagation).

Thanks in advance, Arzani