Approximate Lifted Belief Propagation

Lifting can greatly reduce the cost of inference on first-order probabilistic models, but constructing the lifted network can itself be quite costly. In addition, the minimal lifted network is often very close in size to the fully propositionalized model; lifted inference yields little or no speedup in these situations. In this paper, we address both these problems. We propose a compact hypercube-based representation for the lifted network, which can greatly reduce the cost of lifted network construction. We also present two methods for approximate lifted network construction, which groups together similar but distinguishable objects and treats them as if they were identical. This can greatly reduce the size of the lifted network as well as the time required for lifted network construction, but potentially at some cost to accuracy. The coarseness of the approximation can be adjusted depending on the accuracy required, and we can bound the resulting error. Experiments on six domains show great efficiency gains with only minor loss in accuracy.