UCL Logo

Surya Ganguli

Sloan-Swartz Center for Theoretical Neurobiology, UCSF, USA


Monday 2 April 2007, 16:00


Seminar Room B10 (Basement)

Alexandra House, 17 Queen Square, London, WC1N 3AR


The Information Geometry of Survey Propagation

Graphical Models, representing multivariate probability distributions, are powerful modeling tools that have diverse applications in computational biology. The problem of inferring the marginals of such models arises frequently in these applications and is often solved by an approximate message passing algorithm known as belief propagation (BP). However in certain complex graphical models, even if BP converges, it can give inaccurate marginals. Recent activity at the intersection of statistical physics (namely the theory of spin glasses) and machine learning has generated a new algorithm known as survey propagation (SP), which can succeed in certain instances where BP fails. In this talk, after introducing both BP and SP, we analyze SP from the perspective of information geometry. By combining techniques from statistical physics and Riemannian geometry we show that SP is analogous to a process of “biological evolution” on a restricted manifold of probability distributions that approximate the full graphical model. Each interaction if SP involves a recombination and subsequent selection step in a population of such approximate distributions. The presence of these steps, which are not found in BP, yields geometric insight into the computational power of SP over BP.