Status: draft (2026-11-03, Claude), implemented as described. Related: Extending Mycelium §5, L-SPEC-008 Expectation Propagation and Mixture Reduction, Switching Constraint Factors, Composing Stochastic Factors (E7). Code:
lib/Mycelium.jl/src/cluster.jl; Lenticulumlib/Lenticulum.jl/src/switching.jl(cluster_formmethods).
Sources: Yedidia, Freeman & Weiss, Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms, IEEE Trans. Inf. Theory 51(7), 2005, the region free energy (here regions are solved exactly, not approximated). code:
lib/Mycelium.jl/src/cluster.jl,lib/Lenticulum.jl/src/switching.jl; tests:lib/Lenticulum.jl/test/cluster.jl,lib/Mycelium.jl/test/cluster.jlBibliography: Yedidia et al. 2005
Theory (CT-ML wiki): Variational Free Energy
Scope
A graph operation that replaces a set of factor nodes by one node with exact inference inside, for conditionally linear-Gaussian factors. Automatic grouping, approximate regions (generalised belief propagation with overlapping regions) and clusters inside plates are out of scope.
The contract
§1. The transformation. cluster(g, name, factors) returns a new graph in which the named
factor nodes are one ClusterFactor node name. A variable whose every edge is to a clustered
factor becomes internal; every other variable a clustered factor touches becomes a channel of the
node, named after the variable, on a bidirectional diagonal edge. The other nodes and edges are
copied unchanged. A variable is discrete when a clustered factor switches on it
(cluster_switch); every variable has an Int dimension. Refused: plates, a missing or taken
name, a factor without cluster_form, a factor not on BeliefPropagation(), a parameter key shared
with a node outside, tied groups with different frozen paths, a clustered edge that is not bidirectional,
diagonal and attached.
§2. The factor form. cluster_form(factor, ps) returns ClusterForm(A, C, Q, logw, switch):
with ; switch the
discrete channel is read from (nothing: one column). and do not depend on .
§3. Messages. To a channel, given the messages on the others: the exact message of the
product of the clustered factors, with internal variables integrated and summed out. Discrete
states are enumerated (at most joint states); continuous variables are eliminated in
canonical form; points are substituted; a Gaussian-mixture input is collapsed to its moments. To
a continuous channel the message is a mixture over the joint states, or a GaussianBelief for one;
to a discrete channel a CategoricalBelief. Continuous variables not determined by the factors and
the messages are refused.
§4. Free energy. The node’s local free energy is for its exact
belief , graded (fit, complexity, negentropy); factor_belief and
belief_free_energy give its parameter gradient at a fixed belief. Internal variables do not
appear in the graph’s counting numbers.
§6. Several clusters, tied, and grouping by overlap (planned and implemented 2026-11-03).
cluster(g, groups::Vector{Pair}; params) makes one node per group; with params the nodes read
one entry (tied), and a key shared between groups is allowed only then. overlap_groups(C, maxsize) is E7’s greedy grouping; Lenticulum’s switch_overlaps(g, ps, sum, switches) gives the
switches’ overlaps as they feed one linear factor (largest of their offset directions in the
sum’s total-noise metric). Grouping does not rewire by itself: without E7’s partial sum per block a
cluster of switches meeting only at the sum gains nothing (cluster.md). Lenticulum’s
partial_sums(g, ps, sum, switches, groups; noise) makes that edit (added 2026-11-03,
switching.md §14) and returns the groups to cluster.
§7. Joint outcomes and discrete tables (added 2026-11-03). A ClusterForm’s switch may be a
tuple of discrete channels, the outcome their joint state in column-major order. TableFactor(dims, logtable) is a fixed factor over discrete variables with such a form; its -Inf entries tie
variables together. The node drops the assignments of weight zero before its Gaussian part, and a
zero-weight outcome contributes nothing to the free energy ().
§8. Over a plate (added 2026-11-04). cluster(g, plate, name, factors; params) makes one tied
node per replica of the plate’s template factors and keeps the plate; inside, variables carry
template names. as_plate(g, name, n) records the nodes named x[i] as a plate. For tied nodes
with the same factors and inputs of one shape, messages and free energies are batched
(factor_messages, factor_beliefs → FrozenClusterBeliefs, belief_free_energies); otherwise
per node. Values equal the unplated graph’s.
§9. Per-outcome coefficients and noise (added 2026-11-04). An entry of a ClusterForm’s A
may be an array and its Q an array. Assignments are grouped into
precision classes (one per combination of the varying factors’ outcomes), each eliminated with its
own precision; a message to a continuous channel is then a mixture whose components may differ in
precision (an improper component is the unnormalised exponential its weight multiplies). Over a
plate such nodes are batched as in §8, one shared precision per class (added 2026-11-12; a
RegimeFactor plate row outside a cluster too, through as_cluster).
as_cluster(f) is one factor as a cluster node, for a factor with only a cluster_form; Lenticulum’s
RegimeFactor (, ) is one.
§10. Flat directions (added 2026-11-04). Continuous directions that no factor and no incoming message determines are integrated out in the diffuse limit (a vague prior , , its factor for the flat directions dropped): pseudo-inverse and pseudo-determinant on the range of the precision. Refused when the assignments leave different numbers of directions flat, or when a linear term reaches a flat direction. A marginal with a flat direction is improper.
§5. Parameters and marginals. The node’s parameters are keyed by the clustered factors’
parameter keys; cluster_parameters(gc, name, ps) converts a parameter tree of the original graph.
cluster_marginal(store, gc, name, v, ps) is the marginal of a cluster variable under the node’s
belief.
Checked by
lib/Lenticulum.jl/test/cluster.jl: a switching chain in one cluster against enumeration (free energy to
, marginal moments to , the gradient in tied offsets against central differences);
three switches in one cluster against E7’s block factor (messages to , marginals of the
same loopy schedule and local free energies to ); the cluster of the sum and the switches
has where the plain graph has no free energy; the refusals. lib/Mycelium.jl/test/cluster.jl:
the same on Mycelium’s own prior factors.
Grouping (lib/Lenticulum.jl/test/cluster.jl, bench/cluster_overlap.jl): switch_overlaps equals E7’s normalised
Gram to and overlap_groups E7’s overlap_blocks for block sizes 2–4; on eight switches in
overlapping pairs, blocks of 4 by overlap (with partial sums, made by partial_sums) cut the mean error of the switch
posteriors from 0.092 to 0.031, blocks in index order to 0.092.
Tables (lib/Mycelium.jl/test/cluster.jl): three categorical variables and two tables with
entries in one cluster against enumeration ( and marginals to ), and belief
propagation through the tables on the same tree.
Per-outcome forms (Lenticulum lib/Lenticulum.jl/test/regime.jl): a mixture of factor analysers with three
precisions in one cluster against the closed form (, the regime posterior and the
posteriors of to ; the gradient in , , and the noise against central differences
to , ForwardDiff and Zygote), the one-factor cluster’s messages against the closed form, and
a plate of four points. Batched over a plate (lib/Lenticulum.jl/test/regime_plate.jl): messages, beliefs, free
energies and gradients equal the per-replica ones on random instances (, ); a plated
mixture of factor analysers with random parameters against the closed form ( to , the
gradient to ); EM statistics from stacked beliefs equal per node ().
Flat directions (Lenticulum lib/Lenticulum.jl/test/cluster_flat.jl): free energies, switch posteriors, gradients and
messages against the same graphs with a vague prior (, corrected for its constant) and
against closed forms; the refusals.
Open
- Done 2026-11-12: batching per-outcome forms over a plate (Lenticulum
test/regime_plate.jl). - Done 2026-11-03/04: clusters in plates (§8), E7’s partial sums from the groups (Lenticulum’s
partial_sums), merging repeated components of a message, pruned enumeration, per-outcome coefficients and noise (§9), flat directions (§10), frozen parameter paths (carried over under the factor’s parameter key).