Compression versus Accuracy: A Hierarchy of Lifted Models

Probabilistic graphical models that encode indistinguishable objects and relations among them use first-order logic constructs to compress a propositional factorised model for more efficient (lifted) inference. To obtain a lifted representation, the state-of-the-art algorithm Advanced Colour Passing (ACP) groups factors that represent matching distributions. In an approximate version using varepsilon as a hyperparameter, factors are grouped that differ by a factor of at most (1± varepsilon). However, finding a suitable varepsilon is not obvious and may need a lot of exploration, possibly requiring many ACP runs with different varepsilon values. Additionally, varying varepsilon can yield wildly different models, leading to decreased interpretability. Therefore, this paper presents a hierarchical approach to lifted model construction that is hyperparameter-free. It efficiently computes a hierarchy of varepsilon values that ensures a hierarchy of models, meaning that once factors are grouped together given some varepsilon, these factors will be grouped together for larger varepsilon as well. The hierarchy of varepsilon values also leads to a hierarchy of error bounds. This allows for explicitly weighing compression versus accuracy when choosing specific varepsilon values to run ACP with and enables interpretability between the different models.