BP on trees

[young-jun]

Hi,
first of all thanks for the great library.

I have a question regarding belief propagation on factor graphs that
represent a tree Bayes net.
I thought in that case two passes of messages up and down the tree
should be yet libdai is iterating a (moderate) number of times.
I checked already if I accidentally introduced cycles, which doesnt
seem to be the case, and compared to another implementation.
But I was still wondering if this is due to generic algorithm design
or if something might be wrong with the way I use the library?

Also out of curiosity, if I wanted to run BP on a forest by removing
the root node, can I just do that and get the same result as
specifying separate factor graphs for each of the subtrees?

Thanks,
Young-Jun

[Joris Mooij]

Dear Young-Jun,

On Mon, Feb 13, 2012 at 10:16:01AM -0800, young-jun wrote:
> I have a question regarding belief propagation on factor graphs that
> represent a tree Bayes net.
> I thought in that case two passes of messages up and down the tree
> should be yet libdai is iterating a (moderate) number of times.

That is because there's no automatic detection of trees built into the
BP code. Detecting the tree structure also takes time, so it's a tradeoff.
Currently the BP class does not have such functionality.

> I checked already if I accidentally introduced cycles, which doesnt
> seem to be the case, and compared to another implementation.
> But I was still wondering if this is due to generic algorithm design
> or if something might be wrong with the way I use the library?

No, this is simply because the code was designed that way and the
feature to do faster BP on trees hasn't been implemented (yet?).

> Also out of curiosity, if I wanted to run BP on a forest by removing
> the root node, can I just do that and get the same result as
> specifying separate factor graphs for each of the subtrees?

Yes, all algorithms in libDAI should support multiple components in
the factor graph.

Best, Joris

[kr...@kalish.net]

Young-Jun,

I might be months late here, but I thought it would be valuable to share what I've noticed in regard to using libDAI on trees and have it eternalized on the mailing list. I was having the same problem you were having. I'm constructing a factor graph in a careful fashion such that it is always a tree, but running BP on it was taking almost 40 seconds and a number of iterations (maybe 30 or so?).

I noticed I was using the following parameters to set up the BP algorithm:

std::string algOpts = "BP[inference=MAXPROD,updates=SEQRND,maxiter=1,tol=1e-9,logdomain=1]";

However if I change the update order to SEQMAX, I get convergence in 3 iterations every time with a tree factor graph:

std::string algOpts = "BP[inference=MAXPROD,updates=SEQMAX,maxiter=1,tol=1e-9,logdomain=1]";

It now only takes about 6 seconds to construct the inference algorithm and run it to convergence, a significant improvement. I'm not even sure if implementing the exact algorithm would be significantly faster. I would be curious to see what Dr. Joris Mooij thinks about the performance difference.

-Kris

[Joris Mooij]

Hi Kris & Young-Jun,

I think the best solution would be to add a updates=TREE feature to BP. This
then will first investigate whether the factor graph is a tree, and calculate
the structure of this tree, and then run BP with the minimum number of required
updates on the tree.

Then, you only pay the time for detecting the tree structure, which should be
cheaper in general than running BP updates (even if you use SEQMAX).

Best, Joris

> --
> You received this message because you are subscribed to the Google Groups
> "libDAI" group.
> To unsubscribe from this group and stop receiving emails from it, send an email
> to libdai+un...@googlegroups.com.
> To post to this group, send email to lib...@googlegroups.com.
> Visit this group at http://groups.google.com/group/libdai.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>