Abstract
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.
We will also review the application of this inference method to other
problems in communication and its generalisation when the replica symmetry
is broken.
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)
Users
Please
log in to take part in the discussion (add own reviews or comments).