GraphLab Belief Propagation

[Arpit Jain]

Hello,

I have started using GraphLab for doing inference on graphical models. In particular, I need to use the belief propagation algorithm on my Markov network with my own potential tables. As I understand the code for the same in GraphLab, there is no way to modify the message passing according to one's own custom potential table. 

I have looked at the file lbp_structured_prediction.cpp, and I have tried modifying the function 'convolve', which is where the new message is computed. But the results are incorrect. 

Any help in this regard would be appreciated.

Thanks.

[Danny Bickson]

Hi Jain, 

Previously we got a code contribution from Scott Richardson which was merged into Graphlab. Here is a quick explanation we got from him on how to operate it:

I'd say take a look at toolkits/graphical_models/factors/tests/test_bool_var/test_cat_bool_var.cpp

It creates two variables, foo and bool_var_b, each with two states, connected to a 2x2 factor (there is also a unary evidence factor (prior) attached to bool_var_b). Visually, this looks like

 bool_obs (factor)

     |

     |

 bool_var_b (variable : {false, true})

     |

     |

 factor

 cat/fp-tp |  false | true |

 ----------|--------|------|

 state1    |  0.1   |  0.9 |  ---  foo (variable : {state1, false pos})

 ----------|--------|------|

 false pos |  0.8   |  0.2 |

 ---------------------------

 joint belief values (cbj)

The factor's action is to ensure the compatibility between bool_var_b and foo. That is, when bool_var_b is false, we want foo to report it is more likely a false positive. 

In code, I first construct two variables (with belief_prop::factor_graph::add_variable(...)) and set their prior. I then construct the cbj factor (with belief_prop::factor_graph::add_factor(...)) which is connected to the two variables (technically, it spans the domain defined by the cross product of the two variables). When constructing the factor, I also define its joint probability distribution. Finally, I build the unary prior factor bool_obs. 

I then convert the factor graph into a GraphLab distributed graph with belief_prop::factor_graph::make_bp_graph(...) and kickoff the GraphLab engine in the normal fashion. Finally, I must pull the beliefs back into the factor graph (from the GraphLab distributed graph) with belief_prop::factor_graph::pull_beliefs_for_variables(...). 

Let me know if that helps

Danny Bickson

Co-Founder
GraphLab Inc.

--
You received this message because you are subscribed to the Google Groups "GraphLab API" group.
To unsubscribe from this group and stop receiving emails from it, send an email to graphlabapi...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Arpit Jain]

Hello Danny,

Thanks for the response. I have a few things to clarify.

1. I went through the file test_cat_joint.cpp and also your explanation. I figured that the network it creates is basically two variables, a binary factor and a unary factor. However, I do not understand how the priors and the joint potential table have been defined (in particular, the 'nlog belief values'). Also, how do we look at the output (the marginals of the variables)?

2. The way I understand belief propagation is that we start with the Markov network and build the 'factor graph' from it. And then, we do message passing. Is it creating an explicit factor graph here?

3. It has been described in the GraphLab documentation that we need to look at lbp_structured_prediction.cpp to run belief propagation. Does it work only when the potential tables are symmetrically defined (i.e, the potentials are equal for the variables being equal, as in the 'convolve' function)? Also, it does not appear to create an explicit factor graph. Is that right?

Thanks,

Arpit

[Danny Bickson]

Hi, 

1) Example for setting the prior is here:

https://github.com/graphlab-code/graphlab/blob/master/toolkits/graphical_models/factors/tests/test_bool_var/test_cat_bool_joint.cpp#L112-L114

Example for setting the joint potential is here:

https://github.com/graphlab-code/graphlab/blob/master/toolkits/graphical_models/factors/tests/test_bool_var/test_cat_bool_joint.cpp#L138-L142

2) Yes. The factor graph is illustrated graphically in the text image in the previous email. It has 4 nodes and 3 edges.

3) Belief propagation is a general name of a family of algorithms that have many flavors. Those algorithms split into directed and undirected graphical models. Furthermore, some variants use factor graph notation, namely a bipartite graph with two types of operation while others have the same operation implemented in all nodes. 

There is no connection between the other example which uses convolution to this example.

Danny Bickson

Co-Founder
GraphLab Inc.

[Arpit Jain]

Hi,

