Probabilistic Inference With Algebra and Logic Constraints

This paper pill is based on the Hybrid Probabilistic Inference with Algebra and Logic Constraints tutorial given at IJCAI 2022 and the review [Mor21H] published at IJCAI 2021.

Modeling real-world systems often includes specifying stochastic as well as deterministic relations between the variables of interest. Such constraints can arise either through the nature of the problem, e.g. through the laws of physics, or are imposed to ensure compliance, e.g. with safety related regulations. As one often needs to express constraints on discrete and continuous variables, SMT over (quantifier-free) linear real arithmetic appears to be a suitable candidate for expressing them since it allows combining logic constraints on discrete variables with linear constraints on continuous variables. Transport modelling, traffic forecasting, probabilistic robotics, and cyber-physical systems are some areas where hybrid constraints appear regularly.

Probabilistic graphical models (PGM) are an established way for expressing stochastic relations between variables. While probabilistic programming languages (PPL) such as pyro or Stan allow the encoding of deterministic relations into the computation graph (which dynamically specifies a PGM), they lack the possibility of directly imposing deterministic constraints on already existing models.

Extending PPLs to impose such constraints at inference time calls for adjustments to the inference backend. Weighted model integration (WMI) is a canonical formulation of the main computational task that is encountered during inference. In short, the task is to sum or integrate over the satisfying assignments of an SMT formula weighted by the probability(-density). Problems like computing the probability of a formula or conditioning on it can easily be expressed as the ratio of two weighted model integrals.

Since WMI is #P-hard in general, research has focused on decreasing the computational load either by algorithmic advances or through identifying tractable subclasses of WMI. Typical approaches include:

  • Exploiting conditional independence structure, expressed for example through the tree-width of the PGM [Kol20H].
  • Restriction to simpler base constraint types, e.g. univariate constraints [Bel16C].
  • Approximation schemes on restricted constraint structures such as constraints in disjunctive normal form [Abb22A].
  • Compiling an arithmetic circuit from the input formula (computationally expensive) that can then be cheaply evaluated for different weight functions [Cha08P].
  • Integration can be solved exactly by decomposition of the polytopes imposed by the constraints into simplices and solving the integral piece wise or by using symbolic integration (e.g. build on top of PSI).
  • Integration can also be performed approximately using MC sampling [Mar19E].

While the last decades have been mostly exploring the theoretical aspects of this powerful tool, there have been more and more reports of successful applications in the last couple of years (e.g. in [Vel14I], [Alb17F] or [Mor19A]). I believe we will see even more efforts for building stable software solutions and exploring application areas in the future.

References

  • Hybrid Probabilistic Inference with Logical and Algebraic Constraints: a Survey, Paolo Morettin, Pedro Zuidberg Dos Martires, Samuel Kolb, Andrea Passerini. (2021)
  • An integrated reconfigurable system for maritime situational awareness, Marina Velikova, Peter Novák, Bas Huijbrechts, Jan Laarhuis, Jesper Hoeksma, Steffen Michels. Proceedings of the Twenty-first European Conference on Artificial Intelligence (2014)
  • FairSquare: probabilistic verification of program fairness, Aws Albarghouthi, Loris D'Antoni, Samuel Drews, Aditya V. Nori. Proceedings of the ACM on Programming Languages (2017)
  • Advanced SMT techniques for weighted model integration | Artificial Intelligence, Paolo Morettin, Andrea Passerini, Roberto Sebastiani. Atificial Intelligence (2019)
  • Exact and approximate weighted model integration with probability density functions using knowledge compilation, Pedro Zuidberg Dos Martires, Anton Dries, Luc De Raedt. Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence (2019)
  • On probabilistic inference by weighted model counting, Mark Chavira, Adnan Darwiche. Artificial Intelligence (2008)
  • Approximate weighted model integration on DNF structures, Ralph Abboud, İsmail İlkan Ceylan, Radoslav Dimitrov. Artificial Intelligence (2022)
  • Component Caching in Hybrid Domains with Piecewise Polynomial Densities, Vaishak Belle, Guy Van Broeck, Andrea Passerini. Proceedings of the AAAI Conference on Artificial Intelligence (2016)
  • How to Exploit Structure while Solving Weighted Model Integration Problems, Samuel Kolb, Pedro Zuidberg Dos Martires, Luc De Raedt. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference (2020)

In this series