Message-passing algorithms and homology : from thermodynamics to statistical learning

Message-passing algorithms consist of a parallelised computing scheme to estimate the marginals of a high-dimensional probability distribution. They have been used in various areas where the statistics of a large number of interacting variables have to be studied, including statistical physics, artificial intelligence, decoding in information theory. This thesis desctibes the algebraic and topological structures in which message-passing algorithms naturally take place. In most applications, the probability distribution p is defined by a Markov field or graphical model, i.e. as a product of local factors depending only on small subsets of interacting variables. Equivalently, the total energy H = - ln p (or log-likelihood) is a sum of local interaction potentials. Embedding potentials as the 0-degree subspace of a chain complex of local observables, we show that this constraint is equivalent to assuming a one-to-one parametrisation of total energies by homology classes of interaction potentials. The 1-chains of this complex are statistical analogs of heat fluxes. The evolution of potentials up to the boundary of a heat flux, preserving total energy, produces new belief propagation algorithms as continuous-time diffusion equations. The consistency of pseudo-marginals one seeks to approximate is reciprocally translated by a cohomological constraint, demanding that a collection of local probability distributions has a vanishing differential. The local potentials and local distributions form a pair of dual variables put in correspondence by a smooth non-linear functional, essentially composing the exponential with a sum over subsets, called zeta transform in combinatorics. Pairs at the intersection of the energy conservation and marginal consistency constraint surfaces are shown to be in correspondence with both the stationary points of belief propagation algorithms and the critical points of a local approximation of free energy, computed by the Bethe-Kikuchi combinatorial method, a truncation of the Mobius inversion of the zeta transform.