What is Loopy Belief Propagation?

Belief propagation is an algorithm for efficiently calculating the probability of a variable in a graphical model given some evidence. This requires marginalizing out all the other variables in the graph. The naive approach to marginalization would lead to an algorithm that is exponential in the size of the graph. Belief propagation is a method which relies on "message passing" to store intermediate sums in the marginalization and can therefore calculate the probability of a variable in time linear in the size of the graph.

Unfortunately, this only leads to exact solutions when the structure of the graph is a tree. If there are loops in the graph then belief propagation becomes "Loopy Belief Propagation." In this case the messages don't have a clear path out and back from the query variable and can be passed in loops. In this case the best one can hope for is that the probability of the query variable converges after lots of message passing. Loopy belief propagation is therefore an approximate solution to a query on a graphical model.