How to compute the Gibbs free energy in Bethe approximation for MRF

Question

Hi, I am learning loopy belief propagation for MRF. The general roadmap is to define a Bethe approximation, which is exact for a tree but wrong for general graphs.

I'm currently stuck at the point to compute the Bethe entropy. Let's consider a pairwise tree in here (p. 21).

where $b(\cdot)$ is a belief (marginal distribution) of either a factor or a node.

The entropy is then computed as if it's a sum of the entropy of independent variables. However, $X_a$ overlaps with each other, and $X_a$ actually contains $x_i$ for some $i$. I don't know how this entropy is decomposed.

$$\begin{align} H_b=&-\sum_x\left(\prod_ab_a(X_a)\prod_ib_i(X_i)^{1-d_i}\right)\log\left(\prod_ab_a(X_a)\prod_ib_i(X_i)^{1-d_i}\right)\\ =&-\sum_x\left(\prod_ab_a(X_a)\prod_ib_i(X_i)^{1-d_i}\right)\left(\sum_a\log b_a(X_a)+\sum_i\log b_i(X_i)^{1-d_i}\right) \end{align}$$

Let's consider a particular term in the second parathesis associating with $X_{a^*}$:

$$-\sum_x \left(\prod\limits_a b_a(X_a)\cdot\prod_i b_i(X_i)^{1-d_i} \cdot \log b_{a^*}(X_{a^*})\right)$$

We cannot simply remove unnecessary factors in this term by rearranging the outer summation over $\{x_{a^*}\} \bigcup \mathcal{X}\backslash x_{a^*}$, because $X_a$ and $X_i$ are interwoven with each other.

I referred to Koller's book, and this part is also missing.

I am wondering if any one can point to the derivation of Bethe entropy. Thanks a lot.

Answer 1

I find out one way to simplify the equation:

$$\begin{align} H_b &= -\mathbb{E}_b\left[\log\prod_a b_a(X_a)\prod_i b_i(X_i)^{1-d_i}\right]\\ &=-\mathbb{E}_b\left[\sum_a\log b_a(X_a)+(1-d_i)\sum_i\log b_i(X_i)\right]\\ &=-\sum_a\mathbb{E}_b\left[\log b_a(X_a)\right] +\sum_i(d_i-1)\mathbb{E}_b\left[\log b_i(X_i)\right]\\ &=-\sum_a\sum_{x_a} b_a(x_a) \log b_a(x_a)+\sum_i(d_i-1)\sum_{x_i}b_i(x_i)\log(x_i) \end{align} $$ The last step is simply because we happen to know the beliefs (marginal probabilities) of $x_a$ and $x_i$ which are $b_a(x_a)$ and $b_i(x_i)$, respectively.

In other words, if we see $p=\prod_i \phi_a(X_a)$, where $\phi_a$ is a factor defined on overlapping variables, the entropy $H\ne\sum_a H_a$ in general. Here, $\phi_a$ happens to be defined on beliefs, and thus something like summation over independent variables holds.

It would be appreciated much if anyone can tell whether my understanding is correct. Thanks.