  The computational complexity of inference -- required to compute the
partition function, $Z$, of an Ising model over a graph of $N$''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 $\lambda$-fractional
interpolation, $Z^{(\lambda)}$, where $\lambda=0$ and $\lambda=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)} \geq Z^{(\lambda)} \geq Z^{(BP)}$, and there
exists a unique (``exact") $\lambda_*$ such that $Z=Z^{(\lambda_*)}$.
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
\lambda:\ Z=Z^{(\lambda)}{\tilde Z}^{(\lambda)}$, where the multiplicative
correction, ${\tilde Z}^{(\lambda)}$, 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. The
empirical study yields a number of interesting observations, such as the
ability to estimate ${\tilde Z}^{(\lambda)}$ with $O(N^{2::4})$ fractional
samples and suppression of $\lambda_*$ fluctuations with an increase in $N$ for
instances from a particular random Ising ensemble. We also verify and discuss
the applicability of this approach to the problem of image de-noising.
