Graphical Models - Questions about the code and what is being implemented

User 334 | 6/22/2014, 10:29:13 PM

Hello,

I am an undergrad student and I am trying to implement parameter and structure learning in Bayesian Networks. I thought about using the GraphLab to do it, but I am having a hard time trying to understand the graphical models toolkit.

Thus, I would deeply appreciate if someone can address those questions: Where exactly you implement the Markov Random Fields. Do you have a implementation of Belief Networks? If so, did you implement the Belief propagation? How can I find the Bayesian network implementation? Do you already perform parameter and structure learning? If yes, where and for what models? Do you have more documentation about you Factor implementation, do you use it to implement the MRF?

Sorry if some of those are silly questions, but I ensure I did my best trying to figure out the answers by my own. Thank you very much,

Breno Carvalho

Comments

User 6 | 6/23/2014, 7:39:11 AM

Hi Breno, We do support MRF, Belief networks, including inference (belief propagation). The following toolkit: http://docs.graphlab.org/factor_graphs.html implements this functionality.

We do not support general parameter or structure learning.

We suggest searching this forum: http://forum.graphlab.com/search?Search=factor+graph for more detailed documentation of BP issues.

Best,


User 334 | 9/20/2014, 12:32:24 AM

Danny, I am having a hard time with my implementation of algorithms for learning parameters and learning structures for Belief Networks and MRFs.

Is there any more detailed information about the Factor Graph implementation than what we can find at: http://docs.graphlab.org/graphical_models.html ?

I am trying to use Factor Graph to represent Belief Networks and MRFs and write the algorithms, but I am just lost with the myriad of classes, structs and namespaces we have related to Factor Graphs.

Thank you for the support above. :smiley:


User 6 | 9/20/2014, 4:47:25 PM

This PowerGraph code is a contribution from STR. I recommend looking here for an example: http://forum.graphlab.com/discussion/250/belief-propagation-test-cat-bool-joint If you have specific questions we can redirect them to Scott who contributed this code.


User 334 | 10/2/2014, 12:47:11 PM

I have one now:

How is variable evidence implemented (inserting in the graph the information that the variable is observed)?

Thank you for your time.

Can you provide me with a link to Scott Richardson?


User 140 | 10/4/2014, 4:00:04 PM

Hi Breno,

As Danny suggested, you should take a look at toolkits/graphicalmodels/factors/tests/testboolvar/testcatboolvar.cpp

An example for setting the prior is here: https://github.com/graphlab-code/graphlab/blob/master/toolkits/graphicalmodels/factors/tests/testboolvar/testcatbooljoint.cpp#L112-L114

Example for setting the joint potential is here: https://github.com/graphlab-code/graphlab/blob/master/toolkits/graphicalmodels/factors/tests/testboolvar/testcatbooljoint.cpp#L138-L142

Here is the factor graph is illustrated graphically. It creates two variables, foo and boolvarb, each with two states, connected to a 2x2 factor (there is also a unary evidence factor (prior) attached to boolvarb).

<pre class="CodeBlock"><code>boolobs (factor) | | boolvarb (variable : {false, true}) | | factor cat/fp-tp | false | true | ----------|------|-----| state1 | 0.1 | 0.9 | --- foo (variable : {state1, false pos}) ----------|------|-----| falsepos | 0.8 | 0.2 |


joint belief values (cbj) </code></pre>

For completeness, I will describe this example in detail:

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

In code, I first construct two variables (with beliefprop::factorgraph::addvariable(...)) and set their prior. I then construct the cbj factor (with beliefprop::factorgraph::addfactor(...)) which is connected to the two variables. When constructing the factor, I also define its joint probability distribution. Finally, I build the unary prior factor bool_obs.

