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.
['Thomas Geier', 'Felix Richter', 'Susanne Biundo']
Conditioned belief propagation revisited