Approximate Probabilistic Inference with Bounded Error for Hybrid Probabilistic Logic Programming

Steffen Michels, Arjen Hommersom, Peter J. F. LucasIJCAI 2016

Abstract

Reasoning in hybrid systems—those combining discrete logical rules with continuous numerical data—is a significant challenge in probabilistic programming. Traditional sampling-based methods often fail to capture rare, high-stakes events and lack formal error guarantees. This paper introduces the Iterative Hybrid Probabilistic Model Counting (IHPMC) algorithm. By systematically partitioning the continuous probability space into a Hybrid Probability Tree (HPT), IHPMC provides anytime inference with mathematically bounded errors. Experimental results demonstrate that IHPMC significantly outperforms state-of-the-art samplers in rare-event scenarios and scales effectively to complex relational models.

Introduction: The Challenge of Hybrid Uncertainty

In critical domains such as medical diagnosis, robotics, and crisis management, decision-making requires integrating hard logic with continuous uncertainty. For instance, a system might need to evaluate the rule: "If the cooling system fails, the component temperature $T$ follows a Gaussian distribution." This paradigm is known as Hybrid Probabilistic Logic Programming (HPLP).

Existing solutions primarily rely on sampling techniques like Markov Chain Monte Carlo (MCMC). While versatile, these methods suffer from two critical drawbacks:

  1. The Rare Event Problem: If a failure state is extremely unlikely, a sampler may never encounter it, leading to inaccurate probability estimates.
  2. Lack of Guarantees: Samplers provide point estimates without quantifying the distance from the true probability, which is unacceptable for safety-critical applications.

Methodology: Hybrid Probability Trees

The core contribution of this work is the Iterative Hybrid Probabilistic Model Counting (IHPMC) algorithm. IHPMC avoids the pitfalls of sampling by using a deterministic, tree-based approach to explore the probability space.

The Hybrid Probability Tree (HPT)

The algorithm constructs a Hybrid Probability Tree (HPT), which serves as a structured representation of the problem's logic and continuous distributions.

Figure 1: An example of a Hybrid Probability Tree (HPT) partitioning the continuous space of variable T based on logical conditions.

As shown in Figure 1, the HPT operates through:

  • Space Partitioning: The range of continuous variables (e.g., $T \in (-\infty, \infty)$) is iteratively split into smaller intervals.
  • Logical Pruning: At each node, the algorithm evaluates logical rules. If a condition becomes "True" or "False" for an entire interval, the branch is terminated, effectively "pruning" large sections of the search space.
  • Bounded Error Calculation: By tracking the probability mass in unresolved branches, IHPMC maintains a Lower Bound (assuming all unknown branches are False) and an Upper Bound (assuming they are True). The difference between these bounds represents the maximum possible error.

Experimental Evaluation

The authors evaluated IHPMC using a synthetic diagnostic model involving $n$ components. Failure probabilities were determined by a mix of discrete events, continuous variables (temperature, cooling limits), and relational dependencies. The model was scaled up to 100 components to test computational efficiency.

Performance on Rare Events

A key finding is IHPMC's superior performance in "rare event" scenarios. In these cases, traditional samplers like BLOG (Likelihood Weighting and Rejection Sampling) and Distributional Clauses (DC) struggle to converge.

Figure 6: Mean Squared Error vs. Inference Time for a rare event scenario (p=0.01). IHPMC converges to zero error significantly faster than sampling-based methods.

As illustrated in Figure 6, IHPMC's error drops to near-zero almost instantaneously, whereas competing methods maintain significant error levels even after extended inference time. This is because IHPMC systematically finds the "corners" of the distribution where rare events reside, rather than relying on random chance.

Key Insights and Scalability

  • Logic as a Scalpel: Exploiting logical structure allows IHPMC to ignore irrelevant parts of the continuous space, a major advantage over pure numerical integration.
  • Quantified Uncertainty: Providing an interval (e.g., $[0.021, 0.023]$) rather than a single number allows for more robust risk assessment in engineering and medical contexts.
  • Scalability: The algorithm successfully handled models with 100 components, achieving a guaranteed error of less than 0.01 in approximately 2.3 seconds.

Limitations and Future Directions

While IHPMC is highly effective, it faces challenges with high-dimensional continuous spaces where the number of required splits can grow exponentially. Furthermore, the efficiency of the HPT depends on heuristics for choosing which variable to split first. Future work will explore more sophisticated look-ahead heuristics and the application of this method to non-standard probability distributions.

Conclusion

IHPMC represents a significant step forward for hybrid probabilistic reasoning. By combining the strengths of logical pruning with systematic continuous partitioning, it provides the rigorous error bounds necessary for deploying AI in high-stakes, real-world environments.

Summary updated

BibTeX
@inproceedings{michels2016approximate,
  author = {Steffen Michels and Arjen Hommersom and Peter J. F. Lucas},
  title = {{Approximate Probabilistic Inference with Bounded Error for Hybrid Probabilistic Logic Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure