PaperlayerView exact revision on arXiv

Source-linked AI summary

Merging Belief Propagation and the Mean Field Approximation: A Free Energy Approach

Erwin Riegler, Gunvor Elisabeth Kirkelund, Carles Navarro Manchón, Mihai-Alin Badiu, Bernard Henry Fleury

arXiv:1112.0467v3cs.ITmath.ITstat.ML

TL;DR

BP and MF have different strengths, motivating a unified message-passing method. The paper derives their coupled equations from a constrained region-based free energy and presents a conditionally convergent implementation. In an OFDM example, Algorithm 2 outperforms the compared Gaussian-approximation receiver and performs close to perfect-CSI reception at low pilot density.

  • Problem

    BP and MF have different strengths, motivating a unified message-passing algorithm that combines them on the same factor graph.

    Source: §I · pp. 1–2

  • Method

    The method derives coupled BP–MF message updates from a constrained region-based free energy and implements them with a conditionally convergent algorithm.

    Source: §I · p. 2, §V · p. 10

  • Results

    Algorithm 2 outperforms BP combined with a Gaussian approximation and performs close to perfect-CSI reception even at low pilot density.

    Source: C. Comparison with BP combined with… · p. 10

  • Takeaways & Limitations

    The coupled equations specify when decoder messages are extrinsic values in the BP part and APP values in the MF part.

    Source: §III · p. 6

    Extending the BP part to continuous random variables remains open because the cited approach assumes a differentiable objective, whereas the region-based free energy is generally not differentiable under standard definitions.

    Source: §V · p. 11

Abstract

from arXiv · show

We present a joint message passing approach that combines belief propagation and the mean field approximation. Our analysis is based on the region-based free energy approximation method proposed by Yedidia et al. We show that the message passing fixed-point equations obtained with this combination correspond to stationary points of a constrained region-based free energy approximation. Moreover, we present a convergent implementation of these message passing fixedpoint equations provided that the underlying factor graph fulfills certain technical conditions. In addition, we show how to include hard constraints in the part of the factor graph corresponding to belief propagation. Finally, we demonstrate an application of our method to iterative channel estimation and decoding in an orthogonal frequency division multiplexing (OFDM) system.

I. INTRODUCTION

The paper develops a unified BP–MF message-passing approach from a shared region-based free energy objective, relating its fixed points to stationary points and giving a conditionally convergent update method. It motivates the combination by the methods’ complementary strengths and outlines the notation and free-energy framework used to derive BP and MF updates.

I. INTRODUCTION

  • BP and MF have complementary properties: MF has simple updates and a convergent implementation, while BP supports hard constraints but can be computationally costly.The paper proposes combining them on one factor graph to exploit their respective strengths.Source: §I · pp. 1–2
  • Theorem 2 derives coupled BP–MF fixed-point equations from one constrained region-based free energy approximation and relates their solutions to stationary points.Algorithm 1 implements the updates and is guaranteed to converge when the factor graph satisfies certain technical conditions.Source: §I · p. 2

A. Notation

  • The notation defines finite-set and random-variable conventions, function conventions, and complex Gaussian and matrix notation used throughout.For example, x denotes possible realizations of X, while a particular realization is written x̄.Source: A. Notation · p. 2

A. Region-based free energy approximations [9]

  • The region-based free energy approximation minimizes a sum of region energies and entropies over local beliefs subject to constraints; suitable region choices yield MF or Bethe free energy.The trivial one-region choice yields MF fixed-point equations, while the Bethe free energy yields BP fixed-point equations.Source: A. Region-based free energy… · p. 3

B. BP fixed-point equations

BP fixed points arise as stationary points of a constrained Bethe free energy. The section also distinguishes normalized message updates from the constrained equations and notes the tree-graph case.

