# Derivation of Bethe free energy in the context of graphical models

In some notes (link) titled

Stat 375 Inference in Graphical Models

Variational Methods: A Short Overview

Andrea Montanari

Lecture 6-7 - 2/2/2009

the following claim is made (bottom of pag. 8)

Claim 8. The Bethe free energy is the Lagrangian dual of the Gibbs free energy for the locally consistent marginals.

Then, a schematic proof is provided. However, I am confused about the notation and I am not sure how to fill the gaps to get the detailed proof. Let me be more specific.

The Gibbs free energy is defined as (see Eq. 1 in link)

$$G[b] = U[b] - H[b] \\$$

Here, $\underline{x} = (x_1,...,x_N)$ and $b(\underline{x})$ is a belief distribution. Moreover, $$U[b] = \sum_{\underline{x}} b(\underline{x}) \ln \Psi(\underline{x})$$ is the Gibbs energy, where and $\ln \Psi(\underline{x}) = E(\underline{x})$ is the energy of state $\underline{x}$, and $$H[b] = - \sum_{\underline{x}} b(\underline{x}) \ln b(\underline{x})$$ the Gibbs entropy.

If am not wrong, the Lagrangian dual for this Gibbs free energy (first equation in pag. 9 of link) imposing the conditions of local consistency for the marginals (defined in Eqs. 8 and 9 in link) is given by

$$\mathcal{L}(\{b\},\{\lambda\}) = G[b] + \sum_i \lambda_i \bigg( 1 - \sum_{x_i} b_i(x_i) \bigg) \\ + \sum_{ia} \sum_{x_i} \lambda_{ia}(x_i) \bigg( b_i(x_i) - \sum_{\underline{x}_{\partial a \backslash i}} b_a(\underline{x}_{\partial a}) \bigg)$$

Here, my first confusion arises. Is really $G[b]$ the Gibbs free energy in this last expression? Which $b$ should be inserted in such $G[b]$? I am asking these questions because if I assume that $b_i(x_i)$ and $b_a(\underline{x}_{\partial a})$ are just marginals of $b(\underline{x})$, then the last term of the Lagrangian---the one involving the Lagrange multipliers $\lambda_ia(x_i)$---becomes trivially zero. On the other hand, if I do not assume that $b_i(x_i)$ and $b_a(\underline{x}_{\partial a})$ are just marginals of $b(\underline{x})$, then, I am not sure how to write $G[b]$.

In summary, the overall idea seems to be to derive the Bethe free energy (see Eqs. in pag. 5 in link)

$$G_{Bethe}[b_i,b_a] = \sum_a \sum_{\underline{x}_{\partial a}} b_a(\underline{x}_{\partial a}) \ln \Psi_a(\underline{x}_{\partial a}) + \sum_a \sum_{\underline{x}_{\partial a}} b_a(\underline{x}_{\partial a}) \ln b_a(\underline{x}_{\partial a}) + \sum_i (1-|\partial i|) \sum_{x_i} b_i(x_i) \ln b_i(x_i)$$

from the Gibbs free energy by imposing the local conditions for the marginals. But, I am not sure how to do it.

• I am working on the solution but, it seems that the solution comes from plugging into the Gibbs energy of the Lagrangian, the expression for the belief that is obtained in graphical models without loops, i.e. Bethe's belief $b(\underline{x})=\prod_a b_a(\underline{x}_{\partial a}) \prod_i b_i(x_i)^{1-|\partial i|}$. Commented Dec 15, 2017 at 8:28
• It seems like everything is described in detail on pages 7 and 9. The Bethe free energy in the Lagrangian form is just a constrained optimization over $b$, which means one is optimizing over the possible probability distributions on $X$. Commented Jan 11, 2018 at 7:44
• To do this you need to constrain the parameters such that they permit a valid density. Equations 7-10 are just the constraints to be specified through the Lagrange multipliers such that the resulting function gives valid probabilities. They are: all events have nonnegative probability, all events sum to one, random variables can be consistently marginalized out, and all events in a factor node sum to unity. Commented Jan 11, 2018 at 7:45
• @RyanWarnick The question is about what to put in place of $G[b]$ in order to perform the constrained extremization of the Lagrangian. According to my calculations, if you put the exact definition of $G[b]$ evaluated at the belief distribution $b(x)=\prod_a b_a(\underline{x}_{\partial a})\prod_i b_i(x_i)^{1-|\partial i|}$, you reach an expression for the Lagrangian from where it is not possible to derive the Bethe free energy; at least not if the graphical model has loops. Commented Jan 11, 2018 at 11:22