|
Can we build a junction tree for any given Graphical model (directed, undirected) ? I am using the following line of reasoning to answer this: Thanks in advance |
|
Yes, it is possible to build a junction tree for every graphical model. However, in general the size each node of this junction tree is exponential in the size of the original graph, which makes it impractical to run belief propagation on it. |
|
hi There has to something wrong in the reasoning i presented above. (that one can construct a Junction tree for every graphical model) If we can get a Junction Tree for any graphical model then why do we need approx inference technique like loopy BP, Var inference etc Kindly clarify Is this because for many graphical models the complexity of inference on their respective Junction Tree could be prohibitively very high (because of their large tree-width) thus necessitating the need for approximate inference ?
(Apr 07 '13 at 05:15)
turbo364
There is always a trivial triangulation: a fully connected graph. This yeilds a trivial jointree with a single cluster containing all variables. This is as bad as explicitly representing a full joint distribution table. In general, the complexity of the jointree algorithm is exponential in the largest cluster. As you said, one problem is finding a jointree whose largest cluster is bounded, but one may not exist.
(Apr 11 '13 at 04:23)
arthur
|
|
Yes, also known as "Tree Decomposition" in algorithms literature. |