A factor or variable's probability mass function (PMF) is specified by a densetable (although factors can also be sparsetables), which is basically just an N-d matrix (defined in toolkits/graphicalmodels/factors/densetable.hpp) for which each assignment has a corresponding log probability (we use the log of the belief value for numerical stability). A variable is always a 1D densetable. Factor cbj is a 2D densetable with a domain that spans the cross product of the domains' of 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 densetable::setlogP(discreteassignment, val) or one of the specialized constructors. (A discreteassignment 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'd like).

With the factor graph defined, I can now perform inference. First, I convert the factor graph into a GraphLab distributed graph with beliefprop::factorgraph::makebpgraph(...) and kickoff the GraphLab engine in the standard fashion. For each active vertex, GraphLab then runs the vertex program I defined in factors/bpvertexprogram.hpp, which performs the max-sum version of loopy belief propagation.

Once the evidence has been propagated across the distributed graph, the results are pulled back into the factor graph using factorgraph.hpp::pullbeliefsforvariables(). The resulting marginal distribution for the variable var can then be queried using factorgraph.hpp::beliefforvariable(var), which returns a 1D densetable. You can find the most likely value in the distribution using densetable::maxindex(), which returns the linear index of the largest value.

Let me know if that helps Scott


User 334 | 10/5/2014, 12:12:05 AM

Hi Scott, thank you a lot.

It is actually a insightful explanation of the code that clarifies a lot! :smiley:

If you don't mind I would like to make one more question...

What I meant by "evidence" is that: supposing I have a Belief Network represented by a factor graph I can use "evidence", that is, state that a variable is observed and therefore during this instance of the inference it has a value of 1 in one of the values of one of the rows and 0`s in the other values of that roll the dense_table. This way I can keep my original graph and change it only during the inference process.

<i class="Italic">So in my task I need to perform inference in the same graph several times making small changes in the probability distribution, the densetablet objects. So each time I need to do an inference I start from the original graph, make a small change in the distribution and then run the inference.

Is there an already existent or simple way to do that?</i>

Once again, thank you for your last explanation, and your support :smile:


User 140 | 10/6/2014, 1:50:07 AM

If I understand your question correctly, you would like to construct a graph, perform inference, and then make some small changes and re-run it. (This is opposed to making small changes to the graph while it is running).

If that is the case, I think you can do this (although I haven't tried it) by simply creating a copy of the factor graph before you convert the factor graph into a GraphLab distributed graph with beliefprop::factorgraph:makebpgraph(...), then use factorgraph.hpp:priorforvar(...) (or beliefforvar(...)) to get a reference to the distribution, and then use densetable::setlogP(discreteassignment, val) method to modify values. Then you just run makebpgraph(...) again and kick it off like before.


User 334 | 10/6/2014, 2:27:59 AM

Thank you Scott!

It makes sense. I will try this and then come back with any further questions. I am afraid it might get slow due the fact I am gonna do those slight changes and inferences a lot of times.


User 334 | 10/13/2014, 11:44:22 AM

Hey I have one more question about the code.

I am using two classes to encapsulate a bayesian network, both use a factorgrapht internally. They are:

<pre class="CodeBlock"><code>template<sizet MAXDIM> class BayesianNetwork{ typedef graphlab::densetable<MAXDIM> densetablet; typedef graphlab::discretedomain<MAXDIM> domaint; typedef graphlab::discretevariable variablet; typedef beliefprop::factorgraph<MAXDIM> factorgrapht; factorgrapht fgraph; ...

void addvariable(std::vector<std::string>& values, std::string& variableid){ Variable<MAXDIM> var = new Variable<MAXDIM>(values, variableid, fgraph); variablet fvar = fgraph.addvariable(values.size(), variableid); var.setfgraphnodenum(fvar.id()); variables[variable_id] = &var; hasChanged = true; }; ... }</code></pre>

<pre class="CodeBlock"><code>template<sizet MAXDIM> class Variable{ ... Variable(std::vector<std::string>& values, std::string& variableid, typename BeliefNetwork<MAXDIM>::factorgrapht &fgraph): values(values), id(variableid), evidence(-1), factorgraph(&fgraph) {};

... }</code></pre>

The class Variable stores some information I need about the nodes. So it has a method "void addcpd(std::vector<double> values);" that creates a densetablet object and insert it into the factor graph. The problem arises when I try to create a variable in the BayesianNetwork class. It creates fine but when I try to access the factorgraph node later in the main() function it is just not in the memory (I believe the variable_t variable is deleted because I left the scope of the function who created the Variable object).

What do you suggest I can do to be able to use object oriented programming without losing the variables while I go from a function scope to another? (I can try to use the "new" constructor for my objects, but I am avoiding changing your code)

I hope I could explain my questions in an understandable way.

Long story short, I am having troubles when I am creating variablet objects inside a function in an object and then trying to use those variablet objects later in my main() function.

Thank you for your support :smile:


User 140 | 10/13/2014, 4:39:32 PM

You didn't provide the declaration for BayesianNetwork::variables, but I assume it is something like, <code class="CodeInline">std::vector<Variable<MAX_DIM>*> variables;</code>

Also, is <code class="CodeInline">Variable<MAXDIM> var = new Variable<MAXDIM>(values, variableid, fgraph);</code> a typo? Shouldn't it instead be <code class="CodeInline">Variable<MAXDIM> *var = new Variable<MAXDIM>(values, variableid, fgraph);</code> (note the *).

However, that leaves me wondering why you have <code class="CodeInline">variables[variable_id] = &var;</code> instead of <code class="CodeInline">variables[variable_id] = var;</code>

The variablet (aka discretevariable<>) returned (by value) from fgraph.addvariable(...) is really just a key to access the densetable stored by fgraph. (On a separate note, it might be better named discretedimension because it really just defines how many values the dimension spans (and provides it with an id).) Thus, while the variablet var that is returned by fgraph.addvariable(...) in BayesianNetwork:addvariable(...) will be destroyed when you return from that function, the underlying dense_table stored by fgraph will not be.

To actually get access to the variable created by factorgraph:addvariable(...), you can call factorgraph:priorforvariable(var) (or beliefforvariable) to get a reference to the underlying densetable_t that defines the prior/belief for the variable.

I would say you should store var by value using <code class="CodeInline">std::vector<Variable<MAX_DIM> > variables;</code> and <code class="CodeInline">variables[variableid] = var;</code> in BayesianNetwork:addvariable() and then reference the variable in your main() function with <code class="CodeInline">BayesianNetwork:fgraph:priorforvariable(BayesianNetwork:variables[i]))</code>

Let me know if that helps Scott


User 334 | 10/21/2014, 11:40:02 AM

Hi Scott,

thank you for your support. :smiley: You have being a really useful and nice dude. Indeed all things your pointed above were typos, I was away from my code when I wrote the example.

I hope this question is not too naive, but I think it is quick to answer. <i class="Italic">Once I add a factor over a domain to a factorgraph, how can I retrieve this variable to change its densetable?</i> I am asking that because I am storing much information in those factors and need to update it later.

Thank you once again for clarifying my way through the code and the GraphLab itself


User 140 | 10/21/2014, 2:39:20 PM

See the end of my previous post:

"To actually get access to the variable created by <code class="CodeInline">discretevariable var = factorgraph::addvariable(...)</code>, you can call <code class="CodeInline">factorgraph::priorforvariable(var)</code> (or beliefforvariable) to get a <i class="Italic">reference</i> to the underlying densetable<> that defines the prior/belief for the variable." Then use densetable<>::setlogP(discreteassignment, val) method to modify its values.


User 334 | 10/21/2014, 3:51:11 PM

Sorry,

I think I didn't explain myself clearly, when I say a factor I mean a factor created by <code class="CodeInline">factorgraph::addfactor(...)</code>, not a variable and its prior. Indeed I want to change its table.

I will give an example: <pre class="CodeBlock"><code>//... variablet c = fgraph.addvariable(nlabels, "c"); variablet r = fgraph.addvariable(nlabels, "r");

std::vector<double> logc(nlabels, 0.0); logc[0] = log(0.4); logc[1] = log(0.6);

std::vector<double> logr(nlabels*nlabels, 0.0); logr[0] = log(0.4); logr[2] = log(0.6); logr[1] = log(0.1); logr[3] = log(0.9);

densetablet cfact(c, logc); fgraph.addfactor(cfact, "cfact");

// Create a factor std::vector<variablet> args; // connect vertical neighbors args.pushback(c); args.pushback(r); // Build the factor densetablet cr(args, logr); // Bind the factor to the factor graph fgraph.addfactor(cr, "cr");

//more code here... </code></pre>

Ok, now, <i class="Italic">I want to change one of the double values in the table of the factor created by <code class="CodeInline">fgraph.add_factor(cr, "cr");</code>. Is there a way I can do that?</i>


User 140 | 10/22/2014, 4:46:27 PM

Ahh. Sorry. I see. Hmmm. That's actually not currently possible...

You could change factorgraph.hpp slightly to get access to the internal list of factors by changing the method declared at line 559 to public, i.e., <pre class="CodeBlock"><code>public: std::vector<vertexdatat>& factors() { return factors; }

private: </code></pre> And changing addfactor(...) to return id. You could then get a reference to the belief (or potential) distribution (table) backing a factor with <pre class="CodeBlock"><code>sizet id = fgraph.addfactor(...); std::vector<vertexdatat>& facts = fgraph.factors(); vertexdatat& vertex = facts[id]; // vertexdata<> is defined in bpvertexdata.h factortype& belief = vertex.belief; // or potential densetablet* table = dynamiccast<densetablet*>(belief.table()); assert(table != NULL); </code></pre> Part of the reason I didn't provide an easy way to get access to the factor was because indexing through them can be confusing. For what you're doing, this is probably the best way, <pre class="CodeBlock"><code>tmp[] = {2,1}; std::vector<sizet> subasg(&tmp[0], &tmp[1]); assignmentt asg(args, subasg); // args = [c,r] table->set_logP(val, asg); </code></pre>

Here, you are indexing into the second element of dimension c and the first element of dimension r).

Note, there is another constructor in discreteassignment.hpp, <code class="CodeInline">assignmentt(domaint, std::vector<sizet>)</code>, however this has different semantics. For completeness, I'll describe why this is.

The <code class="CodeInline">assignmentt(std::vector<variablet>, std::vector<sizet>)</code> constructor is really just a convenience constructor which creates a domain and then reorders subasg according to the order of the variables in the domain.

Internally, the ordering of the variables (dimensions) in a discretedomain, and hence, the order of sub-assignments in an assignment, are not defined by the order in which they were added to the domain (as you might expect), but the order in which they were created with factorgraph.add_variable(). For example, if you created c and then r, and then added them both to a domain in the reverse order, the domain would still index over c the fastest and then r. If, on the other hand, you created r and then c, the linear indexing of a domain that spans these two variables would be the transpose of the previous domain.

<code class="CodeInline">assignmentt(domaint, std::vector<size_t>)</code> expects the vector of sub-assignments are ordered according to the ordering of the variables internal to the domain (which, again, is the order in which they were created).

Thus, you either have to provide a list of variables which associates each sub-assignments in an assignment with a dimension, or you have to remember the order in which variables were created and construct your assignment over dimensions in the corresponding order. Neither is ideal, hence, why I didn't give direct access to the factors. There were performance reasons for doing this, however, it has led to several bugs.


User 334 | 10/23/2014, 1:34:57 AM

Thank you Scott,

I will test it as soon as I can and give you a feedback saying if it works or not :smiley:


User 334 | 1/21/2015, 11:31:03 AM

Hi Scott, How are you doing?

I am sorry if it's a silly question...

When I run <code class="CodeInline">mpiexec -n 2 ./testboolvar</code> I would expect to have unique outputs, no repetitions, but it seems that the code runs the same computations on both machines (I mean, wasting computation).

Am I doing something wrong? How am I supposed to use this to run distributed and have the least waste I can have?

Thank you once again,


User 6 | 1/21/2015, 4:36:43 PM

Hi Breno, It seems something is wrong with your MPI setup.

You can test your MPI setup as follows:

Compile the release/demoapps/rpc subfolder (using “cd release/demoapps/rpc/; make”). Copy the files generated by the compile to all machines. Run: mpiexec -n 2 --hostfile ~/machines /home/ubuntu/graphlab/release/demoapps/rpc/rpc_example1 As part of the output, you should see something like this:

TCP Communication layer constructed. TCP Communication layer constructed.

10 5 plus 1 is : 6 11 plus 1 is : 12 If you get something else, it means your MPI is not setup properly. Every machine should be able to ssh each other without password.


User 334 | 1/22/2015, 11:29:17 AM

Hi Danny,

Uhm I got it as part of my output. I am trying to run in only one machine for now (still using -n 2), so among other things I got this:

<pre class="CodeBlock"><code>INFO: dctcpcomm.cpp(connect:467): connection from 0 to 1 established. INFO: dc.cpp(init:571): TCP Communication layer constructed. INFO: dc.cpp(init:573): Cluster of 2 instances created. WARNING: dc.cpp(init:587): Duplicate IP address: 127.0.0.1 WARNING: dc.cpp(init:592): For maximum performance, GraphLab strongly prefers running just one process per machine.</code></pre>

As far I can see the MPI is working fine on my machine.


User 6 | 1/22/2015, 4:24:54 PM

This is expected. In PowerGraph, we recommend running a single MPI node on each machine. (This node has multiple cores)


User 334 | 2/12/2015, 11:40:05 AM

Hey guys,

Danny and Scott, thank you for your helpful replies. :)

Do you know if there is a way for me to initialize a variable in the <code class="CodeInline">vertex_program</code> and then use it in the <code class="CodeInline">apply</code> method of it?

<pre class="CodeBlock"><code>int main(int argc, char** argv){ graphlab::mpitools::init(argc, argv); graphlab::distributedcontrol dc; //... LearningCompleteDataEngine leng(data); leng.learn(distributedctrl, fgraph.getDGraph()); //... std::cout << "closing mpi" << std::endl; graphlab::mpi_tools::finalize(); std::cout << "mpi closed" << std::endl; }

class LearningCompleteDataEngine: public graphlab::ivertexprogram<GraphLabtype, Factor>{ private: DataSet dataset;

Factor& absorb_data(Factor& fact, DataSet& data){
    //...
    return fact;
}

public: LearningCompleteDataEngine(): dataset(DataSet()){}; LearningCompleteDataEngine(DataSet& data): dataset(data){};

void learn(graphlab::distributed_control& dist_ctrl, GraphLab_type& dgraph){
    std::cout << data_set;
    graphlab::omni_engine<Learning_Complete_Data_Engine> engine(dist_ctrl, dgraph, "sync");
    engine.signal_all();
    engine.start();
}

edge_dir_type gather_edges(icontext_type& context,
const vertex_type& vertex) const {
    return graphlab::ALL_EDGES;
}

Factor gather(icontext_type& context, const vertex_type& vertex,
edge_type& edge) const{
    //...
}

void apply(icontext_type& context, vertex_type& vertex,
const gather_type& total) {
    if(vertex.data().getType() == Vertice::FACTOR){
        //...
        fact = absorb_data(fact, data_set);
    }//...
}

//... }</code></pre>

<i class="Italic">When I run the learn() method it runs as I have given no data set (it creates an empty one) I would like to use the one I used in the construction of the vertex program. Is there any way to do it?</i>

What I mean is that, when I run the <code class="CodeInline">omniengine</code> I want it to use a stantiation of the <code class="CodeInline">vertexprogram</code> I wrote instead of initializing a new one, so I can use the variable <code class="CodeInline">data_set</code>.

I hope I am not too confusing...

Thank you for your time, Breno


User 334 | 2/12/2015, 12:52:56 PM

I think the last post is a bit confusing... In a nutshell, I want to read from a variable not defined in the <code class="CodeInline">apply</code> function. Do I have a way to do that?

Once again, thank you folks