Lifted probabilistic inference with counting formulas

TLDR

Lifted inference algorithms exploit repeated structure in probabilistic models to answer queries efficiently, building on prior work such as FOVE that shares potentials across interchangeable random variables. The paper introduces counting formulas to exploit interchangeability within potentials and presents C‑FOVE, a lifted inference algorithm that handles and generates counting formulas during inference. C‑FOVE is defined by six operators and heuristics that determine when to apply them, enabling the creation and use of counting formulas during inference. C‑FOVE achieves asymptotic speed improvements over FOVE by compactly capturing dependencies among large numbers of variables with counting formulas.

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.