GitHub

Forward-Backward Gaussian Belief Propagation

Forward-backward Gaussian belief propagation solves tree-structured Gaussian factor graphs with one forward pass and one backward pass. On a tree, this schedule is exact: after both passes, every edge has sent the messages needed to compute the final variable marginals or MAP estimates.

The inference object determines which Gaussian belief propagation variant is run:

  • moment runs sum-product belief propagation in moment form and stores Gaussian marginals.
  • canonical runs sum-product belief propagation in canonical form and stores Gaussian marginals.
  • minsum runs min-sum belief propagation for MAP inference and stores MAP estimates.

The forward-backward message order is the same for these inference states. The difference is the message representation and the stored variable result: moment and canonical store marginals, while minsum stores MAP estimates.

Start from a tree-structured Gaussian factor graph:

variables = [
    GaussianVariable(:x1, 1; label = "x1"),
    GaussianVariable(:x2, 1; label = "x2"),
    GaussianVariable(:x3, 1; label = "x3"),
]

factors = [
    GaussianFactor(:x1, 1.0, 1.0, 0.1; label = "f1"),
    GaussianFactor(:x1, :x2, 0.0, [1.0 -1.0], 0.2; label = "f2"),
    GaussianFactor(:x2, :x3, 0.0, [1.0 -1.0], 0.2; label = "f3"),
]

graph = factorGraph(variables, factors; root = :x1)

Sum-Product Moment Inference

The moment form runs sum-product Gaussian belief propagation and stores each message and marginal as a mean vector and covariance matrix. Create a moment-form inference state with moment, then use forwardBackward! to run the exact tree sweep:

inference = moment(graph; mean = 0.0, covariance = 1e6)
forwardBackward!(graph, inference)

The mean and covariance keywords define the default initial belief for variables created without their own initial mean or covariance. Scalar defaults are expanded to each variable dimension.

To inspect results, use marginalMean and marginalCovariance when only one field is needed. Use marginal when the full marginal object is needed, or marginals to return all stored variable marginals:

marginalMean(graph, inference, :x2)
marginalCovariance(graph, inference, :x2)

For interactive inspection, printMessages prints messages adjacent to one variable or factor, and printMarginal prints sum-product marginals.

Sum-Product Canonical Inference

The canonical form computes the same exact sum-product Gaussian marginals as the moment form, but represents messages with information vectors and precision matrices. Products of Gaussian messages are represented internally as sums of information vectors and precision matrices.

Create a canonical-form inference state with canonical, then use forwardBackward! to run the exact tree sweep:

inference = canonical(graph; mean = 0.0, covariance = 1e6)
forwardBackward!(graph, inference)

Marginals can still be inspected as means and covariances with the same public lookup functions used for the moment form.

Min-Sum MAP Inference

The min-sum form computes exact MAP estimates on a tree. It is the negative-log quadratic form of Gaussian max-product belief propagation: factor potentials become least-squares costs, messages are quadratic costs, and variable beliefs are MAP estimates.

This form optimizes the most likely state instead of computing marginal covariances.

Create a min-sum inference state with minsum, then use forwardBackward! to run the exact tree sweep:

inference = minsum(graph; mean = 0.0, covariance = 1e6)
forwardBackward!(graph, inference)

The mean and covariance keywords define the default initial belief for variables created without their own initial mean or covariance. For minsum, this belief is converted to an initial quadratic cost message.

Use estimate for one variable and estimates for all variables:

estimate(graph, inference, :x2)
estimates(graph, inference)

For interactive inspection, printMessages prints messages adjacent to one variable or factor, and printEstimate prints min-sum MAP estimates.

Manual Message Updates

Use the manual message functions when you want to control the tree sweep yourself. They run the same message-passing computation as forwardBackward!, but split it into explicit forward, backward, and result recomputation steps.

forward! runs the forward pass, and backward! runs the backward pass. They do not recompute variable results by themselves, so call marginals! for moment and canonical, or estimates! for minsum:

inference = moment(graph)

forward!(graph, inference)
backward!(graph, inference)
marginals!(graph, inference)

For minsum, recompute MAP estimates after the message passes:

inference = minsum(graph)

