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

View a PDF of the paper titled Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms, by Hamidreza Behjoo and 1 other authors

View PDF
HTML (experimental)

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 $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 (enquote{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. Our 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 variation in $lambda_*$ 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.