Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference
This work addresses the challenge of efficient probabilistic inference for complex models like Markov logic networks, offering a flexible approach that bridges approximate and exact methods, but it appears incremental relative to prior lifted inference techniques.
The paper tackles the problem of approximate lifted inference in first-order probabilistic models by introducing a method that starts with a simplified model and incrementally recovers constraints, achieving a spectrum from lifted belief propagation to exact inference. Empirically, it shows substantial improvements over existing approximations, though specific numerical gains are not detailed in the abstract.
We propose an approach to lifted approximate inference for first-order probabilistic models, such as Markov logic networks. It is based on performing exact lifted inference in a simplified first-order model, which is found by relaxing first-order constraints, and then compensating for the relaxation. These simplified models can be incrementally improved by carefully recovering constraints that have been relaxed, also at the first-order level. This leads to a spectrum of approximations, with lifted belief propagation on one end, and exact lifted inference on the other. We discuss how relaxation, compensation, and recovery can be performed, all at the firstorder level, and show empirically that our approach substantially improves on the approximations of both propositional solvers and lifted belief propagation.