Publication
Lifted Probabilistic Inference with Counting Formulas
Brian Milch; Luke S. Zettlemoyer; Kristian Kersting; Michael Haimes; Leslie Pack Kaelbling
In: Dieter Fox; Carla P. Gomes (Hrsg.). Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence (AAAI-2008), July 13-17, Chicago, Illinois, USA, Pages 1062-1068, AAAI Press, 2008.
Abstract
Lifted inference algorithms exploit repeated structure in probabilistic models to answer queries efficiently. Previous work such as de Salvo Braz et al.’s first-order variable elimination (FOVE) has focused on the sharing of potentials across interchangeable random variables. In this paper, we also exploit interchangeability within individual potentials by introducing counting formulas, which indicate how many of the random variables in a set have each possible value. We present a new lifted inference algorithm, C-FOVE, that not only handles counting formulas in its input, but also creates counting formulas for use in intermediate potentials. C-FOVE can be described succinctly in terms of six operators, along with heuristics for when to apply them. Because counting formulas capture dependencies among large numbers of variables compactly, C-FOVE achieves asymptotic speed improvements compared to FOVE.