UCL Logo

David Saad

Neural Computing Research Group, Aston University, UK


Wednesday 25 April 2007, 16:00


Seminar Room B10 (Basement)

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


Bayesian inference by message passing in dense and composite systems


Juan P. Neirotti and Etienne Mallard


Probabilistic graphical models provide a powerful framework for modelling statistical dependencies between variables, mainly in systems that can be mapped onto sparse graphs. They play an essential role in providing principled probabilistic inference in a broad range of applications from medical expert systems, to telecommunication. These methods, that have largely been developed independently in the computer science and information theory literature, also have deep roots in advanced mean field methods of statistical physics.


Message passing techniques are perceived as impractical for densely connected systems due to the computational effort involved and the existence of loops, but can be used in this context by introducing a set of average messages sampled from a Gaussian distribution, whose parameters are updated iteratively [1]. However, this approach fails when the solution space becomes fragmented, for instance, when there is a mismatch between the assumed and true prior information.


We extended this approach [2-3] to tackle inference problems where no reliable prior information is available, conceptually in a similar way to the extension of belief propagation to survey propagation [4] in the case of sparse graphs, by replicating the system variables and calculating pseudo-posterior estimates based on averages over the replicated systems. This is carried out by considering an infinite number of replicated systems and employing methods of statistical physics. The method has been applied to CDMA signal detection and learning in Ising linear perceptron showing optimal performance for large systems.


The new approach also facilitates the use of message passing for inference in composite systems that comprise different levels of connectivity and interaction strengths. We have successfully applied the approach to toy composite models.


Finally, we will review the application of this inference method to other problems in communication and possible extensions.


[1] Y. Kabashima, J.Phys. A Vol. 36 11111 (2003)

[2] J.P. Neirotti and D. Saad, Europhys. Lett. Vol. 71 866 (2005)

[3] J.P. Neirotti and D. Saad, Physica A Vol. 365 203 (2006)

[4] M. Mezard, G. Parisi and R. Zecchina, Science Vol. 297 812 (2002)