Hybrid Probabilistic Inference with Logical Constraints: Tractability and Message Passing

Feasible Regions of a WMI Model

Abstract

Weighted model integration (WMI) is a very appealing framework for probabilistic inference, it allows to express the complex dependencies of real-world hybrid scenarios where variables are heterogeneous in nature (both continuous and discrete) via the language of Satisfiability Modulo Theories (SMT), as well as computing probabilistic queries with complex logical constraints. Recent work has shown WMI inference to be reducible to a model integration (MI) problem, under some assumptions, thus effectively allowing hybrid probabilistic reasoning by volume computations. In this paper, our first contribution is that we theoretically trace the tractability boundaries of exact MI. Indeed, we prove that in terms of the structural requirements on the primal graphs representing formula structures, bounding graph diameter and treewidth is not only sufficient, but also necessary for tractable exact inference via MI. Our second contribution is that we we introduce a novel formulation of MI via an exact message passing scheme on the tractable MI problems. It allows to efficiently compute the marginal densities and statistical moments of all the variables in linear time. As such, we are able to amortize inference for rich MI queries when they conform to the problem structure, i.e., the primal graph.

Publication
In Proceedings of the NeurIPS Workshop on Knowledge Representation and Reasoning Meets Machine Learning (KR2ML)
Zhe Zeng
Zhe Zeng
Ph.D. student in AI

My research interests include probabilistic inference, probabilistic graphical models, knowledge compilation, and formal methods.

Related