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

arXiv: https://arxiv.org/abs/2301.10369 · HTML: https://mlsanity.com/paper/2301.10369/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 37 references that are in the map.
- First posted on arXiv 25 Jan 2023.

## Builds on (most cited first, 6 of 6)

- [Neural Enhanced Belief Propagation on Factor Graphs](https://mlsanity.com/paper/2003.01998/) (2020)
- [Deep learning via message passing algorithms based on belief propagation](https://mlsanity.com/paper/2110.14583/) (2021)
- [Self-Guided Belief Propagation -- A Homotopy Continuation Method](https://mlsanity.com/paper/1812.01339/) (2018)
- [Gauges, Loops, and Polynomials for Partition Functions of Graphical Models](https://mlsanity.com/paper/1811.04713/) (2018)
- [Inference and Sampling of K33-free Ising Models](https://mlsanity.com/paper/1812.09587/) (2018)
- [Approximate inference on planar graphs using Loop Calculus and Belief Propagation](https://mlsanity.com/paper/1408.2034/) (2014)

## Built on by (most cited first, 1 of 1)

- [Thermal Image Calibration and Correction using Unpaired Cycle-Consistent Adversarial Networks](https://mlsanity.com/paper/2401.11582/) (2024)

## Abstract (arXiv)

Computing the partition function, Z, of an Ising model over a graph of N enquotespins 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 (enquoteexact) λ_* such that Z=Z(λ_*). Generalizing the re-parametrization approach of citepwainwrighttree-based2002 and the loop series approach of citepchertkovloop2006, 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(N2::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.