B. BP fixed-point equations

  • BP fixed points are related to stationary points of the Bethe free energy after adding belief normalization and marginalization constraints to its Lagrangian.The normalized factor beliefs are required to satisfy the stated consistency constraints with variable beliefs.Source: B. BP fixed-point equations · pp. 3–4
  • The alternative BP update equations allow arbitrary positive scaling constants, but their solutions need not satisfy the constrained Lagrangian equations after rescaling.A necessary and sufficient rescaling condition is introduced for determining when an alternative-equation solution can be converted to a solution of the constrained equations.Source: B. BP fixed-point equations · p. 4
  • On tree-structured factor graphs, forward-backward messages fulfill the stated consistency condition because the normalization factors equal one.The cited remark states this for ω_a,i = 1 and z̃_a = 1.Source: B. BP fixed-point equations · p. 4

C. Fixed-point equations for the MF approximation

The paper derives MF updates and EM as instances of free-energy minimization, then constructs a constrained region-based free energy whose stationary points correspond to combined BP–MF message-passing fixed points.

C. Fixed-point equations for the MF approximation

  • MF beliefs satisfy stationary equations from the MF free energy, and iterative belief updates converge because each update does not increase that objective over a convex normalized-belief set.For continuous variables, sums in the update equations are replaced by Lebesgue integrals.Source: C. Fixed-point equations for the MF… · pp. 4–5

D. Expectation maximization (EM)

  • EM is a special instance of the MF approximation when selected beliefs are constrained to point masses, with their locations updated by minimizing the resulting free energy.Beliefs for variables outside the constrained set retain the MF stationary-point form.Source: D. Expectation maximization (EM) · p. 5

III. COMBINED BP / MF APPROXIMATION FIXED-POINT

  • The combined approximation uses one MF region, BP factor regions, and adjusted counting numbers for BP variable regions to form a valid region set.The additional counting-number terms ensure that the combined regions and counting numbers are valid.Source: §III · p. 5
  • The combined free-energy approximation is finite under the stated constraints, and Theorem 2 extends to continuous variables by replacing the relevant sums with integrals.The theorem’s third fixed-point identity uses Lebesgue integrals for continuous variables outside the BP part.Source: §III · p. 6
  • Theorem 2 links stationary points of the constrained BP–MF free energy to positive-belief fixed points, with message type determined by whether its factor lies in the BP or MF part.The theorem also covers the converse, and its normalization constants are specified in the paper.Source: §III · p. 6

A. Hard constraints for BP

The paper extends the combined BP–MF fixed-point result to nonnegative BP factors, including hard constraints, by focusing on beliefs with finite region-based free energy.

A. Hard constraints for BP

  • The combined BP–MF result extends to nonnegative BP factors, and setting the MF part empty also extends the BP-only result to hard constraints.The derivation considers solutions whose region-based free energy is not plus infinity.Source: A. Hard constraints for BP · p. 6
  • The result assumes that conditioning on each variable realization leaves the joint pmf nonzero; realizations violating this can be removed.This is the stated support condition used in the hard-constraint analysis.Source: A. Hard constraints for BP · p. 6
  • Under the stated conditions, the constrained free energy is finite exactly when the specified zero-belief conditions hold, and the remaining stationary points correspond to fixed points.The characterization includes realizations where a BP factor is zero.Source: A. Hard constraints for BP · p. 7

B. Convergence and main algorithm

A cycle-free BP part and the stated technical condition permit a convergent alternating implementation of the combined updates. The OFDM example uses BP for modulation and decoding and MF for channel estimation.

B. Convergence and main algorithm

  • A convergent implementation is guaranteed when the BP part is cycle-free and condition (26) holds.The algorithm alternates MF belief updates with the forward-backward algorithm in the BP part.Source: B. Convergence and main algorithm · p. 7
  • The implementation fixes MF messages as input to BP, then uses BP beliefs to update messages and beliefs in the MF part.The MF updates do not increase the region-based free energy because they solve convex optimization problems over normalized beliefs.Source: B. Convergence and main algorithm · p. 7

AND DECODING

  • In the OFDM example, BP handles modulation and decoding while MF estimates channel-gain parameters in a conjugate-exponential model.Applying BP to all factor nodes would be intractable because of its high complexity.Source: AND DECODING · p. 7
  • The example’s BP graph contains cycles from coding, interleaving, and high-order modulation, so using loopy BP in the algorithm removes the convergence guarantee.The example’s factor-graph split assigns channel likelihood and channel-prior factors to MF, with BP handling the remaining factors.Source: AND DECODING · p. 8, Figure 1 · p. 9

