Closed-form M-steps from cluster beliefs:
em_stepcollects each clustered factor’s moment statistics from the exact beliefs and asks the factor for its maximiser (m_step);fit_emalternates inference and M-steps, optionally SQUAREM-accelerated. With every learned factor in a cluster node this is EM, and it reproduces hand-written EM step for step.
Sources: Varadhan & Roland, Simple and Globally Convergent Methods for Accelerating the Convergence of Any EM Algorithm, Scand. J. Statist. 35(2), 2008 (SQUAREM, scheme S3). code:
em.jl; Lenticulumsrc/m_steps.jl(the constraint factors’m_step); tests: Lenticulumtest/em.jlBibliography: Varadhan & Roland 2008
1. What an M-step needs
At a fixed belief the free energy is , and its
parameter-dependent part separates over parameter keys. For a factor stated by a cluster_form
(a residual , noise , weight ), depends on only
through the moments of its continuous channels (stacked) per outcome :
MomentStats holds them. _moment_stats reads them from a FrozenClusterBelief: the means
per assignment, the covariance of the assignment’s precision class (points have none), and the
weights . em_step sums them over the tied nodes and the plate’s replicas of a parameter key,
then calls m_step(factor, stats, ps, frozen), the factor’s minimiser of , with the
key’s frozen paths (a cluster node’s paths with the factor’s key stripped). A factor without a
method keeps its parameters. A node outside a cluster takes part when its factor_belief is a
FrozenClusterBelief (Lenticulum’s RegimeFactor, a one-factor cluster).
With exact beliefs (every learned factor in a cluster node, inference converged) one em_step is
one step of EM: the free energy is of the data, and it does not increase.
2. fit_em and acceleration
fit_em(g, ps, st; schedule) alternates sweeps sweeps (the E-step), the free energy and
em_step, until falls by less than tol. It ends with an E-step at the returned parameters, so
the store and Fs[end] belong to them.
EM is slow when a latent variable is almost determined by the parameters. A switch with
noise feeding a sum of noise 0.09 pins its to the current offset , and each M-step moves
by little. Measured in a scratch run (one data set, 60 points, two switches, the
test/em.jl model):
| switch noise | plain EM | SQUAREM |
|---|---|---|
| 2306 steps to , contraction 0.990 per step, 18.3 s | 86 cycles, 2.3 s, the same (70.534082) | |
| 0.05 | 57 steps, contraction 0.650, 0.5 s | 7 cycles |
accelerate = true runs SQUAREM’s S3 cycle on the learnable subtrees (θ₁ = M(θ₀), θ₂ = M(θ₁),
θ′ = θ₀ − 2αr + α²v with α = −‖r‖/‖v‖ ≤ −1, one stabilising step from θ′), falling back to θ₂ when the cycle
raises . test/em.jl checks that it reaches plain EM’s fixed point in under 200 cycles where plain
EM takes over 1000.
3. Measured on the structure search
examples/structure_edits.jl with STRUCTURE_FIT=em (structure_edits.md) uses fit_em with
SQUAREM in place of 300 Momentum steps. One fit of the generating structure (three switches, 200
points) from a perturbed start, measured in a scratch run after compilation: 1.0 s against 7.7 s,
both reaching . Per call: an E-step (two sweeps and ) 0.017 s, em_step 0.03 s, a
ForwardDiff gradient 0.01 s. em_step builds every replica’s belief on its own; the gradient uses
the plate’s batched beliefs.
The whole search improved less at first, 177 s against 192–200 s on the same day with the same path
and scores. Fitting was not the bottleneck there: the first fit of every new structure spent 11–22 s
compiling (each L is a new parameter type, and the message loop was specialised on it), and the
over-parameterised L = 4 candidates needed 130–170 SQUAREM cycles to (30–50 s; their ,
504.879, is lower than the gradient fit’s). Per-fit timings from an instrumented scratch copy.
The message loop no longer specialises on the parameter tree (passing.md, “Compilation per
structure”), and the example stops EM at (BIC to ): the search takes 58.0 s
with EM against 163.8 s with gradient steps, the same path and scores.
examples/structure_clusters.jl (structure_clusters.md): the per-factor M-step built on
moment_statistics crawled (the same small-noise switches; 1 143 s, a worse structure), and a
collapsed M-step, the ‘s integrated out given the assignment, takes the search to 181 s against
1 121 s with gradient steps, on another path into a worse local optimum of the generating
structure. fit_em(...; mstep) takes such a caller-supplied M-step.
Batched statistics (2026-11-04). A plate row of cluster nodes whose replicas share their
structure is read from its stacked beliefs (FrozenClusterBeliefs, the same the batched free
energy uses): per factor and outcome, , and are a few matrix products over all
replicas’ assignments, instead of a belief per replica and a loop over its assignments. Rows that do
not batch (per-outcome forms, replicas of different input shape) and nodes outside plates take the
per-node path; moment_statistics(...; batched = false) forces it, and test/em.jl checks that both
give the same statistics to . On the graph of §3, em_step fell from 0.03 s to 0.003 s and a warm
fit from 1.0 s to 0.4 s (7.1 s for 300 gradient steps; a scratch timing); the structure_edits
search with EM from 58.0 s to 34.9 s, the same path and scores.
4. What it does not do
- Factors outside clusters, except one-factor clusters, have no statistics: a learned factor on approximate (loopy) beliefs is not fitted by EM here.
- Only closed forms. Factors without
m_stepkeep their parameters; mixing M-steps with gradient steps for the others is the caller’s (generalised EM). - Compilation per structure dominates a structure search’s first fits; that is a property of the typed inference code, not of EM (LP-023’s “typed execution plans”).
5. Difficulties
- The first test compared one step too many.
fit_emruns an M-step after every E-step, soiters = steps + 1performedsteps + 1M-steps, and the graph looked a step ahead of the hand EM. With the count fixed the iterates agree to . - Plain EM did not converge in the switch test (500 steps, still falling by 0.002): the tiny switch noise, §2. Hence SQUAREM.
- The first accelerated fit took 12 s. The extrapolation rebuilt the parameters from a flat
vector as views (
ReshapedArray), a new parameter type that recompiled inference; they are materialised as plain arrays now (1.6 s for the first fit, 1.0 s after).
6. Review of 2026-11-05 (Mistral via vibe)
A read-only review of em.jl and src/m_steps.jl checked the statistics, the batched layout and the
M-step’s minimiser numerically and found them correct. It reported three silent errors, all
confirmed and fixed:
- Batched statistics with an observed discrete input that differs between replicas (the
batching shape,
cluster.md“Review of 2026-11-05”); tested. fit_emread any rise of as convergence (Fs[end-1] - F < tol). It now needstol; with exact beliefs does not rise, with approximate ones a rise is not convergence.- Tied factors that differ in fixed structure (a different
output_coeff) pooled their statistics under the first factor’s.m_step_signature(factor)names that structure, andem_steprefuses to pool unequal signatures; tested (test/em.jl).
Codex was tried first. Every model, the configured default included, was refused with “not supported when using Codex with a ChatGPT account”.