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

5 comments:

Danny Tarlow said...

Very cool. I like it.

Yaroslav Bulatov 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?

remo said...

THANKS FOR THE INFORMATION...
<a href="http://www.chloros.in/digital-marketing-internship.htmlhttp://www.chloros.in/digital-marketing-internship.html>Digital Marketing Internship Program in Bangalore</a>

draj said...



Excellent machine learning blog,thanks for sharing...
Seo Internship in Bangalore
Smo Internship in Bangalore
Digital Marketing Internship Program in Bangalore

john said...
This comment has been removed by a blog administrator.