Loopy Belief Propagation in the Presence of Determinism

It is well known that loopy Belief propagation (LBP) performs poorly on probabilistic graphi-cal models (PGMs) with determinism. In this pa-per, we propose a new method for remedying this problem. The key idea in our method is finding a reparameterization of the graphical model such that LBP, when run on the reparameterization, is likely to have better convergence properties than LBP on the original graphical model. We pro-pose several schemes for finding such reparam-eterizations, all of which leverage unique prop-erties of zeros as well as research on LBP con-vergence done over the last decade. Our exper-imental evaluation on a variety of PGMs clearly demonstrates the promise of our method – it of-ten yields accuracy and convergence time im-provements of an order of magnitude or more over LBP.