Probabilistic Inference With Algebra and Logic Constraints

Hybrid probabilistic inference allows performing probabilistic inference with algebra and logic constraints. Recent advances with emphasis on computational tractability are reviewed and compared against each other.

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.