Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms
This work addresses a fundamental challenge in statistical physics and machine learning for researchers and practitioners dealing with probabilistic graphical models, though it is incremental as it builds upon existing variational methods.
The paper tackles the problem of computing the partition function of Ising models, which is computationally hard, by introducing Fractional Belief Propagation (FBP), a method that interpolates between existing approximations to find an exact solution. The result includes theoretical guarantees for attractive cases and empirical observations, such as estimating corrections with O(N^{2::4}) samples and reduced variation in parameter estimates for large graphs.
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 $λ$-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)} \geq Z^{(λ)} \geq Z^{(BP)}$, and there exists a unique (\enquote{exact}) $λ_*$ such that $Z=Z^{(λ_*)}$. 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 λ:\ 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(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.