forward!(graph, inference)
backward!(graph, inference)
estimates!(graph, inference)

For edge-level control, use forwardStep! and backwardStep!. Each call updates one directed tree message and returns the edge that was updated, or nothing when that pass has no remaining scheduled edge. These functions work with moment, canonical, and minsum:

inference = canonical(graph)

while true
    edge = forwardStep!(graph, inference)
    edge === nothing && break
end

while true
    edge = backwardStep!(graph, inference)
    edge === nothing && break
end

marginals!(graph, inference)

When you already know which edge should be updated, pass the edge selection directly to forwardStep! or backwardStep!:

inference = minsum(graph)

forwardStep!(graph, inference; variable = :x3, factor = "f3")
backwardStep!(graph, inference; variable = :x3, factor = "f3")
estimates!(graph, inference)

Selected-edge calls update only the requested tree message. They are useful for manual or incremental schedules where the caller decides which edges need to be recomputed.

Call reset! before reusing the tree's automatic step cursor:

reset!(graph)

Freezing Updates

Freezing keeps selected messages unchanged while the rest of the tree continues updating. It uses the same inference-state flags as iterative belief propagation.

To freeze all outgoing messages from a factor or variable, use:

freezeFactor!(graph, inference, "f3")
freezeVariable!(graph, inference, :x3)

To freeze both message directions on one edge, use:

freezeEdge!(graph, inference; variable = :x3, factor = "f3")

Resume updates by unfreezing the same selections:

unfreezeFactor!(graph, inference, "f3")
unfreezeVariable!(graph, inference, :x3)
unfreezeEdge!(graph, inference; variable = :x3, factor = "f3")

Inspection helpers return booleans and use the same references:

isFrozenFactor(graph, inference, "f3")
isFrozenVariable(graph, inference, :x3)
isFrozenEdge(graph, inference; variable = :x3, factor = "f3")

A frozen message is not recomputed. While messages remain frozen, the resulting beliefs are partial warm-start beliefs rather than exact tree marginals or exact MAP estimates. Unfreeze the relevant messages and run another complete sweep when exact tree results are needed.

Dynamic Tree Changes

Use addVariable! with a tree inference object when a new variable node must be added after inference has started. A new variable is usually followed by at least one new factor that connects it to the tree. The updated graph must still be a tree:

addVariable!(graph, inference, :x4, 1; label = "x4")
addFactor!(graph, inference, :x3, :x4, 0.0, [1.0 -1.0], 0.2; label = "f4")

forwardBackward!(graph, inference)

Passing the inference object makes this a warm-start update. Existing messages are preserved, and the message arrays are extended when new factor edges are added.

For moment and canonical, existing marginals are also preserved, and a new variable receives an initial belief from its own mean and covariance or from the inference defaults. For minsum, this belief is converted to an initial quadratic cost message and MAP estimate.

Warm-start topology updates extend only the inference object passed to addVariable! or addFactor!. Any other inference object created from the same tree before the topology change no longer matches the tree and should be recreated or updated separately.

For custom incremental schedules, use forwardStep! and backwardStep! on selected edges:

forwardStep!(graph, inference; variable = :x4, factor = "f4")
backwardStep!(graph, inference; variable = :x4, factor = "f4")
estimates!(graph, inference)

Selected-edge calls update only the requested tree messages. They are useful when the caller decides which edges need to be recomputed.

Use updateFactor! when an existing factor's mean, coefficient, or covariance changes without changing tree topology:

updateFactor!(graph, inference; factor = "f4", mean = 0.1)
forwardBackward!(graph, inference)

This reuses the existing inference state as a warm start. The message state still contains information from previous sweeps, which is useful for dynamic inference. For an independent solve, update the tree and then create a fresh moment, canonical, or minsum object.

Because updateFactor! does not change tree topology, other inference objects created from the same tree still structurally match the tree. However, their messages have not been refreshed for the new factor parameters.

Root Selection

The root determines the forward and backward message order. On a connected tree, it does not change the final exact marginals or MAP estimates after a complete sweep:

refresh!(graph; root = "x3")
inference = canonical(graph)
forwardBackward!(graph, inference)