Extended Version of “ Expectation propagation for approximate inference in dynamic Bayesian networks ”
We consider inference in general dynamic Bayesian networks. We are especially interested in models in which exact inference becomes intractable, as, for example, in switching linear dynamical systems. We introduce expectation propagation as a straightforward extension of Pearl’s exact belief propagation. Expectation propagation, is a greedy algorithm, converges in many practical cases, but not always. Our goal is therefore to derive a message propagation scheme that can be guaranteed to converge. Following Minka, we therefore first derive a Bethe-free energy like functional, the fixed points of which correspond to fixed points of expectation propagation. We turn this primal objective into a dual objective in terms of messages or Lagrange multipliers. Approximate inference boils down to a saddle-point problem: maximization with respect to the difference between forward and backward messages, minimization with respect to the sum of the forward and backward messages. We derive several variants, ranging from a double-loop algorithm that guarantees convergence to the saddle point to a damped version of “standard” expectation propagation. We discuss implications for approximate inference in general, treestructured or even loopy, Bayesian networks. This technical report formed the basis of [12]: @inproceedings{Heskes_Zoeter_UAI2002, AUTHOR = "Heskes, T. and Zoeter, O.", YEAR = 2002, TITLE = "Expectation propagation for approximate inference in dynamic {B}ayesian networks", BOOKTITLE = "Proceedings UAI-2002", EDITOR = "Darwiche, A. and Friedman, N.", PAGES = "216--233", URL = "ftp://ftp.snn.kun.nl/pub/snn/pub/reports/Heskes.uai2002.ps.gz"} It is, however, not fully compatible. I tried to update it backwardly, but may not have completely succeeded. If possible, please refer to the published proceedings paper.