design

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; Lenticulum lib/Lenticulum.jl/src/switching.jl (cluster_form methods).

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.jl

Bibliography: 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).