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.
Zhe Zeng
Ph.D. student in AI
My research interests lie in the intersection of machine learning (probabilistic modeling, statistical relational learning, neuro-symbolic AI) and formal methods. My research goal is to enable machine learning models to incorporate diverse forms of constraints into probabilistic inference and learning in a principled way.