Lifted First-Order Belief Propagation
Unifying first-order logic and probability is a long-standing
goal of AI, and in recent years many representations combining
aspects of the two have been proposed. However, inference
in them is generally still at the level of propositional
logic, creating all ground atoms and formulas and applying
standard probabilistic inference methods to the resulting network.
Ideally, inference should be lifted as in first-order
logic, handling whole sets of indistinguishable objects together,
in time independent of their cardinality. Poole (2003)
and Braz et al. (2005, 2006) developed a lifted version of
the variable elimination algorithm, but it is extremely complex,
generally does not scale to realistic domains, and has
only been applied to very small artificial problems. In this
paper we propose the first lifted version of a scalable probabilistic
inference algorithm, belief propagation (loopy or not).
Our approach is based on first constructing a lifted network,
where each node represents a set of ground atoms that all
pass the same messages during belief propagation. We then
run belief propagation on this network. We prove the correctness
and optimality of our algorithm. Experiments show that
it can greatly reduce the cost of inference.