GitHub

Iterative Discrete Belief Propagation

Iterative discrete belief propagation runs message updates on a DiscreteFactorGraph. Each iteration updates messages from factor nodes to variable nodes and from variable nodes to factor nodes, then recomputes the stored variable result. This is the general schedule for arbitrary discrete factor graphs, including graphs with cycles.

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.

Use sumproduct when marginal probabilities are needed. Use minsum when only the MAP assignment is needed.

Start from a 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", initialize = true)
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")
f4 = DiscreteFactor(:x3, :x1, [0.7 0.4; 0.3 0.6]; label = "f4")

graph = factorGraph([x1, x2, x3], [f1, f2, f3, f4])

The example graph contains a cycle, so it uses the general iterative schedule rather than the specialized tree schedule.

Sum-Product Inference

The sum-product form of discrete belief propagation represents messages and marginals as probability vectors. Create a sum-product inference state with sumproduct, then use gbp! to run iterative updates:

inference = sumproduct(graph)
gbp!(graph, inference; iterations = 100, tolerance = 1e-6)

Each iteration updates factor-to-variable messages, variable-to-factor messages, and the stored variable marginals. 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.

If iterations is omitted, gbp! runs at most 10 iterations. The iterations keyword always acts as the maximum number of iterations. The tolerance keyword is applied to maxMarginalChange. If tolerance is omitted, no early stopping is used.

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 MAP estimates. 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. This form optimizes the most likely assignment instead of computing marginal probabilities.

Create a min-sum inference state with minsum, then use gbp! to run iterative updates:

inference = minsum(graph)
gbp!(graph, inference; iterations = 50, tolerance = 1e-6)

Each iteration updates factor-to-variable messages, variable-to-factor messages, and the stored variable MAP estimates. The tolerance keyword is applied to maxEstimateChange.

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 iteration loop yourself. They run the same message-passing computation as gbp!, but split it into explicit message and result steps.

messages! runs one full message step: factor-to-variable messages and variable-to-factor messages. It does not recompute variable results by itself, so call marginals! for sumproduct, or estimates! for minsum:

inference = sumproduct(graph)

for _ in 1:20
    messages!(graph, inference)
end

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

for _ in 1:20
    messages!(graph, inference)
end

estimates!(graph, inference)

For directional control, call the factor-to-variable and variable-to-factor passes explicitly:

inference = sumproduct(graph)

for _ in 1:20
    factorToVariableMessages!(graph, inference)
    variableToFactorMessages!(graph, inference)
end

marginals!(graph, inference)

The directional functions expose the two message passes separately. They are useful when experimenting with custom schedules. For normal inference, gbp! is the simpler entry point.

Convergence Diagnostics

Use maxMessageChange to compare message states between two iterations. For stored variable results, use maxMarginalChange with sumproduct, and maxEstimateChange with minsum.

inference = sumproduct(graph)

for _ in 1:100
    oldVariableMessages = deepcopy(inference.variableToFactor)
    oldFactorMessages = deepcopy(inference.factorToVariable)
    oldMarginals = deepcopy(inference.marginal)

    messages!(graph, inference)
    marginals!(graph, inference)

    messageDiff = maxMessageChange(graph, inference, oldVariableMessages, oldFactorMessages)
    marginalDiff = maxMarginalChange(graph, inference, oldMarginals)

    if messageDiff < 1e-6 && marginalDiff < 1e-6
        break
    end
end

The message change includes both factor-to-variable and variable-to-factor messages. Use maxFactorMessageChange or maxVariableMessageChange to inspect one direction. The marginal change compares marginal probability vectors.

Sequential Schedule

Sequential scheduling is the default update order for gbp! and messages!. Factor-to-variable messages are updated first, followed by variable-to-factor messages. Messages are updated in place, so later updates in the same pass can use values computed earlier in that pass.

You can request sequential scheduling explicitly with schedule = :sequential:

inference = sumproduct(graph)
gbp!(graph, inference; iterations = 20, schedule = :sequential)

For a manual loop, call messages! directly. Sequential scheduling is the default:

inference = sumproduct(graph)

for _ in 1:20
    messages!(graph, inference)
    marginals!(graph, inference)
end

For directional control, call the two sequential message passes directly:

inference = sumproduct(graph)

for _ in 1:20
    factorToVariableMessages!(graph, inference)
    variableToFactorMessages!(graph, inference)
    marginals!(graph, inference)
end

Flooding Schedule

Flooding scheduling updates messages in a next-message buffer before committing them to the inference state. With schedule = :flooding, updates within a pass read from the old message arrays and are committed together.

Use gbp! with schedule = :flooding to run iterative inference with this update order:

inference = sumproduct(graph)
gbp!(graph, inference; iterations = 20, schedule = :flooding)

