AAAI Publications, Workshops at the Twenty-Fourth AAAI Conference on Artificial Intelligence

Font Size: 
Exploiting Logical Structure in Lifted Probabilistic Inference
Vibhav Gogate, Pedro Domingos

Last modified: 2010-07-07


Representations that combine first-order logic and probability have been the focus of much recent research. Lifted inference algorithms for them avoid grounding out the domain, bringing benefits analogous to those of resolution theorem proving in first-order logic. However, all lifted probabilistic inference algorithms to date treat potentials as black boxes, and do not take advantage of their logical structure. As a result, inference with them is needlessly inefficient compared to the logical case. We overcome this by proposing the first lifted probabilistic inference algorithm that exploits determinism and context specific independence. In particular, we show that AND/OR search can be lifted by introducing POWER nodes in addition to the standard AND and OR nodes. Experimental tests show the benefits of our approach.


Lifted inference; Statistical relational learning; first-order graphical models; Markov logic networks; Probabilistic inference

Full Text: PDF