The magic of logical inference in probabilistic programming

Bernd Gutmann, Ingo Thon, Angelika Kimmig, Maurice Bruynooghe, Luc De Raedt

TL;DR

This paper introduces distributional clauses, a powerful extension to probabilistic logic programming that allows for continuous variables and complex generative models. By combining "Magic Sets" (to focus on relevant data) with a heuristic backward-reasoning lookahead, the authors create an inference engine that is both goal-directed and capable of handling evidence much more efficiently than standard sampling methods.

What Problem Does This Paper Address?

Probabilistic Logic Programming (PLP) aims to combine the structured, relational reasoning of logic (like Prolog) with the uncertainty management of probability. However, traditional PLP frameworks like ProbLog or PRISM have two major Achilles' heels:

  1. Continuous Distributions: Most systems are built for discrete "true/false" facts and struggle to represent or reason with continuous variables (like a person's height or a sensor reading).
  2. The Evidence Bottleneck: When you have "evidence" (known facts), standard generative sampling is incredibly wasteful. If you are sampling possible worlds and only 1 in 1,000 matches your evidence, you throw away 99.9% of your work. This is the "rejection problem."

While backward reasoning (starting from the goal) is efficient for logic, it’s hard to apply to generative probabilistic models. Conversely, forward reasoning (starting from facts) is great for generation but often explores irrelevant parts of the program.

Methods

The authors propose a "best of both worlds" approach through three key innovations:

  • Distributional Clauses: They extend Sato’s distribution semantics. A clause like h ~ D :- b1, ..., bn means that if the conditions b are met, the random variable h is drawn from distribution D. This allows the program to represent an unknown number of objects and continuous values.
  • Probabilistic Magic Sets: Borrowed from deductive databases, this transformation rewrites the program so that forward reasoning only "activates" rules that are actually relevant to the specific query or evidence. It makes forward sampling goal-directed.
  • Heuristic Lookahead (Backward Reasoning): During the sampling process, the system uses a depth-bounded meta-interpreter to look ahead. If a partial sample is already logically inconsistent with the evidence, the system stops and rejects it immediately. This "pruning" significantly reduces the time spent on dead-end samples.
  • Likelihood Weighting: Instead of simple rejection sampling, they use importance sampling. They adjust the "weight" of each sample based on how well it matches the evidence, leading to more accurate estimates with fewer samples.

Datasets

The paper uses synthetic benchmarks to evaluate the system's performance:

  • The Urn Model: A custom program where an urn contains a random number of balls (Poisson distributed), and the goal is to infer the color of balls given noisy observations.
  • The BLOG Example: A standard benchmark from the BLOG (Bayesian Logic) community involving an unknown number of objects and noisy sensor models.

Key Insights and Ideas

  • Logic as a Filter: The most profound idea here is using logical inference not just to find answers, but to guide probabilistic sampling. By using logic to identify "impossible" worlds early, you save massive amounts of computation.
  • Symmetry of Reasoning: The authors show that the choice between forward and backward reasoning is a false dichotomy. You can use a "Magic Set" transformation to get the benefits of backward-driven focus while maintaining the generative power of forward sampling.
  • Handling the Infinite: By defining distributions conditional on logical predicates, the system can reason about "infinite" Herbrand models (worlds with potentially infinite objects) in a way that remains computationally tractable through sampling.

Key Results

  • Acceptance Rates: In the Urn experiments, the "Lookahead" depth parameter was crucial. As the depth of the logical check increased, the acceptance rate of samples reached 100% for certain queries, meaning the system never wasted time on an inconsistent sample.
  • Variance Reduction: Likelihood weighting significantly outperformed simple rejection sampling, showing much lower standard deviation in probability estimates.
  • Efficiency: The system was able to handle cases where exact inference engines (like PRISM) ran out of memory, particularly when dealing with larger numbers of objects or Poisson distributions.

Limitations and Future Work

  • Finite Evidence: Currently, the system is optimized for evidence on discrete facts or finite distributions. Handling evidence on continuous variables (e.g., "the temperature is exactly 22.5 degrees") remains a challenge because the probability of hitting an exact continuous value during sampling is zero.
  • Depth-Bound Sensitivity: The performance of the lookahead heuristic depends on the Depth parameter. If set too low, it misses inconsistencies; if set too high, the overhead of the check outweighs the sampling benefits.
  • Future Directions: The authors suggest further optimizing the sampling speed through more advanced program analysis and memoization (caching) of previous logical proofs to avoid redundant work.

Summary updated

Abstract

Today, there exist many different probabilistic programming languages as well as more inference mechanisms for these languages. Still, most logic programming-based languages use backward reasoning based on Selective Linear Definite resolution for inference. While these methods are typically computationally efficient, they often can neither handle infinite and/or continuous distributions nor evidence. To overcome these limitations, we introduce distributional clauses, a variation and extension of Sato's distribution semantics. We also contribute a novel approximate inference method that integrates forward reasoning with importance sampling, a well-known technique for probabilistic inference. In order to achieve efficiency, we integrate two logic programming techniques to direct forward sampling. Magic sets are used to focus on relevant parts of the program, while the integration of backward reasoning allows one to identify and avoid regions of the sample space that are inconsistent with the evidence.
BibTeX
@inproceedings{gutmann2011magic,
  author = {Bernd Gutmann and Ingo Thon and Angelika Kimmig and Maurice Bruynooghe and Luc De Raedt},
  title = {{The magic of logical inference in probabilistic programming}},
  booktitle = {Theory Pract. Log. Program},
  year = {2011},
  url = {https://openreview.net/forum?id=EfbCTklUCOR},
}

Loading related content...

Figure