I looked at the code. But I do not understand how the joint potential has been defined. For example, if we have two variables (as is the case in the test_cat_bool example), we need to define potentials for the four states (00, 01, 10, 11). In the textual image, there are foo, false-positive etc. How do these relate to the four-state potential table is in the naive sense?

Secondly, for the example test_cat_bool_joint, how do we get the output in the formal of marginal probabilities?

Thanks,

Arpit

[Scott Richardson]

Hi Arpit, I can add a few comments,

This factor graph, creates two variables, foo and bool_var_b, each with two states. The variables are related to each other through the factor node, cbj. (bool_obs is also a unary evidence factor (prior) attached to bool_var_b.)

A factor or variable's probability mass function (PMF) is specified by a dense_table (which is basically just an N-d matrix and is defined in toolkits/graphical_models/factors/dense_table.hpp) in which each label has a corresponding log probability (we use the log of the belief value for numerical stability). A variable is always a 1D dense_table. Factor cbj is a 2D dense_table with a domain that spans the cross product of domains' the two variables.)

The nlog belief values in the table for this example are arbitrary. You can set them to whatever your discrete probability mass function is using one of dense_table::logP(size_t), dense_table::logP(discrete_assignment), or one of the specialized constructors. (A discrete_assignment is a subindex over a domain (in Matlab, for example, to access element (1,2) in an array, you would do myArray(1,2); analogously, a discrete_assignment specifies this assignment. I can explain these in more detail if you'l like)). 

Once the evidence has been propagated across the distributed graph and the results pulled back into the factor graph using factor_graph.hpp::pull_beliefs_for_variables(), the resulting marginal distribution for the variable var can be queried using factor_graph.hpp::belief_for_variable(var), which returns a 1D dense_table. Then, you can find the most likely value in the distribution using dense_table::max_index(), which returns the linear index of the largest value.

Does that help at all? 

Scott

[Danny Bickson]

Thanks Scott for your great assistance!! :-)

Danny Bickson

Co-Founder
GraphLab Inc.

[Arpit Jain]

Hi Scott,

Sorry for the delayed response. I ran the program, and the output that it gives (probability of bool_var_b being true) comes to be 0.78. However, I worked out the message passing algorithm by hand, by constructing the nodes and factors and also the potential table. In that case, the marginal comes as 0.94. Note that I defined my potential table as the following:

foo| bool_var_b | potential

0   | 0                    |   0.1 

0   | 1                    |   0.8

1   | 0                    |   0.9

1   | 1                    |   0.2 

My factor graph for the given example (test_cat_bool_joint.cpp) had 2 nodes and 2 factors. I also considered the priors for the variable foo.

Am I relating it in the right way to the one given in the file? Or is my interpretation different?

Thank You

Arpit

[Scott Richardson]

Hi Arpit, I will double check it by hand again. One thing however: the prior should be on the variable bool_var_b, not on the variable foo. Also, I think your potential table should be transposed. (I will also describe how the domain is constructed/ordered for factors in a separate email, as it is actually a little unintuitive...) 

-s

[Scott Richardson]

Hi Arpit, 

I reran the calculation by hand and get the same thing I had. I should mention that we are preforming the max-product (max-sum in log-space) version of belief propagation (although adding support for the sum-product variant would be easy). 

A quick summary on how data in a dense_table (and sparse table, for that matter) is ordered: 

As I mentioned, a factor is defined by a probability mass function, which is stored in a an N-d matrix defined by a dense_table. The N-d matrix of the dense_table spans the domain defined by the factor's neighboring variables. So, for instance, the domain of cbj is defined as the cross product of the domains of the two attached variables, bool_var_b and foo. 

However, the ordering of the domain is important, and I admit, a little counter-intuitive. (It is a hold-over from an older version of this library and maintained for performance reasons.) The domain is ordered such that the variable with the smallest ID iterates fastest. That is, each variable (created with belief_prop::factor_graph::add_variable(...)) is a assigned a consecutive ID. A discrete_domain can then be constructed over a vector of variables and a dense_table can be constructed over the domain. When iterating over the table's domain, the smallest stride will be for the variable with the smallest ID (not, for example, the first variable added to the domain...). So in our example, foo was created before bool_var_b, so the linear index of cbj's domain is, 

 factor

 cat/fp-tp |  false | true |

 ----------|--------|------|

 state1    |    0   |   2  |

 ----------|--------|------|

 false pos |    1   |   3  |

 ---------------------------

 joint belief values (cbj)

 

See dense_table.hpp for additional documentation.

(NOTE there is a convenience constructor in dense_table.hpp which allows you to provide a vector of variables (not an explicit discrete_domain), and a corresponding data vector ordered such that the first variable in the vector iterates the fastest. The entries in the vector are re-sorted such that the variable with the smallest id iterates fastest.)

-s

[Arpit Jain]

Thanks for the great help Scott.

I re-worked the computation by hand. The potential table I defined as the following: (keeping in mind the idea that the variable with the least id iterates fastest)

bool_var_b | foo    | potential

0               |   0     |   0.1

0               |   1     |   0.8

1               |   0     |   0.9

1               |   1     |   0.2

So basically, my factor graph has 2 variable nodes, 1 binary factor and another unary factor. Note that there was a prior on foo, so I defined a unary factor corresponding to it. This unary factor is of the following form:

foo  | potential

0     | exp(-1)

1     | 1-exp(-1)

 Is it right to do so? I have a doubt that this maybe incorrect. But how do we incorporate priors in bp then? So in effect, my factor graph has 2 variable nodes, 2 unary factors and one binary factor.

Then I ran message passing, which converges in single step as is clear. However, I get incorrect marginals (for the case of max-product bp). I am unable to understand where exactly am I wrong as far as the interpretation is concerned. 

Thanks,

Arpit

[Arpit Jain]

Hi Scott,

Just to clear, I got my mistake. I don't think it's legal to define the prior in the form of a unary factor. Correct me if I am wrong. 

I got rid of the prior on foo and reran graphlab. Now the results match those computed by hand.

There are a couple of questions:

1. How do we run sum-product bp instead of max-product?

2. Is it possible to define factors over any number of variables (instead of two, as defined in the example)?

Thanks and Regards,

Arpit

[Scott Richardson]

Hi Arpit 

This gets into the weeds a little, but I think I see your confusion now. Every vertex, factor or variable, has two distributions associated with it---what I call a prior (or sometimes a potential) and a belief. Setting the prior on a variable is equivalent to defining a unary factor node attached to the variable. So in this case, foo has its prior set as you described: 

    foo  | potential

    0  |   exp(-1)

    1  | 1-exp(-1)

Although you could also define a unary factor node attached to foo with this distribution and leave the prior for foo uniform. 

As for your questions

1) It is easy, I just forgot to make a few necessary changes. I'll have to talk over with Danny how best to deliver this update. 

