3
$\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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

The key differences in the implementation of the algorithm / in the passing of the messages are as follows:

  • messages in BP are passed only once; in contrast, messages in loopy BP (LBP) are passed iteratively until "convergence is reached" (convergence means that the belief does not change anymore from one iteration to the other).
  • in a Bayesian Network, messages in BP are passed from "leaves" to "roots", i.e. upwards in the Bayesian Network; in contrast, messages in LBP don't need to be passed in a particular order.

Other than that, the equations to calculate the belief and the messages are completely identical.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I was looking for some answers to the same question, lucky to see this post. Can you provide any links to numerical examples of belief propagation and loopy belief propagation? $\endgroup$
    – oceanus
    Aug 31, 2021 at 13:51
  • $\begingroup$ I describe LBP and BP in one of my papers, which also comes with an R implementation: arxiv.org/pdf/2112.09217.pdf $\endgroup$
    – Fritz
    Jan 22, 2022 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.