In the previous section, we discussed the MAP variable elimination algorithm. In the same way that we extended the sum-product variable elimination algorithm for the clique tree and ended up on the belief propagation algorithm, we can perform MAP using the belief propagation. In cases where variable elimination can be computationally intractable, belief propagation has a clear advantage.

The procedure for belief propagation remains the same as discussed in the case of the sum-product. The only thing that changes is the message that is passed between the two clusters and . Earlier, we used to compute messages from to , that is , as follows:

However, now, instead of summing out the variables , we will maximize with respect to them. Thus, the message in the case of MAP belief propagation can be formulated as follows:

When both, the upward pass and the downward pass of the messages are complete, all the adjacent clusters of the tree are said to be max-calibrated....