0
$\begingroup$

I am wondering why some methods transform the underlying DAG-based graphical model (Bayesian Networks for example) to a joint tree$^1$? What are the advantages?

I believe it's for computational purposes. If that's the case under what circumstances it is not recommended to transform the underlying DAG to jointtrees?

Speaking about graphical models in general (whether they are probabilistic or not), is there some guidelines when to transform them i.e. decompose them?

$^1$ Also known as jointree, junction tree, tree decomposition.

Improve this question
$\endgroup$
1
$\begingroup$

My only background on this subject is a course I took as a grad student, so take my answer with a grain of salt:

The reason that some methods transform the DAG to a tree because some algorithms work on trees but do not work on graphs with cycles. For example, belief propogation is guaranteed to converge on a tree after every node received two messages. On general graphs, on the other hand, no general convergence theorem is known, and we know that convergence occurs only in some special cases. Intuitively, the reason is that on a general graph, a message that goes through a cycle can loop in it indefinitely, each time changing the information stored at the nodes.

Regarding under what circumstances it is recommended to transform the graph into a tree: In the process of transforming the graph into a tree, every node of the new tree is identified with a set of nodes of the original graph. The size of the maximal set with which a node is identified (in the best decomposition) is called the tree-width of the graph. Now, the complexity of belief propagation, as well as other algorithms, is exponential in the tree-width, so you want to transform the graph to a tree only if the tree-width is sufficiently small.

Unfortuantely, it is $NP$-complete to compute the tree-width of a graph exactly, but there are some approximation algorithms. You can read more about it in Shiva Kintali's blog: http://kintali.wordpress.com/2010/01/28/approximating-treewidth/

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Question specifically stated the underlying graph is DAG not general graph. So loops are not important here. But in your answer you totally ignored original part of question. Your answer is not wrong but it's not an answer (or attempt to answer) for this question. $\endgroup$ – Saeed Dec 28 '13 at 13:02
  • 1
    $\begingroup$ Also joint trees are not a real tree to prevent any loop . Its just tree decomposition of graph and may have many loops in bags in general. $\endgroup$ – Saeed Dec 28 '13 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.