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

enter image description here

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.

enter image description here

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


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.