Message-Passing Algorithm (MPA) is a popular inference method in tree-structured graphical models. Pearl’s MPA (1988) is one of the early algorithms of this kind. However, the origin of MP in general is found long before 1988. It might be interesting to see what motivates this algorithms and useful to know its origin. I have an impression that once we know the origin, we may be able to realize how Prof. Pearl came up with his famous Pearl’s MPA. And when we can generalize this MPA framework, we will be able to develop our own MPA for other applications since MPA is a very important concept in combinatorial problems which appear in so many real-world applications these days.
Good materials to read:
This pdf file is the note used on the discussion. Also this is a good example of using Pearl’s message passing from the book “Expert Systems and Probabilistic Network Models” by E. Castillo, J.M. Gutiérrez, and A.S. Hadi.
Message-passing algorithm is extremely useful for inference on Graphical Models. Recently there are some papers discuss about its generalizations which are very good to know and useful for further applications. There are so many good papers on this topic, and these are some of them
This link contributing for message-passing on Bayesian networks is from Microsoft Research, Cambridge. The website contains a various kinds of message-passing algorithms and applications. Also the website provides links to other websites related to message-passing and statistical inference on graphical models as well.
Expectation Propagation is refered as a generalization of belief propagation. This link is also from Dr. Minka of Microsoft Research.
There is a short paper by Prof. Murphy “From Belief Propagation to Expectation Propagation”
Prof. Yeir Weiss’s Homepage. Prof. Weiss has a lot of interesting work about inference on graphical models.
These are the must-read articles:
Bethe free energy, Kikuchi approximations and belief propagation algorithms
Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
Understanding Belief Propagation and its Generalizations