Incremental thin junction trees for dynamic Bayesian networks

Abstract In this paper, we present Incremental Thin Junction Trees, a general framework for approximate inference in static and dynamic Bayesian Networks. This framework incrementally builds junction trees representing probability distributions over a dynamically changing set of variables. Variables and their conditional probability tables can be introduced into the junction tree Υ, they can be summed out of Υ and Υ can be approximated by splitting clusters for computational efficiency. As one of many possible applications of this general framework in dynamic Bayesian Networks, we automatically generate conditionally independent clusters for the prominent Boyen-Koller (BK) algorithm. Theoretical work by Boyen and Koller [BK99] showed that using conditionally independent clusters strongly improves BK's error bounds. We show how to identify these conditionally independent clusters automatically and that the theoretical results carry over to practice. We achieve a contract anytime algorithm which is superior to BK with marginally independent clusters