Hybrid Probabilistic Inference with Logical Constraints: Tractability
  and Message Passing
  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 arbitrarily 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,
we introduce a novel formulation of MI via a message passing scheme that 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
arbitrarily rich MI queries when they conform to the problem structure, here
represented as the primal graph associated to the SMT formula. Furthermore, we
theoretically trace the tractability boundaries of exact MI. Indeed, we prove
that in terms of the structural requirements on the primal graph that make our
MI algorithm tractable - bounding its diameter and treewidth - the bounds are
not only sufficient, but necessary for tractable inference via MI.
