Belief Propagation on Partially Ordered Sets

In this paper, which is based on the important recent work of Yedidia, Freeman, and Weiss, we present a generalized form of belief propagation, viz. belief propagation on a partially ordered set (PBP). PBP is an iterative message-passing algorithm for solving, either exactly or approximately, the marginalized product density problem, which is a general computational problem of wide applicability. We will show that PBP can be thought of as an algorithm for minimizing a certain "free energy" function, and by exploiting this interpretation, we will exhibit a one-to-one correspondence between the fixed points of PBP and the stationary points of the free energy.