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

Computing the partition function, Z, of an Ising model over a graph of N enquotespins 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 λ-fractional interpolation, Z(λ), where λ=0 and λ=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) ≥ Z(λ) ≥ Z(BP), and there exists a unique (enquoteexact) λ_* such that Z=Z(λ_*). Generalizing the re-parametrization approach of citepwainwrighttree-based2002 and the loop series approach of citepchertkovloop2006, we show how to express Z as a product, forall λ: Z=Z(λ)tilde Z(λ), where the multiplicative correction, tilde Z(λ), 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(λ) with O(N2::4) fractional samples and suppression of variation in λ_* 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.