message passing algorithm in general
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:
- Chapter 16: “Message Passing” — “Information Theory, Inference, and Learning Algorithms” by , MacKay, D. J. C. (2003). Cambridge University Press. ISBN 0-521-64298-1. e-book is available on the author’s homepage
- “Solving Combinatorial Problems by Message Passing” by Ben Young (2001) [PDF]