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

Code

• github.com/hamidrezabehjoo/fractional-trw
  OfficialIn papernone★ 0

Abstract

Computing 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 -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 (exact) _* such that Z=Z^(_*). Generalizing the re-parametrization approach of wainwright_tree-based_2002 and the loop series approach of chertkov_loop_2006, we show how to express Z as a product, :\ Z=Z^() Z^(), where the multiplicative correction, 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 Z^() with O(N^2::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.

Reproductions