7
$\begingroup$

It is known that belief propagation gives exact result on trees, are there interesting examples when Generalized Belief Propagation is exact? (edit junction tree is not interesting because it is exactly solvable without GBP)

On the surface, Belief Propagation passes messages between cliques and separators, whereas GBP allows more general region hierarchy. That helps with convergence rate, but I wonder if this also extends the class of exactly solvable inference problems.

Edit: as Thomas Minka points out, junction tree algorithm can be viewed as a version of generalized belief propagation. But it can also be viewed as a version of (cluster)belief propagation. What I'm wondering specifically is if GBP can give exact solution for any problem for which BP can't. The motivation is that with exact solution GBP gives result in a finite number of steps and you can view the result as a kind of algebraic factorization of the problem, in the spirit of Generalized Distributive Law paper

$\endgroup$
6
$\begingroup$

GBP includes the junction tree algorithm as a special case, and since junction tree is exact, GBP will be exact whenever the region graph corresponds to a junction tree. This is the only general case where GBP is exact, as shown by Theorem 14 of Pakzad and Anantharam (Neural Computation, 2005).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.