University of Washington - Department of Electrical Engineering
Exact probabilistic inference for graphical models is known to be NP-hard. For dense graph with many cycles, one has to resort to tractable approximate methods such as loopy belief propagation. It has been shown that loopy BP is equivalent to the minimization of the so-called Bethe free energy in variational methods. First a review of some recently developed approximate algorithms in this context will be given. Then we will present some theory about the Bethe region graph and a convex relaxation method for energy minimization. We also give some analysis of the method's convergence properties. Finally we will introduce a general parallel and distributed framework for inference algorithms. We will show how the synchronization cost can be minimized at the algorithmic level.