Statistics – Machine Learning
Scientific paper
2010-07-04
Statistics
Machine Learning
29 pages. Correction to version 1
Scientific paper
We introduce block-tree graphs as a framework for deriving efficient algorithms on graphical models. We define block-tree graphs as a tree-structured graph where each node is a cluster of nodes such that the clusters in the graph are disjoint. This differs from junction-trees, where two clusters connected by an edge always have at least one common node. When compared to junction-trees, we show that constructing block-tree graphs is faster, and finding optimal block-tree graphs has a much smaller search space. Applying our block-tree graph framework to graphical models, we show that, for some graphs, e.g., grid graphs, using block-tree graphs for inference is computationally more efficient than using junction-trees. For graphical models with boundary conditions, the block-tree graph framework transforms the boundary valued problem into an initial value problem. For Gaussian graphical models, the block-tree graph framework leads to a linear state-space representation. Since exact inference in graphical models can be computationally intractable, we propose to use spanning block-trees to derive approximate inference algorithms. Experimental results show the improved performance in using spanning block-trees versus using spanning trees for approximate estimation over Gaussian graphical models.
Moura Jose M. F.
Vats Divyanshu
No associations
LandOfFree
Graphical Models as Block-Tree Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Graphical Models as Block-Tree Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graphical Models as Block-Tree Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-443030