AAAI Publications, Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
Advances in Lifted Importance Sampling
Vibhav Gogate, Abhay Jha, Deepak Venugopal

Last modified: 2012-07-14


We consider lifted importance sampling (LIS), a previously proposed approximate inference algorithm for statistical relational learning (SRL) models. LIS achieves substantial variance reduction over conventional importance sampling by using various lifting rules that take advantage of the symmetry in the relational representation. However, it suffers from two drawbacks. First, it does not take advantage of some important symmetries in the relational representation and may exhibit needlessly high variance on models having these symmetries. Second, it uses an uninformative proposal distribution which adversely affects its accuracy. We propose two improvements to LIS that address these limitations. First, we identify a new symmetry in SRL models and define a lifting rule for taking advantage of this symmetry. The lifting rule reduces the variance of LIS. Second, we propose a new, structured approach for constructing and dynamically updating the proposal distribution via adaptive sampling. We demonstrate experimentally that our new, improved LIS algorithm is substantially more accurate than the LIS algorithm.


Statistical Relational Models; Markov Logic; Graphical Models; Lifted Inference; Monte Carlo Sampling; Importance Sampling; Lifted Sampling; Statistical models; Machine Learning

Full Text: PDF