Tuesday, November 30, 2010

Visualizing Tree Decompositions

In order to do exact probabilistic inference on real life network efficiently, one must find a good Tree Decomposition of the network. This process is known as the Junction Tree algorithm. It's a bit hard to visualize the result, but while browsing tree decomposition graph pages on Wikipedia, I got an idea. Instead of bags with variables, we plot it as a collection of colored strips where each strip corresponds to a variable and Running Intersection property guarantees there will be no breaks.

Here's the result for the width-7 tree decomposition of the moralized Barley network

Mathematica source


Danny Tarlow said...

Very cool. I like it.

Yaroslav said...

Thanks! I do wonder when the tree decomposition captures the difficulty of exact solution...what kind of problems can your combinatorial MAP approach solve?