Probabilistic Inference in Hybrid Domains by Weighted Model Integration

Vaishak Belle, Andrea Passerini, Guy Van den Broeck

Abstract

This paper introduces Weighted Model Integration (WMI), a framework for exact probabilistic inference in hybrid domains containing both Boolean and continuous variables. By extending Weighted Model Counting (WMC) through Satisfiability Modulo Theories (SMT), WMI enables reasoning over complex logical constraints and continuous distributions. We define piecewise-constant and piecewise-polynomial weight functions and demonstrate the framework's efficacy in parameter learning and scaling on both synthetic and real-world datasets.

Introduction

Probabilistic graphical models, such as Bayesian and Markov networks, are fundamental tools for reasoning under uncertainty. In discrete domains, Weighted Model Counting (WMC) has become a standard approach, reducing inference to a logical counting task. However, real-world applications often involve hybrid data—mixtures of Boolean variables and continuous measurements like time or temperature. Existing hybrid inference methods frequently rely on restrictive assumptions or approximations. This work proposes Weighted Model Integration (WMI) as a general, exact framework for hybrid domains.

Methodology: Weighted Model Integration

The core contribution is the formalization of WMI, which bridges the gap between SMT solvers and automated integration.

Logical Foundation

WMI utilizes Satisfiability Modulo Theories (SMT), specifically Linear Real Arithmetic (LRA). This allows for the representation of formulas that combine Boolean logic with linear constraints over real numbers, such as $p \lor (x + y \le 10)$.

The WMI Task

Unlike WMC, which sums weights over satisfying assignments, WMI computes the volume of the region where a formula holds true. This involves summing over discrete models and performing multi-dimensional integration over continuous variables for each model.

Weight Functions

The framework supports two primary classes of weight functions:

  • CHMN (Piecewise-Constant): Weights are constant over defined regions.
  • PHMN (Piecewise-Polynomial): Weights are polynomials, allowing for high-accuracy approximations of complex distributions like Gaussians.
Approximation of a Gaussian distribution using piecewise-constant (degree 0), linear (degree 1), and cubic (degree 3) polynomials.

Parameter Learning

For CHMNs, the authors derive a Maximum Likelihood Estimation (MLE) approach. Optimal weights are determined by matching the model's expected feature values with empirical averages from the data.

Experimental Evaluation

The WMI framework was evaluated on two distinct datasets:

  1. Synthetic SMT Theories: Randomly generated formulas designed to test algorithmic scaling under increasing complexity.
  2. Strategic Road Network (UK): A real-world dataset comprising over 7 million records of traffic flow and journey times on English motorways.

Results and Discussion

The experimental results demonstrate the practical utility and efficiency of the WMI approach.

Experimental results showing (a) scaling behavior, (b) parameter learning convergence, and (c) example conditional queries on the UK traffic dataset.

Scaling and Performance

The implementation, leveraging the Z3 SMT solver and LattE for integration, scales effectively. The computational time for WMI grows at a rate comparable to standard Boolean model counting (#SAT), indicating that the continuous integration step does not introduce prohibitive overhead in the tested scenarios.

Real-World Application

On the UK traffic dataset, the model successfully learned weights that reflect real-world patterns, such as lower probabilities for short morning journeys during peak hours. Furthermore, WMI proved capable of answering complex conditional queries involving both logical conditions and continuous thresholds.

Conclusion

Weighted Model Integration provides a robust and expressive framework for hybrid probabilistic inference. By decoupling logical structure from numeric weights, it leverages advancements in SMT technology to handle complex constraints. Future research will focus on incorporating optimization techniques like component caching and extending efficient parameter learning to higher-degree piecewise-polynomial models.

Summary updated

BibTeX
@inproceedings{belle2015probabilistic,
  author = {Vaishak Belle and Andrea Passerini and Guy Van den Broeck},
  title = {{Probabilistic Inference in Hybrid Domains by Weighted Model Integration}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure