Heuristics for Automatically Decomposing a Stochastic Process for Factored Inference

Abstract

Dynamic Bayesian networks are factored representations of stochastic processes. Despite their factoredness, exact inference in DBNs is generally intractable. One approach to approximate inference involves factoring the variables in the process into components. In this paper we study efficient methods for automatically decomposing a DBN into weakly-interacting components so as to minimize the error in inference entailed by treating them as independent. We investigate heuristics based on two views of weak interaction: mutual information and the degree of separability ([Pf01] and [Pf06]). It turns out, however, that measuring the degree of separability exactly is probably intractable. We present a method for estimating the degree of separability that includes a mechanism for trading off efficiency and accuracy. We use the aforementioned heuristics in two clustering frameworks to find weakly-interacting components, and we give an empirical comparison of the results in terms of the error encountered in the belief state across the whole system, as well as that in the belief states across single components.