Junction tree algorithm for DBN

A naïve approach to do inference on dynamic Bayesian network (DBN) is to unroll DBN for desired number of timesteps and treat it as a static BN. The problems with this are

• Typically the number of timesteps are unknown, and one may use a time window with a fixed length or do some kind of segmentation.
• Space requirement is high
• Dynamic filtering requires rebuilding the entire time history of the process on every timestep. (?)

Understanding the 2TBN (2 time-slice Bayes net) junction tree algorithm implementation

First of all, a junction tree is a clique tree that satisfies the junction tree property. A clique tree comes from the definition of a clique graph. A clique graph of G is a graph where the set of nodes is precisely the set of maximal cliques in G. And if the clique graph is also a tree, it is a clique tree. The junction tree property means that all the maximal cliques containing the same node v must form a connected subtree.

This is one of the algorithm in Kevin Murphy's Bayesian Network Toolbox. The file name is jtree_2TBN_inf_engine.m.

In the constructor of jtree_2TBN_inf_engine, it creates two jtree_engines. It creates one engine just for slice 1. And another engine for 1.5 slice. The 0.5 slice means the interface nodes from the previous slice. Interface nodes are nodes with children in the next slice. In the case of one-level AHMM, the interface nodes include \(G_t, S_t, F_t^G\). So in this case, the interface algorithm (Murphy, 2002) is the same as the frontier algorithm (Zweig, 1996). In the frontier algorithm, the frontier is the full set of hidden nodes.  It also always makes the interface nodes a clique.

One-level AHMM

Resources: http://ttic.uchicago.edu/~kgimpel/papers/jt-dbn.pdf