GitHub

Forward-Backward Discrete Belief Propagation

Forward-backward discrete belief propagation solves tree-structured discrete 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 discrete belief propagation variant is run:

  • sumproduct runs sum-product belief propagation and stores probability 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: sumproduct stores probability marginals, while minsum stores MAP estimates.

Start from a tree-structured discrete factor graph:

x1 = DiscreteVariable(:x1, 2; label = "x1", states = [:off, :on])
x2 = DiscreteVariable(:x2, 2; label = "x2", states = [:low, :high])
x3 = DiscreteVariable(:x3, 2; label = "x3")

f1 = DiscreteFactor(:x1, [0.8, 0.2]; label = "f1")
f2 = DiscreteFactor(:x1, :x2, [1.0 0.2; 0.1 0.9]; label = "f2")
f3 = DiscreteFactor(:x2, :x3, [0.9 0.3; 0.2 0.8]; label = "f3")

graph = factorGraph([x1, x2, x3], [f1, f2, f3]; root = :x1)

Sum-Product Inference

Discrete tree inference uses the same sumproduct inference state as iterative discrete belief propagation. Messages and marginals are probability vectors. Create a sum-product inference state, then use forwardBackward! to run the exact tree sweep:

inference = sumproduct(graph)
forwardBackward!(graph, inference)

Variables created without an initial probability use a uniform initial message. A unary DiscreteFactor with initialize = true overrides the variable's initial probability for message initialization.

To inspect results, use marginal for one variable's probability vector, marginalProbability for one state, or marginals to return all stored variable marginals:

marginal(graph, inference, :x1)
marginalProbability(graph, inference, :x1, :on)

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

Min-Sum MAP Inference

The min-sum form computes exact MAP estimates on a tree. It is the negative-log form of discrete max-product belief propagation: factor tables become costs, messages are cost vectors, and variable beliefs are MAP states.

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

inference = minsum(graph)
forwardBackward!(graph, inference)

Use estimate for one variable and estimates for all variables:

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

For interactive inspection, printMessages prints min-sum messages adjacent to one variable or factor, and printEstimate prints 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 sumproduct, or estimates! for minsum:

inference = sumproduct(graph)

forward!(graph, inference)
backward!(graph, inference)
marginals!(graph, inference)
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:

inference = sumproduct(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 = sumproduct(graph)

forwardStep!(graph, inference; variable = :x3, factor = "f3")
backwardStep!(graph, inference; variable = :x3, factor = "f3")
marginals!(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, 2; label = "x4", states = [:a, :b])
addFactor!(graph, inference, :x3, :x4, [0.9 0.1; 0.1 0.9]; 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. Adding a factor through the tree view refreshes the tree message order.

For sumproduct, existing marginals are also preserved, and a new variable receives an initial message from its own probability or from the uniform default. For minsum, the corresponding initial belief is converted to an initial 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")
marginals!(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 table changes without changing tree topology:

updateFactor!(graph, inference; factor = "f4", table = [0.8 0.2; 0.2 0.8])
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 sumproduct 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 table.

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 = sumproduct(graph)
forwardBackward!(graph, inference)