Efficient Weighted Model Integration via SMT-Based Predicate Abstraction

Efficient Weighted Model Integration via SMT-Based Predicate Abstraction

Paolo Morettin, Andrea Passerini, Roberto Sebastiani

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 720-728. https://doi.org/10.24963/ijcai.2017/100

Weighted model integration (WMI) is a recent formalism generalizing weighted model counting (WMC) to run probabilistic inference over hybrid domains, characterized by both discrete and continuous variables and relationships between them. Albeit powerful, the original formulation of WMI suffers from some theoretical limitations, and it is computationally very demanding as it requires to explicitly enumerate all possible models to be integrated over. In this paper we present a novel general notion of WMI, which fixes the theoretical limitations and allows for exploiting the power of SMT-based predicate abstraction techniques. A novel algorithm combines a strong reduction in the number of models to be integrated over with their efficient enumeration. Experimental results on synthetic and real-world data show drastic computational improvements over the original WMI formulation as well as existing alternatives for hybrid inference.
Keywords:
Constraints and Satisfiability: Constraints and Satisfiability
Uncertainty in AI: Exact Probabilistic Inference
Uncertainty in AI: Relational Inference