On Triangulating Dynamic Graphical Models
  This paper introduces new methodology to triangulate dynamic Bayesian
networks (DBNs) and dynamic graphical models (DGMs). While most methods to
triangulate such networks use some form of constrained elimination scheme based
on properties of the underlying directed graph, we find it useful to view
triangulation and elimination using properties only of the resulting undirected
graph, obtained after the moralization step. We first briefly introduce the
Graphical model toolkit (GMTK) and its notion of dynamic graphical models, one
that slightly extends the standard notion of a DBN. We next introduce the
'boundary algorithm', a method to find the best boundary between partitions in
a dynamic model. We find that using this algorithm, the notions of forward- and
backward-interface become moot - namely, the size and fill-in of the best
forward- and backward- interface are identical. Moreover, we observe that
finding a good partition boundary allows for constrained elimination orders
(and therefore graph triangulations) that are not possible using standard
slice-by-slice constrained eliminations. More interestingly, with certain
boundaries it is possible to obtain constrained elimination schemes that lie
outside the space of possible triangulations using only unconstrained
elimination. Lastly, we report triangulation results on invented graphs,
standard DBNs from the literature, novel DBNs used in speech recognition
research systems, and also random graphs. Using a number of different
triangulation quality measures (max clique size, state-space, etc.), we find
that with our boundary algorithm the triangulation quality can dramatically
improve.