2) Yes, you can define a factor over as many variables as you'd like, just add them to the vector of variables that is used to construct the domain. Remember, although this example uses a convenience constructor in dense_table to construct a table from a vector of variables, a table is actually defined over a discrete_domain. 

Thanks for your patience on this. I will look into making this example a little clearer. 

-s

[Danny Bickson]

Thanks Scott for your ongoing great support!

Arpit - it would be great if you could summarize your learning so far with the back of the envelope calculation over an email - we would love to update the tutorial with your example giving you credit for it of course.

Thanks

Danny Bickson

Co-Founder
GraphLab Inc.

[Arpit Jain]

Thank you Scott and Danny. I will get back with the calculation etc. that I performed in a short while. 

I am working on a project to parallelize belief propagation, and I found GraphLab quite useful. Since the project is time-bound, would it be possible to implement the sum-product version of belief propagation (like you mentioned) in a short time? Or you could give a few instructions on how to implement it myself.

Thanks again.

Arpit

[Scott Richardson]

Hi Arpit, I hope to know today whether I can patch the file myself or if I have to try to describe the fix. 

-s

[Scott Richardson]

Hi Arpit, I just wanted to let you know that I was able to fix-up the sum-product algorithm. To use it, you have to go into toolkits/graphical_models/factors/bp_vertex_program.hpp and comment out line 237 and uncomment line 239 (it would be nice if this were programmatically configurable, but I'm actually not sure how best to do that, aside from a template parameter, since it is the graphlab engine itself that constructs and keeps all references to the vertex_program).

hope this helps 

Scott

[Arpit Jain]

Hi Scott,

I did as directed, but got the following error:

graphlab/toolkits/graphical_models/factors/tests/../../factors/bp_vertex_program.hpp:239:21: error: no member named 'marginalize' in

      'graphlab::table_base<4>'

    cavity.table()->marginalize(new_message);

--

Arpit

[Scott Richardson]

Did you pull the latest changes from the repository before you modified bp_vertex_program?