Papers › Exact Fractional Inference via Re-Parametrization & Interpolation between...
Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms
Hamidreza Behjoo, Michael Chertkov
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⁽ᵀᴿᵂ⁾ ≥Z^((λ)) ≥Z⁽ᴮᴾ⁾, 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, ∀λ: 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections