Explaining Iterative Belief Propagation
Adnan Darwiche
UCLA

Abstract:

Iterative belief propagation (IBP) has been an influential method for
approximate inference in probabilistic graphical models, perhaps the
most influential method of the last decade. Given its wide-spread
applicability in various domains, there has been a great interest in
developing semantics for this method to both characterize and control
the quality of its approximations. We present in this talk a recent
semantics for IBP, formalizing it as a method of exact inference on a
simplified model that has been obtained by deleting edges from the
original. IBP approximations, as well as the Bethe free energy
approximation, arise in the degenerate case where every model edge has
been deleted. We can thus find improved BP and free energy
approximations by recovering edges into the fully-disconnected
model. This edge deletion semantics characterizes IBP in both directed
and undirected models. Moreover, for the directed case, we show how
one can recover edges efficiently and effectively using the notion of
soft d-seperation that we introduced recently.

Joint work with Arthur Choi.


Bio:

Adnan Darwiche is a professor and vice chair of the computer science
department at UCLA. He obtained his M.S. and Ph.D. degrees in computer
science at Stanford university in 1989 and 1993,
respectively. Professor Darwiche's research interests are in symbolic
and probabilistic reasoning and their applications to real-world
problems. He directs the automated reasoning group at UCLA, which is
responsible for releasing some high profile reasoning systems,
including the Rsat satisfiability solver (first place in the SAT'07
competition), the SamIam system for modeling and reasoning with
Bayesian networks, and the c2d knowledge compiler (see
http://reasoning.cs.ucla.edu/). Professor Darwiche is the Associate
Editor-in-Chief for the Journal of Artificial Intelligence Research
(JAIR) and a AAAI fellow.