A closure of dynamic message-passing equation for general kinetic spin models on a sparse graph

by Gino Del Ferraro (KTH)

Tuesday 11 Nov 2014, 13:30 → 14:30 Europe/Stockholm

122:026

Dynamic message-passing equations represent the natural extension of belief-propagation equations to the dynamic case, in which the variables defined on the vertices of a graph evolve in time according to a specified evolution law. We derive these equations for synchronous dynamics on a locally tree-like topology and we present a method to perturbatively close them and so reduce the computational complexity. The method builds on (a) a graph expansion to eliminate loops from the normalizations of each step in the dynamics, and (b) an assumption that a set of auxilary probability distributions on histories of pairs of spins mainly have dependencies that are local in time. The closure is then effectuated by projecting these probability distributions on n-step Markov processes.