Publication
Efficient Sequential Clamping for Lifted Message Passing
Fabian Hadiji; Babak Ahmadi; Kristian Kersting
In: Joscha Bach; Stefan Edelkamp (Hrsg.). KI 2011: Advances in Artificial Intelligence, 34th Annual German Conference on AI, Proceedings. German Conference on Artificial Intelligence (KI-2011), October 4-7, Berlin, Germany, Pages 122-133, Lecture Notes in Computer Science, Vol. 7006, Springer, 2011.
Abstract
Lifted message passing approaches can be extremely fast at computing approximate marginal probability distributions over single variables and neighboring ones in the underlying graphical model. They do, however, not prescribe a way to solve more complex inference tasks such as computing joint marginals for k-tuples of distant random variables or satisfying assignments of CNFs. A popular solution in these cases is the idea of turning the complex inference task into a sequence of simpler ones by selecting and clamping variables one at a time and running lifted message passing again after each selection. This naive solution, however, recomputes the lifted network in each step from scratch, therefore often canceling the benefits of lifted inference. We show how to avoid this by efficiently computing the lifted network for each conditioning directly from the one already known for the single node marginals. Our experiments show that significant efficiency gains are possible for lifted message passing guided decimation for SAT and sampling.