UWEE Tech Report Series

On Triangulating Dynamic Graphical Models


UWEETR-2003-0007

Author(s):
Jeff Bilmes, Chris Bartels

Keywords:
graphical models, triangulation, dynamic graphical models, bayesian networks, dynamic bayesian networks, DBNs, elimination, slice-by-slice elimination, inference, interface, hidden Markov models, HMMs, the Graphical Models Toolkit, GMTK, DBN inference, DBN triangulation, triangulated DBNs, forward backward algorithm

Abstract

This paper introduces improved methodology to triangulate dynamic graphical models and dynamic Bayesian networks (DBNs). In this approach, a standard DBN template can be modified so the repeating and unrolled graph section may dissect the original DBN time slice and may also span (and partially intersect) many such slices. We introduce the notion of a ``boundary'' which divides a graph into multi-slice partitions each of which has an interface, and define the ``boundary algorithm'', a method to find the best boundary (and corresponding interface) between partitions in such models. We prove that, after using this algorithm, the sizes of the best forward- and backward- interface (and also the corresponding fill-ins) are identical. The boundary algorithm allows for constrained elimination orders (and therefore graph triangulations) that are impossible using standard slice-by-slice constrained elimination. We describe the above using the Graphical Model ToolKit (GMTK)'s notion of dynamic graphical model, slightly generalizing standard DBN templates. We report triangulation results on hand-concocted graphs, novel speech recognition DBNs, and random graphs, and find that the boundary algorithm can significantly improve both tree width and graph weight.

This paper also appeared at the Uncertainty in Artificial Intelligence UAI'2003 conference. A copy of that paper can be found here.

Download the PDF version

Download the Gzipped Postscript version