Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms

Abstract

Computing the partition function, $Z$, of an Ising model over a graph of $N$ \enquote{spins} is most likely exponential in $N$. Efficient variational methods, such as Belief Propagation (BP) and Tree Re-Weighted (TRW) algorithms, compute $Z$ approximately by minimizing the respective (BP- or TRW-) free energy. We generalize the variational scheme by building a $\hat{I}»$-fractional interpolation, $Z^{(\hat{I}»)}$, where $\hat{I}»=0$ and $\hat{I}»=1$ correspond to TRW- and BP-approximations, respectively. This fractional scheme -- coined Fractional Belief Propagation (FBP) -- guarantees that in the attractive (ferromagnetic) case $Z^{(TRW)}\ge Z^{(\hat{I}»)}\ge Z^{(BP)}$, and there exists a unique (\enquote{exact}) $\hat{I}{»}_{\ast }$ such that $Z=Z^{(\hat{I}{»}_{\ast })}$. Generalizing the re-parametrization approach of \citep{wainwright_tree-based_2002} and the loop series approach of \citep{chertkov_loop_2006}, we show how to express $Z$ as a product, $\forall \hat{I}»:Z=Z^{(\hat{I}»)}{\tilde{Z}}^{(\hat{I}»)}$, where the multiplicative correction, ${\tilde{Z}}^{(\hat{I}»)}$, is an expectation over a node-independent probability distribution built from node-wise fractional marginals. Our theoretical analysis is complemented by extensive experiments with models from Ising ensembles over planar and random graphs of medium and large sizes. Our empirical study yields a number of interesting observations, such as the ability to estimate ${\tilde{Z}}^{(\hat{I}»)}$ with $O(N^{2::4})$ fractional samples and suppression of variation in $\hat{I}{»}_{\ast }$ estimates with an increase in $N$ for instances from a particular random Ising ensemble, where $[2::4]$ indicates a range from $2$ to $4$. We also discuss the applicability of this approach to the problem of image de-noising.