A comparison of variable elimination and belief propagation
In the previous sections, we saw that both belief propagation and variable elimination are inter-related. Belief propagation is an extension of the variable elimination algorithm on clique trees. So, one might think that they would have the same computational complexity. However, in reality, belief propagation has some advantages over variable elimination.
The major advantage is the ability to query over multiple variables of a model with a single computation (that is, calibration of the clique tree). Once the tree is calibrated, we could query about multiple variables without performing any further computation. However, in the case of variable elimination, we have to run the algorithm more than once. Thus, if we have such a problem, in which we need to query the model multiple times, we should definitely use belief propagation.
On the flipside, belief propagation also has a disadvantage over variable elimination. Clique trees are...
