2
$\begingroup$

Belief propagation (BP) is an algorithm (or a family of algorithms) that can be used to perform inference on graphical models (e.g. a Bayesian network). BP can produce exact results on cycle-free graphs (or trees). BP is a message passing algorithm: messages are iteratively passed between nodes of the graph (or tree). The marginal probability of a random variable (or node) is then estimated from these messages.

In the case the graph contains loops (or cycles), the algorithm is called loopy belief propagation and it is not an exact inference algorithm (that is, it doesn't produce exact results).

What is the difference between belief propagation and loopy belief propagation, in terms of operations that they perform in order e.g. to find the marginal probability of a random variable? How do BP and loopy BP differ?

$\endgroup$
2
$\begingroup$

The main difference I think isn't so much in terms of how BP operates vs How Loopy BP operates (although there are small differences). It is in the fact that once the graphs start having cycles, the complexity of the problem being solved jumps from the class P (considered easy to solve form a computational point of view) to the class NP (considered hard to solve - see the P vs. NP problem for further details). That's why Loopy BP isn't an exact inference algorithm: Finding an exact solution is very difficult (can take exponential time).

You might want to check out Generalized Belief Propagation and Survey Propagation which also address graphs with cycles.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Yes, I had also read about this. However, I was more interested in an answer that explain the BP algorithm (in detail, if possible) and how it is different from loopy BP (in terms of operations). For example, I don't understand the meaning of a "message" in this context, given that these are probabilities graphical models. $\endgroup$ – nbro May 12 '19 at 20:28

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.