(Part 1, Part 2)

The distributed algorithm for inference I described last time is kind of awkward, and not very well linked with the rest of the field. Olivier Peltre has a better one. It’s connected with the well-known message-passing algorithm for this sort of calculation. Unfortunately, while I think I have a decent idea of the general idea of what’s going on, I don’t have a very detailed understanding of all the moving pieces, so some of this exposition might be just a little bit wrong.

We will need to give up a bit of our nice simplicial structure to make everything work properly. We will instead work directly with a cover of our set of random variables \(\mathcal I\) by a collection of sets \(\mathcal V\), where we require that \(\mathcal V\) be closed under intersection. This requirement makes \(\mathcal V\) a partially ordered set under the relation \(\alpha \leq \beta\) if \(\beta \subseteq \alpha\). (The change in direction is to ensure that our sheaves stay sheaves and our cosheaves stay cosheaves.) The state spaces for each \(\alpha\) still form a sheaf (i.e., a covariant functor) over \(\mathcal V\); and so we also get the cosheaf \(\mathcal A\) of observables and the sheaf \(\mathcal A^*\) of functionals. (This is probably terrible terminology for anyone not comfortable with cellular sheaves, since typically we want to think of a presheaf as a contravariant functor. Sorry.)

We can move back to the simplicial world by taking the nerve \(\mathcal N(\mathcal V)\) of \(\mathcal V\): this is the simplicial complex whose \(k\)-simplices are nondegenerate chains of length \(k+1\) in \(\mathcal V\). In particular, vertices of \(\mathcal{N}(\mathcal V)\) correspond to elements of \(\mathcal V\), while edges correspond to pairs \(\alpha \leq \beta\). A sheaf or cosheaf on \(\mathcal V\) extends naturally to \(\mathcal{N}(\mathcal V)\). The stalk over a simplex \(\alpha \leq \cdots \leq \beta\) is \(\mathcal F(\beta)\), and the restriction maps between 0- and 1-simplices are \(\mathcal F(\alpha) \to \mathcal F(\alpha \leq \beta)\), \(x_\alpha \mapsto \mathcal F_{\alpha \leq \beta} x_\alpha\), and \(\mathcal F(\beta) \to \mathcal F(\alpha \leq \beta)\), \(x_\beta \mapsto x_\beta\).

Extending a sheaf or cosheaf to \(\mathcal N(\mathcal V)\) preserves homology and cohomology (defined in terms of derived functors and all that), so this is not an unreasonable thing to do. The interpretations of \(H_0(\mathcal N(\mathcal V);\mathcal A)\) and \(H^0(\mathcal N(\mathcal V);\mathcal A^*)\) are also the same. Homology classes of \(\mathcal A\) correspond to Hamiltonians defined as a sum of local terms, and cohomology classes of \(\mathcal A^*\) (when normalized) correspond to consistent local marginals (or pseudomarginals).

We now come to the part of the framework I have always found most confusing, because it’s seldom very well explained. Peltre (and others, probably) makes a distinction between the interaction potentials \(h_\alpha\) which are summed to get a Hamiltonian on \(S\), and the collection of local Hamiltonians \(H_\alpha\), obtained by treating each subset \(\alpha\) as if it were an isolated system and summing the potentials \(h_\beta\) for \(\beta \subseteq \alpha\). Both of these can be seen as 0-cochains of \(\mathcal A\), and they are not really homologically related. There is an invertible linear map \(\zeta: C_0(\mathcal{N}(\mathcal V);\mathcal A) \to C_0(\mathcal{N}(\mathcal V);\mathcal A)\) which sends a collection of interaction potentials to its family of local Hamiltonians. The formula is straightforward: \((\zeta h)_\alpha = \sum_{\beta \subseteq \alpha} \mathcal A_{\alpha \leq \beta} h_\beta\). The inverse of \(\zeta\) is the Möbius transform \(\mu\) given by \((\mu H)_\alpha = \sum_{\beta \subseteq \alpha} c_{\beta} \mathcal{A}_{\alpha \leq \beta} H_\beta\). The coefficients \(c_{\beta}\) are the Möbius numbers of the poset \(\mathcal V\). Notice that these formulas refer to the poset relations, not to the incidence of simplices in \(\mathcal N(\mathcal V)\), which is a bit frustrating—the simplicial structure doesn’t seem to really be doing much here. However, \(\zeta\) and \(\mu\) can be extended to chain maps, and hence descend to homology. There are analogous operations on cochains of \(\mathcal A^*\), adjoint to the operations on the chains of \(\mathcal A\).

