Running summarizing tools on a new article

Abstract: Inference efforts -- required to compute partition function, $Z$, of an Ising model over a graph of $N$ ``spins" -- are most likely exponential in $N$. Efficient variational methods, such as Belief Propagation (BP) and Tree Re-Weighted (TRW) algorithms, compute $Z$ approximately minimizing respective (BP- or TRW-) free energy. We generalize the variational scheme building a $λ$-fractional-homotopy, $Z^{(λ)}$, where $λ=0$ and $λ=1$ correspond to TRW- and BP-approximations, respectively, and $Z^{(λ)}$ decreases with $λ$ monotonically. Moreover, this fractional scheme guarantees that in the attractive (ferromagnetic) case $Z^{(TRW)}\geq Z^{(λ)}\geq Z^{(BP)}$, and there exists a unique (``exact") $λ_*$ such that, $Z=Z^{(λ_*)}$. Generalizing the re-parametrization approach of \cite{wainwright_tree-based_2002} and the loop series approach of \cite{chertkov_loop_2006}, we show how to express $Z$ as a product, $\forall λ:\ Z=Z^{(λ)}{\cal Z}^{(λ)}$, where the multiplicative correction, ${\cal 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. The empirical study yields a number of interesting observations, such as (a) ability to estimate ${\cal Z}^{(λ)}$ with $O(N^4)$ fractional samples; (b) suppression of $λ_*$ fluctuations with increase in $N$ for instances from a particular random Ising ensemble.