Let's start with a little recap of exact inference. Assume that we have a factorized distribution in the following form:

Here, Z is the partition function, are the factors in the network, and is the scope of the factor . In the case of exact inference, we computed and then answered queries over this distribution.

In the case of belief propagation, the end result of running the algorithm was a set of beliefs on the clusters and sepsets. This set of beliefs was able to represent the joint distribution . So, in the case of exact inference, we tried to find a set of calibrated beliefs that was able to represent our joint distribution exactly. For approximate algorithms, we will try to select the set of beliefs from all the sets of beliefs that conform to the cluster tree and are best able to represent our original distribution .

So now the question is, how do we compare the similarity between these two distributions? There are many methods that we can use to compute...