From Belief Propagation to Generalise Belief Propagation
Many important problems in error-correcting coding theory, artificial intelligence, computer vision, and statistical physics can be represented in terms of graphical models. It is well known that the “belief propagation” algorithm (BP) is an efficient way to solve these problems but it only gives an approximation unless the underlying graphical model is a tree.
In this talk, first, we will talk about Bethe approximation of the free energy for a factor graph which can be considered as a justification for the BP algorithm. Then, we will talk about the “region based approximation” that is a more sophisticated way to improve the Bethe approximation and leads to an algorithm called “generalised belief propagation” (GBP). Finally, we will cover some of the recent analytical results on estimating the partition function of 2D Ising models with restricted grid size using GBP algorithm.
Mahdi Jafari Siavoshani received his PhD from Swiss Federal Institute of Technology (EPFL) in 2012. From 2012 until 2013, he was a postdoc at the Institute of Network Coding (INC). He is currently an assistant professor of the Computer Engineering Department at Sharif University of Technology, Iran.
He is interested in various fundamental problems that arise in communication systems. His research interests mainly focus on understanding the fundamental limits of such system as well as the design of new techniques and algorithms that are suitable for practical implementation. He is also interested in the connection of communication and computer sciences.