A. “Extrinsic” values versus “APP”

The combined fixed-point equations distinguish message roles by destination: BP receives extrinsic values, while MF receives APPs, matching the cited channel-estimation and detection strategies.

A. “Extrinsic” values versus “APP”

B. Level of MF approximation

The choice of MF variable nodes sets the approximation level and yields a family of algorithms. Splitting the channel variable into separate nodes assumes independence, which may reduce complexity at a performance cost.

B. Level of MF approximation

C. Comparison with BP combined with Gaussian approximation

BP–MF outperforms a complexity-comparable BP approach using Gaussian-approximated messages and approaches perfect-CSI performance even with sparse pilots. The section also describes noise-precision estimation and situates these results within the method’s conclusions and open extensions.

C. Comparison with BP combined with Gaussian approximation

D. Estimation of noise precision

V. CONCLUSION AND OUTLOOK

  • The combined fixed-point equations correspond to stationary points of one constrained region-based free energy, and the updating algorithm is guaranteed to converge under technical conditions.The paper also identifies extending the BP part to continuous variables as future work, noting that the free energy may not satisfy standard differentiability assumptions.Source: §V · pp. 10–11

APPENDIX

The appendix supplies proof details for message-equation equivalence, the continuous-variable MF extension, and the correspondence between constrained free-energy stationary points and message-passing fixed points.

A. Proof of Lemma 1

  • The Lemma 1 proof derives fixed-point equations from a reparameterization of messages and verifies their equivalence to the original equations.Source: A. Proof of Lemma 1 · p. 11

B. Extension of the MF approximation to continuous random variables

  • For continuous random variables, the appendix assumes finite Lebesgue integrals and obtains the MF expressions by replacing sums with integrals.The stated integrability can be checked by inspecting the factors and analytic expressions of the computed beliefs.Source: B. Extension of the MF approximation… · pp. 11–12

C. Proof of Theorem 2

  • The Theorem 2 proof shows that stationary points of the constrained Lagrangian yield positive-belief fixed points satisfying the message-passing equations, with the steps reversible.Source: C. Proof of Theorem 2 · p. 13

D. Proof of Lemma 2

The proof of Lemma 2 establishes finiteness conditions for the free-energy terms and handles factor assignments that impose zero-probability configurations.

D. Proof of Lemma 2

  • Finiteness of F3 and condition (24) imply finiteness of F2; F1 is finite if and only if condition (25) holds.Source: D. Proof of Lemma 2 · p. 13
  • Fixing beliefs at realizations with zero factor values leaves the remaining fixed-point equations unchanged, and those realizations can be restored because they do not contribute to message updates.Source: D. Proof of Lemma 2 · p. 13

E. Proof of convergence

The convergence proof relates minimizing the BP free energy to minimizing the region-based free energy approximation. Under the tree-structure assumption, the BP forward/backward pass computes the required marginals, and Algorithm 1 is guaranteed to converge.

E. Proof of convergence

  • MF-to-BP messages are fixed inputs during the BP step, and condition (26) places the other neighbors of the relevant MF factor in IMF \ IBP.This condition supports treating the corresponding terms as constant in step 2 of Algorithm 1.Source: E. Proof of convergence · p. 14
  • For fixed beliefs on variables shared with the MF part, the marginals of factorization (55) minimize FBP, MF because FBP is nonnegative and vanishes exactly at those marginals.Minimizing FBP in (56) is equivalent to minimizing FBP, MF in (17).Source: E. Proof of convergence · p. 14
  • Algorithm 1 is guaranteed to converge because its BP forward/backward pass computes the marginals of factorization (55).The factor graph in the BP part is assumed to have a tree structure.Source: E. Proof of convergence · p. 14

F. Product of Gaussian distributions

For the product-of-Gaussian-distributions result, the proof is stated to follow from direct computation.

F. Product of Gaussian distributions

Loading 1112.0467v3…