Efficient Bayesian Inference for Dynamically Changing Graphs

Motivated by stochastic systems in which observed evidence and conditional de- pendencies between states of the network change over time, and certain quantities of interest (marginal distributions, likelihood estimates etc. ) must be updated, we study the problem of adaptive inference in tree-structured Bayesian networks. We describe an algorithm for adaptive inference that handles a broad range of changes to the network and is able to maintain marginal distributions, MAP estimates, and data likelihoods in all expected logarithmic time. We give an implementation of our algorithm and provide experiments that show that the algorithm can yield up to two orders of magnitude speedups on answering queries and responding to dy- namic changes over the sum-product algorithm.

Authors

• Ozgur Sumer University of Chicago
• Umut Acar Max-Planck Institute for Software Systems
• Alexander Ihler UC Irvine
• Ramgopal Mettu University of Massachusetts - Amherst

Keywords

No keywords are indexed for this paper.