Belief Propagation - test_cat_bool_joint

User 49 | 5/26/2014, 6:46:28 PM

Hi,

I was running Belief Propagation in GraphLab on a few public datasets (basically used testcatbool_joint). The results seem decent. However, I need to implement 'Lifted Belief Propagation' where I need to modify the message computation (the messages sent by variables to factors and vice versa). Could someone explain what code sequence to look at? And also, does GraphLab construct an explicit factor graph, i.e, one with variables and factors explicitly added with edges between them, or an implicit one (with only the variables, and potentials defined on the edges)?

Thanks!

Comments

User 140 | 5/27/2014, 5:27:39 PM

GraphLab allows the developer to specify a vertex type and an edge type as template parameters when defining a graphlab::distributedgraph. I defined these in src/graphlab/factors/bpgraphdata.h. The vertex program, which computes the messages, is defined in bpvertex_program.hpp

bpgraphdata::vertexdata defines the vertex type, which stores the prior (sometimes referred to as potential) and belief distributions for a vertex. A vertex can define either a variable or a factor node---the difference between variables and factors is semantic. When declaring a variable node, it's distributions are always stored as a 1D densetable (enforced by factorgraph.hpp). A factor node can have either a dense or sparse distribution (although if you are not using sparse tables, then you can ignore this). The only other difference between a variable and factor is an isVariable flag in vertexdata. This is simply used to make some things like logging easier.

The vertex program is run per vertex and essentially gathers all messages on the incoming edges (adding them in logspace with implicit broadcasting) in the Gather phase (bpvertexprogram::gather()). The Apply phase adds the vertex's prior distribution (bpvertexprogram::apply()). And the Scatter phase computes the outgoing messages which are put on the outgoing edges (bpvertexprogram::scatter()).

If you want to make a change to how the messages are computed, you would do it in bpvertexprogram (in scatter() probably).

-s


User 49 | 6/14/2014, 7:43:53 AM

Thank you.

Could you tell me where do I update edge properties? I want the edges in the factor graph (between variables and factors) to contain a new integer as its weight. I can pass it as an argument to the addedge() call from makebpgraph() in factorgraph.hpp. As far as I can see, it calls addedge() in distributedgraph.hpp, which further calls addedge() in distributedingress_base.hpp. But I cannot figure where to add the weight to the edge.


User 49 | 6/15/2014, 4:49:13 PM

Update: I got that thing cleared. You may ignore my previous comment. I would like to what is the quantity 'const gathertype& total' in the function apply() in bpvertex_program.hpp, and how and where is it computed? I need to use modify message passing so that each message gets raised to the corresponding 'edge weight'


User 140 | 6/16/2014, 7:36:22 PM

I'm gonna repost since my previous post was pretty badly mangled and made some things difficult to follow.

To answer what I think is your main question, in bpvertexprogram::scatter(...), you can just 'raise' newmessage by your new weight (I would say after line 237 (cavity.table()->MAP(newmessage);) and before regularization, but you can do it after that if you'd like). Be aware that the message is expected to be stored in log space, so raising a variable to a power is the equivalent of multiplication. Also, the shiftnormalization() performed on newmessage is not a true normalization but rather a shift in log space to preserve dynamic range.

To answer the rest of your question, gathertype is defined when you define the vertex program: <pre><code>template<sizet MAXDIM> class bpvertexprogram : public graphlab::ivertexprogram< typename graphtype<MAXDIM>::type, factorproduct<MAXDIM>, graphlab::messages::sumpriority > { ... typedef typename ivertexprogramt::gathertype gather_type; ... } </code></pre>

In this case, factors/bpvertexprogram.hpp extends graphlab::ivertexprogram, where ivertexprogram is defined in vertexprogram/ivertexprogram.hpp: <pre><code>template<typename Graph, typename GatherType, typename MessageType = graphlab::empty> class ivertexprogram {
... typedef GatherType gather
type; ... } </code></pre>

So gathertype is of type factorproduct<>, which is defined just above bpvertexprogram to wrap the operator+=(...) because graphlab expects gather_type to behave like the accumulator operator (+).

(For completeness, graphtype< >::type is defined in factors/bpgraphdata.h: <pre><code>template<sizet MAXDIM> struct graphtype { typedef graphlab::distributedgraph<vertexdata<MAXDIM>, edgedata<MAX_DIM> > type; }; </code></pre> )

'gathertype& total' is computed by the iengine<>, which is an engine interface and part of core GraphLab. The only iengine I've looked at closely is the synchronousengine in engine/synchronousengine.hpp. synchronousengine::executegathers(...) computes total and executeapplys(...) calls ivertexprogram::apply(...) (bpvertex_program::apply(...) in this case). However, you almost certainly do not want to modify core GraphLab.


User 334 | 10/1/2014, 5:37:01 AM

Hi there,

I have a quick question, that I cannot find out the answer by my self right now.

How is the variable evidence implemented? I mean, before running inference (using the belief propagation algorithm) you should set that some variables have some values ( you are saying that those variables are observed ones). How do we explicit that some variables are observed and have a specific value?

Thank you for your time


User 49 | 10/28/2014, 10:13:49 AM

Hi Breno,

I think one option that we have is that we can define singleton potentials (i.e, a single factor defined over a single variable). The values in its potential table would be according to the observed state of the variable. That is, if the variable was observed to be true, the entry under would be very high and vice versa.

Hope this helps.