Belief Propagation (BP) applied to cyclic problems is a well known approximate inference scheme for probabilistic graphical models. To improve the accuracy of BP, a divide-and-conquer approach termed Conditioned Belief Propagation (CBP) has been proposed in the literature. It recursively splits a problem by conditioning on variables, applies BP to subproblems, and merges the results to produce an answer to the original problem. In this essay, we propose a reformulated version of CBP that exhibits anytime behavior, and allows for more specific tuning by formalizing a further decision point that decides which subproblem is to be decomposed next. We propose some simple and easy to compute heuristics, and demonstrate their performance using an empirical evaluation on randomly generated problems.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 email@example.com
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 firstname.lastname@example.org