Approximate Lifting Techniques for Belief Propagation

Many AI applications need to explicitly represent relational structure as well as handle uncertainty. First order probabilis-tic models combine the power of logic and probability to deal with such domains. A naive approach to inference in these models is to propositionalize the whole theory and carry out the inference on the ground network. Lifted inference tech-niques (such as lifted belief propagation; Singla and Domin-gos 2008) provide a more scalable approach to inference by combining together groups of objects which behave identi-cally. In many cases, constructing the lifted network can it-self be quite costly. In addition, the exact lifted network is often very close in size to the fully propositionalized model. To overcome these problems, we present approximate lifted inference, which groups together similar but distinguishable objects and treats them as if they were identical. Early stop-ping terminates the execution of the lifted network construc-tion at an early stage resulting in a coarser network. Noise-tolerant hypercubes allow for marginal errors in the represen-tation of the lifted network itself. Both of our algorithms can significantly speed up the process of lifted network construc-tion as well as result in much smaller models. The coarseness of the approximation can be adjusted depending on the accu-racy required, and we can bound the resulting error. Extensive evaluation on six domains demonstrates great efficiency gains with only minor (or no) loss in accuracy.