Mixtures from switching factors
Download as a Jupyter notebook
A graph of linear-Gaussian factors never has a second mode, however it is wired. The smallest factor that changes that is SwitchingConstraintFactor: a linear constraint whose right-hand side is chosen by a discrete outcome, $0 = \sum_i A_i x_i - b_k + \varepsilon$ with $P(k) = w_k$. This tutorial uses one such factor as a Gaussian mixture, then wires two of them into a sum node to get a grid of modes. On the grid it compares belief propagation, a mean-field sum node and exact inference. (Background: the vault notes Switching Constraint Factors and Composing Stochastic Factors.)
using Lenticulum, LenticulumCore, Mycelium, LinearAlgebra, LuxCore, Random, Printf
using MyceliumLearning
using CairoMakie: CairoMakie, Figure, Axis, heatmap!, DataAspectOne factor is a Gaussian mixture
With $A = I$ the factor is $w_k \mathcal N(z; b_k, Q)$: a mixture whose means are the columns of b. Q is a fixed hyperparameter; b and the log-weights logw are the parameters.
f = SwitchingConstraintFactor((z = 2,), 3, 2; noise = 0.15)
ps = (A = (z = Matrix(1.0I, 2, 2),), b = [-1.5 1.5 0.0; 0.0 0.0 2.0], logw = log.([0.4, 0.4, 0.2]))Every channel can be the target of an exact message. With nothing observed, the message to z is the mixture itself, a MixtureBelief with the factor's weights:
mz, _ = Mycelium.factor_message(f, :z, nothing, NamedTuple(), nothing, ps, NamedTuple())
mixture_weights(mz), [belief_mean(c) for c in mz.components]([0.39999999999999986, 0.39999999999999986, 0.20000000000000023], [[-1.5, 0.0], [1.5, 0.0], [0.0, 2.0]])Observing z and asking for the outcome is the measurement: the message to k is the evidence of each outcome. In a graph, a data factor clamps z and the outcome is a variable of its own:
function mixture_graph(z)
b = GraphBuilder()
variable!(b, :z, 2); variable!(b, :k, 3)
factor!(b, :data, DataFactor(:z, z)); factor!(b, :sw, f)
connect!(b, :data, :z, :z; direction = Emitting())
connect!(b, :sw, :z, :z; direction = Absorbing())
connect!(b, :sw, :k, :k)
g = build(b)
return g, merge(LuxCore.initialparameters(Xoshiro(0), g), (sw = ps,))
end
g, gps = mixture_graph([0.9, 0.6])
marg, _, st, store = infer!(g, tree_schedule(g), gps, NamedTuple())
probabilities(marg.k)3-element Vector{Float64}:
1.5221780595648985e-8
0.9994616441255261
0.0005383406526935394The factor's belief over $(z, k)$ has a closed-form entropy, $H(k) + H(z \mid k)$, so the graph's Bethe free energy is available, and on this tree it is $-\log p(z)$. Checked against the mixture density:
F, _ = LenticulumCore.scalar_free_energy(store, g, gps, st)
lognormal(x, μ, Σ) = -(dot(x - μ, Σ \ (x - μ)) + logdet(2π * Σ)) / 2
w = exp.(ps.logw)
logp = log(sum(w[k] * exp(lognormal([0.9, 0.6], ps.b[:, k], f.Q)) for k in 1:3))
@printf("free energy %.10f, -log p(z) %.10f\n", F, -logp)free energy 3.2565093126, -log p(z) 3.2565093126
So the free energy of the graph is the model's density. Evaluated on a grid, it draws the mixture:
function free_energy_at(z)
g, gps = mixture_graph(z)
_, _, st, store = infer!(g, tree_schedule(g), gps, NamedTuple())
return first(LenticulumCore.scalar_free_energy(store, g, gps, st))
end
xs = range(-3, 3; length = 90); ys = range(-1.5, 3.5; length = 75)
dens = [exp(-free_energy_at([x, y])) for x in xs, y in ys]
fig = Figure(size = (520, 400))
ax = Axis(fig[1, 1]; aspect = DataAspect(), title = "exp(−F) of the one-factor graph")
heatmap!(ax, xs, ys, dens; colormap = :viridis)
fig
Composition: switches into a sum node
Two binary switches feeding a sum node, $z = c + k_1 \delta_1 + k_2 \delta_2 + \varepsilon$, give four modes on a parallelogram from two offsets. Each switch is a SwitchingConstraintFactor on its own variable $u_l = k_l \delta_l$ (a narrow noise makes it nearly exact), and the sum node is a LinearConstraintFactor, $z - u_1 - u_2 = c$. The two offsets point in similar directions, so the switches overlap: from one observation it is hard to tell which switch is on.
c = [0.0, 0.0]; δ = [2.0 1.6; 0.0 1.2]; p = [0.5, 0.5]; Σ = 0.3 * Matrix(1.0I, 2, 2)
function grid_graph(x, rule)
b = GraphBuilder()
variable!(b, :z, 2); foreach(v -> variable!(b, v, 2), (:u1, :u2)); foreach(v -> variable!(b, v, 2), (:k1, :k2))
factor!(b, :data, DataFactor(:z, x))
factor!(b, :sum, LinearConstraintFactor((z = 2, u1 = 2, u2 = 2), 2; noise = Σ); rule)
connect!(b, :data, :z, :z; direction = Emitting()); connect!(b, :sum, :z, :z; direction = Absorbing())
I2 = Matrix(1.0I, 2, 2)
swps = map(1:2) do l
name = Symbol(:sw, l)
factor!(b, name, SwitchingConstraintFactor((u = 2,), 2, 2; noise = 1e-8))
connect!(b, name, :u, Symbol(:u, l)); connect!(b, :sum, Symbol(:u, l), Symbol(:u, l))
connect!(b, name, :k, Symbol(:k, l))
name => (A = (u = I2,), b = [zeros(2) δ[:, l]], logw = log.([1 - p[l], p[l]]))
end
g = build(b)
ps = merge(LuxCore.initialparameters(Xoshiro(0), g),
(sum = (A = (z = I2, u1 = -I2, u2 = -I2), c = c),), NamedTuple(swps))
return g, ps
endExact inference enumerates the four configurations:
configs = [(a, b) for a in 0:1 for b in 0:1]
function exact(x)
l = [log(p[1]^a * (1 - p[1])^(1 - a) * p[2]^b * (1 - p[2])^(1 - b)) + lognormal(x, c + a * δ[:, 1] + b * δ[:, 2], Σ)
for (a, b) in configs]
P = exp.(l .- maximum(l)); P ./= sum(P)
return [sum(P[i] for (i, (a, _)) in enumerate(configs) if a == 1), sum(P[i] for (i, (_, b)) in enumerate(configs) if b == 1)]
endBelief propagation on this tree is one sweep. At the sum node each switch sees the other only through its prior moments, since the other's mixture message is collapsed to a mean and a covariance before use (assumed-density filtering):
function bp(x)
g, ps = grid_graph(x, BeliefPropagation())
marg, _, _, _ = infer!(g, tree_schedule(g), ps, NamedTuple())
return [probabilities(marg.k1)[2], probabilities(marg.k2)[2]]
endA mean-field sum node (rule = MeanField()) reads the other switch's current marginal instead, and the graph is iterated. The switch factors stay on belief propagation. This is the hybrid of Riegler et al. (2013); its fixed point is mean field over the two switches. hybrid_schedule builds the iteration from the rules: each switch's belief-propagation cluster is swept, then the sum node sends its messages in turn, each followed by the cluster it reached. Convergence is measured on the marginals.
function hybrid(x)
g, ps = grid_graph(x, MeanField())
s = MessageStore(g)
report, _ = propagate!(s, g, hybrid_schedule(g), ps, NamedTuple(); maxsweeps = 200, tol = 1e-10)
return [probabilities(marginal(s, g, g.variable_index[k]))[2] for k in (:k1, :k2)], report
endFor a point between the modes, where the two explanations compete:
x = c + 0.5 * δ[:, 1] + 0.5 * δ[:, 2] + [0.3, -0.2]
P_mf, report = hybrid(x)
@printf("P(k₁ = 1), P(k₂ = 1): exact %.3f %.3f belief propagation %.3f %.3f mean field %.3f %.3f (%d sweeps)\n",
exact(x)..., bp(x)..., P_mf..., report.sweeps)P(k₁ = 1), P(k₂ = 1): exact 0.770 0.238 belief propagation 0.819 0.394 mean field 0.999 0.011 (6 sweeps)
Mean field over single switches settles on one explanation and is overconfident; belief propagation keeps both but misweighs them. The three disagree because the switches explain away each other: given $z$, "switch 1 on" and "switch 2 on" are alternatives, so the exact posterior has a strong negative correlation between them that no factorised answer can hold. Over many points this is what biases learning: the M-step needs $\mathbb E[k_1 k_2]$, and every factorised method replaces it by $q_1 q_2$. The cure measured on the branch experiment-qm is to put overlapping switches into one factor with $2^B$ outcomes, a block that is exact inside, and to keep the sum node on mean field between blocks. Here a single block holds both switches, and the posterior is exact:
block = SwitchingConstraintFactor((z = 2,), 4, 2; noise = Σ)
bps = (A = (z = Matrix(1.0I, 2, 2),), b = reduce(hcat, [c + a * δ[:, 1] + b * δ[:, 2] for (a, b) in configs]),
logw = [log(p[1]^a * (1 - p[1])^(1 - a) * p[2]^b * (1 - p[2])^(1 - b)) for (a, b) in configs])
mk, _ = Mycelium.factor_message(block, :k, nothing, (z = LenticulumCore.DiracBelief(x),), nothing, bps, NamedTuple())
P = probabilities(mk)
@printf("one block of both switches: P(k₁ = 1) %.3f, P(k₂ = 1) %.3f\n",
sum(P[i] for (i, (a, _)) in enumerate(configs) if a == 1), sum(P[i] for (i, (_, b)) in enumerate(configs) if b == 1))one block of both switches: P(k₁ = 1) 0.770, P(k₂ = 1) 0.238
The free energy of the hybrid
A graph with a mean-field node has the merged free energy of Riegler et al. (2013), eq. (17), not the Bethe free energy: the sum node contributes only its average energy under the product of the marginals, and each variable's entropy is counted by its belief-propagation neighbours. Each switch's part of the graph is a tree, so here it is $\mathrm{KL}(q \| p) - \log p(x)$ for the factorised $q$, an upper bound on $-\log p(x)$:
function hybrid_store(x)
g, ps = grid_graph(x, MeanField())
s = MessageStore(g)
propagate!(s, g, hybrid_schedule(g), ps, NamedTuple(); maxsweeps = 500, tol = 1e-10)
return g, ps, s
end
g, gps, s = hybrid_store(x)
F_hybrid = first(LenticulumCore.scalar_free_energy(s, g, gps, NamedTuple()))
l = [log(p[1]^a * (1 - p[1])^(1 - a) * p[2]^b * (1 - p[2])^(1 - b)) + lognormal(x, c + a * δ[:, 1] + b * δ[:, 2], Σ)
for (a, b) in configs]
nlp = -(maximum(l) + log(sum(exp.(l .- maximum(l)))))
@printf("hybrid free energy %.4f exact -log p(x) %.4f gap %.4f\n", F_hybrid, nlp, F_hybrid - nlp)hybrid free energy 2.2921 exact -log p(x) 2.0315 gap 0.2606
The gap is what mean field over the two switches costs at this point. Because the free energy is now defined, free_energy_gradient and parameter_step train such a graph: at a fixed point the gradient holds the factor beliefs and the mean-field node's marginals fixed, which is the derivative of this free energy (checked against central differences in Lenticulum's test/mean_field_free_energy.jl).
The plan for the rest of Mycelium's extension, is in the vault note Extending Mycelium.
This page was generated using Literate.jl.