The action of \(H^0(\mathcal N(\mathcal V);\mathcal A^*)\) on \(H_0(\mathcal N(\mathcal V);\mathcal A)\) calculates the expected value of the Hamiltonian \(H\) given by a class of interaction potentials \(h_\alpha\) with respect to a consistent set of marginals. If a chain represents a collection of local Hamiltonians, then this pairing doesn’t compute an expectation. Instead, if \(p \in H^0\) and \(H \in C_0\), we have to take \(\langle p, \mu \cdot H\rangle\) to get the expectation. By adjointness, this is \(\langle \mu\cdot p, H\rangle\).

For reasons I don’t understand very deeply, these operations play a key role in formulating message passing dynamics. My current understanding is that it has to do with the gradients of the Bethe entropy. The Bethe entropy is defined on a section of \(\mathcal A^*\) by the same inclusion-exclusion procedure as we did before, but using the Möbius coefficients to perform inclusion-exclusion: \(\check{S}(p) = \sum_{\alpha} c_\alpha S(p_\alpha)\). Think of this as computing local (i.e. marginalized) entropy and then applying the Möbius transform.

The Bethe free energy is the functional we minimize to find the approximate pseudomarginals: \(\langle p, h \rangle - \check{S}(p)\). Adding the constraint that \(p\) be consistent (\(\delta p = 0\)) and normalized (\(\langle p_\alpha, \mathbf{1}_\alpha \rangle = 1\)), we get the Lagrangian condition

\[h + \mu (\log p + \mathbf{1}) + \partial \lambda + \tau = 0\]

which we can then convert to

\[-\log p - \mathbf{1} = \zeta(h + \partial \lambda + \tau).\]

The Lagrange multiplier \(\tau\) is an arbitrary 0-chain which is constant on each vertex, so its zeta transform also satisfies the same condition, and we can roll the \(\mathbf 1\) into it. \(\lambda\) is an arbitrary 1-chain. Ultimately, we have the requirement that

\[-\log p = \zeta(h + \partial \lambda) + \tau.\]

This holds on the level of cochains, and of course the cochain \(p\) must also be in \(H^0(\mathcal{N}(\mathcal V),\mathcal A^*)\). So in order to be a critical point for the Bethe free energy functional, \(-\log p\) must be obtained as the zeta transform of something homologous to the given local potential \(h\), up to some normalizing additive constant. Solving the marginalization problem amounts to a search for a local potential \(h'\) homologous to the given \(h\) that makes \(p = \exp(-\zeta h')\) a section of \(\mathcal A^*\). Note that every section of \(\mathcal A^*\) is normalized to some constant sum, so the normalization constraint isn’t all that interesting. Further, if \(p = \exp(-\zeta h')\), it is automatically nonnegative.

One of the key insights now is that if we define a differential equation on \(h\) where the derivative of \(h\) is always in the image of \(\delta\), the evolution of the state will be restricted to the homology class of the initial condition. If we define an operator on \(C_0(\mathcal{N}(\mathcal V);\mathcal A)\) which vanishes when \(\exp(-\zeta h')\) is a section of \(\mathcal A^*\), we’ll be able to use it to implement just such a differential equation.

Let \(\Delta = \partial \circ \mathcal D \circ \zeta\), where \(\mathcal D: C_0(\mathcal N(V);\mathcal A^*) \to C_1(\mathcal N(\mathcal V); \mathcal A)\) is defined by \((\mathcal D H)_{\alpha \leq \beta} = -\log(\mathcal A^*_{\alpha \leq \beta}\exp(-H_\alpha)) +H_\beta \in \mathcal A(\alpha \leq \beta) = \mathcal A(\beta)\). This operator clearly vanishes when \(\exp(-\zeta h)\) is a section of \(\mathcal A^*\), since \(\mathcal D \circ \zeta\) does. In fact, \(\Delta\) vanishes at precisely these points. This operator \(\Delta\) is somewhat mysterious, but if you squint hard enough it looks kind of like a Laplacian. In fact, its linearization around a given 0-chain appears to be a sheaf Laplacian.

Thus the system of differential equations \(\dot{h} = -\Delta h\) has stationary points corresponding precisely to the critical points of the Bethe entropy. If you discretize this ODE with a naive Euler scheme with step size 1, you get a discrete-time evolution equation, and this implies dynamics on local marginal estimates \(p_\alpha \propto \exp(-(\zeta h)_\alpha)\). It turns out that these dynamics on \(p\) are precisely the standard message-passing dynamics, typically described in terms of marginalization, sums, and products. This is a really neat result. And despite the complications involved in defining everything, I find this more comprehensible than the other expositions of generalized message-passing algorithms I’ve read. (I’m looking at you, Wainwright and Jordan.) I’d still like to understand this better, though. What exactly is the relationship between the operator \(\Delta\) and a sheaf Laplacian? Is there a sheaf-theoretic way to understand the max-product algorithm for finding maximum-likelihood elements rather than marginal distributions? Can we use (possibly conically constrained) cohomology of \(\mathcal A^*\) to say anything about the pseudomarginal problem?