Mastering Probabilistic Graphical Models Using Python

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 ...