For a manual flooding loop, pass the same schedule keyword to messages!:

inference = sumproduct(graph)

for _ in 1:20
    messages!(graph, inference; schedule = :flooding)
    marginals!(graph, inference)
end

Flooding scheduling works with sumproduct and minsum inference states. The keyword form is the normal public entry point. Create a FloodingSchedule explicitly only for low-level messages! calls that need a schedule object:

inference = sumproduct(graph)
schedule = floodingSchedule(graph, inference)

for _ in 1:20
    messages!(graph, inference, schedule)
    marginals!(graph, inference)
end

The returned schedule is mutable step state for the selected graph and inference object. Recreate it after changing graph topology or replacing the inference object.

There are no separate public flooding calls for the two message directions, because committing one direction before the other would change the flooding semantics.

Residual Scheduling

Residual scheduling recomputes directed messages and updates only those whose new values differ most from their current values. This can reduce work on loopy graphs where a small subset of messages dominates the current error.

Use gbp! with schedule = :residual to run a complete residual-scheduled loop:

inference = sumproduct(graph)
gbp!(graph, inference; schedule = :residual, updateFraction = 0.2)

The updateFraction keyword controls the fraction of directed messages updated in each residual step. Use updateCount when you want a fixed number of largest-residual messages:

inference = sumproduct(graph)
gbp!(graph, inference; schedule = :residual, updateCount = 5)

For a manual residual loop, pass the same residual schedule keywords to messages!:

inference = sumproduct(graph)

for _ in 1:20
    messages!(graph, inference; schedule = :residual, updateFraction = 0.1)
    marginals!(graph, inference)
end

Residual scheduling works with sumproduct and minsum inference states. The keyword form is the normal public entry point. Create a ResidualSchedule explicitly when you want to inspect or reuse the selected low-level schedule object:

inference = sumproduct(graph)
schedule = residualSchedule(graph, inference; updateFraction = 0.1)

for _ in 1:20
    messages!(graph, inference, schedule)
    marginals!(graph, inference)
end

The residual schedule object stores mutable step state for the selected graph and inference object. Recreate it after changing graph topology or replacing the inference object.

There are no separate public residual calls for complete factor-to-variable or variable-to-factor passes, because each residual step selects individual directed messages.

Damping

Discrete damping blends a new factor-to-variable message with the previous message. For sum-product messages, the blended message is renormalized. Damping is often useful on loopy graphs where undamped message updates may oscillate.

Enable global damping through gbp!:

inference = sumproduct(graph)
gbp!(graph, inference; iterations = 50, damping = true, prob = 1.0, alpha = 0.35)

The alpha keyword is the weight of the previous message. The prob keyword is the probability that damping is applied to an eligible update. Damping is applied to factor-to-variable message updates.

The same damping keywords can be used with the manual messages! API:

inference = sumproduct(graph)

for _ in 1:20
    messages!(graph, inference; damping = true, prob = 1.0, alpha = 0.35)
end

marginals!(graph, inference)

Use dampEdges! to damp selected edges:

dampEdges!(graph, inference; variable = :x2, factor = "f2", prob = 1.0, alpha = 0.35)
areDampedEdges(graph, inference; variable = :x2, factor = "f2")

Use undampEdges! to remove damping from selected edges:

undampEdges!(graph, inference; variable = :x2, factor = "f2")

Freezing Updates

Freezing keeps selected messages unchanged while the rest of the graph continues updating.

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

freezeFactor!(graph, inference, "f2")
freezeVariable!(graph, inference, :x2)

To freeze both message directions on one edge, use:

freezeEdge!(graph, inference; variable = :x2, factor = "f2")

Resume updates by unfreezing the same selections:

unfreezeFactor!(graph, inference, "f2")
unfreezeVariable!(graph, inference, :x2)
unfreezeEdge!(graph, inference; variable = :x2, factor = "f2")

Inspection helpers return booleans and use the same references:

isFrozenFactor(graph, inference, "f2")
isFrozenVariable(graph, inference, :x2)
isFrozenEdge(graph, inference; variable = :x2, factor = "f2")

Dynamic Graph Changes

Use addVariable! with an 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 graph:

addVariable!(graph, inference, :x4, 2; label = "x4", states = [:a, :b])
addFactor!(graph, inference, :x3, :x4, [0.9 0.1; 0.1 0.9]; label = "f5")

gbp!(graph, inference; iterations = 50)

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 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 graph before the topology change no longer matches the graph and should be recreated or updated separately.

Use updateFactor! when an existing factor table changes without changing graph topology:

updateFactor!(graph, inference; factor = "f1", table = [0.7, 0.3], initialize = true)
gbp!(graph, inference; iterations = 50)

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

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