In the earlier section, we discussed a variant of belief propagation where we relaxed the constraint of having a clique tree, and did belief propagation on a cluster graph. In this section, we will take a different approach. Instead of relaxing on the structure, we will be approximating the messages passed between the clusters. Although this approach can be extended to work with cluster graphs as well, the scope of this book is only limited to clique trees.

Let's consider a simple pairwise Markov model, as shown in Fig 4.9. As discussed in the previous section, a pairwise Markov model is simply a Markov model with the factors associated with each edge , along with the univariate factors corresponding to each random variable . Thus, the following model will have factors such as , , and along with , , , and so on. Let's also assume that each random variable present in this network is binary.

Fig 4.9: Markov model represented by 3 x 3 grid network

A cluster...